Microsoft PowerPoint - [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - [兼容模式]"

亚皮
7 years ago
Views:

1 随机信号分析第二章马尔可夫链 (Markov Chains) 罗锴 Signal processing & Information Networking in Communications

2 马尔可夫过程安德雷. 安德耶维奇. 马尔可夫 (A.A.Markov): 俄数学家,1856~1922 概率和统计领域专家当年 Markov 研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了 Markov 过程的数学模型 Markov 过程 80 年代兴起, 在现代工程自然科学社会科学中应用广泛

3 提纲马尔可夫链定义一步转移概率及多步转移概率初始概率及绝对概率遍历的马尔可夫链及平稳分布马尔可夫链状态分类

4 马尔可夫过程时间离散状态离散 : 马尔可夫链时间连续状态离散 : 连续时间的马尔可夫链时间离散状态连续 : 马尔可夫序列时间连续状态连续 : 马尔可夫过程

5 马尔可夫链定义时间状态都是离散的马尔可夫过程, 称为马尔可夫链例如 : 天气预报质点的随机游动

6 马尔可夫链定义例如 : 在某数字通信系统中传递 0,1 两种信号, 且传递需要经过若干级因为系统中有噪声, 各级将造成错误, 若某级输入 0,1 信号后, 其输出不产生错误的概率为 p, 产生错误的概率为 1-p, 则该级的输入输出状态构成了一个两个状态的马氏链

7 马尔可夫链定义设有随机过程, 若对于任意的整数 nt 和任意的 i, 条件概率满足 0, i1,, i n 1I P{ X n 1 P{ X 则称 n 1 i n 1 i { X nt} n, { X nt} X n 1 n, 0 X n i 0, X i n } 1 i 1,, X 为马尔可夫链, 简称马氏链将来的状态只与现在状态有关, 与过去状态无关 n i n } t t 0 过去 t t 0 现在 t t 0 将来

8 一步转移概率及多步转移概率为了描述马尔可夫链 (n+1) 维分布率, 最重要的是条件概率 P{ X i X i }. 它表示在时 n1 n1 n n 刻 n 取 i n 值的条件下, 下一时刻 n+1 取值为 i n+1 的概率 ( 一步转移概率 )

9 一步转移概率及多步转移概率定义 4.2 称条件概率为马尔可夫链 { X nt} 在时刻 n 的一步转移概率, 其中 i, j p ij ( n) P{ X 1 j X i} n, n I, 简称转移概率 n 定义 4.3 若对任意的 i, j I, 马尔可夫链 { X nt} 的转移概率与 n 无关, 则称马尔可夫链是齐次马尔可夫链我们只讨论齐次马氏链并将 n, p ( n) 记为 ij ij p

10 一步转移概率及多步转移概率设 P 表示一步转移概率所组成的矩阵, 则 p11 p12 p1 n P p21 p22 p2 n 称为系统状态的一步转移概率矩阵, 它具有如下性质 : p 0, i, ji ij ji p 1, i, ji ij 满足上述两个性质的矩阵成为随机矩阵

11 一步转移概率及多步转移概率定义 4.4 称条件概率 p ( n) ij P{ X j X i}, i, j I, m 0, n 1 m n 为马尔可夫链 { X, n nt} 的 n 步转移概率, 并称 () n () n () n p11 p12 p1 m ( n) ( n) () n () n () n P ( pij ) p21 p22 p2 m 为马尔可夫链的 n 步转移矩阵规定 m p (0) 0, ij 1, i i j j

12 一步转移概率及多步转移概率例题设马尔可夫链 { X, n nt} 有状态空间 I 0,1, 其一步转移概率矩阵为 P p p p p 求 P{ X 2 0 0} 和两步转移概率矩阵 P (2) m X m 结论 :n 步转移矩阵 P ( n ) P n

13 一步转移概率及多步转移概率解 : (2) P{X m2 0, Xm0} P00 P{Xm 2 0 Xm 0} P{X m 0} P{Xm 20, Xm1 0, Xm0} P{Xm 20, Xm1 1,Xm0} P{X m 0} P{X m 0} P{X m20, Xm 10,X m0} P{X m1 0,X m0} P{X m1 0,X m 0} P{X m 0} P{X m20, Xm1 1,Xm 0}P{ Xm 11,Xm 0} P{Xm1 1,X m0} P{X m 0} P{Xm 2 0 Xm 10,Xm 0}P{Xm 10 Xm 0} P{X 0 X 1,X 0}P{X 1 X 0} m2 m1 m m1 m

14 一步转移概率及多步转移概率 (2) P P{X m2 0 X m1 0}P{X m1 0 X m 0} P{X m2 0 X m1 1}P{X m1 1 X m 0} =P (1) 00 P (1) 00 P (1) (1) 10 P 01 =P 00 P 00 P 10 P 01 (2) (2) 2 P00 P 01 P00 P 01 P00 P 01 P (2) (2) P10 P11 P1 0 P11P 10 P11 结论 :n 步转移矩阵 P ( n ) P n

15 一步转移概率及多步转移概率定理 4.1 设 { X, n nt} 为马尔可夫链, 则对任意整数 n 0, 和,n 步转移概率具有下列性质 : 0 L n i, j I 1. p ( n ) ij k I p ( l ) ik p ( n l ) kj Chapman- Kolmogorov 方程 2. p ( n ) ij k I k 1 n1 I p ik 1 p k 1 k 2 p k n1 j 3. P ( n ) ( n 1) PP i k : j 4. P ( n ) P n o l n- l t

16 一步转移概率及多步转移概率证明 P P{ X j X i} ( n) ij mn m P{ X mn j, X m i} P{ X m i} P{ X mn j, X ml k, X m i} P{ X i} ki P{ X mn j, X ml k, X m i} P{ X k, X i} P{ X ml k, X m i} P{ X i} P{ X j X k, X i} P{ X k X i} P{ X j X m ki ml m m ki mn ml m k} P{ X mn ml ml ki ( nl) ( l) ( l) ( nl) Pkj Pik Pik Pkj ki ki ml k X i} m m

17 一步转移概率及多步转移概率例题 4.1: 无限制随机游动设质点在数轴上移动, 每次移动一格, 向右移动的概率为 p, 向左移动的概率为 q=1-p, 这种运动称为无限制随机游动以 X n 表示时刻 n 质点所处的位置, 则 {X n,n T} 是一个齐次马尔可夫链, 求一步和 k 步转移概率解 : 一步转移概率为 Pii, 1 p Pii, 1 q 1 p Pi, j0 (j i-1,i+1) P......q 0 p q 0 p q 0 p......

18 一步转移概率及多步转移概率设 K 步转移概率为, 即经过 k 步转移结果从状态 i 到状态 j 设在这 K 步转移中向右 x 步, 向左 y 步则 : 因为在 k 步中, 哪 x 步向右哪 x 步向左是任意的, 所以走法 x 有, 则 : ( k ) p ij x y k x y j i 则 : x k j i, y k j i 2 2 C k x x y ( k ) Ck p q k ( j i) pij 0 k ( j i) 为偶数为奇数 k±(j-i) 必须为偶数

19 一步转移概率及多步转移概率例题 : 带一个吸收壁的随机游动质点在数轴上移动, 规律同上例当质点一旦达到 X n = 0 时, X n+1 就停留该 0 状态, 这种状态称为吸收态 {X n,n T} 是一个齐次马尔可夫链, 求一步转移概率解 : P P P P P 00 0 j ii, 1 ii, 1 i, j 1 0 j 0 P q i 1 i 1 0 j i 1,i-1, i

20 一步转移概率及多步转移概率 P q 0 p q 0 p q 0 p q

21 一步转移概率及多步转移概率例题 : 带 2 个吸收壁的随机游动质点在数轴上移动, 规律同上例随机游动的状态空间 I={0,1,2 a}, 其中 0 和 a 为吸收态求一步转移概率解 : P P P P 00 0 j aa aj i, i 1 i, i1 1 0 j j 0 P P 1 i a 1 P q 1 i a 1 P i, j 0 j i 1,i-1, i a

22 一步转移概率及多步转移概率 q 0 p q 0 p q 0 p q q 0 p q 0 p q 0 p q 0 p

23 一步转移概率及多步转移概率例题 : 天气预报问题如果明天是否有雨仅与今日是否有雨有关, 而与过去的天气无关. 并设今日下雨, 明日有雨概率为 0.7, 今日无雨明日有雨的概率为 0.4, 并把有雨称为 0 状态, 无雨称为 1 状态则问 : 今日有雨且第 5 日仍有雨的概率为多少?

24 一步转移概率及多步转移概率解 : 设状态 0 代表有雨, 状态 1 代表无雨, 则一步转移矩阵为 : P= P 10 P P P (4) (4) (4) 4 P00 P P00 P01 (4) (4) P =P = P P P P 所以今天有雨, 第 5 天有雨的概率为 : P (4)

25 初始概率及绝对概率定义 : 称 p j ( n) P{ X n j}, ( j I 夫链的绝对概率 ; 称对概率向量 ) 为 n 时刻马尔可为 n 时刻的绝称 pj (0) P{ X0 j}, ( ji) 的初始概率, 简记为 ; T p j 称 P ( 0 ) ( p1, p 2, 概率向量为马尔可夫链 ) 为马尔可夫链的初始

26 初始概率及绝对概率例题 : 设马尔可夫链有 k 个状态, 已知第 n-1 时刻的绝对概率向量 ( 2 P T ( n1) 为 p1( n 1), p ( n 1),, p k ( n 1)) 求第 n 时刻绝对概率向量

27 初始概率及绝对概率解 : 以两个状态的情况为例 n 个时刻的 Pn ( ), P( n) 1 2 和 n-1 个时刻的 Pn ( 1) 1, P( n1) 2 Pn ( ) PXn { ( ) 1} PXn { ( ) 1, Xn ( 1) 1} PXn { ( ) 1, Xn ( 1) 2} 1 同理所以 = PXn { ( ) 1 Xn ( 1) 1} PXn { ( 1) 1} PXn { ( ) 1 Xn ( 1) 2} PXn { ( 1) 2} = PPn ( 1) PP( n1) P2( n) = P12P1( n1) P22P2( n1) P ( P1( n), P2( n)) ( P1( n1), P2( n1) ) P 结论为 :( P( n),..., P ( n)) ( P( n1),..., P ( n1)) P 1 k 1 k P P

28 初始概率及绝对概率定理 4.2 设 {X n,n T} 为马尔可夫链, 则对任意 j I 和 n 1, 绝对概率 p j (n) 具有下列性质 : p j (n) ii ii T (n) p i p ij p ( n) p ( n 1) j P T ( n ) P (0) P T i ( n) P ( n) P ( n 1) P T p ij

29 初始概率及绝对概率定理 4.3 设 {X n,n T} 为马尔可夫链, 则对任意 i 1,,i n I 和 n 1, 有证明 : ii P{ X1 i1,, Xn in} pi pii p ii P{ X i,... X i } P( { X i, X i,... X i }) 1 1 n1 n n1 ii P X i, X i,... X i } ii ii n 1 i i n1 n P{ X i} P{ X i X i}... P{ X i X i } ii n n n n n1 n1 PX { ip }... p pp 0... p i ii i i 1 n1 n ii i i 1 n1 n

