i, j S
pij (m) P{X m1 j | X m i} i, j S
一、马尔可夫链的定义
1、马尔可夫链的定义
➢k步转移概率
p(
k
) ij
(m)
P{X mk
j
|
Xm
i}
➢通常规定
i, j S
p(0) ij
(m)
ij
1 0
➢转移概率矩阵
i j i j
P( k )
{
p(k
) ij
(m),
j
四、遍历性机及平稳分布
2、平稳分布
✓定义 设{Xn=i}为齐次马氏链，概率分布pi，满足
p j pi pij j 0,1, 2,
i
其中， pi为平衡分布
➢ pj≥0
➢
pj 1
j
➢
n 时，pj j
四、遍历性机及平稳分布
2、平稳分布 对于平稳分布，有
p j pi pij ( pk pki ) pi ( pk pki )
P (m1) [ pij(m1) ]NN [
p p ] (m) (1) ik kj N N
P m1 P
P m1
kS
P(k) Pk
二、切普曼－科尔莫戈洛夫方程
✓定理 设 {X n , n N为}马尔可夫链。其状态空间为S, 且 0 n1 n2 ，n则k Xk的k维概率分布为
P{X n1 i1, X n2 i2 , , X nk ik }
i
in
k
i
pk
p (2) kj
k
pk
p (k) kj
k
➢另外 [1 2 n ] P pij
则 P
五、马尔可夫序列
✓定义 设一个随机序列Xn连续，有
F(xn xn1, , x1) F(xn xn1)
则称此随机序列为马尔可夫序列 其条件概率密度为
f (xn xn1, , x1) f (xn xn1) ➢齐次性 f (xn xn与1) n无关 ➢平稳性 f (xn ) f (x)
➢时间参数t→可连续、可离散
一、马尔可夫链的定义
1、马尔可夫链的定义
✓定义 设 {X n , n N为} 一随机序列，时间参集 N {0,1,，2, }
其状态空间 I {a1, a2, , a，N若}
P{X n
ain
|
X n1
a , X in1
n2
a , in2
, X1 ai1 } P{X n ain | X n1 a } in1
p P{X (nk nk1 )
ik 1ik
0
j, X n1
i1 , X n2
i2 ,
jS
, X nk1 ik 1}
p p P{X j, X i , X i , (nk nk1 ) (nk1 nk2 )
ik 1ik
ik 2ik 1
0
n1
1
n2
2
jS
, X nk2 ik 2 }
p p (nk nk1 ) ik 1ik
f (xn,tn xn1,tn1 , , x1,t1) f (xn,tn xn1,tn1)
P[ X (tn ) xn X (tn1) xn1 , , X (t1) x1] P[ X (tn ) xn X (tn1) xn1]
式中 t1 t2 , , tn
➢状态→取值 ➢状态空间→所有的取值(可连续、可离散)
则称{X n , n N 为} 马尔可夫链。
一、马尔可夫链的定义
1、马尔可夫链的定义 ✓转移概率
pij (m, n) P{X n a j | X m ai} P{X n j | X m i}
➢性质
pi j (m, n) 0 i, j S
pi j (m, n) 1 i S
jS
➢一步转移概率 当n=m+1时，则
( nk1 nk2 ) ik 2ik 1
jS
p p (nk nk1 ) ik 1ik
( nk1 nk2 ) ik 2ik 1
jS
p P{X (n2 n1 )
i1i2
n1
i1, X 0
j}
p p P{X j} (n2 n1 ) (n1 )
i1i2
ji1
0
三、马尔可夫链中的状态分类
1、状态可达和相通
Tij () min{n : X0() i, Xn () j, n 1}
其中，Tij表示从状态i出发，首次进入状态j的时间
Tij ()
终生等待
四、遍历性机及平稳分布
1、遍历性
✓定义 设{Xn=i}为齐次马氏链，对一切状态i，j有
lim
n
pij n
j
其中，πj为平稳分布
➢ πj≥0
➢
j 1
p23 p33
二、切普曼－科尔莫戈洛夫方程
切普曼－柯尔莫哥洛夫方程
p(mr ij
)
(n)
pi(km) (n) pk(jr) (n m)
kS

i, j S
对于齐次马尔可夫链，切普曼－柯尔莫哥洛夫方程
P (2) [ pij(2) ]NN [ pik pkj ]NN P P = P 2 kS
✓ 状态可达 由状态i到状态j，Pij(k) 0，记为i→j
✓ 定理 由i→k，k→j，则i→j ✓ 状态相通 状态i→状态j，且状态j→状态i，记为 i j ✓ 定理 由状态i→状态k，状态k→状态j，则状态i→状态j
三、马尔可夫链中的状态分类
2、首次进入时间
对于任何两个状态i和j，在事件{X0=i}上引入随机变量
第7章 马尔可夫链
马尔可夫链
一、马尔可夫链的定义 二、切普曼-柯尔莫哥洛 夫方程 三、马尔可夫链中状态分类 四、遍历性与平稳分布 五、马尔可夫序列
一、马尔可夫链的定义
马尔可夫过程
F (x1, x2 , , xn;t1, t2 ,
则马尔可夫过程可描述为
n
tn ) F (xi )(xi , ti ) i 1
i,
j
S}
k步转移概率矩阵
一、马尔可夫链的定义
2、齐次马尔可夫链 ✓定义 pij (m) P{X m1 j | X m i} pij i, j S
pi
(k
j
)
(m)=pi
j
(k
)
i, j S
➢一步转移概率矩阵
p11 p12 p13
P
{
pij
,
i,
j
S}
p21 p31
p22 p32