于是: (1)
P{X 0 0, X 2 1}
P{ X 0 0}P{ X 2 1 | X 0 0}
1 5 5 ; 3 16 48
基础部张守成 2014年6月27日星期五
(2) P{X 2 1}
P{X0 0}P{X 2 1 | X0 0} P{X0 1}P{X 2 1 | X 0 1}
第四章 马尔可夫链
基础部张守成
一、马尔可夫链的定义和转移概率
1、马尔可夫性(无后效性)
当已知随机过程在时刻 t i 所处的状态的条件下, 过程在t(>ti)所处的状态与过程在时刻ti以前所处的 状态无关,这种特性称为马尔可夫性或 “无后效性”. 具有马尔可夫性的随机过程称为马尔可夫过程. 过程“将来”的情况和“过去”的情况 无关.
( 2) 问从第二状态至少几 步才能到第三状态 ?
(3) 求2步转移概率矩阵.
基础部张守成 2014年6月27日星期五
解
(1) 有4个状态
(2) 从第二状态至少2步才能到第三状态
13 36 5 12 PP 5 24 1 4 13 36 5 12 11 14 1 2 1 9 1 6 1 12 0 1 6 0 . 1 4 1 4
(4) p01 0.5995.
基础部张守成 2014年6月27日星期五
课堂练习
设齐次马氏链的转移概率矩阵为
1 3 1 P 2 1 4 0 1 1 3 3 1 0 2 1 0 4 1 0 2 0 0 . 1 2 1 2
(1) 问马尔可夫链有几个 状态?
一步转移概率
基础部张守成 2014年6月27日星期五
说明: 改变游动的概率规则,就可得到不同方式的 随机游动和相应的马氏链. 如果把1改为吸收壁，即一旦到达1点，将永 远留在1点,相应链的转移概率矩阵只需把P的第 一行改成 (1,0,0,0,0).
基础部张守成 2014年6月27日星期五
例2 取球问题 有甲、乙两袋球,开始时甲袋有3只球,乙袋有 2球；以后,每次任取一袋,并从袋中取出一球放入 另一袋(若袋中无球则不取). 以Xn表示第n次抽取后甲袋的球数,n=1,2,… I={0,1,2,3,4,5}, 则{Xn,n=1,2,…}是一随机过程， 且当Xn=i时,Xn+1=j的概率只与i 有关，与n时刻 之前的结果是无关的，从而是一个齐次马氏链. 其一步转移概率矩阵为：
P{ X n1 j | X n i } = Pij .
Pij表示处于状态i的过程下一步转移到状态j的概率.
基础部张守成 2014年6月27日星期五
, n}.
,in1 ,i , j I
P{ X n+1 j | X 0 i0 , X1 i1， , X n1 in1 , X n i ,}
解 由于任一天晴或雨是互为逆事件且雨天转
晴天的概率为 1 3 , 晴天转雨天的概率为 1 2 ,
故一步转移概率矩阵为
基础部张守成 2014年6月27日星期五
0
1
0 1 2 1 2 P 1 1 3 2 3
又由于
0 P
( 2)
1
0 5 12 7 12 1 7 18 11 18
P ( m n) P ( m ) P ( n)
即n步转移概率矩阵等于一步转移概率矩阵自乘n次. 为了数学处理便利，通常规定
p
(0) ij
1 i j P{ X m j | X m i } 0 i j
基础部张守成 2014年6月27日星期五
例3 { X n , n 0}是具有三个状态 0,1,2 的齐次马氏
链 , 一步转移概率矩阵为
0
1
2
0 3 / 4 1 / 4 0 P 1 1 / 4 1 / 2 1 / 4 , 2 0 3 / 4 1 / 4
初始分布P{X 0 i} 1 / 3, i 0,1,2.
试求 : (1) P{X 0 0, X 2 1};
(2) P{X 2 1}.
基础部张守成 2014年6月27日星期五
解
先求出二步转移概率矩阵 0 1
P (2)
2
0 P2 1 2
5 / 8 5 / 16 1 / 16 5 / 16 1 / 2 3 / 16 . 3 / 16 9 / 16 1 / 4
n 1

