P(n1 n2 ) P(n1 )P(n2 ) P n1 n2 (1)
kI
pij (n1 n2 ) pik (n1 ) pkj (n2 )
p ( n) p ( s ) P ( s, n)
p ( n) p ( s ) P ( n s ) p( s ) Π n s
0.7 0.3 举例： P(1) 0.4 0.6
0.61 0.39 P(2) 0.52 0.48
0.5749 0.4251 P(4) 0.5668 0.4332
0.5715 0.4285 P(8) 0.5714 0.4286
每 一 行 之 和 为 1
6
马尔可夫链
性质：
p j (n) P{ X (n) a j , X ( s ) ai }
N
P{ X ( s ) ai } P{ X (n) a j | X ( s ) ai }
pi ( s ) pij ( s, n)
i 1
则称该过程为马尔可夫链
, X (1) ai1 }
4
马尔可夫链
马尔可夫链的一般特性 状态概率： 状态概率分布列：
pi (n) P{X (n) ai }
p(n) p1 (n) p2 ( n) p N ( n)
状态转移概率： 状态转移矩阵：
pij (s, n) P{ X n a j | X s ai }Fra biblioteki 1 N
i 1 N
全概率公式
状态转移公式
p ( n) p ( s ) P ( s, n)
例如： p1 (n), p2 (n), p3 (n)
p11 ( s, n) p1 ( s ), p2 ( s ), p3 ( s ) p21 ( s, n) p31 ( s, n)
0 jc 设 u j 为质点从 j 出发到达 0 状态先于到达 c 考虑质点从 j 出发移动一步后的情况：
设 • 在以概率 状态的概率
•
j 1 的假设下， 到达 0 状态先于到达 c 状态的概率为 u j 1 在以概率 q 移到 j 1 的假设下， 到达 0 状态先于到达 c 状态的概率为 u j 1
j 1
N
状态转移矩阵
p11 ( s, n) p ( s , n) 21 P ( s , n) p N 1 ( s , n)
p12 ( s, n) p22 ( s, n) p N 2 ( s , n)
p1N ( s, n) p2 N ( s, n) pNN ( s, n)
q 1 p ，求甲输光的概率。
解：令 c a b ，则状态空间为 一步状态转移矩阵为
1 q P (1) 0 0 0 0 0 p 0 0 0 0
I {0,
, a,
, c}
0 0 0 0 0 0 q 0 p 0 0 1
15
马尔可夫链
马尔可夫性 一个随机过程如果给定了当前时刻 t 的值 X t ，如果 X s
( s t ) 的值不受过去的值 X u (u t ) 的影响，而仅与过
程在 t 时刻的状态有关，此特性称为随机过程的马尔可 夫性或无后效性。 在给定当前知识或信息的情况下，过去（即当前时刻之 前的历史状态）对于预测将来（即当前时刻之后的未来
p(n) p(1)
则此齐次链是平稳的。 判断方法： 若齐次链中 X (1) 和 X (2) 的概率分布列相同，则此链平稳。 证明：
p(2) p(1)
p(3) p(2)Π p(1)Π p(2) p(1)
以此类推
20
马尔可夫链
平稳分布
设有一有限状态的马尔可夫链，若存在一个正整数 m，使 得对状态空间的任何状态 i, j 有 pij ( m) 0 ，则存在平稳 分布
令 P(1) Π ，有 P(k ) Π k 由于
所以
对于齐次马尔可夫链，状态概率由初始概率和一步转移 概率决定。即利用初始分布和一步转移概率矩阵就能完 整地描述齐次马尔可夫链的统计特性。
11
马尔可夫链
例 分析用于表征通信系统的错误产生机制的马尔可夫模型，
假定其级数为2，求二步转移概率矩阵 。
p
移到
由全概率公式，得
u j pu j 1 qu j 1
u0 1, uc 0
16
该差分方程的边界条件为
马尔可夫链
u j pu j 1 qu j 1
( p q)u j pu j 1 qu j 1 p(u j u j 1 ) q(u j 1 u j )
P{ X (n) a j , X ( s) ai } P{ X (s) ai }
N

