第四章 马尔可夫链 马尔可夫过程按其状态和时间参数是连续的或离散的,可分为三类: (1) 时间,状态都是离散的马尔可夫过程,称为马尔可夫链.(2) 时间连续,状态离散的马尔可夫过程,称为连续时间的马尔可夫(3) 时间,状态都连续的马尔可夫过程.4.1 马尔可夫链的概念及转移概率 一,定义假设马尔可夫过程{X ,n e T}的参数集T是离散的时间集合，即nT={0,l,2,...},其相应X可能取值的全体组成的状态空间是离散的状态集 nI — {i ,i ,..•}•l2定义4.1设有随机过程{X , n e T},若对于任意的整数n & T和任意的ni ,i , i ,•••, i • e I，条件概率满足0 1 2 n+1P{ X — i X — i , X — i , • • X, — i }n+1 n+1 0 0 11 n n=P{X — i X — i }, (4.1)n+1 n+1 n n则称{X ,n e T}为马尔可夫链，简称•马氏链.n(4.1)式是马尔可夫链的马氏性(或无后效性)的数学表达式•由定义知P{ X — i , X — i , • • X, — i ]=0 0 1 1 n n=P{X — i X — i ,X — i，…,X — i }• P{X — i ,X — i，…,X — i }n n 0 0 11 n-1 n-1 0 0 11 n-1 n-1=P{X — i X — i }• P{X — i ,X — i，…,X — i }=...n n n-1 n-1 0 0 11 n-1 n-1=P{ X — i X — i } P{ X — i X — i }…n n n-1 n-1 n-1 n -1 n-2 n-2P{ X — i X1 1 0—i } P{X — i }•0 0 0可见，马尔可夫链的统计特性完全由条件概率P{X — i X — i }所决定.n+1 n+1 n n二,转移概率条件概率P{X — jX — i}的直观含义为系统在时刻n处于状态i的条件下,n+1 n在时刻n+1系统处于状态j的概率.它相当于随机游动的质点在时刻n处于状态i 的条件下，下一步转移到状态j的概率•记此条件概率为p (n).ij定义4.2称条件概率p..(n).= P{X — i |X — i }j n+1 n+1 n n为马尔可夫链｛X , n e T｝在时刻n的一步转移概率，其中i,j e I,简称为转移概率.n定义4.3若对任意i,j e I,马尔可夫链｛X , n e T｝的转移概率p (n).与n无关, ij则称马尔可夫链是齐次的，并记p (n).为p .ij ij 下面我们只讨论齐次马尔可夫链,通常将齐次两字省略.设p表示一步转移概率p .所组成的矩阵，且状态空间1=｛1,2,…｝，则ijp p ... p11 12 1np p ... p21 22 2 n称为系统的一步转移概率矩阵,它有性质:(1) p j > 0,i, j e I；(2)工p 二 1,i e I.ij ijjeI通常称满足上述(1),(2)性质的矩阵为随机矩阵.定义 4.4 称条件概率p (n).. = P{X = j|X = i},(i, j e I,m > 0,n > 1)ij m+n m为马尔可夫链｛X ,n e T｝的n步转移概率,.并称p (n) = ( p (n))ijijjeI为马尔可夫链的n步转移矩阵，其中(1) pnj > 0,i, j e I;(2)工p(n).. = 1,i e I.即也是ij ij随机矩阵.当n=1时，p(1)...= p .，此时一步转移矩阵p(1)二p.此外我们规定 ij ijp(0)十丰j，ij I 1，i = j.定理4.1设｛X ,n e T｝为马尔可夫链，则对任意整数n > 0,0 < l < n和i, j e I,n步转移概率 p (n) ij .具有下列性质:(1) p (n) =Y p (l) p (n-l))；ij ik kjkeIp (n) = 工..工 p p ...pk1k2 kn-1 jijk eI k eI1 n -1ik1(4.2)(4.3)(4.4)(3) P(n)二 PP(n一 1)；(4) P(n)二 Pn . (4.5)证明(1) 利用全概率公式及马尔可夫性,有().iv } P{ X = i, X = j}P (n) = P{ X = j|X = i}= m m+nij m+n mP{ X = i, X = k}m m+lP{ X = i}mmy P{ X = i, X = k, X = j} 乙 m m+l m+n—P{ X = i, X = k}kwl m m+l=y P{ X = j|X = k}P{ X = k|X = i}m+n m+l m+l mykw Ip(l).p(n-l). ik kjkwIy p (n-i) (m +1) p (i) (m)=ij ikkw I(2)在⑴中令 l = 1, k = k 得 p(n) = y p p(n-1))1 ij ik1 k1 jk1wI这是一个递推公式,可递推下下去即得(4.3).(3) 在(1).令 l=1 利用矩阵乘法可得.(4) 由(3),利用归纳法可证.定理 4.1 中的(1)式称为切普曼---柯尔哥洛夫方程,简称 C-K 方程 .定义4.5设{X ,n e T}为马尔可夫链，称np = P{X = j}, p (n) = P{X = j},( j e I)j 0 j n为{X ,n e T}的初始概率和绝对概率，并分别称{p , j e I},{p (n), j e I}为n j j{X ,n e T}的初始分布和绝对分布.简记为{p ,},{p (n),}.称概率向量n j jPt (n) = (p (n), p (n),..(肋冷 0)12为 n 时刻的绝对概率向量,而称Pt = (p ,p ,...),(n > 0)12 为初始向量.定理4.2设{X ,n e T}为马尔可夫链，则对任意整数n > 1, j e I,绝对概率np (n) .具有下列性质:⑴ P (n)=j工 P P (n ))；i ijiel(2) Pj工 p (n -1) pi ijiel(3) Pt (n)二 Pt (0)P(n)；(4.6)(4.7)(4.8)(4) Pt (n)二 PT (n -1)P(4.9)证明(1) p (n)二 P{Xj二 j}二工 P{ X0 = i，Xn = j}iel=工 P{X = j|X = i}P{ X = i}0 0iel(2)=工 p p (n)i ijielp (n)二 P{ Xj=j}二工 P{X = i, Xn -1iel=j}=工 P{Xiel=j|X = i}P{ Xn-1 n-1=i}==工 p (n -1)pi ijiel (3)与(4)是(1)与(2)的矩阵形式.定理4.3设{X ,n e T}为马尔可夫链，则对任意i i e I,n > 1,有n 1 nP{ X 二 i , .X.二 i }=工1 1 n np p ... pi ii i i1 n -1 n(4.10)证明 由全概率公式及马氏性有P{ X 二 i , . X.二 i } = P{1 1 n nP{X 二 i, X 二 i，…,X0 1 1X = i, X0ieI二 i }n= i ,..., X = i }1 1 n nP{X 二 i}P{X 二 i |X0 1 r 0=i |X = i,..., X = i }n 0 n-1 n-1二 i X 二 i }n n -1 n -1P{X 二 i}P{X 二 i |X 二 i,}...P{X0 1 f 0 np p ...p .i ii i i1 n -1 nieI 三,马尔可夫链的例子例 4.1 无限制随机游动设质点在数轴上移动，每次移动一格，向右移动的概率为P,向左移动的概率为q=l-p,这种运动称为无限制随机游动.以X表示时刻n质点所处的位置,则n{X ,n e T}是一个齐次马尔可夫链，试写出它的一步和k步转移概率.n解{X ,n e T}的状态空间I二{0,±1,±2,...},其一步转移概率矩阵为 nP=...q 0 p ...0 q 0 p ..设在第k步转移中向右移了 x步向左移动了 y步,且经过k步转移状态从j进入j,则f x + y = k,1 x — y = j — ix k + (j —i) y k —(j —i)22由于x,y都只取整数，所以k ± (j - i)必须是偶数•又在k步中哪x步向右，哪y步向左是任意的，选取的方法有C x种.于是kCxpxqy, k + (j - i)是偶数pk = < k .ij 0, k + (j — i)是奇数例 4.2 赌徒输光问题.两赌徒甲，乙进行一系列赌博•赌徒甲有a元，赌注乙有b元，每赌一局输者给赢 者1元，没有和局,直到两人中有一个输光为止•设在每一局中,甲赢的概率为p,输 的概率为q=1-p，求甲输光的概率.这个问题实质上是带有两个吸收壁的随机游动,其状态空间为1={0,1,2,…,c} c=a+b.故现在的问题是求质点从a出发到达0状态先于到达c=a+b状态的概率.解 设u表示甲从状态i出发转移到状态0的概率，要计算的是u .•由于0和c ia是吸收状态，故u二1, u二0. u由全概公式0 c iu = pu + qu ,(i = 1,2,..., c — 1). (4・11)i i+1 i—1上式的含义是，甲从状态i出发开始赌到输光的概率等于'他接下去赢了一局(概 率为p)处于状态i+1后再输光”;和他接下去输一局(概率为q),处于状态i-1后再输 光”这两个事件的概率.由于p+q=1,(4.11)实质上是一个差分方程u —u =r(u —u ),i=1,2, . .c.—, 1. (4.12)i+1 i i i—1其中r =.q;,其边界条件为u = 1, u = 0.0c先讨论r=1,即p=q=l/2的情况,(4.12)成为u — u = r(u — u ), i = 1,2, . . c 〒1.i+1 i i i—1(4.13)令u = u +a , 得10u = u +a = u + 2a,2 1 0= u +a = u +ia,i—1 0= u + a = u + c a, c —1 0将u = 0,u = 1,代于最后一式，得参数a c0u = 1 — —, i = 1,2, .. c. — 1.ic令 i=a, 求得甲输光的概率为 abu = 1 — = .a c a +b由于甲,乙的地位是对称的,故乙输光的概率为au = ・a a 。