研究生课件_马尔科夫链

= pkj (nl)(m +l)pik (l)(m) = p p ik (l) kj (nl)
kI
kI
4.1 马尔可夫链与转移概率
(2)在(1)中令l=1,k=k1,得
p
(n) ij
=
p p (1) (n1) ik1 k1j
由此可递推出公式kI(3)矩阵乘法 (4)由(3)推出 说明： (1)此为C-K方程(切普曼-柯尔莫哥洛夫) (2) n步转移概率由一步转移概率确定，
初始概率
pj = P{X0 = j}
绝对概率 pj(n)= P{ Xn = j }
初始分布
{pj , jI}
绝对分布
{pj(n), jI}
初始概率向量
pT (0) = (p1, p2, )
绝对概率向量 pT (n) = (p1(n), p2(n), )
4.1 马尔可夫链与转移概率
二、基本性质 命题： P{X0=i0, X1=i1, , Xn=in} =P{Xn=in|X0=i0, X1=i1, , Xn-1=in-1}
ub = (u1 1) 1r
= 1rc
4.1 马尔可夫链与转移概率
例4.3 天气预报问题 RR表示连续两天有雨，记为状态0 NR表示第1天无雨第2天有雨，记为状态1 RN表示第1天有雨第2天无雨，记为状态2 NN表示连续两天无雨，记为状态3
p00=P{R今R明| R昨R今}=P{R明| R昨R今}=0.7 p01=P{N今R明| R昨R今}=0
4.1 马尔可夫链与转移概率
★若t1, t2, , tn-2表示过去，tn-1表示现 在，tn表示将来，马尔可夫过程表明： 在已知现在状态的条件下，将来所处的 状态与过去状态无关。
过去 现在 将来
4.1 马尔可夫链与转移概率
马尔可夫过程通常分为三类：
(1) 时间、状态都是离散的，称为马尔 可夫链 (2) 时间连续、状态离散的，称为连续 时间马尔可夫链 (3) 时间、状态都是连续的，称为马尔 可夫过程
= u1 u0 = ˆ
4.1 马尔可夫链与转移概率
(ui+1 ui)+(ui ui1)+(ui1 ui2)+
+(u1 u0) = (i +1)
即ui+1 u0 = (i +1)
ui+1 = u0 +(i +1) =1+(i +1)
uc =1+c = 0 = 1
(4) PT(n)= PT(n-1)P
4.1 马尔可夫链与转移概率
证明：(1)
pj(n) = P{Xn = j}= P{X0 = i, Xn = j}
iI
= P{Xn = j | X0 = i}P{X0 = i}
iI
=
iI
(n) ij i
p
p
4.1 马尔可夫链与转移概率
(2)
pj(n) = P{Xn = j}= P{Xn1 = i, Xn = j}
2步转移概率矩阵为
一 二 三四
R R RR
0
0
R R NR
0
1
0.49 0.12 0.21 0.18
P (2)
2
=P
0.35 = 0.20
0.20 0.12
0.15 0.20
0.30 0.48
0.10 0.16 0.10 0.64
4.1 马尔可夫链与转移概率
例4.4 具有吸收壁和反射壁的随机游动 状态空间{1,2,3,4}，1为吸收壁，4为反射 壁
pin1in
1
1
n
n
= P{X0 = i, X1 = i1, , Xn = in} iI
= P{X0 = i}P{X1 = i1 | X0 = i} iI
P{X2 = i2 | X1 = i1} P{Xn = in | Xn1 = in1}
= p p p i ii1 i1i2 iI
P= p20
p21
p22
p23

=

0
0.4
0
0.6
p30 p31 p32 p33 0 0.2 0 0.8
若星期一、星期二均下雨，求星期四下雨 的概率
4.1 马尔可夫链与转移概率
星期四下雨的情形如右，
星期四下雨的概率
p
=
p (2) 00
+
p (2) 01
= 0.49+0.12 = 0.61

p11
p12
p21 p22
P =
pm1 pm2
★转移概率满足
(1) pij 0,i, jI
P称为随机矩阵
p1n

p2n



pmn



