随机过程课件(十)

Markov链的其他议题

一、停时与强马氏性

问题的提出：给定“过去"和''现在"，要确定将来的状态，只需

知道'现在'就足够了。如果“现在”是一个随机的时间，Markov性

是否仍然成立？

什么是随机时间？

Markov性是否对所有的随机时间都成立

■停时的定义

设｛匕，〃=0,1,2｝是一个定义在概率空间(Q,£P)上的具有可

数状态空间的随机过程，(Q,£P)上的广义随机变量7称为一个停时,

如果

(1)r只取非负整数值；

(2)对每个非负整数m,事件｛④4⑼工训完全由看,，工确定。

例子

■首达时：

ry(M=inf{〃2O/?(w)=y}

如果力使得对所有的n,匕wy,则取和(0)=8。因为

m

{金<〃z}=U®工3)=处

/7=0

因此却是一个停时。

■r次首达时：

7⑴㈤=inf{〃21,工(卬)=y}

(r)(r-1)

r(d>)=inf{n>T(d>),Yn(w)=y}/=2,3，…

且规定对空集取极小为oo,则{1<m}等价于匕…，工至少有r个等

于y,因此工⑺是停时

练习：判断下面的随机时间是停时

q(G)=inf{〃NO,4(w)”}

r/A(^)=sup{n>O,Yn(w)eA]

■强马氏性

对于停时r,定义X；=｛Xi;〃=0,1,2,...)

定理：每个Markov链｛Xn,n=0,1,2｝都有强markov性，即，对每

个停时r,给定直到时刻r的过去，r之后的随机过程

*；=｛乂小;〃=0/2..・｝在7<8上的条件分布为不，即在储=切上

p(x小=X,,*=jn\X。=i0,…,X,”=0

=P(Xm+tt=jl,-,Xm+ln=jii\Xm=im)

用条件期望的语言来描述

P{X5=3X^=3，XM=，〃|X°，X，…XJ

=P{X5=i。,Xr+”=・X=i〃IX/

Px,{X[°=io，X,

三尸,，X,ln=i〃n}

二、Markov链的大数定律和中心极限定理

设f是状态空间S上的实值函数，定义

k=U

设司)表示过程第r次到达状态j的时间，定义

*+1)

z、=£/(Xk),r=0,l,2,・・.

定义M=max{r>0:4”《川

则

JI)z产〃+“

C1Ti1Nn1Tj

j=-—Zf(Xk)

n〃&=0〃r=l〃k="+l

可以证明，当nf8时:第1项和第3项将趋于零，因此

rS〃Nn1弋7

…nnNn窗

1、无论｛X〃,〃=0,l,2,…｝的初始分布如何，随机变量Z1,Z2,…独立同分

1%

布，因此lim—VZ=EZo

2、如果£(zf)—寸))<00,我们有

(N〃+l)_⑴

lim-----------=E(H2)一婷))

〃78NJJ

因为吁弓弓）,所以

石（工，）-工「）

lim—=3

gooN〃J

等式的右端是返回状态j的平均时间（=与（可））），等式左端的倒数是

单位时间内返回n的平均次数。若定义

兀,—Ej（球）=—

勺

则可以证明｛与"eS是不变分布

定理：设｛X｝为不可约的，正常返的Markov链，无论初始分布）（）如何,

若不变分布〃满足心（|/（Xj|）voo,则

lim-Y/(X,)=a.s.

〃-8n/=Iies

若记〃="U（X。）），用了=/一〃代替f'并记

nn

鼠=Z7（x,〃）=Z（/（x〃AM

f（r+D

Zr=£f（x）r=o,l,2一.

A=¥+I

则_「

马②尸印率以出人正。，〃=。，12…

于是名/=0,：2,...｝是独立同分布序列，零均值并具有有限方差'

则可以证明Markov链的中心极限定理成立，即

1_

~j=S〃—>N（0,b9）

yjn

其中。2=丫叫（/（匕））。

具体证明参看《随机过程论基础,理论・应用》

三、类之间的转移和赌徒输光问题

问题：设J是一给定的常返状态，D是由全部非常返状态的组成的

集合。对icZ),如何计算分，即过程从i出发迟早到达j的概率。

命题若J是常返的，则概率组"小七0满足

fij=ZPdkj+£Pik

kwDkeC

其中C是所有与j相通的状态的集合。

证明:

f..=P[3n<^Xn=j\Xi)=i}

=£尸闫〃<s,X〃=j\X°=i,X,=k}P{Xi=k\X.=i}

keS

ZPikfkj+ZPikfkjPikfkj

keDkeCk《C

k更D