30 初始概率及绝对概率例题 : 设某地区有 1600 居民, 有甲乙丙三个工厂的产品在该地区销售, 据调查 8 月份买甲乙丙三个工厂产品的户数分别为 480,320,800,9 月份调查发现原买甲 48 户转买乙,96 户转买丙 ; 原买乙的有 32 户转买甲, 有 64 户转买丙 ; 原来买丙的有 64 户转买甲, 有 32 户转买乙, 估算 9 月份及 12 月份, 甲乙丙三个工厂的产品在该地区市场占用率

31 解 :9 月份的市场占有率记为 :,,, 则 8 月份的市场占有率为 : P甲 (0), P乙 (0), P 因此初始分布为 :{ P (0), P (0), P (0)} {0.3,0.2,0.5} 一步转移概率矩阵为所以 9 月市场占有率为 { P (1), P (1), P (1)} { P (0), P (0), P (0)} P 若一步转移概率矩阵不变, 则 12 月的市场占有率为 : 甲乙 P 丙 P 甲 (1) P 乙 (1) (1) 丙丙 (0) P甲甲 P甲乙 P甲丙 P P乙甲 P乙乙 P乙丙 P P P 丙甲丙乙丙丙甲乙丙甲乙丙 = {0.27,0.19,0.54} { P (4), P (4), P (4)} { P (0), P (0), P (0)} P 甲乙丙甲乙丙 = {0.2319,0.1698,0.5983} 4

