当前位置:文档之家› 第6讲 第4章马尔科夫链

第6讲 第4章马尔科夫链


P=
2 1/3 1/3 1/3 0 0
3
0
1/3 1/3 1/3
0
1
2
345源自4 0 0 1/3 1/3 1/3
5 0 0 0 0 1
.
称状态 5 为吸收态。 吸收态是位于对角线上的概率1所对应的状态。 吸收态也是马尔科夫链研究的一个问题。 ---- 但是本教材对此不作过多讨论
.
例4.3 无限制随机游动
质点在数轴的整点上做随机游动,每次移动一格,向 右移动概率为p,向左移动概率为q(p+q=1), X n 表 示质点在n时所处的位置,则 Xn 是一齐次马尔科夫链, 写出一步和k步转移概率。
解 状态空间I={0,±1,±2,…}
pi,i1 p,
pi,i1 q,
M M M M L
L
0
p
L
P L q 0 p
L
q
0
p
L
MMMM
.
例4. 生灭链
某种生物群体在n时刻的数量为 X n ,n时刻有 量时,到n+1时刻增加到 i 1 个数量的概率为
i 个数
bi ,
减少到 i 1 个数量的概率为 ai ,保持数量不变的概
率为 ri 1 ai bi 。 a0 0
则 Xn ,n 0 是齐次马尔科夫链。
状态空间I={0, 1,2,…}
P X 0 i0 P X n1 i1 | X 0 i0 L P X nm im | X 0 i0 ,L X nm1 im1
在甲获得1分的情况下, 再赛2局比赛结束的概率: p(1 r) .
.
注1:为方便,我们也可把这5个状态依次用序号表示。
比如 p23表示:甲现处于第二个状态,一步后变为第3
个状态的概率,即
p23 P Xn1 0 | Xn 1 p
那么,在甲获得1分的情况下, 再赛2局比赛结束的概率
就是:p
p(2) 45
p(2) 41
p(1 r ) .
特别提醒: Markov链中有 X n i 时, 有时表示实际状态值是 i ,有时表示状态的序号是 i 。
需要根据表达的方便而定,必要时需要说明。
.
注2:若没有要求计算2步转移概率,只求在甲的1分时,
最多再赛两局可以结束的概率,则可以这样算:
p(2) 45
上面这种游动称为带有两个反射壁的随机游动. 1和5这两点称为反射壁.
.
若将游动的概率规则作如下变动: 质点1、2、3、4的游动规则不变; 质点一旦到了5点,便永远停在5点,游动结束。
(此时5点称为吸收壁).
则只须把P 中第5行改为 (0,0,0,0,1).
便得到相应链的转移概率矩阵:
12345
1 0 1 0 0 0
0
显然,0步转移概率矩阵也随机矩阵。
.
例4.5 无限制随机游动
质点在数轴的整点上做随机游动,每次移动一格,向 右移动概率为p,向左移动概率为q(p+q=1), Xn 表 示质点在n时所处的位置,则 Xn 是一齐次马尔科夫链, 写出一步和k步转移概率。
解 状态空间I={0,±1,±2,…}
M M M M L
P{X (l) k | X (0) i}P{X (n) j | X (0) i, X (l) k}
k
P{X (l) k | X (0) i}P{X (n) j | X (l) k}
k
p p (l ) (nl ) ik kj
马氏性
k
证毕!
.
注: 令l 1 得: P(n) PP(n1)
p11 n
P (n)
p21
n
pi 1 n
p
n
12
p22 n
pi
2
n
p1
j
n
p1
j
n
pij n
为n步转移概率矩阵。
显然,n步转移概率矩阵也是随机矩阵。
注意到 pij1 pij
P(1) P
.
特别规定:
0步转移概率为:
p (0) ij
0 1
i j i j
1 0
0
0步转移概率阵为: P (0 ) 0 1
0
0 0
q
r
p
0
0
p
p(1 r)
1
1
p(2) 41
0 0
q
r
p
q
0
0
0
0
p
p(2) 45
p(2) 41
p(1 r ) .
.
24
三、 一维分布、有限维分布
X n的分布律:
P X n j P X 0 k P X n j | X 0 k k P X 0 k pkjn j I k
定理4.3 齐次马尔科夫链的有限维分布
(1)P X 0 i0, X n1 i1, X n2 i2,L , X nm im
p p p ... p n1
n2 n1
i0 i0i1
i1i2
nm nm1
im1im
(2)P X n1 i1, X n2 i2,L , X nm im
一般情况下,转移概率不仅与i,j有关,还与n有关.
而当此概率与n无关时, 称转移概率具有平稳性. 也称此马尔科夫链是齐次的或时齐的. 本章以后讨论的马氏链都是齐次的.
.
设 {X n n T}是齐次马尔科夫链,
pij P{Xn1 j | Xn i} i, j I
称为该Markov链的转移概率。
.
例4.1(简单信号模型)在某数字通讯系统中,只传输0、1 两种信号,且传输要经过很多级.每级中由于噪声的 存在会引起误传.假设每级输入0、1信号后,其输出 不产生误传的概率分别为0.7、0.6 .记 (n) 为第 n 级的输出信号. 则 {(n),n 0} 是状态有限的马尔科 夫链,求其一步转移概率矩阵.
2 pr r2 2 pq
2qr 0
p2 2 pr r2 pq 0
0
p2
p
1
pr
(3)在甲获得1分的情况下, 再赛2局,甲胜而结束的概率:
P Xn1 2 | Xn 1 p pr p(1 r )
在甲获得1分的情况下, 再赛2局,甲负而结束的概率:
P Xn1 -2 | Xn 1 0
乙胜的概率为 q ,平局的概率为 r ( p q r 1)
每局赛后胜者计1分,负者计-1分,平局不计分, 比赛中有人得2分时,比赛结束。
Xn 表示比赛 n 局后,甲的累积得分,n 1, 2,L .
( 1) 写出状态空间; ( 2) 求2步转移概率; ( 3) 问在甲获得1分的情况下, 最多再赛2局可以 结束的概率.
若记: pj P X 0 j, n 1,2L
P0 p1, p2 ,L
记: pj n P X n j, n 1,2L
Pn p1 n, p2 n,L
称 P0 p1, p2,L 为初始概率向量
称 Pn p1 n, p2 n,L 为绝对概率向量 .
定理 马尔科夫链的一维分布(绝对分布)
第四章 马尔可夫链
无后效性的过程称为马尔科夫过程。 主要研究三类: (1)时间和状态都离散的马尔科夫过程称为马尔可夫链.
(2)时间连续、状态离散的马尔科夫过程称为纯不连续 的马尔科夫过程。
(3)时间和状态都连续的马尔科夫过程。
本章讨论马尔可夫链.
主讲人:
.
§4.1 马尔科夫链定义及基本问题
一、马尔可夫链的定义和转移概率 马尔科夫链的无后效性描述为: 定义4.1: 设随机序列 {X n X (n), n 0,1, 2,L }
L
0
p
L
P L q 0 p
L
q
0
p
L
MMMM
.
下面求 pijk
设质点自状态 i 向右移动 x 步,向左移动了k x 步, 到达状态 j ,则有
i x (k x) j
x jik 2
k为偶数时
pij k
=
Ckx
p
x qk x 0
j i为偶数 其它
k为奇数时
pij k
=
Ckx
Pn P0 Pn
或 pj n P X n j pk pkjn
k
注 由C-K方程,该定里的结论还可以写为:
Pn P0 Pn P0 Pn1P Pn 1 P
或: pj n pk n 1pkj
k
该定理表明:绝对分布由初始分布和一步转移概率确定
请将定理及注的结论与定理4. .2的结论对照!
P
p11
p21
p12 p22
p1 j
p1 j
pi1
pi2
pij
称为该该Markov链的转移概率矩阵。
.
由于Markov从任一状态i出发,下一步必停留在某一状 态,所以有:
1 pij 0 2 pij 1, i 1, 2,L . jI
---符合上述条件的矩阵称为随机矩阵。 所以,Markov的转移概率矩阵是随机矩阵。
0 l n T1,有 P(n) P P (l ) (nl )

p (n) ij
p p , (l ) (nl ) ik kj
i,
j 1, 2,L .
k
.
证明
P (n) ij
P{X (n)
j
|
X (0)
i}
P{X (l) k, X (n) j | X (0) i}
k
条件概率的 乘法公式
有关,即 P{X n1 j | X n i} 不依赖于 n 。
所以 Xn 是齐马尔可夫链.
.
状态空间I={1,2,3,4,5}, 转移概率矩阵为:
相关主题