随机过程及其应用-清华大学

4.1(等待时间的和) 设诚恳按照参数λ的Poisson 过程来到公交站，公交车于时刻t 发出，那么在[0, t ]时间段内到达的乘客等待时间总和的期望应该如何计算那？

对于某一个乘客而言，假设其到达时间为t k ，那么他等待时间就是

t -t k 所以乘客总的等待时间为S (t ) =∑(t -t k )

k =0N (t )

使用条件期望来处理平均等待E (S (t )) =E (E (t ) |N (t ) =n )

对于某已成了而言，其到达时刻t k 随机[0, t ]内均匀分布的随机变量。但在车站上，乘客是先后到达次序排队，所以在N (t ) =n 的条件下，

t 1, t 2,..., t n 形成了独立均匀分布的顺序统计量。不过就他们的和t 1+... +t n

而言，可以那他们看着顺序统计量，也可以把他们看着不排顺序的n 各独立的[0, t ]内均匀分布的随机变量，所以

E (E (t ) |N (t ) =n ) =nt -E (∑t k ) =nt -

k =0n

nt nt =22

N (t ) t t λt 2

从而有E (E (t )) =E () =E (N (t )) =

222

4.2(数值记录) 设{X n , n ∈N }是一独立同分布的非负期望随机变量序列。定义风险率λ(t ) 如下λ(t ) =

f (t )

1-F (t )

这里f (t ) 和F (t ) 分别是X k 的概率密度分布和分布函数。定义随机过程

N (t ) 如下N (t ) =#{n :X n >max(X n -1,.., X 0), X n ≤t }

这里#A 表示集合A 中的元素个数。如果把N (t ) 中的时间t 看做时间，那么N (t ) 是一个非齐次Poisson 过程。事实上，由于X k 彼此独立，所以N (t ) 具有独立增量性。很明显N (0) =0，于是只需要检查一个时间微元内N (t ) 的状态。

假定∆t 充分小，在X n ,..., X 0中只有X n 在(t , t +∆t ]上，因此

P (N (t +∆t ) -N (t ) =1) =∑P (X n ∈(t , t +∆],X n >max(X n -1,..., X 1))

n =1∞

P (X n ∈(t , t +∆],X n >max(X n -1,..., X 1)) =P (X n ∈(t , t +∆],X n -1≤t ,..., X 1≤t ) =P (X n ∈(t , t +∆])P (X n -1≤t ,..., X 1≤t ) =(f (t ) ∆t +o (∆t ))(F (t ))

n -1

所以

P (N (t +∆t ) -N (t ) =1) =(f (t ) ∆t +o (∆t )) ∑(F (x )) n -1

n =2∞

f (t ) ∆t +o (∆t ) 1-F (t ) =λ(t ) ∆t +o (∆t ) =

另一方面，可以证明P (N (t +∆t ) -N (t ) ≥2) =o (∆t ) 所以N (t ) 是非齐次的Poisson 过程，强度λ(t ) 。

这里所提到的风险率在可靠性研究中有着重要作用。假定某种起见的寿命为随机变量，其概率分布和密度分布为F (t ) 和f (t ) ，那么风险率微元λ(t ) ∆t +o (∆t ) 表示该器件在[0, 1]时间段内为失效的条件下，将会在

[t , t +∆t ]内失效的概率。由此可以说明“风险”一次的含义。从而可

知，与指数相应的风险率是常数，而且在所有非负连续随机变量的分布函数中，唯有指数分布相应的风险率为常数。事实上，由

d

F (t ) =λ(1-F (t )), F (0) =0

上式正好指数分布的分布函数。 dt

直接解得F (t ) =1-exp(-λt )

4.3(Poisson过程的和与差) 两个独立的Poisson 过程的和仍然是Poisson 过程，事实上，设N 1(t ) 和N 2(t ) 是两个独立的Poisson 过程，参数分别是λ1和λ2。则N 1(t ) +N 2(t ) 的母函数为

G N 1(t ) +N 2(t ) (z , t ) =E (z N 1(t ) +N 2(t ) ) =E (z N 1(t ) )(z N 2(t ) )

=G N 1(z , t ) G N 2(z , t ) =exp((λ1+λ2) t (z -1))

所以N 1(t ) +N 2(t ) 是参数λ1+λ2

的Poisson 过程。类似的结论可以拓广到n 个独立的Poisson 过程的和：

..., λn ，那么..., N n (t ) 是n 个独立的Poisson 过程，参数分别为λ1，如果N 1(t ) ，

N 1(t ) +... +N n (t ) 仍然是Poisson 过程，参数λ1+... +λn 。