32 遍历的马尔可夫链及平稳分布遍历性定义 : 对于状态有限的马尔可夫链, 若对一切 i,j I, 存在不依赖于 i 的常数 P j, 使得 lim p n ij j n 此链遍历则 P j 为极限分布 ( 最终分布 ) P, 则称定理 : 若对状态有限的马尔可夫链, 存在正整数 ( S ) S, 对于一切 i,j I, P 0, 则此链遍历 ij

33 遍历的马尔可夫链及平稳分布例题 : P 1/2 1/2 2/5 3/5 P (1) 是否遍历? (2) 是否遍历? 一个有限状态的马氏链, 当满足条件时, 经过一段试验时间后, 过程将到平稳 ( 或平稳 ) 状态, 此后过程那一个状态的概率不再随时间而变化. ( s) p ij 0

34 遍历的马尔可夫链及平稳分布平稳分布若存在一个概率分布 ( 1, 2,..., k ), 使得 (,,..., ) (,,..., ) 1 2 k 1 2 k P, 则称该马尔可夫链是平稳的 ( 1, 2,..., k ) 称为该马尔可夫链的平稳分布定理 : 遍历的马尔可夫链, 极限分布等于平稳分布

35 遍历的马尔可夫链及平稳分布例题 : 1/2 1/2 马尔可夫链,, 问是否遍历, 若遍历, 求相应的极限分布例题 : 马尔可夫链,, 求其平稳分布 I {0,1} I {0,1} P P 2/5 3/

