第七讲-马尔可夫链

1、2021/3/2611.6 马尔可夫马尔可夫（Markov）过程过程马尔可夫马尔可夫 当已知随机过程在时刻当已知随机过程在时刻 所处的所处的状态状态的条件下，的条件下，过程在时刻过程在时刻 所处的状态与过程在时刻所处的状态与过程在时刻 以前以前的状态无关，而仅与过程在的状态无关，而仅与过程在 所处的状态有关，则所处的状态有关，则称该过程为马尔可夫过程。这种特性称为随机过程的称该过程为马尔可夫过程。这种特性称为随机过程的“无后效性无后效性”或马尔可夫性。或马尔可夫性。)(itt ititit 马尔可夫过程是一类重要的随机过程。在实马尔可夫过程是一类重要的随机过程。在实际应用中，它是许多工程问题和

2、物理现象的数学际应用中，它是许多工程问题和物理现象的数学模型。因此广泛应用在物理学、生物学、通信、模型。因此广泛应用在物理学、生物学、通信、信息和信号处理、语音处理以及自动控制等领域。信息和信号处理、语音处理以及自动控制等领域。2021/3/2621 T连续连续, ,E连续连续连续马尔可夫过程连续马尔可夫过程2 T连续连续, ,E离散离散离散马尔可夫过程离散马尔可夫过程3 T离散，离散，E连续连续马尔可夫序列马尔可夫序列4 T离散，离散，E离散离散马尔可夫链马尔可夫链马尔可夫过程的分类马尔可夫过程的分类:T表示时间空间表示时间空间 E表示状态空间表示状态空间2021/3/263马尔可夫链马尔可

3、夫链1 1 马尔可夫链的定义马尔可夫链的定义 ,1,2,nXn 为一随机序列，其状态空间为为一随机序列，其状态空间为,21NaaaE ，若对于，若对于任意任意的的n，满足满足( )1(1)2(2)1(1)( )1(1)|,|ni nni nni nini nni nP XaXaXaXaP XaXa), 2 , 1(Ni 则称则称nX为马尔可夫链（简称马氏链）。为马尔可夫链（简称马氏链）。设设表示表示n-1时刻时刻 的状态是的状态是 1nt(1) i na2021/3/2642 2 马尔可夫链的转移概率及性质马尔可夫链的转移概率及性质表明在表明在 时刻出现时刻出现 的条件下，的条件下， 时刻出时

4、刻出现现 的条件概率。的条件概率。 ( ,)|ijm kjmip m mkP XaXamtmiXam ktm kjXa( ,)ijpm mk不仅与不仅与 有关，而且与有关，而且与m有关。有关。若与若与m无关，则称该马氏链为齐次马氏链，此时无关，则称该马氏链为齐次马氏链，此时表示为表示为 。( ,)ijpm mk( )ijpk, ,i j k随机信号分析随机信号分析教学教学组组2021/3/265(1) 一步转移概率一步转移概率在齐次条件下在齐次条件下, ,令令1k(1)( ,1)ijijijppm mpijp NNNNNNppppppppp212222111211P10ijpNjijp11(

5、,)|ijm kjmip m mkP XaXa中中 则则称为一步转移概率。称为一步转移概率。构成的矩阵构成的矩阵称为一步转移概率矩阵称为一步转移概率矩阵,简称转移概率矩阵。简称转移概率矩阵。由所有一步转移概率由所有一步转移概率2021/3/266(2) n步转移概率步转移概率在齐次条件下，令在齐次条件下，令kn( )( ,)|ijijm njmip np m mnP XaXa( ,)|ijm kjmip m mkP XaXa中中 则则表示马氏链由状态表示马氏链由状态 经过经过n步转移到步转移到 的概率。的概率。iaja( )ijp n由所有由所有n步转移概率步转移概率构成构成n步转移概率矩阵步

6、转移概率矩阵 )()()()()()()()()()(212222111211npnpnpnpnpnpnpnpnpnNNNNNNP1)(0npijNjijnp11)(为了数学处理便利，通常规定为了数学处理便利，通常规定jijiaXaXPmmpijimjmij01|),(随机信号分析随机信号分析教学教学组组2021/3/267(3) 切普曼切普曼- -柯尔莫哥洛夫方程（柯尔莫哥洛夫方程（C-K方程）方程） 对于对于 步转移概率，有如下的切普曼步转移概率，有如下的切普曼- -柯尔柯尔莫哥洛夫方程的离散形式莫哥洛夫方程的离散形式lkn)()()()(1kplplkpnprjNririjij表示从状态

7、表示从状态 经过经过n步转移到步转移到 的概率的概率等效等效为为: :先由状态先由状态 经过经过l步到达中间状态步到达中间状态再由状态再由状态 经过经过k步到达状态步到达状态 的概率和。的概率和。 iajaia(1,2,.,)ra rNraja若用概率矩阵表示，有若用概率矩阵表示，有 )()()(klnPPP当当2n时，有时，有 22)()1 () 1 () 1 ()2(PPPPP同理可推出，当同理可推出，当kn 时，有时，有 kkkk)()1 () 1() 1 ()(PPPPP即任意即任意k步转移概率矩阵可由一步转移概率矩阵自乘步转移概率矩阵可由一步转移概率矩阵自乘k次来得到。次来得到。20

8、21/3/268例例 在某数字通信系统中多级传输在某数字通信系统中多级传输0、1两种数字信号。由两种数字信号。由 于系统中存在干扰，在任一级输入于系统中存在干扰，在任一级输入0、1数字信号后，数字信号后， 其输出不产生错误的概率为其输出不产生错误的概率为p，产生错误的概率为，产生错误的概率为q=1- p，求两级传输时的概率转移矩阵。，求两级传输时的概率转移矩阵。解解 系统每一级的输入状态和输出状态构成一个两状态的系统每一级的输入状态和输出状态构成一个两状态的 马氏链，其一步转移概率矩阵为马氏链，其一步转移概率矩阵为pqqppppp11100100P于是，两级传输时的概率转移矩阵等效于两步转移概

9、于是，两级传输时的概率转移矩阵等效于两步转移概率矩阵为率矩阵为 2222222)2(qppqpqqppqqppqqpPP2021/3/269(4) (4) 初始分布与绝对分布初始分布与绝对分布 为了完整的描述一个随机过程，需要给出任意为了完整的描述一个随机过程，需要给出任意有限维概率函数。有限维概率函数。 对于马氏链的任意有限维概率函对于马氏链的任意有限维概率函数完全由数完全由初始分布初始分布和和转移概率矩阵转移概率矩阵来描述。来描述。设设( ),0,1,2,X nn 为一马氏链，其状态空间为一马氏链，其状态空间, 2, 1, 0 E或为有限子集。或为有限子集。令令(0)(0),ipP Xii

10、E，且对任意的，且对任意的i E均有均有0)0(ip1)0(Eiip则称则称 为该马氏链的为该马氏链的初始分布初始分布，也称，也称初始初始概率概率。初始概率是马氏链在初始时间。初始概率是马氏链在初始时间 时处于状时处于状态态i的概率。的概率。(0),ipiE0n2021/3/26101n当当 时，马氏链处于状态时，马氏链处于状态i的概率称为的概率称为绝对概率绝对概率或或绝对分布绝对分布。则称则称 为该马氏链的为该马氏链的绝对分布绝对分布,也称也称绝对概率绝对概率。设设( ),0,1,2,X nn 为一马氏链为一马氏链,其状态空间其状态空间, 2, 1, 0 E或为有限子集。或为有限子集。令令(

11、 )( ),ip nP X niiE,且对任意的且对任意的i E均有均有( )0ip n ( )1ii Ep n( ),ip n iE2021/3/2611定理定理 马氏链的绝对概率由初始分布和相应的转移概马氏链的绝对概率由初始分布和相应的转移概 率唯一确定。率唯一确定。利用利用C-K方程方程，则，则n步转移矩阵可由一步转移步转移矩阵可由一步转移矩阵唯一确定矩阵唯一确定。推论推论 马氏链的绝对概率由初始分布和一步转移概率马氏链的绝对概率由初始分布和一步转移概率 唯一确定。唯一确定。2021/3/2612转移图（状态转移图与概率转移图）转移图（状态转移图与概率转移图） 状态转移图就是在一张图中状

12、态转移图就是在一张图中,首先将马氏链所具有的首先将马氏链所具有的各个状态一一标出各个状态一一标出,然后用标有箭头的连线将各个状态连接然后用标有箭头的连线将各个状态连接起来，箭头所指的状态，就是箭尾所连接的状态一步能够起来，箭头所指的状态，就是箭尾所连接的状态一步能够达到的状态，若在连线上再标出一步转移概率，就构成了达到的状态，若在连线上再标出一步转移概率，就构成了概率转移图。概率转移图。 有了概率转移图，为状态的连通性、可达性、常返性有了概率转移图，为状态的连通性、可达性、常返性以及马氏链的可约性提供方便。以及马氏链的可约性提供方便。2021/3/2613马氏链中状态分类马氏链中状态分类1.

13、到达与相通到达与相通iajai到达到达：如果对于状态：如果对于状态 与与 （可简写为（可简写为 和和 ) ) 总总存在存在某个某个 ，使得，使得 ，则称，则称 自自 状态经过状态经过n步可以到达步可以到达 状态，并记为状态，并记为ji) 1(n0)(npijjji ) 1(n0)(npij反之，若对反之，若对所有所有的的 有有 ，则自则自 状态不可以到达状态不可以到达 状态，并记为状态，并记为ijij到达具有到达具有传递性传递性，即若，即若 , , 则则ri jr ji 2021/3/2614相通相通：若自状态：若自状态i可达状态可达状态j，同时自状态，同时自状态j也可达状态也可达状态 i，则

14、称状态和状态相通，记为，则称状态和状态相通，记为 。ji 相通具有以下等价关系：相通具有以下等价关系： （1 1）若）若 ，则，则 自返性自返性ji ii （2 2）若）若 ，则，则 对称性对称性ji ij （3 3）若）若 ， ，则，则 传递性传递性jr ri ij 如果马尔可夫链的所有状态都是相通的如果马尔可夫链的所有状态都是相通的,则这样则这样的马尔可夫链的马尔可夫链为不可约的为不可约的。 2021/3/2615例例 设一两状态设一两状态 马氏链具有以下转移马氏链具有以下转移 概率矩阵概率矩阵1 , 0E 00011011112201ppppP10)(1)()()()()(2121111

15、00100nnnnpnpnpnpP对于所有的对于所有的n, , ，故状态，故状态“1”不能到达不能到达状态状态“0”；而存在而存在n使得使得 ，故状态故状态“0”可以到达可以到达状态状态“1”。0)(10np01( )0pn 讨论其状态的到达特性。讨论其状态的到达特性。解解 要讨论这一马氏链两个状态的到达性，可先求出它要讨论这一马氏链两个状态的到达性，可先求出它 的的n步转移概率矩阵。由于步转移概率矩阵。由于2021/3/26162状态的分类状态的分类 设设 为一马氏链，对任一状为一马氏链，对任一状态态i与与j，称，称( ),0,1,2,X nn 0,min0njXiXnTnij为为 自状态自

16、状态i出发出发首次首次进入状态进入状态j的的时刻，或称为自时刻，或称为自i到到j的的首达首达时。时。( ),0,1,2,X nn 如果如果 可能永不取值可能永不取值j,规定规定 。 ijTnXijT是是一随机变量一随机变量。 为了对马氏链进行分类为了对马氏链进行分类,需要明白马氏链存在哪些状态需要明白马氏链存在哪些状态,哪些是暂时出现（哪些是暂时出现（最多有限次到达最多有限次到达），哪些永恒出现（），哪些永恒出现（无限无限次到达次到达）。）。2021/3/2617 设设 为一马氏链，对任一状态为一马氏链，对任一状态i与与j，称，称( ),0,1,2,X nn 为为 自状态自状态i出发经过出发经

17、过n步步首次首次进入进入状状态态j的的概率概率。( ),0,1,2,X nn 0( )|ijijfnP Tn Xi显然有显然有11 21110( );,1,2,1|,1nnijnmii iiijjijifnP Xj Xj mnXip ppn从而从而100(1)|( ),|ijijijmfpP Xj XifP Xjm Xi 对一切2021/3/2618 设设 为一马氏链，对任一状态为一马氏链，对任一状态i与与j，称，称( ),0,1,2,X nn 为为 自状态自状态i出发出发迟早迟早进入状态进入状态j的概率。的概率。( ),0,1,2,X nn 011( )|ijijijijnnffnP Tn

18、XiP T 显然有显然有ijijijfTPf1)(1)(0ijijfnf2021/3/2619定理定理 对任何状态对任何状态1,nEji, ,有有 nljjijijlnplfnp1)()()(说明说明:马氏链从状态马氏链从状态i出发经过出发经过n步转移到状态步转移到状态j的概率的概率:从从i出发经过出发经过l步步首次首次到达状态到达状态j,在从状态在从状态j出发经过出发经过n-l步转移步转移又又到了状态到了状态j（ ）,这些事件的概率这些事件的概率之和。之和。1,2,.,ln 如果如果 ，则称状态，则称状态j是是常返常返的。的。 如果如果 ，则称状态，则称状态j是是非常返非常返的的( (或称为

19、瞬时的或称为瞬时的) ) 如果马尔可夫链的任一状态都是常返的，则称此如果马尔可夫链的任一状态都是常返的，则称此链为常返马尔可夫链。链为常返马尔可夫链。1jjf1jjf2021/3/2620定理定理 的充要条件是的充要条件是 。0ijfji 定理定理 状态状态j是常返（是常返（ ）的充要条件为）的充要条件为1jjf0)(njjnp推论推论 如果状态如果状态j是非常返的，则必有是非常返的，则必有0)(limnpjjn2021/3/2621iiT) 1 (iif)2(iif)(nfii12NP由数学期望的定义，可得由数学期望的定义，可得 1)(niiiiinnfTEuiu称称 为状态为状态i的的平均

20、返回时间平均返回时间。 i ), 2 , 1( niiTiX0 设设i是一是一常返态常返态，则从，则从i出发可经过出发可经过n 步首次返回步首次返回i， 在在 的条件下的分布列为的条件下的分布列为设设i是常返态，如果是常返态，如果 ，则称状态，则称状态i是是正正常返态；常返态； 如果如果 ，则称状态，则称状态i是是零零常返态。常返态。iuiu2021/3/2622 对于状态对于状态i，若正整数集合，若正整数集合 非空，则称该集合的最大公约数非空，则称该集合的最大公约数L为状态为状态i的周期。的周期。 若若 ，则称状态，则称状态i是是周期周期的。的。 若若 ，则称状态，则称状态i是是非周期非周期

21、的。的。 如果状态如果状态i是非周期且正常返的，则称状态是非周期且正常返的，则称状态i是是 遍历遍历的。的。0)(, 1:npnnii1L1L2021/3/2623定理定理 设设i为常返状态，有周期为常返状态，有周期 ,则则(1)L L lim( )jjnjLpnu马氏状态分类图马氏状态分类图 状态空间状态空间周期周期常返常返非周期非周期非常返非常返正常返正常返零常返零常返遍历遍历2021/3/2624状态分类判别法：状态分类判别法： 1( )iinipn （1） 是非常返1( )lim( )0iiiinnipnpn （2） 是零常返且1( )lim( )0iiiinnipnpn （3） 是正

22、常返且11( )lim( )0iiiinniipnpn （4） 是遍历且2021/3/2625、定理定理 若若 ，则，则 （1 1）i与与j同为常返或同为非常返；同为常返或同为非常返； （2 2）若若i与与j常返，则常返，则i与与j同为正常返或同为零常返；同为正常返或同为零常返； （3 3）i与与j或同为非周期的，或同为周期的且有相同的周期或同为非周期的，或同为周期的且有相同的周期。ij上述讨论常返性上述讨论常返性,下面讨论下面讨论相通性相通性2021/3/26263遍历性与平稳分布遍历性与平稳分布 设齐次马氏链设齐次马氏链 的状态空间为的状态空间为E,若对一切若对一切 ,存在存在不依赖于不依

23、赖于i的极限的极限 ( ),0X nn , i jElim( )ijjnpnp则称马尔可夫链具有遍历性。并称则称马尔可夫链具有遍历性。并称 为状态为状态j的稳的稳态概率。态概率。jp说明说明:无论从那个状态无论从那个状态i出发出发,当转移步数充分大时当转移步数充分大时, 转移到状态转移到状态j的概率接近的概率接近 ，即当，即当n足够大时，足够大时， 可用可用 作为作为 的近似值。的近似值。jpjp( )ijpn2021/3/2627 ( ),1,2,3,.n n( )0ijpm ,0,1,2,i jN所有则此链是遍历性的，且则此链是遍历性的，且 是方程组是方程组12,jNpppp011Njii

24、jiNjjpp pp定理定理 对于一有限状态的马氏链对于一有限状态的马氏链 ， 若存在一正整数若存在一正整数m，使，使 的唯一解。的唯一解。马氏链的遍历性马氏链的遍历性 利用上述的定理，可以判断齐次马氏链的遍历性；利用上述的定理，可以判断齐次马氏链的遍历性； 以及求出稳态概率以及求出稳态概率 ，此时，此时稳态概率即为平稳分布稳态概率即为平稳分布。jp2021/3/2628马氏链的平稳性马氏链的平稳性物理意义物理意义:对于任意的时刻对于任意的时刻,系统处于同一状态的概率是系统处于同一状态的概率是 相同的。相同的。定义定义:若齐次马氏链的概率分布不随时间若齐次马氏链的概率分布不随时间n的变化而变化

25、。的变化而变化。即满足即满足 ,Njiijji Ipnp pnpjE2021/3/26292021-12-2829 一个非周期，不可约的马氏链是常返的，它存在一个非周期，不可约的马氏链是常返的，它存在一个平稳分布一个平稳分布 ，即，即 平稳分平稳分布就是极限分布。布就是极限分布。 1jjpu1lim( )ijjnjpnpu 遍历的马氏链一定具有平稳性，但平稳的马氏链不遍历的马氏链一定具有平稳性，但平稳的马氏链不一定具有遍历性（不遍历的马氏链也可具有平稳性）。一定具有遍历性（不遍历的马氏链也可具有平稳性）。 2021/3/2630例例 设马尔可夫链的状态空间设马尔可夫链的状态空间 ，一步转移概率

26、矩阵，一步转移概率矩阵1,2,3,4E 100001001200331110442P试对该链进行分类，并说明其遍历性。试对该链进行分类，并说明其遍历性。解解 根据一步转移概率矩阵可画出如图所示的状态转移图。从图中可根据一步转移概率矩阵可画出如图所示的状态转移图。从图中可 知，和都是非周期的正常返状态，和状态都是非常返状知，和都是非周期的正常返状态，和状态都是非常返状 态。态。由于由于11( )1pn 21( )0pn 311( )3pn 41411141111111 ( )11 11 1 1111112( )( )()( ).142 42 2 42442212nnnnnllp nfl p n

27、lfn 说明说明 存在（存在（i=1,2,3,4）, ,但与但与i有关，所以该链不是遍历的。有关，所以该链不是遍历的。lim( )ijnpn2021/3/26312021-12-2831马尔可夫序列马尔可夫序列1 1 定义定义 设设 表示随机过程表示随机过程 在在 为整数时刻的取为整数时刻的取样的样的随机序列随机序列，记为，记为 ( (简记为简记为 或或 ) ) 则可按以下方式定义马尔可夫序列。则可按以下方式定义马尔可夫序列。 若对于若对于任意任意的的n，有，有则称则称 为马尔可夫序列。此概率密度函数称为转移概率密为马尔可夫序列。此概率密度函数称为转移概率密度函数。进一步可以推出度函数。进一步可以推出 即联合概率密度函数可由转移概率密度和起始时刻的一维概即联合概率密度函数可由转移概率密度和起始时刻的一维概率密度来确定。率