考虑两个独立Poisson 过程差X (t ) =N 1-N 2。可以肯定，X (t ) 不是Poisson 过程，因为P (X (t ) 0，这与Poisson 过程的非负明显矛盾。计算X (t ) 的特征函数可以知道：

φN -N (j ω) =E (exp(j ω(N 1(t ) -N 2(t ))))

1

2

=E (exp(j ω(N 1(t ))) E (exp(-j ωN 2(t ))) =φN 1(t ) (j ω) φN 1(t ) (-j ω)

=exp(λ1t (exp(j ω) -1) +λ2t (exp(-j ω) -1)) =exp(λ1+λ2) t (P (j ω) -1)

λ2λ1+λ2

exp(-j ω)

这里P (j ω) =

λ1λ1+λ2

exp(j ω) +

所有X (t ) 是Poisson 过程，其中Poisson 过程参数λ1+λn ，随机变量Y k 服从两点分布：P (Y k =1) =

λ1λ1+λ2

, P (Y k =1) =

λ2λ1+λ2

4.4(事件分类)[0,t]内进入商店的顾客服从Poisson 过程，顾客有男有女之分。如果每次进入商店的顾客中，男顾客出现的概率为p ，女顾客出现的概率为q ，p +q =1那么每次进入想点的男顾客人数N m (t ) 有

N m (t ) =∑Y k

k =0N (t )

其中，Y k 为取值0,1独立同分布的随机变量，不妨设男顾

客出现时Y k 取1，

1

根据式φY (t ) (j ω) =G N (t ) (φY (t ) (j ω)) =exp(λt (φY (t ) (ω) -1))

得到φN m (t ) exp((j ω), t ) =exp(λt (φY (exp (j ω)) -1)

=exp(λt (p exp (j ω) +q -1) =exp(λpt (exp (j ω) -1)

可以看到，进入商店的男顾客

人数N m (t ) 服从参数为λp 的Poisson 过程。同理女顾客人数服从参数为

λq 的Poisson 过程。

4.6(散弹噪声分析) 电真空以及半导体中的噪声有很大一部分来源于“散弹效应”。单个电子在器件内渡越是会引起微小的窄脉冲电流，设该波形为i (t ) 。而阴极发射的电子数目服从Poisson 分布，大量电子的运动在电路中的总电流强度可以用过滤Poisson 过程进行近似。

Y (t ) =∑i (t -τk )

k =0N (t )

q 为电子所携带电荷量，τa 为电子在器件内的⎧2q

⎪2t , t ∈[0, τa ]

其中i (t ) =⎨τa

⎪⎩0, 其他

t

渡越时间。由式m Y (t ) =E (Y (t )) =λ⎰0h (t , τ) d τ, 设t >τa 得

m Y (t ) =λ⎰i (i -τ) d τ=λq , 如果设t , s >τa 由式C Y (t , s ) =λ⎰

0t

min(t , s ) 0

h (t , τ) h (s , t ) d τ可知

Y (t ) 的协方差函数为C Y (t , s ) =λ⎰

min(t , s )

i (t -τ) i (s -τ) d τ整理后得到

⎧4q 2⎛11⎫⎪λ4 τa (τa -(t -s )) 2-(τa -(t -s )) 3⎪

C Y (t , s ) =⎨τa ⎝26⎭, |t -s |≤τa 所以散弹效应所

⎪0, |t -s |>τa ⎩

引起的噪声电流是宽平稳的随机过程。

4.7(发射强度很大时的Gauss 近似) 过滤Poisson 过程的性质不仅仅受到滤波器冲击响应h 的影响，和标准Poisson 过程N (t ) 的强度λ也有

很大关系。现需要研究当λ→∞时，过滤Poisson 过程Y (t ) 的渐进形态，为此首先把Y (t ) 归一化。设m Y (t ) =E (Y (t )), σY (t ) =(Y (t )) , 令

η(t ) =

Y (t ) -m Y (t )

则E (η(t )) =0, Var (η(t )) =1。η(t ) 的特征函数满足

σY (t )

φη(t ) (ω) =exp -j

⎝

lg(φη(t ) (ω)) =-j

⎛

⎫⎛ω⎫

⎪取对数以后得到 m Y (t ) ⎪φY (t ) ⎪⎪σY (t ) ⎭⎝σY (t ) ⎭

ω

⎛ω⎫

⎪m Y (t ) +lg(φY (t ) ) ⎪σY (t ) ⎝σY (t ) ⎭

ω

=-j

ωσY (t ) ω

m Y (t ) +λ⎰(exp(j

t

ωσY (t )

t

h (t , τ) -1) d τ

t ω2

=-j m Y (t ) +j λ⎰h (t , τ) d τ-2λ⎰h 2(t , τ) d τ

σY (t ) σY (t ) 02σY (t ) 0

2ω⎛1⎫=-+o ⎪所以当λ→∞时有

2⎝⎭

ω2

lg(φη(t ) (ω)) →-

ω

2

也就是说φη(t ) (ω) →exp(-

ω2

2

)

所以当单位时间内出现的脉冲个数趋于无穷大时，归一化的过滤Poisson 过程的极限分布为Gauss 分布。

4.8(特烈：Poisson 过程) 如果某个更新过程的更新强度为

⎧λ, t ≥0

可以利用更新方程式来计算时间间隔的概率分布，由式λN (t ) =⎨

⎩0,

t

f T (t ) =λN (t ) -⎰λN (t -τ) f T (τ) d τ得f T (t ) =

d

F T (t ) =λ(1-F (t )) 立刻得 dt

F (t ) =1-exp(-λt ) 恰好说明分布函数就是指数分布。

4.

7.6(周期性) 状态i 的周期d i 是集合T i ={n :P ii (n ) >0}的最大公约数，即

(n ) d i =gcd{n :P >0}如果d 1=1, 就状态i 非周期的。如果d i >1，则称状态i ii

为周期态。

7.10(两个状态的Markov 链) 设离散时间Markov 链的样本空间只有两个状态，这种连接在现实生活中十分常见。比如天气预报问题，吧晴天和阴天作为(0,1)两种样本状态，可以通过构造Markov 链来研究天气在两种状态之间的统计规律。两个状态Markov 链的一步转移概率

1-α

为2*2的随机矩阵，为P =(

α

1-β

β

要得到n 步) 其中α，β∈[0, 1]。

转移概率，需要计算P n 。可以利用特征分解吧矩阵对角化一简化矩阵乘幂的计算。以上矩阵为列，设其两个特征值不同，则可以找到2*2的矩阵Q ，使得P =Q (

λ0

λ1

) Q -1其中λ0，λ1非标是矩阵P 的两个特征值，

n

矩阵Q 的列分别是对应于λ0，λ1的特征向量。从而有P =Q (

λn 0

λ1

-1

) Q n

只需要具体求出P 的特征向量就可以完成P n 的计算。P 的特征值是下

t -λI ) =0其中I 是单位矩阵。于是列特征方程的解d e (P

(1-α-λ)(1-β-λ) -αβ=0得到的两个解是λ0=1，λ1=1-α-β-因

1α

) 且有 α>0, β>0, 所以λ0≠λ1，进而得到Q =(1βQ -1=

1β

(α+β1

) 所以 -1

α

P n =

0β11α1

()()(α+β1β0(1-α-β) n 11βα(1-α-β) α) =() +(-1α+ββα-βα+β

n

α-α

)

β

如果

|1-α-β|

1βα

() 即当时间n 趋于无穷大时，

α+ββα

N 步咋混一概率存在极限，即

lim

n →∞

(n ) (n ) P 00=lim P 10=

n →∞

βα+β

和

lim

n →∞

(n ) (n )

P 11=lim P 01=

n →∞

αα+β

抓你概率极限与初始状态无关，如果

时转移概率为

|1-α-β|=1，必然有α+β=2，即α=β=1，此

01P =() 链从一个状态转移到另一个状态，随机性消失，过程具有很强的周期性，

10

正是这种周期导致你步转移概率在n →∞时不存在极限。 7.11设有三个状态{0,1，2}的Markov 链，一步转移矩阵为

121(2

1

02

1111

) 有于P 01=>0, 所以0→1。而P 12=>0，故1→2，导致0→1→2

2444

120

3311P 21=>0和P =>0得到2→1→0，所以该链所以状态都相通，是不可约的。 10

32

状态图

7.12设有四个状态{0，1，2，3}的Markov 链，一步转移概率为

121(2120

1212120

00120

00121

) 状态如下所示，状态3是吸收态。状态0，1相互可达，

但是两者都无法到达状态2。所以该链有两个闭集{3}和{0,1}。状态

2可以到达其他状态，而无法从其他状态到达状态

2.

不可约链的一步转移矩阵具有明显的特征，即不可能通过初等行列置换得到如下形式：

（

D B

其中C 是方阵。如果链还可约的，那么一定可以同初等行列）0C

D B

吧一步转移矩阵变换为式的形式，子 阵C 本身就是随机矩阵。 （）

0C

进一步证明，任何一个Markov 链的转移概率矩阵通过适当行列置换

P 10

可以化为如下的一般形式：P =(

0R 1

0P 2

00

00

) 其中P ....., P m 分别是1，0Q

0 P m R 2 R m

不可约的闭子集的转移矩阵，且相应于Q 的状态不存在不可约的闭子集。

7.14(两个状态的周期性) 最简单也是基本的两个状态周期链{0,1}具有如下形式的一步转移矩阵：P =(期2。

01

) 其状态转移图如下所示，该链周10

如果周期i 具有周期d i ，并不是说对于任何的

正整数k ，都有P ii (kd ) >0。当k 充分大后，这一论断成立。

i

可以证明，相同的状态具有相同的周期性，即周期性的类性质。设

i ⇔j , i 和j 的周期分别为d i 和d j ，则

∃m , n , k , 使得P ii

(m +kd j +n )

>P ij (m ) P jj

(kd j )

(n )

P ji >0⇒d i |m +kd i +n

(m +(k +1) d i +n ) (m ) ((k +1) d i ) (n )

P >P P ji >0⇒d i |m +(k +1) d i +n ii ij P jj

所以d j |d i , 同理可证明 d j |d i ，因此d i =d j 。

利用周期性，可以对Markov 链中的状态从周期的角度进行分类。为方便起见，只讨论不可约链的情况，，此时各个状态周期d 都相同。状态空间为E ，整条链呈现出从一组状态向另一组状态转移的循环往复的特征。选状态i 0，引入如下子类。

) C 0={j ∈E , P i 0(n j >0, n ≡0(modd )}) C 1={j ∈E , P i 0(n j >0, n ≡1(modd )}

) C d -1={j ∈E , P i 0(n j >0, n ≡d -1(modd )}

很明显E =C 0⋃C 1⋃... ⋃C d -1

上面给出的子类的表示方法说明了链的转移很规律，当0≤k ≤d -1时，从子类C k 转移到C k +1，然后从子类为说明上述分析的正确性，只C d -1回到C 0。需验证如果

(a )

i ∈C p ，P ，则j ∈C p +1。由于P a =kd +p , 进而有a +1=kd +p +1，ij >0i 0i >0, 所以

而

a +1a

P i 0i ≥P i 0i ≥P ii >0, 结论是自然的，如下图

7.14（不可约周期性链的转移矩阵）上面的结果如果从转移矩阵的角度出发可以看得更清楚。通过适当的行列置换，周期为d 且不可约的Markov 链的一步转移概率矩阵可以写成如下形式

00P =(

0A d 1

A 120 00

0 A 23 00

00

) 自行计算P 2，P 3,...., 体会其变化规律。

A d -1, d

7.15(一维无限制随机游动) 研究一维无限制随机游动中个状态的性质。链中质点向右和向左的概率分别为p 和1-p 。该状态所以状态都相通，故各个状态具有相同的性质。因而只需要讨论0状态。经你步从0转移的概率为

(n )

P 00

2k

∞() p k (1-p ) k , n =2k

={k 由∑n =1P ii (n ) =∞可知，0状态十分具有常返性决

0, n =2k -1

∞

∞2k k (2k )! k k

定于下列级数是否收敛，即∑() p (1-p ) =∑(p (1-p ) k ) 为分析

k =1k k =1k ! k !

该级数的收敛性，引入Stirling 公式n ! 2πn () n , n →∞则有：

(2k k

) p k (1-p ) k

22k (

2k 2k

)

[4p (2-p )]k k k （其中 是˷） p (1-p ) =

k 2k k 2πk () e

n e

∞

[4p (1-p )]k 1

如果p=1/2，级数∑发散，吃屎0状态是 常返状态。 ∑

k k k =1k =1

∞

如果p ≠1/2, 4p =(1-p ) =a

∞

[4p (1-p )]k a k

∑0状态是滑过态。∑k k =1k =1k ∞

7.16(二维随机无限制“平衡”时的随机游动) 现在讨论二维平面上随机游动的各状态性质，质点的位置是平面上坐标为整数点，每个一点代表一个状态，每一个状态有上下左右四个相邻状态，质点的每一次转移都以一定的概率转移到四个相邻状态之一。故平面上的随机游动也是不可约的。根据一维随机游动的结论，只讨论“平衡”的情况，此时向上下左右运动的概率完全相同，均为1/4。由于链不可约，所以仍然只研究(0,0)状态，入下图所示。主要到奇数步不可能返回，所以只考虑偶数步从（0,0）转移到(0,0)的概率。

P

2n

00, 00

(2n )! 12n 12n 2n n n n

=∑() =() （）()() ∑n k n -k k ! k ! (n -k )! (n -k )! 44k =1k =1

∞

n

根据有关组合的恒等式∑()(

k =0

n n

k n -k

) =(

2n

12n 2n 2(2n )

) 得到P 00=() () ，00n n 2

使用Stirling 公式

P

(2n )

00，00

12n 4n 21

() () =位发散级数。4n πn π

∑P

k =1

∞

(2n )

00, 00

∑

1k =1n π

∞

得到二维无限制“平衡”是随机游动是常返的。

7.17设有四个状态{0，1，2，3}的Markov 链，其一步转移矩阵为

00(

100101

1200012

0) 有图知，00

该链所以状态图都

相通，是不可约链，所以状态都是常返的。

7.18设有5个状态{0,1,2,3,4}的Markov 链，其一步转移矩阵为

1212(

0014

12120014

0012120

0012120

000) 012

由图知{0,1}和{2,3}是两个闭

真子集，子集内状态彼此相通，所以状态{0,1,2,3}均常返。而状态4位非常返。

7.19(一维无限制随机游动) 已经知道当p =时，一维无限制随机游动是常返的，现在进一步研究其是否为正常返。由于链中有无穷多个相通状态，所以尽管链是不可约的，也无法对它是否正常返值直接做判

(n )

断。因此所限计算以P 00为系数的幂级数（列7.15）。利用负二项式定

1

2

理，有。

P (z ) =∑P

k =0∞

(2k ) 2k 00

z

-1

1n -1(2k )! z 2k 22

(1-z ) A (z ) =∑() =(1-z ) 利用式lim ∑a k =lim -n →∞z →1n k =0k =0k ! k ! 2∞

-1

1n -1(2k )

得到lim ∑P 00=lim (1-z ) P (z ) =lim (1-z )(1-z 2) 2=0所以μ0=∞，从而可--n →∞n z →1z →1

k =0

知0状态是零常返的，进而得到一维无限制随机游动的所有状态为零常返。

7.20(正常返，但转移概率无极限) 这个列子在讨论周期性时提过。这链有两个状态{0,1}，一步转移矩阵为P =(

P

(n ) 00

0110

) 容易看出

=P

(n ) 11

⎧1, n =2k 1n -1(n ) 1

所以有lim 很明显该链为正常返，且平P =⎨∑11=n →∞n 20, n =2k -1k =0⎩

(n ) (n )

P 00和lim P 均返回时间为2, 。可是另一方面，lim 11都不存在极限。这n →∞n →∞

说明几遍是正常返的链，其n 步转移概率的极限仍然可能不存在。 7.21(无穷多个平稳分布) 设Markov 链有四个状态{1,2,3,4}，其一步转

0100

1000

) 则有两个不可约正常返的闭真子集，{1,2}

00010010

移概率矩阵为(

和{3,4}。该链的平稳分布为(, , , ), α, β≥0, α+β=1所以平稳分布

2222

ααββ

有无穷多个。

7.22(双随机转移矩阵) πi =1

7.23(Ehrenfest模型)Ehrenfest 买模型的状态空间{0, 1, 2,..., M }是有限集

⎛0 1 M

合，其一步转移矩阵为

⎝

102M

M -1M 03M

0M -1M

2M 01

⎫⎪⎪⎪⎪⎪⎪

⎪很明星该模⎪⎪⎪1⎪⎪M ⎪0⎭

型是不可约的，且状态有限，所以所有状态都正常返。状态转移如图所示

现求它的平稳分布。

1π1M

i -1i +1

πi =(1-) πi -1+πi +1, i =1, 2,.., M -1

M M 1

πM =πM -1

M

π0=

M M

⎛M ⎫⎛M ⎫1M

⎪ ⎪可以求得πi = 所以 ππ=π=π2⇒π=∑∑i 000M i ⎪0 i ⎪2i =0i =0⎝⎝⎭⎭

平稳分布为πi = i ⎪⎪2M , I =1, 2,... M ⎝⎭零状态的平均返回时间μ0，有平稳分布得到π0=

⎛M ⎫1

111M

=⇒μ==2 0M 2μ0π0

7.24(带有一个反射壁的一维随机游动) 设带一个反射壁的随机游动状

⎛q q

态空间为{0, 1, 2,...}，0为反射壁，其一步转移矩阵为P = 0

⎝

p 0q 0p 0 00p

⎫⎪ ⎪

⎪ ⎪ ⎪⎭

很明显该链是不可约的，状态转移如图所示，现求其平衡方程式π=πP

π0=q π0+π1⎛p ⎫

的解π={π0, π1,...}由此得到πj = q ⎪⎪π0 πj =p πj -1+q πj +1, j ≥1⎝⎭

⎛p ⎫所以，要让π成为分布，必须满足∑πj =π0∑ q ⎪⎪=1话句话说，需要 j =0j =0⎝⎭

∞

∞

j

j

⎛p ⎫ ∑ q ⎪⎪

∞

j

如果p

⎛p p ⎫⎛p ⎫

⎪ ⎪π

0=1-, πj = 1-, j ≥1 ⎪ ⎪q ⎝q ⎭⎝q ⎭

j

7.25定理(带一个反射壁的一维随机游动) 正如在7.24中所提到过得，利用平稳方程无法判断该链的正常性。所以利用定理7.9(常返性判据

1-p n -2q k

Ⅱ) ，有y 1=py 2，y k =py k +1+qy k -1, k =2, 3,..... 解得y n =(∑() +1) y 1可p k =0p

q q

见该方程具有非零有界解得充分必要条件是∑()

p k =0p

∞

k

因此当q

。

7.26(一维无限制的随机游动) 本列采用定理7.9研究7.15中给定的随机游动，列7.15中给出的方法涉及诸如String 公式等复杂的分析工

1

2

12

12

具。现在用定理7.9重新分析该问题。划去0状态所有对应的行和列，有y 1=py 2, y k =py k +1+py k -1, k =2, 3,... ，

p n -2q k

y -1=qy y -2, y k =py k +1qy k -1, k =-2, -3,.... 得到y n =(∑() +1) y 1, n =2, 3,....

q k =0p p n -2p k

是上述方程没有非零有界解得y -n =(∑() +1) y -1, n =2, 3,.... 不难看出，

q k =0q

∞

q k p

充分不要条件是∑() =∞, 且∑() k =∞所以只有当p =q 时，否则一定

k =0p k =0q

∞

常返。

7.27(首次返回时间)Markov 链中最典型也是最重要的停时时首次返回时间，也就是从状态i 出发首次返回i 的时间，即 T i =inf{n :X n =i |X 0=i }如果X n ≠i , ∀n , 那么T i ={∞}。

7.28(首次击中时间) 另外一个重要停时是Markov 链首次到达状态空间返回时间的某个子集A 的时间T A , 称为首次击中时间

T A =inf{n :X n ∈A }很明显

{ω：T A (ω) =n}={ω:X 0(ω) ∈A,..., X n -1(ω) ∈A, X n (ω) ∈A}

7.29(停时的延迟) 如果τ是停时，n 0是确定整数，那么τ+n 0也是停时，因为事件{τ+n 0=m}等价于事件{τ=m -n 0}，而根据停时定义，事件

{τ=m -n 0}仅依赖于{X 0, X 1,..., X m -n 0}，因此是停时。也就是说，停时确

定性延迟还是停时。

7.30(停时反列Ⅰ) 设{X n }为Markov 链，i 为该链的一个状态，对随机时间τ做如下定义：

τ=inf{n ≥0:X n -1=i }则τ不是停时，因为事件{τ=n}和X n +1有关，不是有

{X 0, X 1,.... X n }决定。

7.30(停时反列Ⅱ) 设{X n }为Markov 链，i 为该链的一个状态，对随机时间τ做如下定义：

不仅τ=sup{n ≥0:X n =i }则τ不是停时，因为事件{τ=n}和{Xk }∞k =n +1有关，仅有{τ=n}和{Xk }∞k =0所决定。

7.32(赌徒输光问题) 两个赌徒甲、乙入赌场进行一些赌博。令A 为甲的原始读本，每次读本输赢的概率相同，赌注为1. 假设甲手中的赌术到达B 时，即认为自己到达了赚钱的目的，会离开赌场，那么在他达到赚钱目的之前，有多大的肯会把手中的赌本全部输光？该问题称为赌徒输光问题。

设X 0是甲在起始时刻的赌本，每次下注的结果为X k ，第n 时刻甲手中的赌本为{S n }，高过程具有两个吸收壁(0和B) 的唯一对称随机游动，即S n =∑X k +X 0这里P (X i =1) =P (X i =-1) =, i =1, 2,... 于是赌徒输光问题

k =0n

1

2

就变成了过程{Sn }在到达B 之前到达0的概率有多大。这个问题可以使用Wald 等式解决。

设T =inf{n :S n 或S n =B }很显然T 是过程{Xk }的停时。由Wald 等式，得到

(-A ) P (S T =0) +(B -A ) P (S T =B ) =E (∑X k ) =E (T ) E (X 1) =0

k =1T

且有P (S T =0) +P (S T =B ) =1，所以有P (S T =B ) =, P (S T =0) =

A

B B -A

。 B

7.33(首达时间的计算) 考虑一维无限制随机游动，向右和向左的概率分别为p 和q =1-p ，设X 0=1, 现在通过母函数来计算从1出发到达0所用时间的概率分布。令T 0=inf{n :X n =0|X 0=1}则T 0分布的母函数为

G (z ) =E (z T 0|X 0=1) =pE (z T 0|X 1=2, X 0=1) +qE (z T 0|X 1=0，X 0=1)

=

pzE (z 0|X 1=2, X 0=1) +qE (z |X 1=2, X 0=1) 这里T 0是首次到达2之后，继

续转移并首次到达0所用的时间。由于首次到达2的时间是停时，有强

Markov

性得到

E (z T 0|X 1=2, X 0=1) =E (z T 0|X 1=2)

所以

~

G (z ) =pzE (z T 0|X 1=2) +qz 由于T 0=T 1+T 0，其中T 1是达到2后，继续转移

并首次到达1的时间：T 0是到达1后，继续转移并首次到达0所需的时间。再次使用强Markov 性，有

E (z |X 1=2) E (z |X T 1=1) =G 2(z ) 因此G (z ) =pzG 2(z ) +qz

T 1

~T 0

~

进而有

1--4pqz 2

G (z ) =

2pz

其中，G (z ) 为T 0的母函数。通过Taylor 展开可以得到T 0的分布，同时

⎧∞, p ≥q

d ⎪G (z ) =⎨1还可以得到T 0的均值，即E (T 0|X 0=1) =lim , p

⎪⎩q -p

7.34(更新时刻) 考虑Markov 链{X n }∞n =0，设T 0=0，且X 0=i ，令

T k =inf{n >T k -1:X n =i },k =1, 2,.... T k 代表是从状态i 出发后，第k 次到达状

态i 的时间。鱼鱼{T k =m }仅决定于{X n }∞n =0，所以T k 是停时。设

τk =T k -T k -1，则得到随机序列{τ1, τ2,...}，且有

P (τk =s k |τk -1=s k -1,..., τ1=s 1) =P (X T k =i , X T k -1+m ≠i , 0

根据Markov 性，在X T k -1=i B ={τk -1=s k -1,... τ, 1=s 1}是T k -1前所发生的事件。

的条件下，B 和T k -1后发生的事件τk =s k 相互独立，所以

P (τk =s k |τk -1=s k -1,..., τ1=s 1) =(X T k =i , X T k -1+m ≠i , 0

Markov 性，得到P (X T =i , X T

k

k -1+m

≠i , 0

=P (X T k -1+τk =i , X T k -1+m ≠i , 0

(s )

所以{τk }∞是独立同分布的随机序列，满足习惯上称时P (τ=s ) =f k =1k ii 。

刻{T k }为相应状态i 的更新时刻。

7.35设Markov 链的状态空间为{1,2,3,4,5,6},其一步转移概率矩阵为

⎛ 0 1 3 0 0 0 1 ⎝4

120120014

01301300

001201214

00013014

1⎫⎪2⎪1⎪3⎪⎪0⎪

该链是不可约且非周期的，其平稳分布π⎪很明显，1⎪

3⎪1⎪2⎪⎪0⎪⎭

为

所以该为可π= ⎪可以直接验证πi P ij =πj P ji , ∀i , j ∈E 成立。逆Markov 链。

并不是所有在平稳分布的Markov 链都是可逆的。如状态空间(1,2,3)

⎛1

2

的Markov 链，具有如下转移矩阵 0

1 ⎝2

⎫0⎪⎪1⎪

很明显，该链是不可约且2⎪1⎪0⎪

2⎭1111

状态有限，是正常返且存在平稳分布π=(, , ) 但是π1P 12-π2P 21=≠0

3336

1212

⎛131311⎫⎝81681684⎭

所以该链是不可逆的。

7.36利用细致平衡方程求解7.35，得到

π1

2

==

π2

3

π2

3

==

π3

2

π4

3

==

π3

2

π5

2

==

π4

3

π1

2

π6

4

π2

3

π6

4

π4

3

π6

4

π5

2

π6

4

131311⎫

立刻得到分布π为π=⎛ ⎪所以链是可逆的，且平稳分布

⎝81681684⎭

为π。

7.37(Ehrenfest模型) 该模型的一步转移矩阵如式

1⎛⎫ 0⎪

M ⎪1M -1 ⎪0 M ⎪M ⎪2

0 ⎪M ⎪

3 ⎪所示，可以得到如下关系

⎪M

1 ⎪

0 ⎪M

M -11⎪ ⎪0

M M ⎪ 10⎪⎝⎭

M -1i i -1M -(i -1) i -1πi (+) =(1-i ) πi -1+πi 即πi -1=πi , 0≤i ≤M

M M M M M

所以该模型是可逆。因此求解细致平衡方程

M π01

M -(i -1) M (M -1)...(M -(i -1)) πi =πi -1=... =π0

i M (M -1)... 2⋅1

π1=

⎛M ⎫

= i ⎪⎪π0, 1≤i ≤M ⎝⎭

得到π0=

⎛M ⎫11

⎪ π=, 1≤i ≤M i M M ⎪2⎝i ⎭2

7.38(整数值生灭过程) 设Markov 链的状态空间为整数集Z ，一步转移高了为

⎧p i , j =i +1⎪

P ij =⎨q i , j =i -1其细致平衡方程为

⎪0, 其他⎩

πi p i =πi +1q i +1

i

p i p

故πi +1=πi =... =π0∏k , i ≥0

q i +1k =0q k +1-1q i +1q πi =πi +1=... =π0∏k +! , i

p i k =i p k

p k -∞-1q k +1

由此知道，如果1+∑∏+∑∏

i =0k =0q k +1i =-1k =i p k

∞

i

该链可逆，否则不可逆。如果转移概率满足p i =p , q i =q 那么该链就退化成了一维无限制随机游动，此时一定不可逆，不能使用细致平衡方程来求解平稳分布。

7.39(带反射壁的整数值生灭过程) 吧列7.38中抓住哪个台0改为反射

⎧q 0, i =0, j =0

⎪p , i =0j =1

0⎪⎪

壁，于是得到新的一步转移概率P ij =⎨p i , i >0, j =i +1其细致平衡方程为

⎪q , i >0j =i -1⎪i ⎪0, 其他⎩

πi p i =πi +1q i +1, i ≥0

很明显，如果p i =p , q i =q , 当p

所以πi +1=π0∏, i ≥0

q k =0k +1

i

的。有于p

7.40(带反射壁的整数值生灭过程) 把列7.16已就“平衡”情况讨论了二维无限制随机游动的常返性，现在利用细致平衡方程讨论该链的可逆性，并讨论平稳分布{π(m , n ) }的存在性。其一步转移概率为

⎧a , (k , l ) =(1, 0), (0, 1), (0, 1)

P (i , j )(i +k , j +l ) =⎨k , l

⎩0, (k , l ) 为其他整值

选择(0,0)作为基点，二维空间上任何一点(m,n)都可以找到一条路径和(0,0)

相

通

。

不

妨

设

m , n ≥0

, 则路径为

(m , n ) →(m -1, n ) →... →(0, n ) →(0, n -1) →... →(0, 0)

对于其他情况，可以构造出相应的路径。利用细致平衡方程，得到

π(m , n )

⎛a 1, 0⎫⎛a ⎫

⎪π(m -1, n ) =... = 1, 0⎪π(0, n ) = a ⎪ a ⎪⎝-1, 0⎭⎝-1, 0⎭⎛a 1, 0⎫

⎪= a ⎪⎝-1, 0⎭

m

m

⎛a 1, 0⎫⎛a 0, 1⎫

⎪ ⎪ a ⎪π(0, n -1) =... = a ⎪

-1⎭⎝0，⎝-1, 0⎭

m

⎛a 0, 1⎫

a ⎪⎪π(0, 0)

-1⎭⎝0，

n

同理可得

π(-m , n )

⎛a -1, 0⎫⎛a ⎫

⎪π(-m +1, n ) =... = -1, 0⎪π(0, n ) = a ⎪ a ⎪⎝1, 0⎭⎝1, 0⎭⎛a -1, 0⎫

⎪= a ⎪⎝1, 0⎭

m

m

⎛a 0, 1⎫⎛a ⎫ ⎪π(0, n -1) =... = -1, 0⎪ a ⎪ a ⎪⎝0, -1⎭⎝1, 0⎭

m

⎛a 0, 1⎫

⎪

a ⎪π(0, 0) ⎝0, -1⎭

n

π(m , -n )

⎛a 1, 0⎫⎛a 1, 0⎫ ⎪⎪π(0, -n ) = π(m -1, -n ) =... = ⎪ ⎪⎝a -1, 0⎭⎝a -1, 0⎭⎛a 1, 0⎫

⎪= a ⎪⎝-1, 0⎭

m

m

⎛a 0, -1⎫⎛a ⎫ ⎪π(0, -n +1) =... = 1, 0⎪ a ⎪ a ⎪⎝0, -1⎭⎝-1, 0⎭

m

m

⎛a 0, -1⎫

⎪

a ⎪π(0, 0) ⎝0, 1⎭

n

π(-m , -n )

⎛a -1, 0⎫⎛a -1, 0⎫ ⎪⎪π(0, -n ) = π(-m +1, n ) =... = ⎪ ⎪⎝a 1, 0⎭⎝a 1, 0⎭⎛a -1, 0⎫

⎪= a ⎪⎝1, 0⎭

m

⎛a 0, -1⎫⎛a ⎫ ⎪π(0, n -1) =... = -1, 0⎪ a ⎪ a ⎪⎝0, 1⎭⎝1, 0⎭

∞

m

⎛a 0, -1⎫

⎪

a ⎪π(0, 0) ⎝0, 1⎭

n

⎛⎛a ⎫m ⎛a ⎫m ⎫∞⎛⎛a ⎫n ⎛a ⎫n ⎫

1, 0⎪+ -1, 0⎪⎪∑ 0, 1⎪+ 0, -1⎪⎪

⎪ a ⎪⎪n =0 a ⎪ a ⎪⎪ m =0⎝a -1, 0⎭⎝1, 0⎭⎭⎝⎝0, -1⎭⎝0, 1⎭⎭⎝

这个条件是无法到达的，所以该链不可逆。事实上，当

a 1, 0=a 0, 1=a -1, 0=a 0, -1时，二维无限制“平衡”的随机游动的所有状态都

是零常返，平稳分布不存在：其他情况下，所有状态均为非常返态，

平稳分布同样不存在。和一位情形相似，如果设x 轴和y 轴为反射壁，限制质点在第一象限运动，那么可逆条件为

⎛a 1, 0⎫ ⎪∑ ⎪m =0⎝a -1, 0⎭

∞

m

⎛a 0, 1⎫

⎪∞

n

此时平稳分布为

π(m , n )

⎛a 1, 0⎫

⎪= a ⎪⎝-1, 0⎭

m

⎛a 0, 1⎫ ⎪ a ⎪⎝0, -1⎭

n

⎛a ⎫ 1-1, 0⎪ a ⎪

-1, 0⎭⎝

-1

⎛a ⎫

1-0, 1⎪ a ⎪

0, -1⎭⎝

-1

7.41设有离散分支过程，群体中单个个体繁殖下一代的数目如下分布

则个体繁殖下一代数目的均值值m X 为

13117

m X =1⨯+2⨯+3⨯=>0

2161616

1131

母函数G (z ) =+z +z 2+z 3求解G (z ) =z ，得到

421616

(z -1)(z 2+4z -4) =0⇒z 1=1, z 2=-2+22, z 3=-2-22最小正根(灭种概

率) 22-1）=0. 828如果调整下一代个体繁殖数目的概率取值，可以得到表所示的结果

有表可知，通过改变个体繁殖数目的统计特性，可以调整其均值并而

影响群体的灭种概率。当m X ≤1时，群体必然灭种；而当m X >1时，增大m X 可以改变母函数G (z ) 的形状，从而灭种概率想笑的方向发展。 7.43(有限个非常返态) 如果Markov 链中非常返态的数目有限，则其一

⎛D n ⎛D 0⎫n 步转移矩阵可以写成P = B Q ⎪⎪可知P = *

⎝⎭⎝

0⎫

⎪由式7-74(如果状态n ⎪Q ⎭

j 非常返，那么∀i 即P ij (n ) →0, n →∞) ，对于非常态j 有P ij (n ) →0, n →∞，

v (n ) =lim Q n I A =0A 也就是说，如果所以Q n →0, n →∞，由此得到v =lim

n →∞n →∞

非常返态数目有限，则在非常返态中无限逗留的概率是0。这和直观非常一致。

列7.44(带有一个反射壁的一维随机游动) 列7.25中已经讨论了带一个反射壁的随机游动的常返性，使用的工具定理是7.9。这里从另外一个角度，利用“从状态i 出发永不访问0状态的概率v i >0”以说明当

p >q 时

0状态为非常，从而该链所有状态均为非常返。

选定A=N,解方程v =Qv 得到

1q

v 1=(1+) v 1p p 1q q v 3=(v 2-qv 1) =v 1(1++() 2)

p p p v 2=q

v i =∑() k

k =1p

i -1

鉴于0≤v i ≤1,

q q v 1∑() k ≤1→v 1≤1-

p k =0p

q q

从而得到v i ≤1-() i 其实只要p p

∞

由于v 是方程v =Qv 的最大解，所有v 1=1-有

v 1>0就可以说明0状态非常返了

7.45(设备维修问题) 考虑7.7中设备维修问题，该链的一步转移矩阵为

⎛a 0 a 0P = 0

0 ⎝

a 1a 1a 00

a 2a 2a 1a 0

a 3 ⎫

⎪a 3 ⎪

a 2 ⎪其中{a i , i ≥0}代表每天机器失效数目的概率分

⎪a 1 ⎪

⎪ ⎭

布，如果a 0a 1a 2>0，则该链是不可约的。

在状态空间中任取状态i ，考虑A i ={i , i +1,...}，对于任意的i , i ≥1, A i 对应

⎛a 1

a 0

得转移矩阵都是相同的，Q = 0

⎝

a 2a 1a 0

a 3 ⎫

⎪a 2 ⎪

所以对于方程v =Qv ，满⎪a 1 ⎪⎪ ⎭

足0≤v ≤I A 的最大完全解完全一样。换句话说，不同的A i 相应的无限逗留概率没有区别。

对于而言，v i =P (X n ≥1, n ≥1|X 0≥i ) 是从状态i 出发永不访问状态0的概率。而对于A i , v 1=P (X n ≥i , n ≥1|X 0≥i ) 是从状态i 出发永不访问子集

{0, 1, 2,..., i -1}的概率由于访问{0, 1, 2,..., i -1}必然经过状态i -1，所以v 1也就

是永不访问状态i -1的概率。要想从i 出发达到0状态，必须搜西安从然后再从i -1状态到达0状态。于是有如下i 站在哪个台到达i -1状态，

递推关系1-v i =(1-v 1)(1-v i -1) 设v 1=1-β, 对上式递推可以得到v i =1-βi 为了得到确定β，回到方程v =Qv ，由第一行得带v 1=a 1v 1+a 2v 2+a 3v 3... 从而有1-β=a 1(1-β) +a 2(1-β2) +a 3(1-β3) +...

由于{a}是概率分布，所以有β=a 0+a 1β+a 2β+... =∑a k βk =G (β) 函

∞

k k =0

2

k =0∞

数G (β) 是相应于概率分布{ak }∞。。。。。。未完 k =0的母函数。

7.46设Markov 链的状态空间为{1, 2,.. 7, }一步转移矩阵为

⎛0. 50. 5⎫ ⎪0. 80. 2 ⎪ ⎪00. 40. 6 ⎪P = 100⎪计算从状态出发，被各个常返类吸 ⎪100 ⎪ 0. 100. 20. 10. 20. 30. 1⎪ ⎪0. 10. 10. 100. 10. 20. 4⎝⎭

收的概率。

7}, 且有 该链有两个常返类R 1={1，2},R 2={3，4，5}非常返类为T ={6，

⎛00. 40. 6⎫

⎪⎛0. 50. 1⎫

P 0⎪, ⎛0. 10⎫⎛0. 20. 10. 2⎫ 1= 0. 20. 4⎪⎪，P 2= 10

⎝⎭ 10⎪B 1= 0. 10. 1⎪⎪，B 2= 0. 100. 1⎪⎪0⎝⎭⎝⎭⎝⎭

⎛0. 30. 1⎫⎛1⎫⎛0. 1⎫将R 1, R 2简并后，得到Q = 0. 20. 4⎪⎪, b 1=B 1 1⎪⎪= 0. 2⎪⎪

⎝⎭⎝⎭⎝⎭

⎛1⎫

⎪⎛0. 5⎫⎛10

⎪b 2=B 2 1⎪= 0. 2⎪

1⎪⎝⎭此时一步转移矩阵变成了P = 01⎝⎭ b b

⎝12

0⎫⎪0⎪ Q ⎪⎭

利用L

(∞)

k

⎛0. 2⎫⎛0. 8⎫-1-1 ⎪ (I -Q ) b =，(I -Q ) b ==∑Q b k =(I -Q ) b k ，有12 0. 4⎪ 0. 6⎪⎪ ⎝⎭⎝⎭m =0

∞

m

-1

所以状态6出发，被R 1吸收的概率为 0. 2，被R 2吸收的概率为0. 8。第八章