36 遍历的马尔可夫链及平稳分布解 : 显然遍历 1/2 1/2 ( 0, 1) ( 0, 1) 2/5 3/ /9 1 5/9

37 马尔可夫链状态分类周期非周期常返非常返常返分为正常返零常返非周期的正常返称为遍历状态到达和互通

38 马尔可夫链状态分类设马尔可夫链的状态空间 I={1,2,3,4,5,6,7,8,9}, 状态转移图如下观察状态 1

39 马尔可夫链状态分类定义 4.6 如集合 {n: n 1,p (n) ii >0} 非空, 则称该集合的最大公约数 d=d(i)=g.c.d{n:p (n) ii >0} 为状态 i 的周期如 d>1 就称 i 为周期的, 如 d=1 就称 i 为非周期的由定义知, 当 n 不能被 d 整除时, p (n) ii =0 引理 4.1 如 i 的周期为 d, 则存在正整数 M, 对一切 n M, 有 p ii (nd) >0

40 马尔可夫链状态分类例题 : 设有 4 个状态的马尔可夫链, 它的一步转移概率矩阵为 : 0 0 1/2 1/ /2 1/2 1/2 1/ /2 1/2 0 0 画出其状态传递图, 该过程是否具有周期性?

41 马尔可夫链状态分类解 : 0 0 1/2 1/ /2 1/2 1/2 1/ /2 1/2 0 0 所有状态周期为 2 1/2 1/ /2 1/2 1/2 1/2 1/ /2

