Probability Notes 7 马尔可夫链

7 马尔可夫链 (Markov Chains)

7.1 马尔可夫模型 (Markov Models)

  • 一个马尔可夫链模型通过如下三点定义:
  1. 状态的集合(set of states)S=left{1,2,dots,mright}
  2. 可能的转变的集合(set of possible transitions),集合的元素是满足p_{ij} data-recalc-dims=0" />的状态对(i,j)
  3. p_{ij}的数值
  • 上述马尔可夫链模型所定义的马尔可夫链是随机变量X_0,X_1,X_2,dots,的序列,变量从状态集合S中取值,并且满足,对于任何时间n、任意状态i,j和任意可能的序列i_{0},dots,i_{n-1}有:
    P(X_{n+1}=j|X_{n}=i,X_{n-1}=i_{n-1},dots,X_{o}=i_{0})=p_{ij}

7.2 n步转变概率:察普曼-科莫高洛夫方程式(Chapman-Kolmogorov Equation for the n-Step Transition Probabilities)

  • 经过n次转变后进入某一状态的概率可以用如下递归公式进行计算:
    r_{ij}(n)=sum_{k=1}^{m}r_{ik}(n-1)p_{kj},~~~~~text{for}~n data-recalc-dims=1,~text{and all}~i,j" />
  • n=1时,r_{ij}(1)=p_{ij}

7.3 马尔可夫链的分解(Markov Chain Decomposition)

  • 一个马尔可夫链可以被分解成为一个或多个循环类(recurrent classes)和可能一个或多个过渡状态(transient states)
  • 任何一个循环状态都可以被其所属的循环类内所有其他状态转变而成,但是不能从其他循环类内的任意状态转变而来
  • 过度状态不能从任何循环状态转变而成
  • 给定一个过度状态,从其进行转变则至少能到达一个循环状态

7.4 周期性(Periodicity)

  • 考虑一个循环类R
  1. 如果类中的状态可以被划分为d data-recalc-dims=1" />个互斥子集S_1,dots,S_d,使得S_k中所有的转变都指向S_{k+1}(如果k=d则指向S_{1}),则称诶这个类具有周期性的
  2. 当且仅当存在一个时刻n,使得r_{ij}(n) data-recalc-dims=0,~text{for all}~i,jin{R}" />,则称这个类是非周期的

7.5 稳态收敛定理(Steady-State Convergence Theorem)

  • 考虑一个包含了一个具有周期性的循环类的马尔可夫链,则状态j所有的稳态概率pi_{j}具有如下属性:
  1. 对于任意状态j,有:
    lim_{nrightarrow{infty}}r_{ij}(n)=pi_{j},~~~~~~text{for all}~i
  2. pi_{j}是下面方程组的唯一解:
    pi =sum_{k=1}^{m}pi_{k}p_{kj},~~~~~j=1,2,dots,m
    1=sum_{k=1}^{m}pi_{k}
  3. 对于任意过度状态j有:pi_{j}=0;对于任意循环状态j有:pi_{j} data-recalc-dims=0" />

7.6 稳态概率和期望状态频率(Steady-State Probabilities as Expected State Frequencies)

  • 考虑仅包含单一一个非周期类的马尔可夫链,稳态概率pi_{j}满足:
    pi_{j}=lim_{nrightarrow{infty}}frac{v_{ij}(n)}{n}
  • 其中v_{ij}(n)是在从状态i开始的前n次转变中状态j出现次数的期望值

7.7 特定转变的期望频率(Expected Frequency of a Particular Transition)

  • 考虑仅包含单一一个非周期类的马尔可夫链,从一个给定的初始状态开始,经过n次转变。令q_{jk}(n)是这样的从状态jk的转变种类的期望值。无论给定的初始状态为何,均有:
    lim_{nrightarrowinfty}frac{q_{jk}(n)}{n}=pi_{j}p_{jk}

7.8 吸收概率方程(Absorption Probability Equations)

  • 考虑一个马尔可夫链,其中的状态不是过渡状态就是吸收状态,给定一个吸收状态s,则从状态i开始,最后终于到达状态s的概率a_i是如下方程组的唯一解:
    a_{s}=1
    s_{i}=0,~~~~text{for all absorbing}~ineq{s}
    a_{i}=sum_{j=1}^{m}p_{ij}a_{j},~~~~text{for all transient}~i

7.9 吸收时间期望方程(Equations for the Expected Time to Absorption)

  • 到达吸收的时间的期望值mu_{1},dots,mu_{m}是下面方程组的唯一解:
    mu_{i}=0,~~~~~~text{for all recurrent states}~i
    mu_{i}=1+sum_{j=1}^{m}p_{ij}mu_{j}~~~text{for all transient states}~i

7.10 首次通过和再次出现时间平均值的方程(Equations for Mean First Passage and Recurrence Times)

  • 考虑一个只包含一个循环类的马尔可夫链,令s是一个特定的循环状态:
  1. 从状态i开始,首次转变至状态s所需时间t_i的期望是下面方程组的唯一解:
    t_s=0
    t_i=1+sum_{j=1}^{m}p_{ij}t_{j},~~~~text{for all}~ineq{s}
  2. 状态s的再次出现时间t_{s}^{*}的期望值为:
    t_{s}^{*}=1+sum_{j=1}^{m}p_{sj}t_{j}

Leave a Reply

Your email address will not be published. Required fields are marked *