当前位置:文档之家› 马尔可夫链

马尔可夫链

2020年5月21日星期四
例7 设马氏链{Xn}的状态空间为 I={1, 2, 3, 4, 5}, 转移概率矩阵为
1 2
1
2
0 0
0
1 2
1 2
0
0
0
P 0 0 1 0 0
3 / 16 . 1/ 4
于是: (1) P{X0 0, X2 1}
P{ X0 0}P{ X2 1 | X0 0} 1 5 5 ;
3 16 48
2020年5月21日星期四
(2)P{X2 1}
P{X0 0}P{X2 1 | X0 0} P{X0 1}P{X2 1 | X0 1}
显然有
p(n) 11
p(n) 21
P(n)
p(n j1
)
L
p(n) 12
p(n) 22
p(n) 1j
L
p(n) 2j
L
p(n) j2
p(n) jj
L
LL
L
(1)
0
p(n) ij
1
(2)
p(n) ij
1,
i
1,
2,L
j
2020年5月21日星期四
切普曼-柯尔莫哥洛夫方程(C-K方程): 对任意的m,n≥0,有
的矩阵
p11 p21
P
L
pj1 L
p12 L p22 L LL pj2 L LL
p1 j L
p2 j L
L
L
p jj L
L L
称为一步转移概率矩阵. 显然有
(1) 0 pij 1
(2)
pij 1, i 1, 2,L
j
2020年5月21日星期四
3、马尔可夫链举例
例1 一维随机游动 一随机游动的质点在如图所示直线的点集 I {1,2,3,4,5}上作随机游动,并且仅仅在1秒、2秒 等时刻发生游动.
P{X0 2}P{X2 1 | X0 2}
1 3
5 16
1 2
9 16
11 .
24
2020年5月21日星期四
例4 设任意相继的两天中, 雨天转晴天的概率为 1 3, 晴天转雨天的概率为1 2, 任一天晴或雨是互 为逆事件. 以0 表示晴天状态,以1表示雨天状态, Xn 表示第n天状态 ( 0或1). 试写出马氏链{ Xn , n 1} 的一步转移概率矩阵. 又已知5月1日为晴 天 ,问5月3日为晴天, 5月5日为雨天的概率各等 于多少? 解 由于任一天晴或雨是互为逆事件且雨天转 晴天的概率为1 3, 晴天转雨天的概率为1 2,
以Xn表示第n次抽取后甲袋的球数,n=1,2,… 则{Xn,n=1,2,…}是一随机过程,I={0,1,2,3,4,5}, 且当Xn=i时,Xn+1=j的概率只与i 有关,与n时刻 之前的结果是无关的,从而是一个齐次马氏链.
其一步转移概率矩阵为:
2020年5月21日星期四
0 1 2 34 5
0
1
故一步转移概率矩阵为
2020年5月21日星期四
又由于
01
P
0 1 1 1
2 3
1 2 2 3
0
1
P (2)
0 1
5 7
12 18
7 12 11 18
故 5月1日为晴天, 5月3日为晴天的概率为
p(2) 00
5
12
0.4167 ,
2020年5月21日星期四
又由于
0
P (4)
0 0.4005 1 0.3997
注:可达关系与互通关系都具有传递性 (1) 若ij , jk ,则ik ; (2) 若ij , jk ,则ik .
2020年5月21日星期四
定理 若ij ,则 (1) i与j同为常返或非常返,如为常返,则它们同 为正常返或零常返; (2) i与j有相同的周期.
1
1
1
22
1 2
1
3
4
1
2020年5月21日星期四
二、马尔可夫链的状态分类
设{Xn, n0}是齐次马尔可夫链,pij为转移概率, i,jI,I={1,2,}为状态空间,{pi, i I}为初始分布. 定义 状态i的周期d:
d=G.C.D{n:n≥1, p(n) >0} ii
(最大公约数greatest common divisor) 如果d >1,就称i为周期的; 如果d =1,就称i为非周期的.
P{ X n+1 j | X0 i0 , X1 i1, , X n1 in1 , X n i, }

