1
概率论与数理统计第 17讲本文件可从网址
http://math.vip.sina.com
上下载
(单击 ppt讲义后选择 '工程数学 1'子目录 )
2
第十一章 马尔可夫链
§ 1 马尔可夫过程及其概率分布
3
在物理学中,很多确定性现象遵从如下演变原则,由时刻 t0系统或过程所处的状态,可以决定系统或过程在时刻 t>t0所处的状态,而无需借助于 t0以前系统或过程所处状态的历史资料,如微分方程初值问题所描绘的物理过程,
将这样的原则延伸到随机现象,引入 马尔可夫性 或 无后效性,过程 (或系统 )在时刻 t0所处的状态为已知条件下,过程在时刻 t>t0所处状态的条件分布与过程在时刻 t0之前的状态无关,
即已经知道过程 "现在 "的条件下,其 "将来 "
不依赖于 "过去 ".
4
设随机过程 {X(t),t?T}的状态空间为 I,如果对任意 n个时间值 t1<t2<...<tn,n?3,ti?T,在条件
X(ti)=xi,xi?I,i=1,2,...,n-1下,
P{X(tn)?xn|x(t1)=x1,X(t2)=x2,...,X(tn-1)=xn-1}
=P{X(tn)?xn|X(tn-1)=xn-1},xn?R,(1.1)
或写成
),,|,(
),,,;,,,|,(
11|
121121|
1
1
--
--
-
nnnntt
nnnnttt
txtxF
tttxxxtxF
nn
nn
则称过程 {X(t),t?T}具有马尔可夫性或无后效性,并称此过程为 马尔可夫过程,
5
例 1 设 {X(t),t?0}是独立增量过程,且 X(0)=0,
证明 {X(t),t?0}是一个马尔可夫过程,
证 由 (1.1)式 知,只要证明在已知 X(tn-1)=xn-1的条件下 X(tn)与 X(tj),j=1,2,...,n-2相互独立即可,
而当 0<tj<tn-1<tn,j=1,2,...,n-2时,增量
X(tj)-X(0) 与 X(tn)-X(tn-1)
相互独立,根据条件 X(0)=0和 X(tn-1)=xn-1,知
X(tj) 与 X(tn)-xn-1
相互独立,此时 X(tn)与 X(tj),j=1,2,...,n-2相互独立,这表明 X(t)具有无后效性,即 {X(t),t?0}
是一个马尔可夫过程,
6
由此可知,泊松过程是时间连续状态离散的马氏过程,维纳过程是时间状态都连续的马氏过程,
时间和状态都是离散的马尔可夫过程称为 马尔可夫链,简称马氏链,记为 {Xn=X(n),n=0,1,
2,...},它可以看作在时间集 T1={0,1,2,...}上对离散状态的马氏过程相继观察的结果,我们约定记链的状态空间 I={a1,a2,...},ai?R.
7
对链的情形,对任意的正整数 n,r和 0?t1<t2<...<
tr<m; ti,m,n+m?T1,有
)2.1(},|{
},,,,|{
2211
imjnm
imitititjnm
aXaXP
aXaXaXaXaXP
rr
)4.1(.,2,1,1),(
1
inmmP
j
ij
其中 ai?I,记上式右端为 Pij(m,m+n),称
Pij(m,m+n)=P{Xm+n=aj|Xm=ai} (1.3)
为马氏链在时刻 m处于状态 ai条件下,在时刻
m+n转移到状态 aj的 转移概率,易知
8
转移概率组成的矩阵 P(m,m+n)=(Pij(m,m+n))
称为马氏链的 转移概率矩阵,上式表明此矩阵的每一行元素之和等于 1.
当转移概率 Pij(m,m+n)只与 i,j及时间间距 n有关时,把它记为 Pij(n),即
Pij(m,m+n)=Pij(n)
并称此转移概率具有 平稳性,同时也称此链是齐次的 或 时齐的,以下仅限于讨论齐次马氏链,
9
在马氏链为齐次的情形下,转移概率
Pij(n)=P{Xm+n=aj|Xm=ai} (1.5)
称为马氏链的 n步转移概率,P(n)=(Pij(n))为 n
步转移概率矩阵,在以下的讨论中特别重要的是一步转移概率
pij=Pij(1)=P{Xm+1=aj|Xm=ai}
或由它们组成的一步转移概率矩阵
10
在上述矩阵的左侧和上边标上状态 a1,a2,...,是为了显示 pij是由状态 ai一步转移到状态 aj的概率,
PP
ppp
ppp
ppp
a
a
a
aaa
X
X
ijii
j
j
i
j
m
m
记成态状的的状态
)1(
21
22221
11211
2
1
21
1
11
例 2 如图所示只传输数字 0和 1的系统串联系统中,设每一级传真率为 p,误码率为 q=1-p,
设一个单位时间传输一级,X0是第一级的输入,
Xn是第 n级的输出 (n?1),则 {Xn,n=0,1,2,...}是一随机过程,状态空间 I={0,1},当 Xn=i,i?I为已知时,Xn+1所处的状态的概率分布只与 Xn=i
有关,而与时刻 n以前的状态无关,所以它是一个齐次的马氏链,
1 2 nX0
X1 X2 Xn-1 Xn
12
它的一步转移概率和一步转移概率矩阵分别为
1,0,,,,,}|{ 1?
jiijq
ijpiXjXPp
nnij
pq
qp
P
1
0
10
和
13
例 3 一维随机游动 设一醉汉 Q在如图所示直线的点集 I={1,2,3,4,5}上作随机游动,且仅在 1
秒 2秒等时刻发生游动,游动的概率规则是,如果 Q现在位于点 i(1<i<5),则下一时刻以 1/3概率向左或向右移动一格,或以 1/3的概率留在原处 ; 如果 Q现在位于 1(或 5)这点上,则下一时刻就以概率 1移动到 2(或 4)上,1和 5这两点称为 反射壁,这叫 带有两个反射壁的随机游动,
1 2 3 4 5
14
若以 Xn表示时刻 n时 Q的位置,不同的位置就是 Xn不同的状态,那么 {Xn,n=0,1,2,...}是一随机过程,状态空间就是 I,而且当 Xn=i,i?I为已知时,Xn+1所处的状态的概率分别只与 Xn=i有关,而与 Q在时刻 n以前如何到达 i是完全无关的,所以 {Xn,n=0,1,2,...}是一齐次马氏链,它的一步转移概率为
-
-?
2||,0
,4,52,1,1
,51,1,,1,
3
1
}|{
1
ij
jiji
iiiij
iXjXPp
nnij
或
15
一步转移概率矩阵为
01000
3/13/13/100
03/13/13/10
003/13/13/1
00010
5
4
3
2
1
54321
P
如果把 1这点改为吸收壁,就是说 Q一旦到达 1
这一点,则就永远留在点 1上,此时,相应的转移概率矩阵只需把 P中第 1横行改为 (1,0,0,0,0).
总之,改变游动的概率规则,就可得到不同方式的随机游动和相应的马氏链,
16
例 4 排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成,如图所示,服务规则是,先到先服务,后来者在等候室依次排队,假定一个需要服务的顾客到达系统时发现系统内已有 3个顾客 (一个正在接受服务,两个在等候室排队 ),则该顾客就离去,
等候室 服务台系统随机到达者 离去者
17
设时间间隔 Dt内有一个顾客进入系统的概率为 q,有一原来被服务的顾客离开系统 (即服务完毕 )的概率为 p,又设当 Dt充分小时,在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的,再设有无顾客来到与服务是否完毕是相互独立的,现用马氏链来描述这个系统,
设 Xn=X(nDt)表示时刻 nDt时系统内的顾客数,
即系统的状态,{Xn,n=0,1,2,...}是一随机过程,
状态空间 I={0,1,2,3},易知它是一马氏链,下面计算一步转移概率,
18
p00,在系统内没有顾客的条件下,经 Dt后仍然没有顾客的概率 (此处是条件概率,以下同 )p00=1-q.
p01:系统内没有顾客的条件下,经 Dt后有一顾客进入系统的概率,p01=q.
p10:系统内恰 有一顾客正在接受服务的条件下,经 Dt后系统内无人的概率,它等于在 Dt间隔内顾客因服务完毕而离去,且无人进入系统的概率,p10=p(1-q).
19
类似地有
p11=pq+(1-p)(1-q)
p12=(1-p)q
p13=0
p21=p32=p(1-q),
p22=pq+(1-p)(1-q)
p23=q(1-p)
pij=0(|i-j|?2)
p33=pq+(1-p).
20
于是一步转移概率矩阵为
-?-
---?-
---?-
-
)1()1(00
)1()1)(1()1(0
0)1()1)(1()1(
001
3
2
1
0
3210
ppqqp
pqqppqqp
pqqppqqp
qq
P
21
在实际问题中,一步转移概率通常可通过统计试验确定,下面看一实例,
例 5 某计算机房的一台计算机经常出故障,研究者每隔 15分钟观察一次计算机的运行状态,
收集了 24小时的数据 (共作 97次观察 ),用 1表示正常状态,用 0表示不正常状态,所得的数据序列如下,
111001001111111001111011111100111111111
000110110111101101101011101110111101111
110011011111100111
设 Xn为第 n(n=1,2,...,97)个时段的计算机状态,
22
可以认为它是一个齐次马氏链,状态空间
I={0,1},96次状态转移的情况是,
0?0:8次 ; 0?1:18次 ; 1?0:18次 ; 1?1:52次,
因此,一步转移概率可用频率近似地表示为
.
70
52
5218
52
}1|1{
,
70
18
5218
18
}1|0{
,
26
18
188
18
}0|1{
,
26
8
188
8
}0|0{
111
110
101
100
nn
nn
nn
nn
XXPp
XXPp
XXPp
XXPp
23
例 6 前例中计算机从某状态 0的条件下能连续正常工作 3个时段的条件概率为多少?
解 由题意可得
P{X1=1,X2=1,X3=1|X0=0}
=P{X0=0,X1=1,X2=1,X3=1}/P{X0=0}
=P{X0=0}P{X1=1|X0=0}P{X2=1|X1=1,X0=0}
P{X3=1|X2=1,X1=1,X0=0}/P{X0=0}
=P{X1=1|X0=0}P{X2=1|X1=1}P{X3=1|X2=1}
.382.0
70
52
70
52
26
18)1()1()1(
111101 PPP
24
现在研究齐次马氏链的有限维分布,首先,记
pj(0)=P{X0=aj},aj?I,j=1,2,....
称它为马氏链的初始分布,再看马氏链在任一时刻 n?T1的一维分布,
pj(n)=P{Xn=aj},aj?I,j=1,2,...,(1.6)
1
.1)(
j
j np显然应有
,}{}|{
},{}{
1
00
1
0
i
iijn
i
jnijn
aXPaXaXP
aXaXPaXP
又有
25
一维分布 (1.6)也可用行向量表示成
p(n)=(p1(n),p2(n),...,pj(n),...),(1.6)'
这样,利用矩阵乘法 (I是可列无限集时,仍用有限阶矩阵乘法的规则确定矩阵之积的元 ),
p(n)=p(0)P(n),(1.7)'
此式表明,马氏链在任一时刻 n?T1时的一维分布由初始分布 p(0)和 n步转移矩阵所确定,
)7.1(.,2,1,)()0()(
1
jnPpnp
i
ijij或即
26
又,对于任意 n个时刻 t1<t2<...<tn,ti?T1,以及状
)8.1(
).()()(}
|{}|{}{
},,,|{
}|{}{
},,,{
:,,,,
1121
121111
112211
112211
112211
2211
21
-
--
---
--
nniiiiiit
itititit
itititit
ititit
ititit
iii
ttPttPtpaX
aXPaXaXPaXP
aXaXaXaXP
aXaXPaXP
aXaXaXP
nIaaa
nnnn
nn
nnnn
nn
n
维分布马氏链的态
27
由此,并结合 (1.7)或 (1.7)'可知,马氏链的有限维分布同样完全由初始分布和转移概率所确定,
总之,转移概率决定了马氏链运动的统计规律,
因此,确定马氏链的任意 n步转移概率就成为马氏链理论中的重要问题之一,
28
§ 2 多步转移概率的确定
29
设 {X(n),n=0,1,2,...}是一齐次马氏链,则对于任意的 u,v?T1,有
)1.2(.2,1,,)()()(
1
jivPuPvuP
k
kjikij
这是切普曼 -科尔莫戈罗夫方程,简称 C-K方程,
ai
ak aj
s s+u s+u+v tO
30
C-K方程基于下述事实,即 "从时刻 t所处的状态 ai,即 X(s)=ai出发,经时段 u+v转移到状态 aj,
即 X(s+u+v)=aj" 这一事件可分解成 "从 X(s)=ai
出发,先经时段 u转移到中间状态 ak(k=1,2,...),
再从 ak经时段 v转移到状态 aj"这样一些事件的和事件,
先固定 ak?I和 s?T1,由条件概率和乘法定理,
P{X(s+u+v)=aj,X(s+u)=ak|X(s)=ai}
=P{X(s+u)=ak|X(s)=ai}
P{X(s+u+v)=aj|X(s+u)=ak,X(s)=ai}
=Pik(u)Pkj(v),(2.2)
31
又由于事件组 "X(s+u)=ak",k=1,2,...构成一划分,故有
Pij(u+v)=P{X(s+u+v)=aj|X(s)=ai}
.})(|)(,)({
1
k
jkj asXausXavusXP
将 (2.2)式 代入上式,即得所要证明的 C-K方程,
C-K方程 也可写成矩阵形式,
P(u+v)=P(u)P(v),(2.1)'
32
P(u+v)=P(u)P(v),(2.1)'
利用 C-K方程容易确定 n步转移概率,在 (2.1)'
式中令 u=1,v=n-1,得递推关系
P(n)=P(1)P(n-1)=PP(n-1),
从而可得 P(n)=Pn,(2.3)
就是说,对齐次马氏链而言,n步转移概率矩阵是一步转移概率矩阵的 n次方,
进而可知,链的有限维分布可由初始分布与一步转移概率完全确定,
33
例 1 设 {Xn,n?0}是具有三个状态 0,1,2的齐次马氏链,一步转移概率矩阵为
4/14/30
4/12/14/1
04/14/3
2
1
0
210
P
初始分布 pi(0)=P{X0=i}=1/3,i=0,1,2,试求 (i)
P{X0=0,X2=1}; (ii)P{X2=1}.
34
解 先求出二步转移概率矩阵
4/116/916/3
16/32/116/5
16/116/58/5
2
1
0
210
)2(
2
PP
.
24
11
16
9
2
1
16
5
3
1
)2()0(
)2()0()2()0(}1{)2(( i i );
48
5
16
5
3
1
)2()0(
212
11101021
010
Pp
PpPpXPp
Pp
于是 (i)P{X0=0,X2=1}=P{X0=0}P{X2=1|X0=0}
35
例 2 在 § 1例 2中,(i)设 p=0.9,求系统二级传输后的传真率与三级传输后的误码率 ; (ii)设初始分布 p1(0)=P{X0=1}=a,p0(0)=P{X0=0}=1-a,
又已知系统经 n级传输后输出为 1,问原发字符是 1的概率是多少?
解 先求出 n步转移概率矩阵 P(n)=Pn,由于
)1(
1
0
10
pq
pq
qp
P -
有相异的特征值 l1=1,l2=p-q,
36
由线性代数知识,可将 P表示成对角阵
-
qp0
01
0
0
2
1
l
l
,
2121
2121
],[
.
21
21
,
21
21
21
21
-
-
eeH
ee
令的相似矩阵,具体做法是,求出 l1,l2对应的特征向量
37
则 P=H?H-1,于是,容易算得
Pn=(H?H-1)n=H?nH-1
)4.2(.
)(
2
1
2
1
)(
2
1
2
1
)(
2
1
2
1
)(
2
1
2
1
1
0
10
-?--
---?
nn
nn
qpqp
qpqp
38
(i) 因此,当 p=0.9时,系统二级传输后的传真率与三级传输后的误码率分别为;244.0)1.09.0(
2
1
2
1
)3()3(
,820.0)1.09.0(
2
1
2
1
)2()2(
3
0110
2
0011
--
-
Pp
Pp
.
))(12(1
)(
)()0()()0(
)()0(
}1{
}1|1{}1{
}1|1{
111010
111
00
0
n
n
n
n
n
qp
qp
nPpnPp
nPp
XP
XXPXP
XXP
--?
-?
a
aa
(ii)根据贝叶斯公式有
39
对于只有两个状态的马氏链,一步转移概率矩阵一般可表示为
.1,0,1110
10
-
-? ba
bb
aaP
)5.2(.,2,1
,
)1(1
)()(
)()(
)(
1110
0100
-
-
--
n
bb
aa
ba
ba
ab
ab
ba
nPnP
nPnP
PnP
n
n
利用类似于例 2的方法,可得 n步转移概率矩阵为
40
§ 3 遍历性
41
对于一般的两个状态的马氏链,由 (2.5)式 可知,
当 0<a,b<1时,Pij(n)有极限
.)(lim)(lim
.)(lim)(lim
11101
01000
记成记成
ba
a
nPnP
ba
b
nPnP
nn
nn
即对于固定的状态 j,不管链在某一时刻从什么状态 (i=0或 1)出发,通过长时间的转移,到达状态 j的概率都趋近于?j,这就是所谓的遍历性,
又由于?0+?1=1,所以 (?0,?1)=?构成一分布律,
称它为链的极限分布,
42
设齐次马氏链的状态空间为 I,若对于所有
ai,aj?I,转移概率 Pij(n)存在极限
.)(
)()(lim
21
21
21
)(
j
j
j
n
n
jij
n
PnP
inP
或不依赖于
1
j
j?则称此链具有 遍历性,又若,则同时称?=(?1,?2,...)为链的 极限分布,
43
齐次马氏链在什么条件下才具有普遍性?如何求出它的极限分布?这问题在理论上已经圆满解决,但叙述它需要较多篇幅,下面仅就只有有限个状态的链,即 有限链 的遍历性给出一个充分条件,
44
定理 设齐次马氏链 {Xn,n?1}的状态空间为
I={a1,a2,...,aN},P是它的一步转移概率矩阵,如果存在正整数 m,使对任意的 ai,aj?I,都有
Pij(m)>0,i,j=1,2,...,N,(3.1)
则此链具有遍历性,且有极限分布
=(?1,?2,...,?N),它是方程组
=?P或即
)2.3(,,2,1,
1
Njp
N
i
ijij
)3.3(1,0
1
N
j
jj
的满足条件的唯一解,
45
依照定理,为证有限链是遍历的,只需找一正整数 m,使 m步转移概率矩阵 Pm无零元,而求极限分布?的问题,化为求解方程组 (3.2)的问题,注意,方程组 (3.2)中仅 N-1个未知数是独
.1,
1
确定而唯一解可用归一条件立的
N
j
j?
在定理的条件下,马氏链的极限分布又是平稳分布,意即,若用?作为链的初始分布,即
p(0)=?,则链在任一时刻 n?T1的分布 p(n)永远与?一致,事实上,由 (1.7)',(2.3)和 (3.2)式有
p(n)=p(0)P(n)=?Pn=?Pn-1=...=?P=?.
46
例 1 试说明 § 1例 3中,带有两个反射壁的随机游动是遍历的,并求其极限分布 (平稳分布 ).
解 为简便计,以符号 "?"代表转移概率矩阵的正的元,于是,由 例 3中的一步转移概率矩阵
P(2)=P2=
00
0
0
00
0000
00
00
00
0000
0000
00
00
00
0000
47
P(4)=P4=
即 P(4)无零元,由定理,链是遍历的,再根据
(3.2)和 (3.3)式,写出极限分布?=(?1,?2,...,?5)满足的方程组,
.
00
0
0
00
00
0
0
00
48
先由前四个方程,解得 3?1=?2=?3=?4=3?5,将它们代入最后一个方程,解得极限分布为
=(1/11,3/11,3/11,3/11,1/11).
.1
,)3/1(
,)3/1()3/1(
,)3/1()3/1()3/1(
,)3/1()3/1(
,)3/1(
54321
45
5434
4323
3212
21
49
例 2 试说明 § 1例 4(排队模型 )中的链是遍历的,
并求其极限分布,
解 依照例 1,由中的一步转移概率矩阵 P,可算得 P(3)=P3无零元,根据定理,链是遍历的,而极限分布?=(?0,?1,?2,?3)满足下列方程组,
--?
-?---?
-?--
-?-?
.1
,)]1([)1(
,)1()]1)(1([)1(
,)1()]1)(1([
,)1()1(
3210
323
3212
2101
100
ppqpq
qpqppqpq
qpqppqq
qpq
50
解出的唯一解为
0=p3(1-q)3/C,?1=p2q(1-q)2/C,
2=pq2(1-q)(1-p)/C,?3=q3(1-p)2/C,
其中 C=p3(1-q)3+p2q(1-q)2+pq2(1-q)(1-
p)+q3(1-p)2.
假若在此例中,p=q=1/2,则可算得此时的极限分布为
=(1/7,2/7,2/7,2/7),这就是说,经过相当长时间后,系统中无人的情形约占 14%的时间,而系统中有一人,二人,三人的情形约各占 29%的时间,
51
例 3 设一马氏链的一步转移概率矩阵为
.
02/102/1
2/102/10
02/102/1
2/102/10
P
.
2/102/10
02/102/1
2/102/10
02/102/1
)2(
2
PP
试讨论它的遍历性,
解 先算得
52
进一步可验证,当 n为奇数时,P(n)=P(1)=P; n
为偶数时,P(n)=P(2),这表明对任一固定的 j(
,.)(lim),4,3,2,1 按定义都不存在极限 nP ij
n
此链不具遍历性,
53
作业 第十一章习题第 374页第 7题
54
请提问
概率论与数理统计第 17讲本文件可从网址
http://math.vip.sina.com
上下载
(单击 ppt讲义后选择 '工程数学 1'子目录 )
2
第十一章 马尔可夫链
§ 1 马尔可夫过程及其概率分布
3
在物理学中,很多确定性现象遵从如下演变原则,由时刻 t0系统或过程所处的状态,可以决定系统或过程在时刻 t>t0所处的状态,而无需借助于 t0以前系统或过程所处状态的历史资料,如微分方程初值问题所描绘的物理过程,
将这样的原则延伸到随机现象,引入 马尔可夫性 或 无后效性,过程 (或系统 )在时刻 t0所处的状态为已知条件下,过程在时刻 t>t0所处状态的条件分布与过程在时刻 t0之前的状态无关,
即已经知道过程 "现在 "的条件下,其 "将来 "
不依赖于 "过去 ".
4
设随机过程 {X(t),t?T}的状态空间为 I,如果对任意 n个时间值 t1<t2<...<tn,n?3,ti?T,在条件
X(ti)=xi,xi?I,i=1,2,...,n-1下,
P{X(tn)?xn|x(t1)=x1,X(t2)=x2,...,X(tn-1)=xn-1}
=P{X(tn)?xn|X(tn-1)=xn-1},xn?R,(1.1)
或写成
),,|,(
),,,;,,,|,(
11|
121121|
1
1
--
--
-
nnnntt
nnnnttt
txtxF
tttxxxtxF
nn
nn
则称过程 {X(t),t?T}具有马尔可夫性或无后效性,并称此过程为 马尔可夫过程,
5
例 1 设 {X(t),t?0}是独立增量过程,且 X(0)=0,
证明 {X(t),t?0}是一个马尔可夫过程,
证 由 (1.1)式 知,只要证明在已知 X(tn-1)=xn-1的条件下 X(tn)与 X(tj),j=1,2,...,n-2相互独立即可,
而当 0<tj<tn-1<tn,j=1,2,...,n-2时,增量
X(tj)-X(0) 与 X(tn)-X(tn-1)
相互独立,根据条件 X(0)=0和 X(tn-1)=xn-1,知
X(tj) 与 X(tn)-xn-1
相互独立,此时 X(tn)与 X(tj),j=1,2,...,n-2相互独立,这表明 X(t)具有无后效性,即 {X(t),t?0}
是一个马尔可夫过程,
6
由此可知,泊松过程是时间连续状态离散的马氏过程,维纳过程是时间状态都连续的马氏过程,
时间和状态都是离散的马尔可夫过程称为 马尔可夫链,简称马氏链,记为 {Xn=X(n),n=0,1,
2,...},它可以看作在时间集 T1={0,1,2,...}上对离散状态的马氏过程相继观察的结果,我们约定记链的状态空间 I={a1,a2,...},ai?R.
7
对链的情形,对任意的正整数 n,r和 0?t1<t2<...<
tr<m; ti,m,n+m?T1,有
)2.1(},|{
},,,,|{
2211
imjnm
imitititjnm
aXaXP
aXaXaXaXaXP
rr
)4.1(.,2,1,1),(
1
inmmP
j
ij
其中 ai?I,记上式右端为 Pij(m,m+n),称
Pij(m,m+n)=P{Xm+n=aj|Xm=ai} (1.3)
为马氏链在时刻 m处于状态 ai条件下,在时刻
m+n转移到状态 aj的 转移概率,易知
8
转移概率组成的矩阵 P(m,m+n)=(Pij(m,m+n))
称为马氏链的 转移概率矩阵,上式表明此矩阵的每一行元素之和等于 1.
当转移概率 Pij(m,m+n)只与 i,j及时间间距 n有关时,把它记为 Pij(n),即
Pij(m,m+n)=Pij(n)
并称此转移概率具有 平稳性,同时也称此链是齐次的 或 时齐的,以下仅限于讨论齐次马氏链,
9
在马氏链为齐次的情形下,转移概率
Pij(n)=P{Xm+n=aj|Xm=ai} (1.5)
称为马氏链的 n步转移概率,P(n)=(Pij(n))为 n
步转移概率矩阵,在以下的讨论中特别重要的是一步转移概率
pij=Pij(1)=P{Xm+1=aj|Xm=ai}
或由它们组成的一步转移概率矩阵
10
在上述矩阵的左侧和上边标上状态 a1,a2,...,是为了显示 pij是由状态 ai一步转移到状态 aj的概率,
PP
ppp
ppp
ppp
a
a
a
aaa
X
X
ijii
j
j
i
j
m
m
记成态状的的状态
)1(
21
22221
11211
2
1
21
1
11
例 2 如图所示只传输数字 0和 1的系统串联系统中,设每一级传真率为 p,误码率为 q=1-p,
设一个单位时间传输一级,X0是第一级的输入,
Xn是第 n级的输出 (n?1),则 {Xn,n=0,1,2,...}是一随机过程,状态空间 I={0,1},当 Xn=i,i?I为已知时,Xn+1所处的状态的概率分布只与 Xn=i
有关,而与时刻 n以前的状态无关,所以它是一个齐次的马氏链,
1 2 nX0
X1 X2 Xn-1 Xn
12
它的一步转移概率和一步转移概率矩阵分别为
1,0,,,,,}|{ 1?
jiijq
ijpiXjXPp
nnij
pq
qp
P
1
0
10
和
13
例 3 一维随机游动 设一醉汉 Q在如图所示直线的点集 I={1,2,3,4,5}上作随机游动,且仅在 1
秒 2秒等时刻发生游动,游动的概率规则是,如果 Q现在位于点 i(1<i<5),则下一时刻以 1/3概率向左或向右移动一格,或以 1/3的概率留在原处 ; 如果 Q现在位于 1(或 5)这点上,则下一时刻就以概率 1移动到 2(或 4)上,1和 5这两点称为 反射壁,这叫 带有两个反射壁的随机游动,
1 2 3 4 5
14
若以 Xn表示时刻 n时 Q的位置,不同的位置就是 Xn不同的状态,那么 {Xn,n=0,1,2,...}是一随机过程,状态空间就是 I,而且当 Xn=i,i?I为已知时,Xn+1所处的状态的概率分别只与 Xn=i有关,而与 Q在时刻 n以前如何到达 i是完全无关的,所以 {Xn,n=0,1,2,...}是一齐次马氏链,它的一步转移概率为
-
-?
2||,0
,4,52,1,1
,51,1,,1,
3
1
}|{
1
ij
jiji
iiiij
iXjXPp
nnij
或
15
一步转移概率矩阵为
01000
3/13/13/100
03/13/13/10
003/13/13/1
00010
5
4
3
2
1
54321
P
如果把 1这点改为吸收壁,就是说 Q一旦到达 1
这一点,则就永远留在点 1上,此时,相应的转移概率矩阵只需把 P中第 1横行改为 (1,0,0,0,0).
总之,改变游动的概率规则,就可得到不同方式的随机游动和相应的马氏链,
16
例 4 排队模型 设服务系统由一个服务员和只可以容纳两个人的等候室组成,如图所示,服务规则是,先到先服务,后来者在等候室依次排队,假定一个需要服务的顾客到达系统时发现系统内已有 3个顾客 (一个正在接受服务,两个在等候室排队 ),则该顾客就离去,
等候室 服务台系统随机到达者 离去者
17
设时间间隔 Dt内有一个顾客进入系统的概率为 q,有一原来被服务的顾客离开系统 (即服务完毕 )的概率为 p,又设当 Dt充分小时,在这时间间隔内多于一个顾客进入或离开系统实际上是不可能的,再设有无顾客来到与服务是否完毕是相互独立的,现用马氏链来描述这个系统,
设 Xn=X(nDt)表示时刻 nDt时系统内的顾客数,
即系统的状态,{Xn,n=0,1,2,...}是一随机过程,
状态空间 I={0,1,2,3},易知它是一马氏链,下面计算一步转移概率,
18
p00,在系统内没有顾客的条件下,经 Dt后仍然没有顾客的概率 (此处是条件概率,以下同 )p00=1-q.
p01:系统内没有顾客的条件下,经 Dt后有一顾客进入系统的概率,p01=q.
p10:系统内恰 有一顾客正在接受服务的条件下,经 Dt后系统内无人的概率,它等于在 Dt间隔内顾客因服务完毕而离去,且无人进入系统的概率,p10=p(1-q).
19
类似地有
p11=pq+(1-p)(1-q)
p12=(1-p)q
p13=0
p21=p32=p(1-q),
p22=pq+(1-p)(1-q)
p23=q(1-p)
pij=0(|i-j|?2)
p33=pq+(1-p).
20
于是一步转移概率矩阵为
-?-
---?-
---?-
-
)1()1(00
)1()1)(1()1(0
0)1()1)(1()1(
001
3
2
1
0
3210
ppqqp
pqqppqqp
pqqppqqp
P
21
在实际问题中,一步转移概率通常可通过统计试验确定,下面看一实例,
例 5 某计算机房的一台计算机经常出故障,研究者每隔 15分钟观察一次计算机的运行状态,
收集了 24小时的数据 (共作 97次观察 ),用 1表示正常状态,用 0表示不正常状态,所得的数据序列如下,
111001001111111001111011111100111111111
000110110111101101101011101110111101111
110011011111100111
设 Xn为第 n(n=1,2,...,97)个时段的计算机状态,
22
可以认为它是一个齐次马氏链,状态空间
I={0,1},96次状态转移的情况是,
0?0:8次 ; 0?1:18次 ; 1?0:18次 ; 1?1:52次,
因此,一步转移概率可用频率近似地表示为
.
70
52
5218
52
}1|1{
,
70
18
5218
18
}1|0{
,
26
18
188
18
}0|1{
,
26
8
188
8
}0|0{
111
110
101
100
nn
nn
nn
nn
XXPp
XXPp
XXPp
XXPp
23
例 6 前例中计算机从某状态 0的条件下能连续正常工作 3个时段的条件概率为多少?
解 由题意可得
P{X1=1,X2=1,X3=1|X0=0}
=P{X0=0,X1=1,X2=1,X3=1}/P{X0=0}
=P{X0=0}P{X1=1|X0=0}P{X2=1|X1=1,X0=0}
P{X3=1|X2=1,X1=1,X0=0}/P{X0=0}
=P{X1=1|X0=0}P{X2=1|X1=1}P{X3=1|X2=1}
.382.0
70
52
70
52
26
18)1()1()1(
111101 PPP
24
现在研究齐次马氏链的有限维分布,首先,记
pj(0)=P{X0=aj},aj?I,j=1,2,....
称它为马氏链的初始分布,再看马氏链在任一时刻 n?T1的一维分布,
pj(n)=P{Xn=aj},aj?I,j=1,2,...,(1.6)
1
.1)(
j
j np显然应有
,}{}|{
},{}{
1
00
1
0
i
iijn
i
jnijn
aXPaXaXP
aXaXPaXP
又有
25
一维分布 (1.6)也可用行向量表示成
p(n)=(p1(n),p2(n),...,pj(n),...),(1.6)'
这样,利用矩阵乘法 (I是可列无限集时,仍用有限阶矩阵乘法的规则确定矩阵之积的元 ),
p(n)=p(0)P(n),(1.7)'
此式表明,马氏链在任一时刻 n?T1时的一维分布由初始分布 p(0)和 n步转移矩阵所确定,
)7.1(.,2,1,)()0()(
1
jnPpnp
i
ijij或即
26
又,对于任意 n个时刻 t1<t2<...<tn,ti?T1,以及状
)8.1(
).()()(}
|{}|{}{
},,,|{
}|{}{
},,,{
:,,,,
1121
121111
112211
112211
112211
2211
21
-
--
---
--
nniiiiiit
itititit
itititit
ititit
ititit
iii
ttPttPtpaX
aXPaXaXPaXP
aXaXaXaXP
aXaXPaXP
aXaXaXP
nIaaa
nnnn
nn
nnnn
nn
n
维分布马氏链的态
27
由此,并结合 (1.7)或 (1.7)'可知,马氏链的有限维分布同样完全由初始分布和转移概率所确定,
总之,转移概率决定了马氏链运动的统计规律,
因此,确定马氏链的任意 n步转移概率就成为马氏链理论中的重要问题之一,
28
§ 2 多步转移概率的确定
29
设 {X(n),n=0,1,2,...}是一齐次马氏链,则对于任意的 u,v?T1,有
)1.2(.2,1,,)()()(
1
jivPuPvuP
k
kjikij
这是切普曼 -科尔莫戈罗夫方程,简称 C-K方程,
ai
ak aj
s s+u s+u+v tO
30
C-K方程基于下述事实,即 "从时刻 t所处的状态 ai,即 X(s)=ai出发,经时段 u+v转移到状态 aj,
即 X(s+u+v)=aj" 这一事件可分解成 "从 X(s)=ai
出发,先经时段 u转移到中间状态 ak(k=1,2,...),
再从 ak经时段 v转移到状态 aj"这样一些事件的和事件,
先固定 ak?I和 s?T1,由条件概率和乘法定理,
P{X(s+u+v)=aj,X(s+u)=ak|X(s)=ai}
=P{X(s+u)=ak|X(s)=ai}
P{X(s+u+v)=aj|X(s+u)=ak,X(s)=ai}
=Pik(u)Pkj(v),(2.2)
31
又由于事件组 "X(s+u)=ak",k=1,2,...构成一划分,故有
Pij(u+v)=P{X(s+u+v)=aj|X(s)=ai}
.})(|)(,)({
1
k
jkj asXausXavusXP
将 (2.2)式 代入上式,即得所要证明的 C-K方程,
C-K方程 也可写成矩阵形式,
P(u+v)=P(u)P(v),(2.1)'
32
P(u+v)=P(u)P(v),(2.1)'
利用 C-K方程容易确定 n步转移概率,在 (2.1)'
式中令 u=1,v=n-1,得递推关系
P(n)=P(1)P(n-1)=PP(n-1),
从而可得 P(n)=Pn,(2.3)
就是说,对齐次马氏链而言,n步转移概率矩阵是一步转移概率矩阵的 n次方,
进而可知,链的有限维分布可由初始分布与一步转移概率完全确定,
33
例 1 设 {Xn,n?0}是具有三个状态 0,1,2的齐次马氏链,一步转移概率矩阵为
4/14/30
4/12/14/1
04/14/3
2
1
0
210
P
初始分布 pi(0)=P{X0=i}=1/3,i=0,1,2,试求 (i)
P{X0=0,X2=1}; (ii)P{X2=1}.
34
解 先求出二步转移概率矩阵
4/116/916/3
16/32/116/5
16/116/58/5
2
1
0
210
)2(
2
PP
.
24
11
16
9
2
1
16
5
3
1
)2()0(
)2()0()2()0(}1{)2(( i i );
48
5
16
5
3
1
)2()0(
212
11101021
010
Pp
PpPpXPp
Pp
于是 (i)P{X0=0,X2=1}=P{X0=0}P{X2=1|X0=0}
35
例 2 在 § 1例 2中,(i)设 p=0.9,求系统二级传输后的传真率与三级传输后的误码率 ; (ii)设初始分布 p1(0)=P{X0=1}=a,p0(0)=P{X0=0}=1-a,
又已知系统经 n级传输后输出为 1,问原发字符是 1的概率是多少?
解 先求出 n步转移概率矩阵 P(n)=Pn,由于
)1(
1
0
10
pq
pq
qp
P -
有相异的特征值 l1=1,l2=p-q,
36
由线性代数知识,可将 P表示成对角阵
-
qp0
01
0
0
2
1
l
l
,
2121
2121
],[
.
21
21
,
21
21
21
21
-
-
eeH
ee
令的相似矩阵,具体做法是,求出 l1,l2对应的特征向量
37
则 P=H?H-1,于是,容易算得
Pn=(H?H-1)n=H?nH-1
)4.2(.
)(
2
1
2
1
)(
2
1
2
1
)(
2
1
2
1
)(
2
1
2
1
1
0
10
-?--
---?
nn
nn
qpqp
qpqp
38
(i) 因此,当 p=0.9时,系统二级传输后的传真率与三级传输后的误码率分别为;244.0)1.09.0(
2
1
2
1
)3()3(
,820.0)1.09.0(
2
1
2
1
)2()2(
3
0110
2
0011
--
-
Pp
Pp
.
))(12(1
)(
)()0()()0(
)()0(
}1{
}1|1{}1{
}1|1{
111010
111
00
0
n
n
n
n
n
qp
qp
nPpnPp
nPp
XP
XXPXP
XXP
--?
-?
a
aa
(ii)根据贝叶斯公式有
39
对于只有两个状态的马氏链,一步转移概率矩阵一般可表示为
.1,0,1110
10
-
-? ba
bb
aaP
)5.2(.,2,1
,
)1(1
)()(
)()(
)(
1110
0100
-
-
--
n
bb
aa
ba
ba
ab
ab
ba
nPnP
nPnP
PnP
n
n
利用类似于例 2的方法,可得 n步转移概率矩阵为
40
§ 3 遍历性
41
对于一般的两个状态的马氏链,由 (2.5)式 可知,
当 0<a,b<1时,Pij(n)有极限
.)(lim)(lim
.)(lim)(lim
11101
01000
记成记成
ba
a
nPnP
ba
b
nPnP
nn
nn
即对于固定的状态 j,不管链在某一时刻从什么状态 (i=0或 1)出发,通过长时间的转移,到达状态 j的概率都趋近于?j,这就是所谓的遍历性,
又由于?0+?1=1,所以 (?0,?1)=?构成一分布律,
称它为链的极限分布,
42
设齐次马氏链的状态空间为 I,若对于所有
ai,aj?I,转移概率 Pij(n)存在极限
.)(
)()(lim
21
21
21
)(
j
j
j
n
n
jij
n
PnP
inP
或不依赖于
1
j
j?则称此链具有 遍历性,又若,则同时称?=(?1,?2,...)为链的 极限分布,
43
齐次马氏链在什么条件下才具有普遍性?如何求出它的极限分布?这问题在理论上已经圆满解决,但叙述它需要较多篇幅,下面仅就只有有限个状态的链,即 有限链 的遍历性给出一个充分条件,
44
定理 设齐次马氏链 {Xn,n?1}的状态空间为
I={a1,a2,...,aN},P是它的一步转移概率矩阵,如果存在正整数 m,使对任意的 ai,aj?I,都有
Pij(m)>0,i,j=1,2,...,N,(3.1)
则此链具有遍历性,且有极限分布
=(?1,?2,...,?N),它是方程组
=?P或即
)2.3(,,2,1,
1
Njp
N
i
ijij
)3.3(1,0
1
N
j
jj
的满足条件的唯一解,
45
依照定理,为证有限链是遍历的,只需找一正整数 m,使 m步转移概率矩阵 Pm无零元,而求极限分布?的问题,化为求解方程组 (3.2)的问题,注意,方程组 (3.2)中仅 N-1个未知数是独
.1,
1
确定而唯一解可用归一条件立的
N
j
j?
在定理的条件下,马氏链的极限分布又是平稳分布,意即,若用?作为链的初始分布,即
p(0)=?,则链在任一时刻 n?T1的分布 p(n)永远与?一致,事实上,由 (1.7)',(2.3)和 (3.2)式有
p(n)=p(0)P(n)=?Pn=?Pn-1=...=?P=?.
46
例 1 试说明 § 1例 3中,带有两个反射壁的随机游动是遍历的,并求其极限分布 (平稳分布 ).
解 为简便计,以符号 "?"代表转移概率矩阵的正的元,于是,由 例 3中的一步转移概率矩阵
P(2)=P2=
00
0
0
00
0000
00
00
00
0000
0000
00
00
00
0000
47
P(4)=P4=
即 P(4)无零元,由定理,链是遍历的,再根据
(3.2)和 (3.3)式,写出极限分布?=(?1,?2,...,?5)满足的方程组,
.
00
0
0
00
00
0
0
00
48
先由前四个方程,解得 3?1=?2=?3=?4=3?5,将它们代入最后一个方程,解得极限分布为
=(1/11,3/11,3/11,3/11,1/11).
.1
,)3/1(
,)3/1()3/1(
,)3/1()3/1()3/1(
,)3/1()3/1(
,)3/1(
54321
45
5434
4323
3212
21
49
例 2 试说明 § 1例 4(排队模型 )中的链是遍历的,
并求其极限分布,
解 依照例 1,由中的一步转移概率矩阵 P,可算得 P(3)=P3无零元,根据定理,链是遍历的,而极限分布?=(?0,?1,?2,?3)满足下列方程组,
--?
-?---?
-?--
-?-?
.1
,)]1([)1(
,)1()]1)(1([)1(
,)1()]1)(1([
,)1()1(
3210
323
3212
2101
100
ppqpq
qpqppqpq
qpqppqq
qpq
50
解出的唯一解为
0=p3(1-q)3/C,?1=p2q(1-q)2/C,
2=pq2(1-q)(1-p)/C,?3=q3(1-p)2/C,
其中 C=p3(1-q)3+p2q(1-q)2+pq2(1-q)(1-
p)+q3(1-p)2.
假若在此例中,p=q=1/2,则可算得此时的极限分布为
=(1/7,2/7,2/7,2/7),这就是说,经过相当长时间后,系统中无人的情形约占 14%的时间,而系统中有一人,二人,三人的情形约各占 29%的时间,
51
例 3 设一马氏链的一步转移概率矩阵为
.
02/102/1
2/102/10
02/102/1
2/102/10
P
.
2/102/10
02/102/1
2/102/10
02/102/1
)2(
2
PP
试讨论它的遍历性,
解 先算得
52
进一步可验证,当 n为奇数时,P(n)=P(1)=P; n
为偶数时,P(n)=P(2),这表明对任一固定的 j(
,.)(lim),4,3,2,1 按定义都不存在极限 nP ij
n
此链不具遍历性,
53
作业 第十一章习题第 374页第 7题
54
请提问