42 马尔可夫链状态分类例 4.7: 状态转移图状态 2 和 3 具有相同的周期, 但是状态 2,3 有区别. 为此引入首中概率常返性的概念

43 马尔可夫链状态分类首中概率它表示质点由 i 出发, 经 n 步首次到达 j 的概率, 表示为 f ( n) ij P( X mv j,1 v n 1, X mn j X m i) 同时我们令 n 1 f ij f ij ( n ) 表示质点由 i 出发, 经有限步终于到达 j 的概率

44 马尔可夫链状态分类定义 4.7 若 f ii =1, 称状态 i 为常返的 ; 若 f ii <1, 称状态 i 为非常返的 ( 滑过态 ) 对于常返态 i, 由定义知 {f ii (n),n 1} 构成一概率分布, 此分布的期望值 n1 i nf ii ( n) 表示由 i 出发再返回的 i 的平均返回时间定义 4.8 如 μ i <, 则称常返态 i 为正常返的 ; 如 μ i =, 则称常返态 i 为零常返的

45 马尔可夫链状态分类定理 n 对任意的状态 i,j 以及, 有 : C-K 方程 n ( n) ( k) ( n k) ij ij jj k1 p f p C-K 方程与定理 4.4 都是马尔可夫链的关键公式, 因为他 ( n ) p ij p (n) ij ki p (l) (nl) ik p kj 们都可以把分解成较低步的转移概率之和的形式.

46 马尔可夫链状态分类证明 : p P( X j X i) ( n) ij n k 1 k 1 k 1 n 0 PX ( j,1vk1, X jx, j X i) n v k n PX ( j X ix, j,1vk1, X j) n 0 v k. PX ( j,1vk1, X j X i) n v p f ( nk) ( k) jj ij k 0 0

47 马尔可夫链状态分类状态 i 特性 ( 常返和非常返 ) 的判断准则 : 定理 4.5 状态 i 常返的充要条件为 : n0 p ( n) ii 状态 i 非常返的充要条件为 : n0 p ( n) ii 1 1 f ii

48 马尔可夫链状态分类零常返和正常返的判断准则 : 定理 4.7 以及推论状态 i 常返, 则 : (1) 零常返 (2) 正常返其中, 周期为 d, lim ( n) p 0 ii n ( nd ) p ii n lim 0 lim n p ( nd ) ii 非周期时,( 遍历 ) d u lim i n p ( n ) ii 1 u ( 非周期的正常返称为遍历状态 ) i

49 马尔可夫链状态分类到达如果对状态 i 和 j 存在某个 n(n 1), 使得 p ij (n) >0, 即由状态 i 出发, 经过 n 次转移以正的概率达到状态 j, 则称自状态 i 可达状态 j, 并记为反之如果状态 i 不能到达状态 j, 记为 i j i j 例如 : 无限制的随机游动中, 每个状态都能够到达任何其它状态当时在带有吸收壁的随机游动中, 吸收状态却不同到达其他状态

50 马尔可夫链状态分类定义 : 互通有两个状态 i 和 j, 如果由状态 i 可以到达状态 j, 且由状态 j 也可以到达状态 i, 则称状态 i,j 互通记为 : i j

51 马尔可夫链状态分类定理 4.8 可达关系与互通关系的传递性 i j j k i k i j j k i k 若,, 则若,, 则定理 4.9 如果状态 i,j 互通, 则 : i 和 j 同为常返或非常返如为常返, 同为正常返或零常返 i 和 j 有相同的周期

52 马尔可夫链状态分类例题 4.9: { X } I {0,1, 2,...} 设马氏链 n 的状态空间为, 转移概率为 p00, pii, 1, pi0, ii /2 1/2 1/2 1/2 1/2 1/ /2 1/2 判断各状态的性质 ( 从常返和周期性两方面 )

