第6章-马尔可夫过程

第六章

马尔可夫过程

马尔可夫过程的一般概念



马尔可夫过程是一种重要的随机过程，它具有如下特性： 当 随 机 过 程 在 时 刻 ti 所 处 的 状 态 已 知 时 ， 过 程 在 时 刻 t(t>ti)所处的状态仅与过程在 ti时刻的状态有关，而与过 程在ti时刻以前所处的状态无关。此特性称为随机过程的 无后效性或马尔可夫性。此特性也可理解为：随机过程 X(t)在“现在”状态已知的条件下，过程“将来”的情况 与“过去”的情况无关。或者说，过去只影响现在，而不 影响将来。

P{将来|现在、过去}=P{将来|现在}

马尔可夫过程



举例：一维随机游动(Random Walk)

x

0

1 p

p

Xn  k

质点正向移动一个单位 质点反向移动一个单位



4 3 2 1 0

+ + + + +

P( X n 1  k  1| X n  k )  p

+

1

2

3

4

5

6

7

n

P( X n 1  k  1| X n  k )  q

3

马尔可夫过程的分类



按马尔可夫过程参数空间和状态空间的不同可分为

X t 

t

离散 连续

离散 马尔可夫链 离散马尔可夫 过程

连续 马尔可夫序列 连续马尔可 夫过程

马尔可夫链的定义



状态(ai, i=1,2,

…N)和时间参量都是离散的随机过程，在

r 时刻状态已知的条件下，其后 r+1 时刻所处状态的概率

只与 r 时刻的状态有关，而与以前时刻 r-1、r-2……的状

态无关，则该过程称马尔可夫链。

P{xr  s  ai ,r  s xr  ai ,r , xr 1  ai ,r 1 , , x1  ai ,1}  P{xr  s  ai ,r  s xr  ai ,r }

马尔可夫链的定义

二元通信信道：

1-



0



 

0

P( X n 1  1| X n  0)   P( X n 1  0 | X n  1)  

Xn



X n 1



1

1-

1

P{xn 1  ai ,n 1 xn  ai ,n , xn 1  ai ,n 1 ,  P{xn 1  ai ,n 1 xn  ai ,n }

, x1  ai ,1}

马尔可夫链的定义

一维随机游动(Random Walk)

x

0

1 p

p

Xn  k

质点正向移动一个单位 质点反向移动一个单位



4 3 2 1 0

+ + + + +

P( X n 1  k  1| X n  k )  p

+

1

2

3

4

5

6

7

n

P( X n 1  k  1| X n  k )  q

7

马尔可夫链的统计特性



状态概率：

p j (n)  P{X n  a j }



概率分布列：

p(n)   p1 (n)

p2 ( n)  p N ( n) 

T



转移概率：

pij (s, n)  P{X n  a j X s  ai }

 

j

i

pij (s, n)

马尔可夫链的统计特性



状态转移概率矩阵：

 p11 ( s, n)  P ( s, n)     pN 1 ( s, n)

每一行元素之和为0，

p1N ( s, n)    pNN ( s, n)  

 

j

i

pij (s, n)

 p ( s , n)  1

j 1 ij

N

9

马尔可夫链的统计特性

p j (n)  P{X n  a j }

  P{ X n  a j , X s  ai }

i 1

N

N



j



i

  P{ X n  a j X s  ai }P{ X s  ai }

i 1

pij (s, n)

  pij ( s, n) pi ( s)

i 1

N

p(

n)  P ( s, n)p( s )

10

T

马尔可夫链的统计特性



性质: (a)

(b)

 p ( n)  1

j 1 j

N

p

j 1

N

ij

( s, n)   P{ X n  a j X s  ai }  1

j 1

N

(c) p j (n) 

p

i 1

N

ij

( s, n) pi ( s)

(d) p(n)  PT ( s, n)p( s)

11

状态转移图

12

切普曼－柯尔莫哥洛夫方程

切普曼－柯尔莫哥洛夫(Chapman-Kolmogorov)方程

pij ( s, n)   pik ( s, r ) pkj (r , n) ，n  r  s

