概率统计及随机过程：第十三章 马尔可夫链

1、第十三章第十三章 马尔可夫链马尔可夫链 马尔可夫过程是一类特殊的随机过程, 马尔可夫链 是离散状态的马尔可夫过程,最初是由俄国数学家马 尔可夫1896年提出和研究的. 应用十分广泛,其应用领域涉及计算机,通信,自动 控制,随机服务,可靠性,生物学,经济,管理,教育,气象, 物理,化学等等. 第一节第一节: 马尔可夫链的定义马尔可夫链的定义 一定义1 设随机过程 的状态空间 是 ),(TttXS 有限集或可列集,对任意正整数 对于内任意个 , n 参数 和 内任意 个状态 121 nn ttttS1n , 121 nn jjjj 如果条件概率 )(,)(,)(|)( 221111nnnn jtX

2、jtXjtXjtXP 恒成立,则称此过程为马尔可夫链. )(|)( 11nnnn jtXjtXP (13.1) 式(13.1)称为马尔可夫性,或称无后效性. 马氏性的直观含义可以解释如下: 将 看作为现在时刻,那末 ,就是过去时 n t 121 , n ttt 刻,而 则是将来时刻.于是, (13.1) 式是说,当已知 1n t 系统现时情况的条件下,系统将来的发展变化与系 统的过去无关.我们称之为无后效性. 许多实际问题都具有这种无后效性. 例如 生物基因遗传从这一代到下一代的转移中仅 依赖于这一代而与以往各代无关. 二：马尔可夫链的分类 状态空间 是离散的(有限集或可列集),参数集 ST

3、可为离散或连续的两类. 三：离散参数马尔可夫链 （1）转移概率 定义2 在离散参数马尔可夫链,),( 210 n ttttttX 中,条件概率 称为 在 )()(|)( 1mijmm tpitXjtXP )(tX 时刻(参数) 由状态 一步转移到状态 的一步转移 m tij 概率,简称转移概率. 条件概率 称为 在时 )()(|)( )( m n ijmnm tpitXjtXP )(tX n 刻(参数) 由状态 经 步转移到状态 的 步 m t i njn 转移概率. (2)转移概率的性质:对于状态空间 内的任意两个S 状态 和 ,恒有ij (1) 0)( )( m n ij tp (2) ,

4、 1)( )( m Sj n ij tp , 2 , 1n )( )( m Sj n ij tp )(|)(itXjtXP mnm Sj )( )(,)( itXP itXjtXP m Sj mnm )( )()( itXP itXjtXP m Sj mnm 1 )( )( itXP itXP m m 四.离散参数齐次马尔可夫链 定义3 在离散参数马尔可夫链 ,),( 210 n ttttttX 中,如果一步转移概率 不依赖于参数 ,即 )( mij tp m t 对任意两个不等的参数 和 , 有 m t k tkm )()(|)( 1mijmm tpitXjtXP ijkijkk ptpit

5、XjtXP )()(|)( 1 则称此马尔可夫链具有齐次性或时齐性,称 )(tX 为离散参数齐次马尔可夫链. 例1： Bernoulli序列是离散参数齐次马尔可夫链. 第二节：参数离散的齐次马尔可夫链 对离散参数齐次马尔可夫链,本节讨论以下四个问题. 一：转移概率矩阵 设 是齐次马尔可夫链,由于状 ,),( 210 n ttttttX 态空间 是离散的(有限集或可列集),不妨设其状态 S 空间 . , 2 , 1 , 0 nS 则对内的任意两个状态 和 ,由转移概率 排序i j ij p 一个矩阵 ijii j j ppp ppp ppp P 10 11110 00100 称为(一步)转移概率

6、矩阵 )(|)( 1 itXjtXPp mmij 转移概率矩阵的性质： (1) ,即元素均非负;0 ij p (2) ,即每行和为1.1 Sj ij p 具有以上两个特点的方阵称为随机矩阵. 转移概率矩阵就是一个随机矩阵. 例1 Bernoulli序列的状态空间 ,转移概率矩阵1 , 0S pq pq pp pp P 1110 0100 )(|)( 1 itXjtXPp mmij 1, 0, )( 1 jp jq jtXP m 例2：一维随机游动 一个质点在直线上的五个位置:0,1,2,3,4之上随机 游动.当它处在位置1或2或3时,以的1/3概率向左移 动一步而以2/3的概率向右移动一步;当

7、它到达位置 0时,以概率1返回位置1;当它到达位置4时以概率1停 留在该位置上(称位置0为反射壁,称位置4为吸收壁). 例3（成功流） 设在一串贝努里试验中,每次试验成功的概率为 , p 令 nkknk n X n 1 , , 0 次成功次试验接连第第 次试验失败第 则 是齐次马尔可夫链.求转移矩阵。 , 3 , 2 , 1, nX n 二：切普曼-柯尔莫哥洛夫方程 定理一 设 是马尔可夫链,则有 ,),( 210 n ttttttX )()()( )()()( nm l kj k m n ikm ln ij tptptp (13.6) 称为切普曼-柯尔莫哥洛夫方程. 如果马尔可夫链具有齐次性

8、,那么切普曼-柯尔莫哥 洛夫方程化为 , )()()(l kj k n ik ln ij ppp (13.7) 当时 ,得到 1, 1ln kj k ikij ppp )2( 进一步改写为矩阵形式 2)2( PP 其中 是两步转移概率矩阵, 是一步转移)( )2()2( ij pPP 用数学归纳法可得 nn PP )( , 4 , 3 , 2n(13.8) 式(13.8)表明:步转移概率矩阵 等于一步转 )( )()(n ij n pP 移概率矩阵 的 次幂.因此也常把 作为 步转移 Pn n Pn 概率矩阵的符号. 例4：在本节例2中,求 和 . )2( 00 p )2( 31 p 例5 传

9、输数字0和1的通讯系统,每个数字的传输需 经过若干步骤,设每步传输正确的概率为9/10,传输 错误的概率为1/10,(1)问:数字1经三步传输出1的概 率是多少? (2)若某步传输出数字1,那么又接连两步 都传输出1的概率是多少? 三.有限维概率分布 马尔可夫链 在初始时刻 的概率 ,),( 210 tttttX 0 t 称为初始分布. ,)()( 00 jtXPtp j , 2 , 1 , 0j分布: 初始分布与转移概率完全地确定了马尔可夫链的 任何有限维分布.下面的定理二正是论述这一点. 不妨设齐次马尔可夫链的参数集和状态空间都是 非负整数集,那么有如下定理。 定理二 设齐次马尔可夫链 的

10、状态 , 2 , 1 , 0),( nnX 空间 则对任意 个非负整数 , 2 , 1 , 0 iSn n kkk 21和 内的任意 个状态 Sn , 21n jjj 有 )(,)(,)( 2211nn jkXjkXjkXP )()()( 0 1 1 12 21 1 1 )0( nn nn kk jj kk jj k ij i i pppp (13.9) 例6 在本节例5中,设初始时输入0和1的概率分别为 1/3和2/3,求第2、3、6步都传输出1的概率. 马尔可夫链在任何时刻 的一维概率分布 n t ,)()(jtXPtp nnj , 2 , 1 , 0j 又称为绝对概率,或称为瞬时概率.

11、由全概率公式得 , )()()( 0 11 i nijninj tptptp , 2 , 1 , 0j 如果马尔可夫链具有齐次性,那么上式化为 ,)()( 0 1 i ijninj ptptp , 2 , 1 , 0j(13.10) 由式(13.10)递推得到 ,)()( 0 )( 0 i n ijinj ptptp , 2 , 1 , 0j (13.11) 式中 是初始时刻.式(13.11)表明:齐次马尔可夫链 0 t 在时刻 的瞬时概率完全地由初始分布和 步转 n tn 移概率所确定. 将公式(13.11)写成向量形式得 ),(,),(),( 10 njnn tptptp )( 00100

12、 ),(,),(),( n j Ptptptp 步转移概率矩阵 n nn ij n PpP)( )()( 例7 本节例2中,设质点在初始时刻 恰处在状态2, 0 t 试求在 时刻,质点处在各个状态的概率. 2 t 四.平稳分布 如果一维分布 与 无关,那么式(13.10)化为下式 )( nj tp n t (13.12),于是有 定义4 对于齐次马尔可夫链 如果,),( 210 tttttX 存在概率分布 满足 , j p , 2 , 1 , 0j , 0 i ijij ppp , 2 , 1 , 0j(13.12) 则称 为平稳分布,称 具有平稳性, , j p ), 2 , 1 , 0( j)(tX 是平稳齐次马尔可夫链. 改写成向量:平稳分布律要满足 ),( 210j ppppPpppp j ),( 210 并且有 1 0 j j p 定理 如果齐次马尔可夫链 的初,),( 210 tttttX 始分布 ,)()( 00 jtXPtp j ), 2 , 1 , 0( j 是一个平稳 分布,则 ),()()( 0 tpjtXPtp jnnj , 2 , 1 , 0j ), 2 , 1( n 例8 带一个反射壁的一维随机游动,以 表示 jtX n )( 在时刻 粒子处