第十三章 马尔可夫链马尔可夫过程是一类特殊的随机过程, 马尔可夫链是离散状态的马尔可夫过程,最初是由俄国数学家马尔可夫1896年提出和研究的.应用十分广泛,其应用领域涉及计算机,通信,自动控制,随机服务,可靠性,生物学,经济,管理,教育,气象,物理,化学等等.第一节 马尔可夫链的定义一．定义定义 1 设随机过程}),({T t t X ∈的状态空间S 是有限集或可列集,对任意正整数n ,对于T 内任意1+n 个参数121+<<⋅⋅⋅<<n n t t t t 和S 内任意1+n 个状态121,,,,+⋅⋅⋅n n j j j j ,如果条件概率})(,,)(,)(|)({221111n n n n j t X j t X j t X j t X P =⋅⋅⋅===++})(|)({11n n n n j t X j t X P ===++,(13.1) 恒成立,则称此过程为马尔可夫链. 式(13.1)称为马尔可夫性,或称无后效性.马氏性的直观含义可以解释如下: 将n t 看作为现在时刻,那末,121,,,-⋅⋅⋅n t t t 就是过去时刻,而1+n t 则是将来时刻.于是,(13.1)式是说,当已知系统现时情况的条件下,系统将来的发展变化与系统的过去无关.我们称之为无后效性.许多实际问题都具有这种无后效性.例如 生物基因遗传从这一代到下一代的转移中仅依赖于这一代而与以往各代无关.再如,每当评估一个复杂的计算机系统的性能时,就要充分利用系统在各个时刻的状态演变所具有的通常概率特性:即系统下一个将到达的状态,仅依赖于目前所处的状态,而与以往处过的状态无关.此外,诸如某公司的经营状况等等也常常具有或近似具有无后效性.二． 马尔可夫链的分类状态空间S 是离散的(有限集或可列集),参数集T 可为离散或连续的两类.三．离散参数马尔可夫链（1）转移概率定义2 在离散参数马尔可夫链},,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 中,条件概率)(})(|)({1m ij m m t p i t X j t X P ===+称为)(t X 在时刻(参数)m t 由状态i 一步转移到状态j 的一步转移概率, 简称转移概率.条件概率)(})(|)({)(m n ij m n m t p i t X j t X P ===+称为)(t X 在时刻(参数)m t 由状态i 经n 步转移到状态j 的n 步转移概率.(2)转移概率的性质:对于状态空间S 内的任意两个状态i 和j ,恒有(1) 0)()(≥m n ij t p ;(2)1)()(=∑∈m Sj n ij t p ,⋅⋅⋅=,2,1n ()()(m Sj n ij t p ∑∈ })(|)({i t X j t X P m n m Sj ===+∈∑ })({})(,)({i t X P i t X j tX P m S j m n m ====∑∈+ })({}})(}){)({({i t X P i t X j t X P m S j m n m ====∑∈+1})({})({====i t X P i t X P m m )四.离散参数齐次马尔可夫链定义3 在离散参数马尔可夫链},,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 中,如果一步转移概率)(m ij t p 不依赖于参数m t ,即对任意两个不等的参数m t 和k t ,k m ≠,有)(})(|)({1m ij m m t p i t X j t X P ===+ij k ij k k p t p i t X j t X P =====+)(})(|)({1则称此马尔可夫链具有齐次性或时齐性,称)(t X 为离散参数齐次马尔可夫链.例1 Bernoulli 序列是离散参数齐次马尔可夫链.验证 在Bernoulli 序列},3,2,1,{⋅⋅⋅=n X n 中, 对任意正整数 n , 121+<<⋅⋅⋅<<n n t t t t ,121,,,,+⋅⋅⋅n n t t t t X X X X 相互独立, 故对 ,1,0=k j )1,,2,1(+⋅⋅⋅=n k ,有},,,|{211211n t t t n t j X j X j X j X P n n =⋅⋅⋅===++}{11+==+n t j X P n}|{11n t n t j X j X P n n ===++即满足马尔可夫性,且}|{11n t n t j X j X P n n ==++⎩⎨⎧=-====++++0,11,}{1111n n n t j p j p j X P n 当当 , 不依赖于参数n t ,满足齐次性.故Bernoulli 序列是离散参数齐次马尔可夫链.例2 爱伦菲斯特(Ehrenfest)模型 一容器中有a 2个粒子在作随机运动.设想有一实际不存在的界面把容器分为左右容积相等的两部分.当右边粒子多于左边时,粒子向左边运动的概率要大一些,大出部分与两边粒子的差数成正比;反之,当右边粒子少于左边时,粒子向右边运动的概率要大一些.以nX 表示n 次变化后,右边粒子数与均分数a 之差,则状态空间},1,,2,1,0,1,,1,{a a a a S -⋅⋅⋅-⋅⋅⋅+--=,转移概率 ⎪⎪⎪⎩⎪⎪⎪⎨⎧==±≠∈-=+=+---+-1,),1(21),1(211,1,1,1,a a a a j j j j p p a j S j a j p a j p则 },3,2,1,{⋅⋅⋅=n X n 是齐次马尔可夫链.第二节 参数离散的齐次马尔可夫链对于离散参数齐次马尔可夫链,本节讨论以下四个问题.一. 转移概率矩阵设 },,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X 是齐次马尔可夫链, 由于状态空间S 是离散的(有限集或可列集)，不妨设其状态空间 },,,2,1,0{⋅⋅⋅⋅⋅⋅=n S .则对S 内的任意两个状态i 和j ,由转移概率 ij p 排序一个矩阵⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=ij i i j j p p p p p p p p p P 101111000100 称为(一步)转移概率矩阵 .})(|)({1i t X j t X P p m m ij ===+转移概率矩阵的性质：(1) 0≥ij p ,即元素均非负;(2) 1=∑∈S j ij p ,即每行和为1.具有以上两个特点的方阵称为随机矩阵.转移概率矩阵就是一个随机矩阵.例1 Bernoulli 序列的状态空间}1,0{=S ,转移概率矩阵⎝⎛=⎪⎪⎭⎫ ⎝⎛=q q p p p p P 11100100 ⎪⎪⎭⎫p p , })(|)({1i t X j t X P p m m ij ===+⎩⎨⎧=====+1,0,})({1j p j q j t X P m .例1 一维随机游动一个质点在直线上的五个位置:0,1,2,3,4之上随机游动.当它处在位置1或2或3时,以31的概率向左移动一步而以32的概率向右移动一步;当它到达位置0时,以概率1返回位置1;当它到达位置4时以概率1停留在该位置上(称位置0为反射壁,称位置4为吸收壁).以j t X n =)(表示时刻n t 质点处于位置j ,4,3,2,1,0=j ,则},,,),({210⋅⋅⋅=t t t t t X 是齐次马尔可夫链.其状态空间}4,3,2,1,0{=S ,状态0是反射状态,状态4是吸收状态.其转移概率矩阵⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛==1000032031000320310003203100010)(ij p P})(|)({1i t X j t X P p m m ij ===+分别以4,3,2,1,0,0==j i ； 4,3,2,1,0,1==j i ；4,3,2,1,0,2==j i ；4,3,2,1,0,3==j i ；4,3,2,1,0,4==j i按题设条件求出转移概率 })(|)({1i t X j t X P p m m ij ===+ 画出状态转移示意图如图例3（成功流）设在一串贝努里试验中,每次试验成功的概率为p ,令⎩⎨⎧≤≤=n k k n k n X n 1,,,0次成功次试验接连第第次试验失败第则},3,2,1,{⋅⋅⋅=n X n 是齐次马尔可夫链.其状态空间},,,2,1,0{⋅⋅⋅⋅⋅⋅=k S ,其转移概率pq X P i X X P n n n -======++1}0{}|0{11,p n P i X i X P n n =+==+=+}1{}|1{1次试验时成功第,,0,,020100===p p p q p ，⎪⎪⎩⎪⎪⎨⎧=≤<+=+≥====+0,0,01,2,0}|{1j q i j i j p i j i X j X P p n n ij , （ ,3,2,1=i ）于是转移概率矩阵⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅⋅=ij i i j j p p p p p p p p p P 101111000100⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=p q p q p q p q 0000000000二． 切普曼-柯尔莫哥洛夫方程定理一 设 },,,,,),({210⋅⋅⋅⋅⋅⋅=n t t t t t t X是马尔可夫链,则有)()()()()()(n m l kj km n ik m l n ij t p t p t p ++∑=, (13.6)称为切普曼-柯尔莫哥洛夫方程.证 由条件概率定义计算公式,利用全概率公式和马氏条件,得})(|)({)()(i t X j t X P t p m l n m m l n ij ===+++})({})(,)({i t X P j t X i t X P m l n m m ====++ })({}})(,)(}){)({({i t X P j t X i t X k t X P m Sk l n m m n m =====∑∈+++})({})(,)(,)({i t X P j t X k t X i tX P m Sk l n m n m m=====∑∈+++ })({})(,)({})(,)({})(,)(,)({i t X P k t X i t X P k t X i t X P j t X k t X i t X P m n m m kn m m l n m n m m ===⋅======+++++∑})(|)({})(,)(|)({i t X k t X P k t X i t X j t X P m n m n m m kl n m ==⋅====++++∑})(|)({})(|)({i t X k t X P k t X j t X P m n m n m kl n m ==⋅===++++∑)()()()(n m l kj km n ik t p t p +∑= 证毕.如果马尔可夫链具有齐次性,那么切普曼-柯尔莫哥洛夫方程化为)()()(l kjkn ik l n ij p p p ∑=+ ,(13.7)当1,1==l n 时,得到kj kik ij p p p ∑=)2(,进一步改写为矩阵形式 2)2(P P=其中)()2()2(ijp P =是两步转移概率矩阵,P 是一步转移概率矩阵.用数学归纳法可得 nn P P =)(,⋅⋅⋅=,4,3,2n (13.8) 式(13.8)表明:n 步转移概率矩阵)()()(n ij n p P =等于一步转移概率矩阵P 的n 次幂.因此也常把n P 作为n 步转移概率矩阵的符号.例2 在本节例2中,求)2(00p 和)2(31p.解 由kj kik ij p p p ∑=)2(,得3131140)2(00=⨯==∑=k k k p p p,913131413)2(31=⨯==∑=k k k p p p.或用2)2()2()(P p Pij==.例3 传输数字0和1的通讯系统,每个数字的传输需经过若干步骤,设每步传输正确的概率为109,传输错误的概率为101,(1)问:数字1经三步传输出1的概率是多少? (2)若某步传输出数字1,那么又接连两步都传输出1的概率是多少?解 以n X 表示第n 步传输出的数字,则},2,1,0,{⋅⋅⋅=n X n 是一齐次马尔可夫链,0X 是初始状态,状态空间}1,0{=S ,一步转移概率矩阵⎝⎛=101109P ⎪⎪⎪⎪⎭⎫109101 (1) 2)2(P P =⎝⎛=101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109 ⎪⎪⎪⎪⎭⎫109101= ⎝⎛1001810082⎪⎪⎪⎪⎭⎫10082100183)3(P P =⎝⎛=101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101= ⎝⎛1001810082⎪⎪⎪⎪⎭⎫1008210018 ⎝⎛101109⎪⎪⎪⎪⎭⎫109101=⎝⎛10002441000756 ⎪⎪⎪⎪⎭⎫10007561000244,756.01000756)3(11==p ; (2) }1|1,1{21===++n n n X X X P}1|1{1===+n n X X P }1,1|1{12===⋅++n n n X X X P}1|1{1===+n n X X P }1|1{12==⋅++n n X X P81.0)109(21111==⋅=p p .。