=EPiJkj+[Pik

keDkeC

其中第二个等式利用C-K方程，最后一个等式是利用若k和j互通,

则兀=1。

例：赌徒输光问题。考虑一赌徒，在每局赌博中他以概率P赢一元,

以概率1-P输一元。假定各局赌博是独立的，赌徒开始有i元，问他

的赌金到达0（输光）之前达到N元的概率是多少？

解：以Xn记赌徒在时刻n的赌金，贝iJ｛Xn,n=O,1,…｝是Markov

链，其转移概率为

Poo=PNN=1，

Pi,i+i=P，Pg=1—〃，i=l,2…,N-\

此Markov链可分为二类：｛0｝、｛N｝、｛1,2,…，N—1｝,其中第一和

第二类是常返的，第三类是非常返的。

记Z三九记赌徒从i元的赌本开始，最终达到N的概率。根据命

题，有

i=\，2,…,N—\

由于p+q=1，

九-1-九）

由于工）=0,从上式可见

£7咛5＜）=用"

人1=25-/）=用

.

、

i叶"（/1f'

(、N—1

1人=%—=£

<P)

将前i—1个方程相加得

j=/>/〃)+(/〃产+…+。〃尸］

得

1-⑷PY

ifq/pw1

/=<i-q/p)

Ifi，ifq/p=\

利用人=1得

if〃wl/2

/=i-g/"'

V.l/N,ifp=l/2

1-⑷Pl'

ifpwl/2

因此，j\=<\-(q/p)''

UN,ifp=l/2

注意到，Nfoo时，

(q/p)',ifp^l/2

z=|o,

ifp=l/2

因此由概率得连续性知，在与有无穷赌本的对手赌博中，当p>l/2时,

赌徒的赌本以一正概率趋于无穷，而当pWl/2时，将以概率1输光。

四、状态的逗留次数

1、

设N,表示从i出发再次返回i的次数(therandomnumberoftimes

thatstateiisvisitedifyoubegininstateI(i.e.Xo=i)),用数学可以表示为

请问

⑴£(乂)=?

(2)N,的分布是多少

令

x°='4=[o1Xxn"="i‘‘°"】

则Nj=/()+/[+，2，从而

008

E(Ni)=££(/〃)=/口尸(X〃=i\X.=i)+0P(X〃"|X。=0]

〃=()77=0

0000

=f[ipr)+0(1-P俨)]=!＞，"

〃=0n=0

因此

若i常返状态*石(乂)=之〃俨=8

f=0

若i是非常返状态)矶M)=£P：?<00

/=()

假设i是非常返状态，下面求N,的分布，

由于i是非常返状态，z,.<io

若从i出发，在有限时间内从未没有返回i,则Ni=l且

P(Nj=l)=\-储

若从i出发，在有限时间内曾经返回i,则乂22,且

P(Ni>2)=l-fii

从i出发，只返回i一次的概率为

P(M=2)=P(Nj=21N,.>2)P(M>2)

=(i-A)A-

类似的推理，从i出发，返回i有k次的概率为

P(N尸k)=*Q-fJ

因此M服从几何分布，E(N,)=「二。

1-Ju

2、设丹•表示从i出发，到达状态j次数(therandomnumberoftimeperiod

thatMarkovchainisinstatej,giventhatitstartsinstatei),即

请问E(N口

若j是常返态，且if/,则成%)=8。

若i是常返状态，且j是非常返状态，则Nij=0

若i和j都是非常返状态，则成N")<8。下面来求石(NQ的值

考虑一个有限状态的Markov链，设了={1,2,.../}表示非常返状态

的全体，令

\…Ef

表示从非常返状态到非常返状态的转移概率矩阵。注意PT不是转移矩

阵（为什么？）。

对非常返状态i和j,令”表示从i出发,到达状态j次数（theexpected

numberoftimeperiodthatMarkovchainisinstatej,giventhatitstartsin

statei),即“=E(Ng),贝(J

t

见+XPikSkj

k=l

1/=/

其中..。设S=(%),f即

'J、o

S][S]?…M,

S=.••••••••・•♦

_S“S/2…stt_

则方程(*)可以写为

S=I+PTS

其中I表示恒等矩阵，从而

(I_PT)S=I

S=Q-耳)7

例：考虑赌博输光问题，〃=。4，N=7。假设赌徒开始拥有的3

元钱，求

(1)赌徒会增加到5元钱的概率？平均有多少次机会他会拥有5元钱

(theexpectedamountoftimethegamblerhas5units)?

(2)赌徒会减少到2元钱的概率？平均有多少次机会他会只拥有到2

元钱？

在赌徒输光问题中，非常返状态有1,2,3,4,5,6,

00.40000

0.600.4000

00.600.400

PT二

000.600.40

0000.600.4

000