N k 1
P{ X (n) a j , X (r ) ak , X ( s ) ai } P{ X ( s ) ai }
P{X (n) a j , X (r ) ak , X (s) ai } P{X (r ) ak , X (s) ai } P{X (r ) ak , X (s) ai } P{X (s) ai } k 1
0 2 pr r 2 2 pq 2qr 0
0 p2 2 pr r 2 pq 0
0 0 p2 p rp 1
所求概率为 p45 (2) p41 (2)
14
马尔可夫链
例 赌徒甲有资本 a元，赌徒乙有资本 b元，两人进行赌
博，每赌一局输者给赢者1元，没有和局，直赌至两人中 有一人输光为止。设在每一局中，甲获胜的概率为 p，乙 获胜的概率为
马尔可夫过程
李勇
信息与通信工程学院 liyong@
马尔可夫过程
马尔可夫性的提出 有一类现象或过程有以下特点：在“现在”是已知的情 况下，这种变化过程的“未来”与“过去”是毫无联系
的。例如：
液体中颗粒的布朗运动 电话交换机的呼叫次数 天气的变化
马尔可夫
1
马尔可夫过程
r r d0 当 r 1 时，有 u j 1 r
j c
i j
c 1
c 1
i j
i j
当
r 1 时，有 u j (c j )d 0
18
马尔可夫链
两式比较，得
r r 当 r 1 时，有 u j 1 rc
j
c
故
当
综上 当
r 1 时，有
c j uj c
12
马尔可夫链
例 甲、乙两人进行比赛，设每局比赛中甲胜的概率是 p，
乙胜的概率是 q，和局的概率是 r，（
p q r 1）。
设每局比赛后，胜者记“+1”分，负者记“-1”分，和局 不记分。当两人中有一人获得2分结束比赛。以 X n 表示比 赛至第 n局时甲获得的分数。问在甲获得1分的情况下， 再赛二局可以结束比赛的概率是多少？ 解：先确定状态空间 记甲获得“负2分”为状态1，获得“负1分”为状态2， 获得“0分”为状态3，获得“正1分”为状态4，获得 “正2分”为状态5，则状态空间为
p11 ( s, n) P ( s , n) p N 1 ( s, n) p1N ( s, n) pNN ( s, n)
5
马尔可夫链
性质：
p ( n) 1
p
j 1
N
i 1 N
i
ij
( s, n) P{ X n a j | X s ai } 1, i
pij (s, n) pij (n s)
一步转移概率：
pij pij (1)
p1N (n s ) pNN (n s )
10
n s 步转移矩阵：
p11 (n s) P(n s ) pN 1 ( n s )
马尔可夫链
由C-K方程，有 证明：
p12 ( s, n) p22 ( s, n) p32 ( s, n)
p13 ( s, n) p23 ( s, n) p33 ( s, n) 7
马尔可夫链
切普曼－柯尔莫哥洛夫方程（C-K方程）
pij ( s, n) P{ X (n) a j | X (s) ai } (n r s )
状态）是无关的。
2
马尔可夫过程
马尔可夫过程的分类
X t
t
离散 马尔可夫链 离散马尔可夫过程
连续 马尔可夫序列 连续马尔可夫过程
离散 连续
3
马尔可夫链
马尔可夫链的定义 设随机过程 X ( n) 的状态空间为 I {a1 , a2 , }
若满足
P{ X (n k ) aink | X (n) ain , X (n 1) ain1 , P{X (n k ) aink | X (n) ain }
解：一步转移矩阵可写为
p
0 0
p q P(1) q p
二步转移矩阵为
q q
1
p
图6.2 二进制对称信道
1
2 2 p q p q p q 2 pq P(2) P(1)P(1)= = 2 2 q p q p 2 pq p q
P{ X (n) a j | X (r ) ak , X ( s) ai } P{ X (r ) ak | X ( s) ai } P{ X (n) a j | X (r ) ak } P{ X (r ) ak | X ( s) ai }
k 1 N k 1 N
可见 p() p(1)P() 不依赖于 p(1)