随机信号分析 第二章 马尔可夫链 (Markov Chains) 罗锴 Signal processing & Information Networking in Communications
马尔可夫过程 安德雷. 安德耶维奇. 马尔可夫 (A.A.Markov): 俄数学家,1856~1922 概率和统计领域专家 当年 Markov 研究普希金诗歌里元音字母和辅音字母交替出现的规律时提出了 Markov 过程的数学模型 Markov 过程 80 年代兴起, 在现代工程 自然科学 社会科学中应用广泛
提纲 马尔可夫链定义 一步转移概率及多步转移概率 初始概率及绝对概率 遍历的马尔可夫链及平稳分布 马尔可夫链状态分类
马尔可夫过程 时间离散状态离散 : 马尔可夫链 时间连续状态离散 : 连续时间的马尔可夫链 时间离散状态连续 : 马尔可夫序列 时间连续状态连续 : 马尔可夫过程
马尔可夫链定义 时间 状态都是离散的马尔可夫过程, 称为马尔可夫链 例如 : 天气预报 质点的随机游动
马尔可夫链定义 例如 : 在某数字通信系统中传递 0,1 两种信号, 且传递需要经过若干级 因为系统中有噪声, 各级将造成错误, 若某级输入 0,1 信号后, 其输出不产生错误的概率为 p, 产生错误的概率为 1-p, 则该级的输入输出状态构成了一个两个状态的马氏链
马尔可夫链定义 设有随机过程, 若对于任意的整数 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 将来
一步转移概率及多步转移概率 为了描述马尔可夫链 (n+1) 维分布率, 最重 要的是条件概率 P{ X i X i }. 它表示在时 n1 n1 n n 刻 n 取 i n 值的条件下, 下一时刻 n+1 取值为 i n+1 的概率 ( 一步转移概率 )
一步转移概率及多步转移概率 定义 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
一步转移概率及多步转移概率 设 P 表示一步转移概率所组成的矩阵, 则 p11 p12 p1 n P p21 p22 p2 n 称为系统状态的一步转移概率矩阵, 它具有如下性质 : 1. 2. p 0, i, ji ij ji p 1, i, ji ij 满足上述两个性质的矩阵成为随机矩阵
一步转移概率及多步转移概率 定义 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
一步转移概率及多步转移概率 例题设马尔可夫链 { X, n nt} 有状态空间 I 0,1, 其一步转移概率矩阵为 P p p 00 10 p p 01 11 求 P{ X 2 0 0} 和两步转移概率矩阵 P (2) m X m 结论 :n 步转移矩阵 P ( n ) P n
一步转移概率及多步转移概率 解 : (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
一步转移概率及多步转移概率 (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
一步转移概率及多步转移概率 定理 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
一步转移概率及多步转移概率 证明 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
一步转移概率及多步转移概率 例题 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 0 0......0 q 0 p 0......0 0 q 0 p......
一步转移概率及多步转移概率 设 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) 必须为偶数
一步转移概率及多步转移概率 例题 : 带一个吸收壁的随机游动质点在数轴上移动, 规律同上例 当质点一旦达到 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 1 0 1 2
一步转移概率及多步转移概率 P 1 0 0 0 0.. q 0 p 0 0.. 0 q 0 p 0.. 0 0 q 0 p.. 0 0 0 q 0.........
一步转移概率及多步转移概率 例题 : 带 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 0 1 0 j 0 P P 1 i a 1 P q 1 i a 1 P i, j 0 j i 1,i-1, i 1 0 1 2 a
一步转移概率及多步转移概率 1 0 0 0 0........ q 0 p 0 0........ 0 q 0 p 0........ 0 0 q 0 p........ 0 0 0 q 0............................. q 0 p 0 0 0.. 0 q 0 p 0 0.. 0 0 q 0 p 0.. 0 0 0 q 0 p....... 0 0 0 0 0 1
一步转移概率及多步转移概率 例题 : 天气预报问题如果明天是否有雨仅与今日是否有雨有关, 而与过去的天气无关. 并设今日下雨, 明日有雨概率为 0.7, 今日无雨明日有雨的概率为 0.4, 并把有雨称为 0 状态, 无雨称为 1 状态 则问 : 今日有雨且第 5 日仍有雨的概率为多少?
一步转移概率及多步转移概率 解 : 设状态 0 代表有雨, 状态 1 代表无雨, 则一步转移矩阵为 : 00 01 P= P 10 P 11 0.4 0.6 P P 0.7 0.3 4 (4) (4) (4) 4 P00 P01 0.5749 0.4251 P00 P01 (4) (4) 10 11 10 11 P =P = P P 0.5668 0.4332 P P 所以今天有雨, 第 5 天有雨的概率为 : P (4) 00 0.5749
初始概率及绝对概率定义 : 称 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, 概率向量 为马尔可夫链 ) 为马尔可夫链的初始
初始概率及绝对概率 例题 : 设马尔可夫链有 k 个状态, 已知第 n-1 时刻的绝 对概率向量 ( 2 P T ( n1) 为 p1( n 1), p ( n 1),, p k ( n 1)) 求第 n 时刻绝对概率向量
初始概率及绝对概率 解 : 以两个状态的情况为例 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) 11 1 21 2 P2( n) = P12P1( n1) P22P2( n1) P ( P1( n), P2( n)) ( P1( n1), P2( n1) ) P 11 12 21 22 结论为 :( P( n),..., P ( n)) ( P( n1),..., P ( n1)) P 1 k 1 k P P
初始概率及绝对概率 定理 4.2 设 {X n,n T} 为马尔可夫链, 则对任意 j I 和 n 1, 绝对概率 p j (n) 具有下列性质 : 1. 2. 3. 4. 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
初始概率及绝对概率 定理 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 0 1 1 n1 ii P X i, X i,... X i } ii ii 0 1 1 1n 1 i i n1 n P{ X i} P{ X i X i}... P{ X i X i } ii n n 0 1 1 0 n n n1 n1 PX { ip }... p pp 0... p i ii i i 1 n1 n ii i i 1 n1 n
初始概率及绝对概率 例题 : 设某地区有 1600 居民, 有甲 乙 丙三个工厂的产品在该地区销售, 据调查 8 月份买甲 乙 丙三个工厂产品的户数分别为 480,320,800,9 月份调查发现原买甲 48 户转买乙,96 户转买丙 ; 原买乙的有 32 户转买甲, 有 64 户转买丙 ; 原来买丙的有 64 户转买甲, 有 32 户转买乙, 估算 9 月份及 12 月份, 甲 乙 丙三个工厂的产品在该地区市场占用率
解 :9 月份的市场占有率记为 :,,, 则 8 月 480 320 份的市场占有率为 : P甲 (0), P乙 (0), P 1600 1600 因此初始分布为 :{ 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) 800 1600 P甲甲 P甲乙 P甲丙 0.7 0.1 0.2 P P乙甲 P乙乙 P乙丙 0.1 0.7 0.2 P P P 0.08 0.04 0.88 丙甲丙乙丙丙 甲乙丙甲乙丙 = {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
遍历的马尔可夫链及平稳分布 遍历性定义 : 对于状态有限的马尔可夫链, 若对一切 i,j I, 存在不依赖于 i 的常数 P j, 使得 lim p n ij j n 此链遍历 则 P j 为极限分布 ( 最终分布 ) P, 则称 定理 : 若对状态有限的马尔可夫链, 存在正整数 ( S ) S, 对于一切 i,j I, P 0, 则此链遍历 ij
遍历的马尔可夫链及平稳分布 例题 : P 1/2 1/2 2/5 3/5 P 1 0 0 1 (1) 是否遍历? (2) 是否遍历? 一个有限状态的马氏链, 当满足 条件时, 经过一 段试验时间后, 过程将到平稳 ( 或平稳 ) 状态, 此后过程那一 个状态的概率不再随时间而变化. ( s) p ij 0
遍历的马尔可夫链及平稳分布 平稳分布若存在一个概率分布 ( 1, 2,..., k ), 使得 (,,..., ) (,,..., ) 1 2 k 1 2 k P, 则称该马尔可夫链 是平稳的 ( 1, 2,..., k ) 称为该马尔可夫链的平稳分布 定理 : 遍历的马尔可夫链, 极限分布等于平稳分布
遍历的马尔可夫链及平稳分布 例题 : 1/2 1/2 马尔可夫链,, 问 是否遍历, 若遍历, 求相应的极限分布 例题 : 马尔可夫链,, 求 其平稳分布 I {0,1} I {0,1} P P 2/5 3/5 0.5 0.4 0.1 0.3 0.4 0.3 0.2 0.3 0.5
遍历的马尔可夫链及平稳分布 解 : 显然遍历 1/2 1/2 ( 0, 1) ( 0, 1) 2/5 3/5 1 2 0 0 1 2 5 1 3 1 0 1 2 5 0 1 1 0 4/9 1 5/9
马尔可夫链状态分类 周期 非周期 常返 非常返 常返分为正常返 零常返 非周期的正常返称为遍历状态 到达和互通
马尔可夫链状态分类 设马尔可夫链的状态空间 I={1,2,3,4,5,6,7,8,9}, 状态转移图如下 观察状态 1
马尔可夫链状态分类 定义 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
马尔可夫链状态分类 例题 : 设有 4 个状态的马尔可夫链, 它的一步转移概率矩阵为 : 0 0 1/2 1/2 0 0 1/2 1/2 1/2 1/2 0 0 1/2 1/2 0 0 画出其状态传递图, 该过程是否具有周期性?
马尔可夫链状态分类 解 : 0 0 1/2 1/2 0 0 1/2 1/2 1/2 1/2 0 0 1/2 1/2 0 0 所有状态周期为 2 1/2 1/2 0 2 1/2 1/2 1/2 1/2 1/2 1 3 1/2
马尔可夫链状态分类 例 4.7: 状态转移图 状态 2 和 3 具有相同的周期, 但是状态 2,3 有区别. 为此引入首中概率 常返性的概念
马尔可夫链状态分类 首中概率它表示质点由 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 的概率
马尔可夫链状态分类 定义 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 为零常返的
马尔可夫链状态分类 定理 4.4 1 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 们都可以把分解成较低步的转移概率之和的形式.
马尔可夫链状态分类 证明 : 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
马尔可夫链状态分类 状态 i 特性 ( 常返和非常返 ) 的判断准则 : 定理 4.5 状态 i 常返的充要条件为 : n0 p ( n) ii 状态 i 非常返的充要条件为 : n0 p ( n) ii 1 1 f ii
马尔可夫链状态分类 零常返和正常返的判断准则 : 定理 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
马尔可夫链状态分类 到达 如果对状态 i 和 j 存在某个 n(n 1), 使得 p ij (n) >0, 即由状态 i 出发, 经过 n 次转移以正的概率达到状 态 j, 则称自状态 i 可达状态 j, 并记为 反之如果状态 i 不能到达状态 j, 记为 i j i j 例如 : 无限制的随机游动中, 每个状态都能够到达任何 其它状态 当时在带有吸收壁的随机游动中, 吸收状态 却不同到达其他状态
马尔可夫链状态分类 定义 : 互通有两个状态 i 和 j, 如果由状态 i 可以到达状态 j, 且由状态 j 也可以到达状态 i, 则称状态 i,j 互 通 记为 : i j
马尔可夫链状态分类 定理 4.8 可达关系与互通关系的传递性 i j j k i k i j j k i k 若,, 则 若,, 则 定理 4.9 如果状态 i,j 互通, 则 : i 和 j 同为常返或非常返 如为常返, 同为正常返或零常返 i 和 j 有相同的周期
马尔可夫链状态分类 例题 4.9: { X } I {0,1, 2,...} 设马氏链 n 的状态空间为, 1 1 1 转移概率为 p00, pii, 1, pi0, ii. 2 2 2 1/2 1/2 1/2 1/2 1/2 1/2 0 1 2 3 1/2 1/2 判断各状态的性质 ( 从常返和周期性两方面 )
马尔可夫链状态分类 1/2 1/2 1/2 1/2 1/2 1/2 0 1 2 3 1/2 1/2 先考察状态 0, 由图可以知道 : (1) 1 (2) 1 1 (3) 1 1 1 f 所以 : 00, f00., f00.., 2 2 2 2 2 2 f 00 n1 1 2 n 1, 所以状态 0 为常返的 1 u nf n 2 ( n) 0 00 n n1 n1, 所以状态 0 为正常返的
马尔可夫链状态空间分解 闭集 状态空间 I 的子集 C 称为闭集, 如果对任意 k 及 ic都有 pik 0 C 不可约 闭集 C 称为不可约的, 如果 C 的状态互通 如果其状态空间不可约, 马尔可夫链称为不可约的
马尔可夫链状态空间分解 如果单个状态构成一个闭集, 则称这个闭集为吸收态 它是比较小的闭集 (1) 闭集意味着质点一旦进入闭集中, 将永远留在该闭集中 (2) 一个大的闭集可以包含几个小的闭集
马尔可夫链状态空间分解 例题 : 设马氏链 {X n } 的状态空间 I={1,2,3,4,5}, 转移矩阵为 : 1/2 0 0 1/2 0 1/2 0 1/2 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 找出该马氏链中所有闭集, 马氏链是否不可约? 1/2 1/2 1/2 1 2 1 4 1 1/2 5 1 3
马尔可夫链状态空间分解 定理 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 中的状态
马尔可夫链状态空间分解 例题 4.13: 设 I={1,2, 6}, 转移矩阵为 : 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1/3 1/3 0 1/3 0 0 1 0 0 0 0 0 0 1/2 0 0 0 1/2 试分解此链并指出各状态的常返性及周期性.
马尔可夫链状态空间分解 1/3 4 1/3 1/3 1 2 1 1 5 1/2 1 3 1 6 1/2 I D C1 C2 {4} {1,3,5} {2, 6}
马尔可夫链状态空间分解 推论 : (1) 不可约的有限状态的马尔可夫链必为正常返的 (P61 推论 1) (2) 有限状态的不可约非周期马尔可夫链必存在平稳分布 (P65 推论 1) 有限状态的不可约非周期马尔可夫链必一定是遍历的
马尔可夫链状态空间分解 小结 : (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
马尔可夫链状态空间分解 思考题 : (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 是否为马尔可夫链?
作业 习题四 4.1 4.6 4.8 4.12