Ch6 第六章*马尔可夫链 1随机游动 考虑数轴上的一个质点,设在时刻t=0时它处于位置a(a是整数) 以后每隔单位时间,它分别以概率p向正向移动一个单位,以概率q=1-p 向负向移动一个单位。这种模型称为直线上的随机游动。一般我们会具体考 虑下面几种模型 (1)无限制的随机游动 假定质点在时刻0从原点出发,记 Xn=质点在时刻t=n时的位置, 考虑Xn的分布P(Xn=k),显然有|>n时P(Xn2=k)=0。此时,前n 步中有(n+k)/2步向正向移动,(m-k)/2步向负向移动。于是就有 P(X,=b)=/c型1号,固≤n且kn奇偶性相同 其他. (2)带吸收壁的随机游动 假定质点在0时刻位于x=a,而在x=0及x=a+b=c处各有 吸收壁,其中a,b>0。也就是说,当质点遇到0或c中的一点时,就停止移 动,被吸收了。求质点被x=0及x=c吸收的概率 可以看出,这就是赌徒模型。记r=q/p,则质点被0点吸收的概率满足 Pk= ppk+1+gpk-1 于是可以解得 ra+b ≠1, 同样的,质点被c点吸收的概率为 74+6,7 ≠1 a+b
Ch6 1 ✂✁✂✄ * ☎✂✆✂✝✂✞✂✟ §1 ✠✂✡✂☛✂☞ ✌✂✍✂✎✂✏✂✑✓✒✓✔✖✕✓✗✖✘✚✙✜✛✓✢✖✣✓✤ t = 0 ✣✂✥✂✦✂✧✂★✓✩ a ✪ a ✫✂✬✎✮✭✯✙ ✰✲✱✲✳✲✴✲✵★✂✣✷✶✸✙✹✥✂✺✂✻✰✂✼✂✽ p ✾❀✿❁✾❀❂✲❃✔✂✕✵★❄✙ ✰✂✼✂✽ q = 1 − p ✾❆❅✷✾❆❂✂❃✔✂✕✵★❈❇❊❉✂❋✓●✂❍✓■✂❏✓❑✂▲✓✑✂✒✓▼✂◆✓❖❃ ❇❊✔✓P✂◗✓❘✂❙✓❚✂❯✓✌ ✍✂❱✂❲✂❳✂❋✂●✂❍❄❨ (1) ❩✂❬✂❭✒✂▼✂◆✂❖❃ ❪✂❫✂✗✂✘✂✢✂✣✂✤ 0 ❴✂❵✘✷❛❆❜❈✙❊❝ Xn = ✗✂✘✂✢✂✣✂✤ t = n ✣✂✒✂★✂✩, ✌✂✍ Xn ✒✂✺✂❞ P(Xn = k) ✙❊❡✂❢✂❣ |k| > n ✣ P(Xn = k) = 0 ❇❊❤✂✣❈✙❊✐ n ❥✷❦❣ (n + k)/2 ❥ ✾❆✿✷✾❆❂✂❃✙ (n − k)/2 ❥ ✾❆❅✷✾❆❂✂❃❇❊✧✫✓❧❣ P(Xn = k) = ( C n+k 2 n p n+k 2 q n−k 2 , |k| 6 n♠ k, n ♥✂♦✂♣✂q✷r, 0, s✂t. (2) ✉✂✈✂✇✂①✒✂▼✂◆✂❖❃ ❪✂❫✂✗✂✘✂✢ 0 ✣✂✤✂★✂✧ x = a ✙③②✂✢ x = 0 ④ x = a + b = c ✦✂⑤✂❣✂✔ ✈✲✇✲①✙ s ❦ a, b > 0 ❇⑦⑥❧✲✫✲⑧✙⑩⑨✂✗✓✘✂❶✂❷ 0 ❸ c ❦✒✲✔✲✘✲✣❄✙ ❧✓❹✂❺✂❂ ❃ ✙❊❻✈✂✇✂❼ ❇❾❽✓✗✓✘✂❻ x = 0 ④ x = c ✈✂✇✒✼✂✽❇ ❿✰✲➀❛➁✙➂❉❧✲✫✂➃✂➄●✂❍❄❇➅❝ r = q/p ✙➂➆✲✗✲✘✲❻ 0 ✘✈✲✇✒✼✲✽✲➇✂➈ pk = ppk+1 + qpk−1, ✧✫ ❿✰✂➉✂➊ pk = r a − r a+b 1 − r a+b , r 6= 1, b a + b , r = 1. r❆➋✒❈✙❊✗✂✘✂❻ c ✘✈✂✇✒✼✂✽❏ p ∗ k = 1 − r a 1 − r a+b , r 6= 1, a a + b , r = 1. 1
Ch6 (3)带反射壁的随机游动 假定质点在0时刻位于x=a,而在x=0及x=a+b=c处各有 反射壁,其中a,b>0,也就是说,当质点到达0点时,下一步就必然向右移 动到1。同样,当质点到达c点时,下一步必然向左移动到c-1 现在考虑图上的随机游动,概率与电压有很大关系。现在以数轴正半轴 上整点带吸收壁的随机游动为例 设连接点i和i+1的边上的电阻为(2),i=0,1,2,…,加上电压使得 p 0点电压V=1,c点电压V=0。这时,对于0和c中间的任意一点k点 的电压Vk满足 Vk-1-vk Vk-vk+ q\ 整理即得 Vk=pV+1+qvk-1s 与上面的带吸收壁的随机游动相比较可知V与Pk满足相同的方程,故 Vk=pk 对于一般的图也可以给根据概率给定电阻,然后规定电压,将概率与电 压对应起来。 §2随机游动的常返性 对于数轴上整点的随机游动,考虑从0点出发,经过2n步后返回0点 的概率(经过奇数步不可能返回0点) P(X2n=0)=C2np"q 对n求和有 ∑P(Xn=0)=∑C2p 当p≠q时,4p<(p+q)2=1,故随机游动经过0点的次数为有限的 概率为1。而当p=q=1/2时,上式等于无穷大,也就是说,随机游动会经 过0点无穷多次
Ch6 2 (3) ✉✂➌✂➍✂①✒✂▼✂◆✂❖❃ ❪✂❫✂✗✂✘✂✢ 0 ✣✂✤✂★✂✧ x = a ✙③②✂✢ x = 0 ④ x = a + b = c ✦✂⑤✂❣✂✔ ➌✲➍✲①✙ s ❦ a, b > 0 ✙⑦⑥❧✲✫✲⑧✙⑩⑨✓✗✂✘✓❷✂➎ 0 ✘✲✣❈✙⑦❱✲✔❥❧✓➏❢ ✾❆➐✂❂ ❃ ❷ 1 ❇ r❆➋✙❊⑨✂✗✂✘✂❷✓➎ c ✘✂✣❈✙❊❱✂✔❥ ➏❢ ✾➒➑✂❂✓❃❷ c − 1 ❇ ➓✢✂✌✂✍✷➔❆✑✂✒✂▼✂◆✂❖❃ ✙ ✼✂✽✓→✷➣➒↔❣✓↕✂➙✓➛✂➜❄❇ ➓✢✰ ✎✂✏✿✂➝✏ ✑ ✬ ✘✉✂✈✂✇✂①✒✂▼✂◆✓❖❃ ❏✓➞❄❇ ✛✲➟✲➠✲✘ i ➡ i + 1 ✒✲➢✲✑✲✒ ➣❆➤❏ q p i , i = 0, 1, 2, · · · ✙⑩➥✲✑➣❀↔✲➦✂➊ 0 ✘ ➣❆↔ V0 = 1 ✙ c ✘ ➣❆↔ Vc = 0 ❇➧❉✂✣❄✙➧➨✂✧ 0 ➡ c ❦ ✶❆✒✂➩✂➫✂✔✂✘ k ✘ ✒ ➣❆↔ Vk ➇✂➈ Vk−1 − Vk q p k−1 = Vk − VK+1 q p k , ✬✂➭✂➯➊ Vk = pVk+1 + qVk−1, →✑✲❲✲✒✉✲✈✲✇✂①✒✂▼✂◆✂❖❃✂q✷➲❆➳❿✂➵ Vk → pk ➇✲➈q❁r✒✲➸✲➺❄✙➅➻ Vk = pk ❇ ➨✂✧✂✔✂P✂✒✷➔❆⑥❿✰✂➼✂➽✂➾✂✼✂✽✓➼❫ ➣❆➤✙❊❢✱✂➚❫➣➒↔✙❊➪✼✓✽✂→➶➣ ↔➨✂➹✂➘✂➴❈❇ §2 ✠✂✡✂☛✂☞✂➷✂➬✂➮✂➱ ➨✂✧✂✎✂✏✂✑✬ ✘✂✒✂▼✓◆✂❖❃ ✙➧✌✓✍❴ 0 ✘✷❛❆❜❈✙❾✃✂❐ 2n ❥✱✂❒✷❮ 0 ✘ ✒✼✂✽ ✪ ✃✂❐♥✎❥✓❰❿✓Ï❒➶❮ 0 ✘✮✭✯✙ P(X2n = 0) = C n 2np n q n . ➨ n ❽ ➡❣ X∞ n=1 P(X2n = 0) = X∞ n=1 C n 2np n q n = 1 1 − √ 4pq . ⑨ p 6= q ✣❈✙ 4pq < (p + q) 2 = 1 ✙❾➻✂▼✂◆✂❖❃✃✂❐ 0 ✘✂✒✂Ð✂✎✂❏✂❣❬ ✒ ✼✂✽❏ 1 ❇Ñ②✂⑨ p = q = 1/2 ✣❈✙Ñ✑✂Ò✂Ó✂✧❩✂Ô➙❈✙❊⑥❧✓✫✂⑧✙❊▼✓◆✂❖❃❙✓✃ ❐ 0 ✘❩✂Ô✂ÕÐ❈❇ 2
Ch6 定义称一个点是常返的,如果从这一点出发的随机游动会无穷次返回 这一点。 从一点v出发的随机游动是常返的充要条件为 ∑P(Xn=0) 在这里不给出证明 接下来看二维的情形。二维有四个方向,当四个方向的概率不相等的时 候,容易证明所有点都是非常返的。而当四个方向概率都相等的时候,考虑 从任何一点U出发的随机游动,有 P(X2n=)=∑ k!k!(n-k)(n-k)! 12 k=0 于是,二维的格点上的随机游动是常返的 用同样的方法可以证明,三维以上的格点上的随机游动是非常返的。 对zd上的随机游动,每一步都可以用一个向量表示。记第n步的向量 为5n,则￡n是是独立同分布的随机变量,其值域为{±e,i=1,…,d},其 中e;为沿第i个方向上的单位向量。此时,第n步质点的位置Xn就是n 个独立同分布的随机变量的和 51+52 特别的,当μrin取各个向量的概率都相等的时候,也就是说, P(n=e1)=P(5n=-e1) 此时称随机游动为z4上的简单随机游动,简记为SRW 上一节提到了图上随机游动的概率与电网络的电压有关联,因为它们都 满足调和方程。下面将继续利用电压来讨论随机游动的问题
Ch6 3 Ö✂× ■✂✔✂✕✂✘✫✂Ø❒✒✚✙➧Ù✓Ú❴❉✓✔✓✘✷❛➒❜✓✒✓▼✓◆✓❖❃❙ ❩✓ÔÐ❒✷❮ ❉✂✔✂✘❈❇ ❴ ✔✂✘ v ❛❆❜✂✒✂▼✂◆✂❖❃✂✫✂Ø❒✒✓Û✂Ü✓Ý✓Þ✂❏ X∞ n=1 P(Xn = v) = ∞. ✢✂❉✂ß❰➼❛❆à✷á➁❇ ➠✂❱✂➴➀✂â✂ã✒✂ä✂å❈❇ â✂ã❣✷æ➒✕✂➸✾ ✙❊⑨✷æ➒✕✂➸✾✒✼✂✽❰ qÓ✂✒✓✣ ç❄✙➧è✂é✂à✷á❆ê✂❣✓✘✓ë✫✓ì✓Ø❒✒✚❇í②✓⑨➶æ❆✕✓➸✾✼✓✽ë qÓ✓✒✓✣✓ç✚✙➧✌✓✍ ❴ ➩✂î✂✔✂✘ v ❛❆❜✂✒✂▼✂◆✂❖❃ ✙❊❣ P(X2n = v) = Xn i=0 (2n)! k!k!(n − k)!(n − k)! 1 4 2n = 1 4 2n (2n)! (n!)2 Xn k=0 C k nC n−k n = 1 4 2n (C n 2n ) 2 . ✧✫ ✙ â✂ã✒✂ï✂✘✂✑✓✒✂▼✓◆✓❖❃✓✫✂Ø❒✒❄❇ ð r❆➋✒✂➸✂ñ❿✰à✷á➁✙➧òã✂✰ ✑✂✒✓ï✓✘✂✑✓✒✓▼✂◆✓❖❃✓✫✓ì✂Ø❒✒❈❇ ➨ Z d ✑✂✒✂▼✂◆✂❖❃ ✙ ✳✔❥ë❿✰ ð✔✂✕✾➒ó✂ô✓õ ❇❾❝✓ö n ❥✒ ✾❆ó ❏ ξn ✙➧➆ ξn ✫✂✫✂÷✂ø✷r✺✂❞✓✒✂▼✓◆✓ùó ✙ s✓ú✓û❏ {±ei , i = 1, · · · , d} ✙ s ❦ ei ❏✂ü✂ö i ✕✂➸✾✑✂✒✵★ ✾➒ó❇ý❤✖✣✚✙ýö n ❥✗✂✘✂✒✂★✓✩ Xn ❧✂✫ n ✕ ÷✂ø✷r✺✂❞✂✒✂▼✂◆✂ùó ✒ ➡ ❨ Xn = ξ1 + ξ2 + · · · + ξn. þ✂✻✂✒❈✙❊⑨ |xin ÿ ⑤✂✕✾❆ó✒✼✂✽ë qÓ✓✒✂✣✓ç❄✙❾⑥❧✓✫✂⑧✙ P(ξn = ei) = P(ξn = −ei) = 1 2d , ❤✂✣✂■✂▼✂◆✂❖❃ ❏ Z d ✑✂✒✁✵▼✂◆✂❖❃ ✙✂✓❝✂❏ SRW ❇ ✑✲✔☎✄☎✆✲❷❼ ➔❆✑✂▼✂◆✂❖❃ ✒✼✂✽✂→✷➣✁✝✟✞✒ ➣❆↔❣✂➛✁✠❄✙☛✡❆❏✂✥✂❘✂ë ➇✂➈✁☞➡➸✂➺❈❇❊❱✓❲✓➪✁✌✎✍✁✏ð ➣❆↔➴✁✑✎✒✓▼✂◆✓❖❃ ✒✔✓✟✕❄❇ 3
Ch6 记N=N(u)={随机游动返回0点的次数},则有 N=∑1(xn=0)(u) n=1 由上一节给的定理,有 P(N=∞)=1+→EN=∑P(Xn=0)=∝ n=1 定义 Ti=infn>0: Xn =i, Tt=infn>0: Xn=il, 则0点常返即t<∞ 对于Z上的随机游动,考虑从0点出发的SRW(可以通过平移将任 何一点变成0点),给每条边加上电阻1,加电压使得0点电压为1,无穷远 处电压为0.则可以证明,0点常返的充要条件是从0点到无穷原点的等效 电阻为无穷大
Ch6 4 ❝ N = N(ω) = {▼✂◆✂❖❃❒✷❮ 0 ✘✂✒✂Ð✂✎} ✙❊➆✂❣ N = X∞ n=1 1(Xn=0)(ω). ✖❆✑✂✔✁✄➼✒✂❫➭ ✙❊❣ P(N = ∞) = 1 ⇐⇒ EN = X∞ n=1 P(Xn = 0) = ∞. ❫✁✗ τi = inf n {n > 0 : Xn = i}, τ + i = inf n {n > 0 : Xn = i}, ➆ 0 ✘Ø❒ ➯ τ + 0 < ∞ ❇ ➨✂✧ Z d ✑✂✒✂▼✂◆✂❖❃ ✙ ✌✂✍❴ 0 ✘✷❛❆❜✂✒ SRW ✪ ❿✰✁✘❐✁✙❂ ➪✓➩ î✂✔✂✘✂ù✁✚ 0 ✘➶✭ ✙ ➼✂✳Ý✓➢✂➥✓✑➣➒➤ 1 ✙Ñ➥ ➣❆↔✂➦✂➊ 0 ✘ ➣❆↔❏ 1 ✙ ❩✂Ô✁✛ ✦➣❆↔❏ 0 ❇③➆❿✰à✷á ✙ 0 ✘Ø❒✒✂Û✂Ü✓Ý✓Þ✫✓❴ 0 ✘✂❷❩✂Ô✂❵✘✓✒✓Ó✎✜ ➣❆➤❏❩✂Ô➙❈❇ 4