(2) p ij =1,iI
jI
4.1 马尔可夫链与转移概率
(n) ij
为马尔可夫链{Xn，nT }的n步转移概率 (i,jI, m 0, n 1)。
（甲在状态i下输光：甲赢一局后输光或甲
输一局后输光）
4.1 马尔可夫链与转移概率
(p+q)ui = pui+1 +qui1 p(ui+1 ui) = q(ui ui1)
q ui+1 ui = (ui ui1)
p i =1,2, ,c 1
(1) q =1,即p = q = 1
p
2
ui+1 ui = ui ui1 = ui1 ui2 =
第四章 马尔可夫(Markov)链
4.1 马尔可夫链与转移概率
一、基本概念
定义4.0 设 {X(t)，t T }为随机过程， 若对任意正整数n及t1< t2<< tn， P{X(t1)=x1,, X(tn-1)=xn-1}>0，且条件 分布P{X(tn)xn|X(t1)=x1,, X(tn-1)=xn1}= P{X(tn) xn|X(tn-1)=xn-1}，则称 {X(t)，t T }为马尔可夫过程。
c
ui =1+i =1 i
c
ua =1
a c
=b a +b
,同理可得ub =
a a +b
4.1 马尔可夫链与转移概率
(2) q 1,即p q,设 q = r
p
p
ui+1 ui = r(ui ui1)
c1
c1
i=k
i=k
=
(u1
1)
r k rc 1r
4.1 马尔可夫链与转移概率
iI
= P{Xn = j | Xn1 = i}P{Xn1 = i}
iI
= pi(n1)pij
iI
(3)(4)为(1)(2)的矩阵表示。
4.1 马尔可夫链与转移概率
定理4.3 设{Xn，nT }为马尔可夫链，则
对任意整数i1, i2,,inI和n 1 有
P{X1 = i1, , Xn = in}= p p p i ii1 i1i2 iI
pin1in
三、应用举例
4.1 马尔可夫链与转移概率
例4.1
无限制随机游动
q
p
-1
0
1
i-1
i
i+1
一步转移概率:
pi,i+1 = p
pi,i1 = q =1 p
pii = 0
4.1 马尔可夫链与转移概率
k步转移概率:
i经过k步进入j,向右移了x步,向左移了y步
则
k +(j i)
x + y = k
n步转移概率矩阵由一步转移概率矩阵 确定(n次幂)
4.1 马尔可夫链与转移概率
定理4.2 设{Xn，nT }为马尔可夫链， 则对任意整数jI和n1 ，绝对概率
pj(n)满足
(1) pi j(n(inj )) = p p
iI
(2) pj (n) = p (ni 1)p ij
iI
(3) PT(n)=PT(0)P(n)
P{X0=i0, X1=i1, , Xn-1=in-1} = P{Xn=in|Xn-1=in-1}
P{Xn-1=in-1 |X0=i0,X1=i1,,Xn-2=in-2} P{X0=i0,X1=i1,,Xn-2=in-2}
=P{Xn=in|Xn-1=in-1}P{Xn-1=in-1 |Xn-2=in-2} P{X0=i0,X1=i1,,Xn-2=in-2}
(n)
(1)
p (n) ij
=
p
p(l) (nl)
ik kj
kI
(2)p
(n) ij
=
p pikk11k2
k1I kn1I
(3) P(n)=PP(n-1)
(4) P(n)=Pn
pkn1j
4.1 马尔可夫链与转移概率
证明：(1)
{ p
(n) ij
+ = }= = =n m X P m { i X{j |
状态转1 移图
1 3
11
3
2
1
1 3
3
1
4
3
1
1 3
3
状态转移矩阵
1 1
3
P = 0
1 3
i
n n＋1 T
4.1 马尔可夫链与转移概率
定义4.3：若对任意的i,jI，马尔可夫链{Xn, nT }的转移概率pij(n)与n无关，则称马 尔可夫链是齐次的，并记pij(n)为pij。
I 5 4 3 2 1
01
2 3 4 5T
4.1 马尔可夫链与转移概率
齐次马尔可夫链具有平稳转移概率，状态空间 设为I={1, 2, 3, }，一步转移概率矩阵为