3马尔可夫链及转移概率 定义设Xn(n=0,1,2,……)的值域至多可数(记值域为,称为状态空 间),如果对任意的i0,i1,…,in-1,i,j∈I,都有 P(Xn+lX, X P(Xn+1=∥|Xn=i) 则称随机序列{Xn;m≥0}为一马尔可夫链(简称马氏链)。如果进一步,对 任意的n都有 P(Xn+1=jXn=i)=P(X1=jXo=i) 则称该马氏链是时齐的。在这里我们只考虑时齐马氏链。 对马氏链{Xn,n≥0},定义(一步)转移概率为 (X1=j|X0=i) 相应的,(P7)hxn称为转移概率阵。 此时,考虑{Xn}的有限维联合分布 P(X P(X0=i0)P(X1=i1X0=i0)P(X2=i2 P(Xn=inIXn-I=in- P(X 0= lopioinpi p(2n-12 于是,在知道了P(X0=i0)之后,联合分布就唯一确定了。称P(X0 io)为马氏链的初分布 对转移概率,显然有 (1)ⅵ,∈I,p;≥0 Pij 对于马氏连{Xn;n≥},称 (j)=P(Xn=川|X0=i)
Ch6 1 §3 ✂✁✂✄✂☎✂✆✂✝✂✞✂✟✂✠✂✡ ☛✌☞ ✍ Xn(n = 0, 1, 2, · · ·) ✎✌✏✌✑✌✒✌✓✂✔✂✕✗✖✙✘✂✏✚✑✂✛ I ✜✣✢✌✛✌✤✌✥✌✦ ✧✩★ ✜✫✪✂✬✂✭✂✮✂✯✂✎ i0, i1, · · · , in−1, i, j ∈ I ✜✫✰✂✱ P(Xn+1|Xn = i, X0 = i0, X1 = i1, · · · , Xn−1 = in−1) = P(Xn+1 = j|Xn = i), ✲✢✌✳✌✴✌✵✚✶ {Xn; n > 0} ✛✌✷✌✸✌✹✌✔✂✺✚✻✗✖✙✼✚✢✂✸✾✽✿✻ ★❁❀ ✪✂✬✚❂✂✷✚❃❄✜❅✭ ✮✂✯✂✎ n ✰✂✱ P(Xn+1 = j|Xn = i) = P(X1 = j|X0 = i), ✲✢✂❆✂✸✾✽❇✻✂❈✂❉✂❊✂✎ ❀●❋✚❍✚■✚❏✂❑✚▲✂▼✚◆❉✂❊✚✸❖✽❇✻❀ ✭✂✸✾✽❇✻ {Xn, n > 0} ✜✫P✂◗❘✖✙✷✂❃ ★❚❙✂❯✚❱✂❲✛ pij = P(X1 = j|X0 = i). ❳✂❨✎❩✜ (pij )n×n ✢✂✛❙✂❯✂❱✂❲✾❬❭❀ ❪❉❩✜ ▼✂◆ {Xn} ✎✂✱✂❫✂❴✂❵✂❛✂❜✂❝ P(X0 = i0, X1 = i1, · · · , Xn = in) = P(X0 = i0)P(X1 = i1|X0 = i0)P(X2 = i2|X1 = i1, X0 = i0) · · ·P(Xn = in|Xn−1 = in−1, · · · , X0 = i0) = P(X0 = i0)pi0i1 pi1i2 · · · p(in−1in). ❞❈❩✜ ❋✂❡✂❢✂❣ P(X0 = i0) ❤✂✐❩✜✫❵✂❛✂❜✂❝✂❥✚❦✚✷✂❧✚P❣❄❀ ✢ P(X0 = i0) ✛✂✸✾✽❇✻✂✎✂♠✂❜✂❝❀ ✭ ❙✂❯✂❱✂❲✜✫♥✂♦✂✱ (1) ∀i, j ∈ I ✜ pij > 0; (2) ∀i ∈ I ✜ X j∈I pij = 1. ✭ ❞ ✸✾✽❇♣ {Xn; n >} ✜✫✢ pn(ij) = P(Xn = j|X0 = i) 1
Ch6 为n步转移概率,相应的,称(Pn(ij)xn为n步转移阵 对n步转移概率,有下面的K-C方程: pn(i)=∑pm1(k)Ppn-m(k,Ⅵ≤m≤n-1 证对Xmn的状态进行分解 Pn(ij)= P(Xn=jlO=i) ∑P(Xn=j,Xm=AX0= >P(Xm=klO=i)P(Xn=jlM=k, Xo=i) k∈I >P(Xm=klO=i)P(Xn=jlM=k) ∑pnl(k)pn-m(k) 容易证明,n步转移概率也是时齐的。由上面的K-C方程可知 (Pn2(ij)=(P)2 下面给出几个马氏链的例子。 例31I={…,-2,-1,0,1,2,…}是全体整数集合,转移概率 P,j=i+1, 4, J 0,其他 这就是直线上的无限制随机游动,其转移阵为 P 00 0 例321={0,1,…,C},c≥2.对1≤i≤c-1,p与上例中相同,而 p00=P
Ch6 2 ✛ n ❃❙✂❯✂❱✂❲✜ ❳✂❨✎❄✜●✢ (pn(ij))n×n ✛ n ❃❙✂❯✾❬❭❀ ✭ n ❃❙✂❯✂❱✂❲✜✫✱✂q✂r✚✎ K-C s✂t❄✉ pn(ij) = X k∈I pm(ik)pn−m(kj), ∀1 6 m 6 n − 1. ✈ ✭ Xm ✎✂✤✂✥✂❂✂✇✂❜✂① pn(ij) = P(Xn = j|X0 = i) = X k∈I P(Xn = j, Xm = k|X0 = i) = X k∈I P(Xm = k|X0 = i)P(Xn = j|Xm = k, X0 = i) = X k∈I P(Xm = k|X0 = i)P(Xn = j|Xm = k) = X k∈I pm(ik)pn−m(kj). ②✂③✂④✾⑤ ✜ n ❃❙✂❯✂❱✂❲✂⑥❈✂❉✂❊✂✎ ❀⑧⑦✿⑨r✂✎ K-C s✂t✂✔❡ (pn(ij)) = (pij) n . q✂r✂⑩✾❶❇❷✂❸✂✸✾✽❇✻✂✎✂❹✚❺❀ ❻ 3.1 I = {· · · , −2, −1, 0, 1, 2, · · · } ❈✂❼✂❽✂❾✂✕✂❿✂❛❩✜ ❙✚❯✂❱✚❲ pij = p, j = i + 1, q, j = i − 1, 0, ➀✂➁, ❍ ❥✂❈✂➂✂➃⑨ ✎✂➄✂❫✂➅✚✳✚✴✂➆✚➇❄✜●➀❙✂❯❖❬✛ P = · · · · · · · · · · · · · · · · · · · · · · · · q 0 p 0 0 · · · · · · 0 q 0 p 0 · · · · · · 0 0 q 0 p · · · · · · · · · · · · · · · · · · · · · · · · . ❻ 3.2 I = {0, 1, · · · , c} ✜ c > 2 ❀ ✭ 1 6 i 6 c−1 ✜ pij ➈⑨ ❹➊➉❳➊➋ ✜➍➌ p00 = pcc = 1. 2
Ch6 这是具有两个吸收壁0和c的随机游动,其转移阵为 1g 0 P 0 g0 p 例33将上例中P00=pe=1换成p01=pa(-1)=1,得到的是有两个 反射壁的随机游动。当质点走到区间0,d两端的时候,下一步一定被反射 回来。其转移阵为 q P 0 0 P q P 0010 例34 Ehren∫est模型。设{Xn;m≥0}是一马氏链,I={0,1,……} 而对i∈I,有 P(-)=c 它可以用一个摸球的模型来实现:一个密封容器中装有c个球(白色的 或者黑色的),随机的从中取一个球,并换成另一种颜色的球放回。则容器中 的白球数就是上面的Xn 对于n步转移概率阵P(n),一般通过将P转化为 JJordan标准型来求 连平稳分布 对于马氏链{Xn;n≥0},设其转移概率阵为P=(P3)n×n,在给定初始 分布即ⅹ0的分布后,Xn的分布也就确定了。具体地说,由全概公式,记Xn
Ch6 3 ❍ ❈✂➎✂✱✂➏✂❸✂➐✂➑✂➒ 0 ➓ c ✎✂✳✂✴✂➆✂➇❩✜✫➀❙✚❯✾❬✛ P = 1 0 0 0 · · · · · · · · · · · · · · · q 0 p 0 · · · · · · · · · · · · · · · 0 q 0 p · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 0 q 0 p · · · · · · · · · · · · · · · 0 0 0 1 . ❻ 3.3 ➔ ⑨ ❹✾➉ p00 = pcc = 1 →✂➣ p01 = pc(c−1) = 1 ✜❅↔✂↕✂✎✂❈✂✱✂➏✂❸ ➙✂➛➒✂✎✂✳✩✴✚➆✩➇❀➝➜✚➞✚➟✩➠↕➢➡ ✧ [0, c] ➏✂➤✂✎✂❉✂➥➦✜➝q✚✷✩❃✚✷✩P✚➧➙✚➛ ➨❇➩❀ ➀ ❙✂❯✾❬✛ P = 0 1 0 0 · · · · · · · · · · · · · · · q 0 p 0 · · · · · · · · · · · · · · · 0 q 0 p · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 0 q 0 p · · · · · · · · · · · · · · · 0 0 1 0 . ❻ 3.4 Ehrenfest ➫✂➭❀➯✍ {Xn; n > 0} ❈✂✷✂✸✾✽❇✻➦✜ I = {0, 1, · · · } ✜ ➌✂✭ i ∈ I ✜✫✱ pi(i+1) = c − i c , pi(i−1) = i c . ➲✔✂➳✂➵✂✷✂❸✂➸✂➺✂✎✂➫✂➭➩✂➻✂➼✉❅✷✚❸✂➽✚➾②✚➚➉✿➪✂✱ c ❸✂➺➶✖➘➹❇➴✂✎ ➷✌➬✌➮➴✌✎ ★ ✜❚✳✂✴✂✎✂➱✾➉❇✃✂✷✂❸✂➺❄✜➍❐✂→✂➣✂❒✂✷✂❮✂❰✂➴✂✎✂➺✂Ï➨ ❀➍✲②✂➚➉ ✎✾➹❇➺✂✕✂❥✂❈⑨r✂✎ Xn ❀ ✭ ❞ n ❃❙✌❯✌❱✌❲➊❬ P(n) ✜Ð✷✌Ñ✌Ò✌Ó✌➔ P ❙✌Ô✛ Jordan Õ✌Ö✌➭➩✌×❀ §4 Ø✂Ù✂Ú✂Û ✭ ❞ ✸➊✽Ü✻ {Xn; n > 0} ✜ ✍➀ ❙✌❯✌❱✚❲✾❬✛ P = (pij)n×n ✜ ❋⑩✌P✌♠✌Ý ❜✌❝✌Þ X0 ✎✌❜✌❝✌✐❩✜ Xn ✎✌❜✌❝⑥ ❥✌❧✌P❣❄❀ ➎✂❽✌ß✂à❄✜ ⑦ ❼ ❱✂á✌â✜ã✘ Xn 3
Ch6 的分布列向量为pn,则 n+1 u,P 于是就有 定义称分布列=(2)ier为马氏链{Xn;n≥0}的不变分布列,如果 以它为初始分布时,X0,X1,……,Xn,……同分布 容易看出,μ为不变分布列的充要条件是它满足下面的方程 P 对于一般的马氏链,直接利用转移阵就可以解出它的不变分布。下面介 绍一种特殊的马氏链,可逆马氏链。 定义一个马氏链{Xn;n≥0}称为可逆的,如果存在分布丌={r}er 使得 vi,j∈I. 此时,称分布π为该马氏链的可逆分布 容易求出,可逆分布是平稳分布 对于可逆马氏链,可以如下求出可逆分布,也就是平稳分布 适当给状态标号,使得pnn+1)>0(这一般是可以做到的)。取po=1, 然后如下递归: n+1= P(n+1)n 记H=∑m,则可逆分布为 例41考虑有两个反射壁的对称随机游动(参见上节例3.3),此时有 1/2 取 则 =n----
Ch6 4 ✎✂❜✂❝✂✶✾ä❇å✂✛ µn ✜ ✲ µ 0 n+1 = µ 0 nP, ❞❈✂❥✂✱ µ 0 n = µ 0 0P n . ☛✂☞ ✢✂❜✂❝✂✶ µ = (pi)i∈I ✛✂✸✾✽❇✻ {Xn; n > 0} ✎✂æ✂ç✂❜✂❝✂✶❄✜è✪✂✬ ➳➲ ✛✂♠✂Ý✂❜✂❝✂❉❩✜ X0 , X1, · · · , Xn, · · · ➋❜✂❝❀ ②✂③✂é❶❭✜ µ ✛✂æ✂ç✂❜✂❝✂✶✂✎✂ê✂ë✂ì✚í✚❈➲✚î✚ïq✚r✂✎✚s✚t➦✉ µ 0 = µ 0 P. ✭ ❞✷✂Ñ✂✎✂✸✾✽❇✻❩✜❅➂✂ð✂ñ✚➵❙✚❯✾❬❥✂✔✚➳✂①❖❶ ➲ ✎✂æ✚ç✂❜✚❝❀ q✂r✚ò ó✷✂❮✂ô✂õ✂✎✂✸✾✽❇✻❄✜●✔✚ö✂✸❖✽✿✻❀ ☛✌☞ ✷✌❸✌✸➊✽Ü✻ {Xn; n > 0} ✢✌✛✌✔✌ö✌✎❄✜✣✪✌✬✚÷❋❜✚❝ π = {πi}i∈I ✜ ø ↔ πipij = πjpji , ∀i, j ∈ I. ❪❉❩✜✫✢✂❜✂❝ π ✛✂❆✂✸✾✽❇✻✂✎✂✔✂ö✂❜✂❝❀ ②✂③× ❶❭✜✫✔✂ö✂❜✂❝✚❈✂ù✚ú✚❜✂❝❀ ✭ ❞✔✂ö✂✸✾✽❇✻❩✜✫✔✚➳✂✪✚q× ❶✿✔✂ö✚❜✚❝❄✜ ⑥ ❥✂❈✚ù✚ú✂❜✚❝➦✉ û✂➜⑩✂✤✂✥✂Õ✂ü❄✜ ø ↔ pn(n+1) > 0 ✖ ❍ ✷✂Ñ✂❈✂✔✂➳✂ý✂↕✚✎ ★❁❀ ✃ µ0 = 1 ✜ ♦✂✐✂✪✂q✂þ✂ÿ❄✉ µn+1 = µn pn(n+1) p(n+1)n , ✘ µ = X∞ n=0 µn ✜ ✲✔✂ö✂❜✂❝✂✛ πn = µn X∞ n=0 µn = µn µ . ❻ 4.1 ▼✂◆✱✂➏✂❸➙✂➛➒✂✎✚✭✚✢✂✳✚✴✚➆✚➇ ✖ ✁✄✂⑨✄☎❹ 3.3 ★ ✜ ❪❉✂✱ p = q = 1/2 ❀ ✃ µ0 = 1 ✜ ✲ µ1 = µ0 p01 p10 = 2µ0 = 2, µn = µn−1 p(n−1)n pn(n−1) = 1 2 µn−1. 4
而当1≤i<m-1时,有 计+1= 1 于是有p2×n-1=1, p2=2n 故 可以验证,丌=(丌0,x1,…,丌n)是马氏链的可逆分布
Ch6 5 ➌ ➜ 1 6 i < n − 1 ❉❩✜✫✱ µi+1 = µi pi(i+1) p(i+1)i = µi = µ1 = 2. ❞❈✂✱ µn = 1 2 µn−1 = 1 ✜ µ = Xn i=1 µi = 2n ❀ ✆ π0 = πn = 1 2n ✜ πi = 1 n ✜ i = 1, · · · , i − 1 ❀ ✔✂➳✞✝④ ✜ π = (π0, π1, · · · , πn) ❈✂✸✾✽❇✻✂✎✂✔✂ö✂❜✂❝❀ 5