53 马尔可夫链状态分类 1/2 1/2 1/2 1/2 1/2 1/ /2 1/2 先考察状态 0, 由图可以知道 : (1) 1 (2) 1 1 (3) f 所以 : 00, f00., f00.., f 00 n1 1 2 n 1, 所以状态 0 为常返的 1 u nf n 2 ( n) 0 00 n n1 n1, 所以状态 0 为正常返的

54 马尔可夫链状态空间分解闭集状态空间 I 的子集 C 称为闭集, 如果对任意 k 及 ic都有 pik 0 C 不可约闭集 C 称为不可约的, 如果 C 的状态互通如果其状态空间不可约, 马尔可夫链称为不可约的

55 马尔可夫链状态空间分解如果单个状态构成一个闭集, 则称这个闭集为吸收态它是比较小的闭集 (1) 闭集意味着质点一旦进入闭集中, 将永远留在该闭集中 (2) 一个大的闭集可以包含几个小的闭集

56 马尔可夫链状态空间分解例题 : 设马氏链 {X n } 的状态空间 I={1,2,3,4,5}, 转移矩阵为 : 1/ /2 0 1/2 0 1/ 找出该马氏链中所有闭集, 马氏链是否不可约? 1/2 1/2 1/ /

57 马尔可夫链状态空间分解定理 4.10 ( 状态空间的分解定理 ) 任一马尔可夫链的状态空间 I, 可唯一的分解成有限个或可列个互不相交的子集 D, C 1, C 2, 之和, 使得 1 每一 C n 是常返态组成的不可约闭集 ; 2 C n 中的状态同类, 或全是正常返, 或全是零常返它们有相同的周期且 f jk =1,j,k C n 3 D 由全体非常返状态组成, 自 C n 中的状态不能到达 D 中的状态

58 马尔可夫链状态空间分解例题 4.13: 设 I={1,2, 6}, 转移矩阵为 : /3 1/3 0 1/ / /2 试分解此链并指出各状态的常返性及周期性.

59 马尔可夫链状态空间分解 1/3 4 1/3 1/ / /2 I D C1 C2 {4} {1,3,5} {2, 6}

60 马尔可夫链状态空间分解推论 : (1) 不可约的有限状态的马尔可夫链必为正常返的 (P61 推论 1) (2) 有限状态的不可约非周期马尔可夫链必存在平稳分布 (P65 推论 1) 有限状态的不可约非周期马尔可夫链必一定是遍历的

61 马尔可夫链状态空间分解小结 : (1)i 为非常返态, f 1, 或者 (2) i 为常返态, f 1, 或者其中, 正常返态零常返态 u i n1 ii u i ii nf ( n) ii n1 nf ( n) ii 或者 n1 n1 p p ( n ) ii ( n) ii 或者 ( n) lim p ii 0 n lim ( n) p 0 ii n

62 马尔可夫链状态空间分解思考题 : (1) 试研究无限制随机游动各状态 {0,+1,+2, +3 } 的性质? (2) 设 { X( n), n1} 为独立同分布随机变量序列, 它们的概率分布为 1 4 PXn { ( ) 1} PXn { ( ) 1} 5 5 令 Y( n) X( n1) X( n) 1 计算 { Yn ( ), n1} PY { ( n1) 1 Y( n) 1, Y( n1) 1} 2 是否为马尔可夫链?

63 作业习题四

主标题

主标题随机信号分析复习课罗锴 Signal processing & Information Networking in Communications 提纲随机过程基本概念泊松过程马尔可夫链正态过程平稳过程平稳过程的谱分析随机过程的基本概念回顾数学建模时间随机变量的基本概念概率空间规定一个随机试验, 所有样本点之集合构成样本空间 Ω, 在样本空间中一个样本点或若干个样本点之适当集合