k 1

N

aN pkj(r,n) ak xn=aj

xs=ai

pik(s,r)

a1 s r

n

13

切普曼－柯尔莫哥洛夫方程

pij ( s, n)  P  X n  a j | X s  ai  

P  X n  a j , X s  ai  P  X s  ai 



k 1

N

N

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 s  ai  P  X r  ak , X s  ai  k 1 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

N

  pik ( s, r )  pkj (r , n)

k 1

N

P(s,n)=P(s,r)P(r,n)

14

齐次马尔可夫链

如果马尔可夫链的转移概率只取决于 n-s，而与n和s本身的 值无关，则称为齐次马尔可夫链，简称齐次链。



齐次链的转移概率写为pij(n-s)，而转移矩阵写为P(n-s)， 并称为n-s步转移矩阵。

 

当n－s＝1时，称为一步转移矩阵，利用切普曼方程，有

P  n   [P  1]n , PT  n   [PT  1 ]n



T p ( n )  P ( s, n)p( s) 根据

有

p(n  k )  PT (n)p(k )  [PT (1)]n p(k )

齐次马尔可夫链 的状态概率只与 起始状态及一步 转移概率有关。

15

齐次马尔可夫链

16

平稳链



如果齐次链中所有状态的概率分布列相同，即：

p(n)  p(1)

则此齐次链是平稳的。  若齐次链中序列X1和X2的概率分布列相同，则此链平稳。

p(2)  p(1)

p(3)  PT (1)p(2)

P (1)p(1)  p(1)

T



显然，一旦 X(n) 进入某个平稳分布后，就一直处于该分布上， 不再改变。

17

平稳链

PT (1)p(1)  p(1)

 p11 p PT (1)   12     p1N p21 p22 p2 N pN 1  pN 2     pNN  

p11 p1  p21 p2  p12 p1  p22 p2  p1 N p1  p2 N p2 

 pN 1 pN  p1  pN 2 pN  p2  pNN pN  pN

加上

p1  p2    p N  1

18

平稳链



例：具有反射壁的随机游动。设有一质点在线段上游动，终端设

有反射壁。质点只能停留在 a1  2l , a2  l , a3  0, a4  l , a5  2l

上，游动的概率法则如下：如果游动前质点在 a 2 , a3 , a 4位置，则 以1/2概率向前或向后移动一单位L，在 a1 , a5位置，则以概率1返

回，画出状态转移图，并求该链平稳时的概率分布列。

X (t )

2l

l

1

1/2

1/2

a3 a4

1/2

a5

0

t

a1

1/2

a2

1/2

l

2l

(a)质点一维游动图

1/2

1

(b)状态转移图

19

图6.3 具有反射壁的随机游动

平稳链



t  nT时刻质点的位置为 X n  X (nT )，该随机变量的可能值为 a1 , a2 , , a5 。不难看出，这五种状态中的任意两种间的转移概率 pij (s, n)

解：设 与



n 和

s 本身的值无关，而只与

 0 1 2  P (1)   0   0   0 1 0 12 0 0

n  s 有关

0 0 0 12 0 1 0  0   0   1 2 0  

其一步转移矩阵为

12 0 12 0

20

平稳链

 p2  2  p1  列出以下的方程组并求解:  p  p3  p 2  1 2 p p4  2   p3  2 2   p3  2  p5  p4   p1  p2  p3  p4  p5  1  

p2  p3  p4 

1 4

1 p1  p5  8

21

平稳链

例：设一个二进制通信系统，其模型可用马尔可夫链描述，其 一步转移矩阵为 1  1 2  ，n时刻的概率为



3 P 1  4

3  3 4 

5 p ( n)    4  5 

试问这是不是一个齐次链，请画出状态转移图，并求出n+1时 刻、 n+2 时刻的状态概率分布列，试问这是不是一个平稳链？ 如果要求该链平稳，求出它的的状态概率分布列。



22

遍历性

23

本章小结

    

马尔可夫链的性质 切普曼－柯尔莫哥洛夫方程 齐次马尔可夫链 平稳性 遍历性

24