《马尔可夫链与泊松过程》由会员分享，可在线阅读，更多相关《马尔可夫链与泊松过程（25页珍藏版）》请在金锄头文库上搜索。
1、Ch.7 马尔可夫链与泊松过程马尔可夫过程是研究信号多级传输、分子的布朗运动、顾客服务、计算机网络流量等等诸多问题时使用的经典模型。本章讨论：1) 马尔可夫过程的基本概念2) 转移概率与C-K方程3) 状态分类及极限特性4) 独立增量过程定义及性质5) 泊松过程定义及相关问题Ch.7 马尔可夫链与泊松过程7.1 马尔可夫链7.2 马尔可夫链的状态分类7.3 独立增量过程7.4 泊松过程7.1 马尔可夫链 此句作为后面每页ppt 的标题定义7.1随机序列X(n)，可数集状态空间E，如果下式P(X= i X = i , X = i , , X = i )n+1n+10011n n=P(X= i X
2、 = i )n+1n+1nn恒成立，则称X(n)是马尔可夫链(Markov chain)。上式称为马尔可夫性(马氏性)、无后效性。定义7.2任意i, j w E， n e T，称条件概率p (n,n +1) = P(X= j|X = i)ijn+1n为(n 时刻的)一步转移概率(One step transition probability)。齐次马尔可夫链(Homogeneous Markov chain):满足下式条件的马尔可夫链：P = P (n, n +1)ij ij转移概率性质：(1)非负性：P. 0(2)归一性：工p = 1ijijjeEm步转移概率：n时刻到n + m时刻的转移概
3、率p( m, n) =ij=i)转移概率矩阵： P(m, n) = p (m,n) iji, jeE并且：(1)工 p (n, n + m) = 1ijjwE pij(n,n)=M-j)=0i: j齐次马尔可夫链：P(m)二P(n, n + m)例7.1 设 X (n +1) = g(X (n)+ Z(n +1)，X(0) = 0，其中Z(n),n = 1,2,3,是独立随机序列，试说明X(n)是马尔可夫链。解：P(X= x X = x，,X = x )n+1n+1I 11nnn+1 11nn=pg (X ) + Z= xX = x 丿=pG nn+1n+1nn=xn+1n+1 nn例7.2
4、级联的独立二进制传输系统如图所示 试说明X (n), n = 0,1,2,-是齐次马尔可夫链，并求(一步)转移概率。解：(1) X(n)是齐次马尔可夫链，因为pG= x |X = x，,X = x )= pQ= xn+1n+100nn+1n+1n nP(X = x |X = x )= P(Xn+1n+1 nn=x |X = x )n n-1 n-12)一步转移概率矩阵为厂pp、00 01I pp丿10 11n 时刻的转移概率矩阵：P(n, n +1)=(P00p10pp01 p11 p21p02p12p(n, n +1)iji, jeE对于齐次马尔可夫链：P = P(n, n +1)=C )l
5、i i*E状态转移图：用带符号的圆圈表示状态，带箭头的弧线表示可能的转移及其概率的一种有向图。例7.3 直 线上作 随机游 动的质 点： 时 刻 k 的 游 动位移 为Z(k) e1,0,l且统计独立,k = 1,2,。相应取值概率为(p, r, q)。令X(n) = Hz(k) , X(0) = 0，试说明 X(n)k=1是马尔可夫链。解：是例7.1中函数g(x) = x时的一个特例。X (n)=另 Z (k)=艺 Z (k) + Z (n) = X (n 1) + Z (n)k =1k =1定义7.3若X(n)是马尔可夫链，称行向量p(n)=(兀(n),兀(“)，)12为n时刻的概率分布向
6、量。兀.(n)= P(X(n) = l)。 l设n m 0，贝1：P(X = l) = Y P(X = l|X = jL(X = j)nnmmjeE向量形式：p(n) = p(m)P(m,n)定理7.1(査普曼-柯尔莫哥洛夫方程)设n r m ,马尔可夫链的转移概率矩阵满足p (m,n) = Y p (m,r) p (r,n)ljlkkjkeE简称 C-K (Chapman-Kolmogorov)方程。矩阵形式：P(m, n) = P(m, r)P(r, n)证明思路：运用全概率公式和马尔可夫性证明：当P(X = l)丰0时mP(X 二 i, X 二 k, X 二 j)mrn=P(X = j|
7、X 二 k, X 二 i)P(X 二 k|X 二 i)P(X 二 i)nrmrmm=P(X = j|X 二 k)P(X 二 k|X 二 i)P(X 二 i)nrrmmC-K方程特点：一步转移概率矩阵为P的齐次马尔可夫链(1) P(m, n) = P(m, m + 1)P(m +1, m + 2) P(n 1, n) = Pn-m(2) k 步转移概率：p (k) = p (m,m + k)ijij(3) k步转移概率矩阵：P(k) = P(m,m + k)(4) p (m + n) = Y p (m)p (n)ijikkjkwE(5) P(m + n) = P(m)P(n) = Pm+n(6)
8、 p(n +1) = p(n)P = p(0)Pn+i例7.4随机序列(X(n),n = 0,1,2,取值(0 , 1),概率PX(n)=0=q， PX(n)=1= p ，经过累加器后得到随机过程Y (n)。(1)证明Y (n)是齐次马尔可夫链；(2) 给出Y(n)的转移概率矩阵与状态图；(3 )求n步转移概率 p (k,k + n)。ij解：(1)证：Y(n) = X(i) = Y(n -1) + X(n)且 X (n)为独i=1立平稳序列，是例7.1 的特例；p (n,n +1) = P(Y(n +1) = j|Y(n) = i)= P(X(n +1) = j-i)qj - i = 0=
9、1因此Y (n)是齐次马尔可夫链。(2)Y (n)的一步状态转移概率矩阵| qp0000qp00 00qp0 000qp k -丿3)利用二项分布特性p (k, k + n)= ij0 (j - i) n其它例7.5 记 X (n) 为在两个 反射壁之间作一维随机游动粒子的位0 1 0、 置，状态空间为 E = ),1,2, P = 0.5 0 0.5(1) 绘出状态图；(2 ) 求时刻n处于状态0且时刻n + 3处于各状态的概率;(3 ) 求时刻n处于状态0且时刻n + 4处于各状态的概率。解：( 1)状态图反射壁(Reflecting barrier):由于在0与2状态上，以概率1转移(弹
10、回)到下一状态。2)p (n,n + 3)= 000p (n,n + 3)= 101p (n,n + 3)= 0024)p (n,n + 4)= 0.500p (n, n +014)= 0p (n,n + 4)= 0.502例7.6 某个具有双吸收壁的质点随机运动的状态图如下,试给出它的一步转移矩阵。解：吸收壁(Absorbing barrier)：进入状态0或3后，该链永远 停留在那里。也称为吸收态(Absorbing state)。一步转移概率矩阵：10000.500.50P 二00.500.5、0001丿定义7.4马尔可夫链X(n)的一步转移概率矩阵为P，如果存在一种分布P = (1)兀
11、(2)，下式恒成立pP 二 p则称 p 为 X(n) 的一个平稳分布。因为一旦X(n)进入该分布后，它就永远处于该分布上。也称为X (n)的极限分布或最终分布。例 7.7 E = ),1 的齐次马尔可夫链x(n),n = 0,1,(0 1)P = 0，P(0) = (0.5 0.5)，求：k10丿(1) n = 3时刻的状态概率向量；( 2 ) 给出其中的一个可能序列；(3)p.(n)当n Ta时是否存在？ij解：(1)p=p(0)P3 = (0.5 0.5)(2) X (n)的可能样本序列为010101或101010。(3)当n为偶数时:0)1丿(1P(n)二 Pn 二k0当n为奇数时:P(
12、n)二 Pn 二(0k11)0丿所以， lim p (n) 不存在极限。n Ta ij例 7.8 取 值 为 (0, 1) 的 有 噪 声 对 称 二 进 制 传 输 系 统P 二 P 二 P ， P 二 P 二 q ， p + q 二 1 ，其中 00 11 01 10p = P(X = j|X =i)， X和X分别是输入输出随机变 jOII O量。将该类型传输系统进行n级级联，并设输入到该级联系统的信源数据概率为P(0) = (r ,1 - r)。求:1)系统的转移概率。2)信源经过级联系统后，输出符号的取值概率。(3) 当n趋于无穷大时，上述两问的结果又如何?解：该系统是一个齐次马尔可夫
13、链，P =(1) n级级联后系统的转移概率为P(n)二 Pn -P 特征分解，故有，P(n )=，0)1 X丿21 (p - q)n-+ _221(p - q 2 -2V -1丿nV-1(p - q)n 12 21 (p - q)n 十2 2 丿2)信源经过该级联系统后，输出符号的取值概率为p(n) = 2 - (-2r 十 - q)n1 丄(一2r +1)(p - q)“) 十2(3)令n趋于无穷大,当 |p-主 1 时，PS) = limP(n)=ns0.5 0.5丿，并且p(g) =(0.5 0.5)当|p - q=1时，如果p二，因此PS)二而 p(g) = p(0);如果P =，P(g)与p(g)都不存在。本例说明了一个有趣的结果：不论原始信息的分布如何，经过很多次有错(o q 0使p (N ) 0，则称1ij 1状态i可达状态j，简记为iT j ；若同时还存在整数N 0，使p (N )