P{ Xn1 j | Xn i} = Pij . Pij表示处于状态i的过程下一步转移到状态j的概率.
2020年5月21日星期四
具有这种平稳转移概率的马尔可夫链称为齐次的
Pij称为一步转移概率,由所有的一步转移概率构成
非周期的正常返态称为遍历状态.
例:判断下面马氏链各状态的类型
1
1
1
22
1 2
1
3
4
1
2020年5月21日星期四
马氏链状态分类图
状态空间
周期
非周期
常返
非常返
正常返
零常返
遍历
2020年5月21日星期四
状态的可达与互通 如果存在n>0,使 pi(jn),称 自0 状态i可达状态j ,
并记为 i j. 如果 i j且j i, 则称i与j 互通,记为 i j.
以Xn表示时刻 n时Q的位置,则{X n,n 0,1, 2,L } 是一个齐次马氏链. 其状态空间就是 I .
2020年5月21日星期四
一维随机游动的演示
单击图形播放/暂停 ESC键退出
2020年5月21日星期四
一步转移概率 pij P{ Xn1
j
|
Xn
i}
1 13,
,
ji i 1,
1, j
初始分布P{X0 i} 1 / 3, i 0,1,2.
试求 : (1)P{X0 0, X2 1}; (2)P{X2 1}.
2020年5月21日星期四
解 先求出二步转移概率矩阵
012
0 5/8
P(2) P2 1 5 / 16
2 3 / 16
5 /16 1/ 2 9 /16
1 / 16
1 0.5995 0.6003 ,
故 5月1日为晴天, 5月5日为雨天的概率为
p(4) 01
0.5995.
2020年5月21日星期四
课堂练习
设齐次马氏链的转移概率矩阵为
1 3
1 3
1 3
0
(1) 问马尔可夫链有几个 状态?
1 P 12
1
2 1
0 0
0
1
.
(2) 问从第二状态至少几 步才能到第三状态?
P{ X 0
i0 , X1
i1,L
, X n1
i } P n1
in1 ,in
P P P L P . i0 i0 ,i1 i1 ,i2
in1 ,in
5月21日星期四
5、切普曼-柯尔莫哥洛夫方程
在齐次条件下,可得到n步转移概率
p(n) ij
P{ X mn
j|
Xm
i}
由所有的n步转移概率就可得到n步转移概率矩阵
注:(1) 若状态i为非常返的,则由该状态出发将
以1-fii的概率永不返回.
(2) 若状态i为常返的,则 f (n), n构 1成一 ii
概率分布,其期望值为
i
nf (n) ii
n1
表示由i出发再返回到i的平均返回时间(步数).
2020年5月21日星期四
定义 设i为常返态
若i <,则称常返态i为正常返的; 若i =,则称常返态i为零常返的.
12345 游动的概率规则 如果 Q 现在位于点i(1 i 5), 则下一时刻各1 的概率向左或向右移动一格,
3 或以1的概率在原处;
3
2020年5月21日星期四
12345 如果Q现在位于1(或5)这点上, 则下一时刻就以概率1 移动到 2(或4)这一点上 . 1和5这两点称为反射壁. 上面这种游动称为带有两个反射壁的随机游动. 理论分析:
i, i 1, 1 2 或 i 5,
i j
5 4
0, j i 2.

12345
步 转 移
1 0 1 0 0 0
2 1 / 3 1 / 3 1 / 3 0
0

P 3 0 1/3 1/3 1/3 0
率 矩
4
0
0 1 / 3 1 / 3 1 / 3

5 0 0 0 1 0
2020年5月21日星期四
例6 设马氏链{Xn}的状态空间I={0,1,2,},转
移概率为
1
1
1
p00
2
,
pi ,i1
, 2
pi 0
2
,i
I
试讨论各状态的常返性和周期性.
解:根据题意作出状态转移图如下
1
1
1
1
1
2
2
2
2
20
1 2
11
2
3
2 1
2
2020年5月21日星期四
f (1) 00
1 2
,
f (2) 00
1 2
1 2
2020年5月21日星期四
例5 设马尔可夫链的状态空间I={1,2,3,4},转移概 率如下图
1
1
1
22
1
3
4
1
1
2
易得状态2和3有相同的周期d=2.但是从状态3出发
经两步必定返回状态3,而从状态2出发一旦转移
相关主题