基础部张守成 2014年6月27日星期五
定义
若fii=1，称状态i为常返的；
若fii<1，称状态i为非常返的.
(1) 若状态i为非常返的,则由该状态出发将 注： 以1-fii的概率永不返回. (2) 若状态i为常返的,则 f 概率分布，其期望值为
i nf ( n )
n 1
ii
基础部张守成 2014年6月27日星期五
例5 设马尔可夫链的状态空间I={1,2,3,4}，转移概 率如下图
1
1
1 2
2
1 2
1
3 4
1
易得状态2和3有相同的周期d=2.但是从状态3出发 经两步必定返回状态3，而从状态2出发一旦转移 到状态3后再也不能返回状态2.
为了区别这两种状态，下面引入常返性概念
故 5月 1日为晴天 , 5月3日为晴天的概率为
p
(2) 00
5 12 0.4167,
基础部张守成 2014年6月27日星期五
又由于 P
(4)
0
1
0 0.4005 0.5995 , 1 0.3997 0.6003
故 5月 1日为晴天 , 5月 5日为雨天的概率为
基础部张守成 2014年6月27日星期五
5 1 2 4 3 如果Q现在位于 1 （或5 ）这点上， 则下一时刻就以概率 1 移动到 2 （或4 ）这一点上 . 1和5这两点称随机游动.
理论分析:
以X n表示时刻 n时Q的位置，则 {X n，n 0,1, 2, }
记
具有这种平稳转移概率的马尔可夫链称为齐次的 Pij称为一步转移概率，由所有的一步转移概率构成 的矩阵
p11 p21 P p j1 p12 p22 pj2 p1 j p2 j p jj
称为一步转移概率矩阵. 显然有
(1)
(2)
0
基础部张守成 2014年6月27日星期五
4、齐次马氏链的性质
定义：记 pi P X0 i , i I , 称为齐次马氏链的初始分布. 定理: 齐次马氏链完全由其初始分布和一步转移 概率矩阵确定. 证 P{ X 0 i0 , X1 i1 , , X n in }
P{ X 0 i0 , X1 i1 ,
0 pij 1
p
j
ij
1, i 1, 2,
基础部张守成 2014年6月27日星期五
3、马尔可夫链举例
例1 一维随机游动 一随机游动的质点在如图所示直线的点集
I {1,2,3,4,5}上作随机游动,并且仅仅在1秒、 2秒
等时刻发生游动 .
1 2
3
4
5
游动的概率规则 如果 Q 现在位于点 i (1 i 5), 1 则下一时刻各 的概率向左或向右移动 一格， 3 1 或以 的概率在原处； 3
(n)
ii
,n 1
构成一

表示由i出发再返回到i的平均返回时间(步数）.
基础部张守成 2014年6月27日星期五
定义 设i为常返态 若i <，则称常返态i为正常返的; 若i =，则称常返态i为零常返的.
P{ X 0 i0 , X1 i1 , P{ X 0 i0 , X1 i1 ,
, X n1 in1 }
P{ X n in X0 i0 , X1 i1 ,
, X n1 in1 }
, X n1 in1 } P{ X n in X n1 in1 } , X n1 in1 } Pi
基础部张守成
2、马尔可夫链的定义和转移概率
参数和状态都是离散的马尔可夫过程称为马尔
记为 { X n X (n), n 0， 1, 2, }. 可夫链,简称为马氏链 ，
状态空间为可列 I {1, 2, }或有限 I {1, 2,
马氏链的马尔可夫性可具体描述为：
对于任意的n T , 任意的状态i0 ,i1 ,

P (n)

) p(jn 2
显然有
(1)
( n) p2 j p(jjn )
( n) p1 j
( n) p ij 1, i 1, 2, j
0 p
( n) ij
1
(2)
基础部张守成 2014年6月27日星期五
切普曼-柯尔莫哥洛夫方程(C-K方程): 对任意的m,n≥0,有
是一个齐次马氏链. 其状态空间就是 I .
基础部张守成 2014年6月27日星期五
一维随机游动的演示
单击图形播放/暂停 ESC键退出
基础部张守成 2014年6月27日星期五
1 3 , j i 1, i , i 1, 1 i 5 1, i 1, j 2 或 i 5, j 4 pij P{ X n1 j | X n i } 0, j i 2. 一 1 2 3 4 5 步 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 1 0 0
(3)
P (2)