CH马尔可夫链与泊松过程学习教案

1随机信号随机信号(xnho)分析分析第第7 7章章 马尔可夫链与泊松过程马尔可夫链与泊松过程(guchng)(guchng)第1页/共97页第一页，共98页。第7章 马尔可夫链与泊松过程(guchng) 马尔可夫过程是研究信号多级传输、分子的布朗运动、顾客服务、计算机网络流量等等诸多问题时使用的经典模型。 本章讨论： 1）马尔可夫过程的基本概念 2）转移概率与C-K方程 3）状态(zhungti)分类及极限特性 4）独立增量过程定义及性质 5）泊松过程定义及相关问题第2页/共97页第二页，共98页。第7章 马尔可夫链与泊松过程(guchng)7.1 马尔可夫链7.2 马尔可夫链的状态分类(fn li)7.3 独立增量过程7.4 泊松过程第3页/共97页第三页，共98页。7.1 马尔可夫链第7章 马尔可夫链与泊松过程(guchng)7.1.1 7.1.1 基本(jbn)(jbn)定义 定义 随机(su j)序列 的状态空间 E 为可数集，如果对任意 ，有：则称该序列是马尔可夫链（Markov Chain）。 上式刻画了马尔可夫链的特性，称为马尔可夫性（简称马氏性），也称无后效性。第4页/共97页第四页，共98页。7.1 马尔可夫链第7章 马尔可夫链与泊松过程(guchng)7.1.1 7.1.1 基本(jbn)(jbn)定义 定义(dngy) 任取 ，则条件概率称为（n时刻的）一步转移概率（One Step Transition Probability）。 如果在任意时刻n， 都相同，则记为：称这时的马尔可夫链为齐次马尔可夫链。第5页/共97页第五页，共98页。7.1 马尔可夫链 性质(xngzh) 转移概率满足： 为了直观地理解马尔可夫性，设想一质点在某直线的整数格点上随机(su j)运动的情形： 表示在 n 时刻质点位于 i 位置这一随机(su j)事件，如果把时刻 n 看做现在，时刻 0,1,2,n-1 表示过去，时刻 n+1 表示将来，那么马尔可夫性表明：此时位于 i 的质点将来会出现在哪里与它过去曾经在哪些位置停留过没有关系。简言之，将来完全由现在决定，与过去无关。转移概率 表示质点在时刻 n 从位置 i 向 j 转移的可能性，而齐次性表明在所有时刻质点的转移特性是相同的。) 1,(nnpij第6页/共97页第六页，共98页。7.1 马尔可夫链证明(zhngmng)： 例 设 是独立随机序列，随机序 列 中，相邻两个随机变量(su j bin lin)满足递归方程：式中， 。试证明(zhngmng)随机序列 是马尔可夫链。彼此独立，与 独立，与 独立，与 独立。因此，上式的条件部分可如下简化：第7页/共97页第七页，共98页。7.1 马尔可夫链所以(suy)， 是马尔可夫链。第8页/共97页第八页，共98页。7.1 马尔可夫链第9页/共97页第九页，共98页。7.1 马尔可夫链证明：级联的二进制传输信道中，前一节的输出即为后一节的输入(shr)。每节基本信道是彼此独立的，因此，在给定任意第n节输出X(n)的条件下，第n+1节的输出X(n+1)不再依赖于第n节以前所有(0,1,2,n-1)节的输出结果，即： 所以，X(n)是马尔可夫链。又由于每节信道的转移概率(gil)都相同，所以，它是齐次的。第10页/共97页第十页，共98页。7.1 马尔可夫链（2）因为每节的转移概率是相同(xin tn)的，于是，一步转移概率为：第11页/共97页第十一页，共98页。7.1 马尔可夫链第12页/共97页第十二页，共98页。7.1 马尔可夫链第13页/共97页第十三页，共98页。7.1 马尔可夫链0)0(X 例 在直线上有一质点作随机游动，质点在不同时刻 k 的随机运动 Z(k), k=1,2, 是统计独立的，取值为 +1, 0, -1 ， 相应的取值概率为 p, r, q ，p+r+q=1 。质点初始时刻位于(wiy)原点，n 时刻的绝对位置为 ，试证明 是马尔可夫链。证明(zhngmng)： 该式是例中当函数(hnsh) 时的一个特例。因此， 是马尔可夫链。第14页/共97页第十四页，共98页。7.1 马尔可夫链它的一步转移(zhuny)概率矩阵为：状态(zhungti)转移图为：第15页/共97页第十五页，共98页。7.1 马尔可夫链7.1.2 7.1.2 转移概率(gil)(gil)与切普曼- -科尔莫戈罗夫方程 对 n 时刻的一步转移概率与一步转移概率矩阵(j zhn)做简单的扩展，可定义 m 时刻到 n 时刻的转移概率为：转移(zhuny)概率矩阵为：显然，该矩阵所有元素非负，并且任取第 i 行满足：第16页/共97页第十六页，共98页。7.1 马尔可夫链)(nX7.1.2 7.1.2 转移(zhuny)(zhuny)概率与切普曼- -科尔莫戈罗夫方程 定义(dngy) 若 是马尔可夫链，称行向量为 n 时刻(shk)的概率分布向量。对于 ，n时刻的概率分布可由全概率公式求出写成向量形式为：)(nX其中， 是 n 时刻 取 i 的概率。当n=0 时，称 p(0) 为初始分布。第17页/共97页第十七页，共98页。7.1 马尔可夫链 定理 （切普曼-科尔莫戈罗夫方程(fngchng)）设 ， 马尔可夫链的转移概率满足：简称(jinchng)C-K（Chapman-Kolmogorov）方程。 矩阵(j zhn)形式为：注：可由马尔可夫性和全概率公式证明7.1.2 7.1.2 转移概率与切普曼- -科尔莫戈罗夫方程第18页/共97页第十八页，共98页。7.1 马尔可夫链证明(zhngmng)：第19页/共97页第十九页，共98页。7.1 马尔可夫链第20页/共97页第二十页，共98页。7.1 马尔可夫链C-K方程(fngchng)的特点：如果马尔可夫链是齐次的，且一步(y b)转移概率矩阵为P，则 可见(kjin)： 与绝对时刻无关，而只与两时刻之差有关，这时称转移概率是平稳的，并将它们简记为：分别称为k步转移概率和k步转移概率矩阵。这时，C-K方程表示为：定理 齐次马尔可夫链满足：第21页/共97页第二十一页，共98页。7.1 马尔可夫链第22页/共97页第二十二页，共98页。7.1 马尔可夫链解：所以(suy)， 是马尔可夫链。该转移概率(gil)与n无关，第23页/共97页第二十三页，共98页。7.1 马尔可夫链第24页/共97页第二十四页，共98页。7.1 马尔可夫链第25页/共97页第二十五页，共98页。7.1 马尔可夫链第26页/共97页第二十六页，共98页。7.1 马尔可夫链解：因为随机游动粒子的位置 是马尔可夫过程，其状态空间 E=0,1,2 ，由一步状态转移(zhuny)矩阵可得到如下的状态转移(zhuny)图：)(nX第27页/共97页第二十七页，共98页。7.1 马尔可夫链（2）根据(gnj)齐次马尔可夫链的性质，可得：因此：时刻n处于状态0，时刻n+3处于各个(gg)状态的概率为：第28页/共97页第二十八页，共98页。7.1 马尔可夫链（3）根据(gnj)齐次马尔可夫链的性质，可得：故有：时刻(shk)n处于状态0，时刻(shk)n+4处于各个状态的概率为：第29页/共97页第二十九页，共98页。7.1 马尔可夫链第30页/共97页第三十页，共98页。7.1 马尔可夫链解：由状态转移(zhuny)图可知：进入状态0或3后，该链永远停留在那里，形象地称这两个状态为吸收壁或吸收态。由状态(zhungti)转移图可得一步转移矩阵为：第31页/共97页第三十一页，共98页。7.1 马尔可夫链7.1.3 7.1.3 平稳(pngwn)(pngwn)分布与极限分布)(nX 定义(dngy) 对于一步转移概率矩阵为 的马尔可夫链 ，如果存在一种分布 ，使得则称 为 的一个平稳(pngwn)分布。)(nX 显然，一旦 进入某个平稳分布后，它就一直处于该分布上，不再改变。)(nX)(nX)(nX 在 时收敛于某个分布，则称该分布为 的极限分布或最终分布。第32页/共97页第三十二页，共98页。7.1 马尔可夫链第33页/共97页第三十三页，共98页。7.1 马尔可夫链解：（1）根据齐次马尔可夫链的性质(xngzh)，可知n=3时刻的概率分布向量为：第34页/共97页第三十四页，共98页。7.1 马尔可夫链第35页/共97页第三十五页，共98页。7.1 马尔可夫链解：n级级联的二进制传输系统可描述(mio sh)为一个取值为（0,1）的马尔可夫链，易见，该链的一步状态转移概率为：第36页/共97页第三十六页，共98页。7.1 马尔可夫链因此(ync)有:第37页/共97页第三十七页，共98页。7.1 马尔可夫链第38页/共97页第三十八页，共98页。7.1 马尔可夫链 结论：本例说明了一个有趣的结果,不论原始信息的分布如何(rh)，经过很多次有错(0q1)传播后,即使错误概率很小，其分布总趋于均匀分布,信息趋于未知。第39页/共97页第三十九页，共98页。7.2 马尔可夫链的状态(zhungti)分类 7.2.1 7.2.1 可达、互通(htng)(htng)、首达与首达概率第40页/共97页第四十页，共98页。7.2 马尔可夫链的状态(zhungti)分类 第41页/共97页第四十一页，共98页。7.2 马尔可夫链的状态(zhungti)分类第42页/共97页第四十二页，共98页。7.2 马尔可夫链的状态(zhungti)分类解：由一步状态转移(zhuny)概率矩阵可得如下的状态转移(zhuny)图：1. 可达、互通(htng)：第43页/共97页第四十三页，共98页。7.2 马尔可夫链的状态(zhungti)分类第44页/共97页第四十四页，共98页。7.2 马尔可夫链的状态(zhungti)分类2. 首达时间(shjin)的取值空间为:第45页/共97页第四十五页，共98页。7.2 马尔可夫链的状态(zhungti)分类第46页/共97页第四十六页，共98页。7.2 马尔可夫链的状态(zhungti)分类第47页/共97页第四十七页，共98页。7.2 马尔可夫链的状态(zhungti)分类 （1） 表示从状态(zhungti)i出发经过n步首次返回i的概率，简称为n步首返概率。 （2） 表示(biosh)从状态i出发迟早返回i的概率，简称为最终返回概率。第48页/共97页第四十八页，共98页。7.2 马尔可夫链的状态(zhungti)分类7.2.2 7.2.2 常返、非常返、周期(zhuq)(zhuq)与遍历第49页/共97页第四十九页，共98页。7.2 马尔可夫链的状态(zhungti)分类7.2.2 7.2.2 常返、非常返、周期(zhuq)(zhuq)与遍历第50页/共97页第五十页，共98页。7.2 马尔可夫链的状态(zhungti)分类第51页/共97页第五十一页，共98页。7.2 马尔可夫链的状态(zhungti)分类马尔可夫链的状态(zhungti)分类第52页/共97页第五十二页，共98页。7.2 马尔可夫链的状态(zhungti)分类第53页/共97页第五十三页，共98页。7.2 马尔可夫链的状态(zhungti)分类解：该马尔可夫链有4个状态(zhungti)，分别设为0,1,2,3，其状态(zhungti)转移图为：对状态(zhungti)0：所以状态0是非常返态。第54页/共97页第五十四页，共98页。7.2 马尔可夫链的状态(zhungti)分类对状态(zhungti)1：所以状态(zhungti)1是非周期的正常返态，是遍历态。同理，状态2和状态3也是遍历态。因此，该马尔可夫链不是遍历链，但有三个遍历态。第55页/共97页第五十五页，共98页。7.2 马尔可夫链的状态(zhungti)分类它指示(zhsh) 是否停留在 j 状态，则：)(nX 可以证明(zhngmng)：常返状态平均返回次数为无穷多次，非常返状态平均返回次数为有限多次。第56页/共97页第五十六页，共98页。7.2 马尔可夫链的状态(zhungti)分类第57页/共97页第五十七页，共98页。7.2 马尔可夫链的状态(zhungti)分类解：该链的状态(zhungti)转移图为：第58页/共97页第五十八页，共98页。7.2 马尔可夫链的状态(zhungti)分类状态(zhungti)0：所以(suy)状态0是常返态， 为遍历态。状态1：是遍历态。状态2：是非常返态。第59页/共97页第五十九页，共98页。7.2 马尔可夫链的状态(zhungti)分类同理可得，状态(zhungti)3、4、5也是遍历态。 因此，所有状态(zhungti)可以分为常返状态(zhungti)集 和非常返状态(zhungti)集 。第60页/共97页第六十页，共98页。7.3 独立增量(zn lin)过程 如果连续参量随机过程 具有无后效性，即任取 n 与 ，条件(tiojin)概率满足：则称 是连续(linx)参数马尔可夫过程。 如果 的取值状态空间是离散的，有限（或无限）可列的，这种随机过程也称为连续参数马尔可夫链。)(tX 独立增量过程是一种重要的马尔可夫过程，其参数和状态可以是连续的，也可以是离散的。第61页/共97页第六十一页，共98页。7.3 独立(dl)增量过程0)0(X 所谓独立增量(zn lin)是指非重叠时段的增量(zn lin)是彼此独立的。针对此特点，一般总是按顺序地安排时刻点： ，并令初值为零，即 ，使得第62页/共97页第六十二页，共98页。7.3 独立(dl)增量过程考察如下的条件(tiojin)概率由于(yuy) 彼此独立，nnnnxtXxtXxtXxtXP )(,)(,)()(110011所以，独立增量过程是马尔可夫过程。第63页/共97页第六十三页，共98页。7.3 独立增量(zn lin)过程 增量的平稳性使得 与 有着相同(xin tn)的概率分布，因此： 性质(xngzh)1 平稳独立增量过程 的一维特征函数为：第64页/共97页第六十四页，共98页。7.3 独立增量(zn lin)过程 性质2 平稳独立(dl)增量过程 满足：（1）均值与方差(fn ch)是 t 的线性函数，即：（2）协方差函数（3）自相关函数（4）相关系数函数其中， 与 为正常数，分别称为均值变化率与方差变化率。第65页/共97页第六十五页，共98页。7.3 独立增量(zn lin)过程证明(zhngmng)：（1）任取 ，有已被表示为两段不重叠时段上的增量(zn lin)，因此相互独立。于是：)(tX 如果函数 对任意 t 与 s 恒有： ，由数学知识可证明 必是 线性函数，并通过原点。令方差变化率为 ，有2)(xg第66页/共97页第六十六页，共98页。7.3 独立增量(zn lin)过程 （2）任取 ，有 先考虑 ，同样将 表示(biosh)为两段不重叠增量，并利用独立性，有)(tX综合(zngh)考虑 的情况，得到：注意：平稳独立增量过程本身是非平稳过程，只是其增量具有平稳性，并且彼此独立。第67页/共97页第六十七页，共98页。7.3 独立增量(zn lin)过程解：第68页/共97页第六十八页，共98页。7.3 独立增量(zn lin)过程)(nX 例 设 是 0-1分布的伯努利序列，其取值为0、1的概率分别为q、p。令 则 称 为二项（计数）过程。证明该过程是平稳独立增量过程，并讨论其基本(jbn)特性。 解：由于 是彼此独立的，因此， 的任意非重叠增量是独立的。又因 是同分布的，使得增量的分布与它的起始时刻(shk)无关。于是， 是平稳独立增量过程。)(nX)(nX第69页/共97页第六十九页，共98页。7.3 独立增量(zn lin)过程平稳独立(dl)增量过程 的典型样本序列与增量如图所示：（a）二项过程(guchng)（b）增量第70页/共97页第七十页，共98页。7.3 独立(dl)增量过程（1）特征函数为：（2）将其展开(zhn ki)为：（3）由特征函数定义可知(k zh)，其各种可能的概率取值为：。即：注意到 ，均值与方差的变化率为：（4）均值和方差为：注意到 ，均值与方差的变化率为：（4）均值和方差为：结论：如果说 是独立随机序列，则其累加过程是独立增量序列。特别地，若 是相互独立且同分布的随机变量，则其累加过程 是平稳独立增量过程。 , 2 , 1),(nnX第71页/共97页第七十一页，共98页。7.4 泊松过程(guchng) 泊松过程是一种典型的独立(dl)增量过程，它具有连续参数t与分离散状态取值，因而也是连续参数马尔可夫链。在通信、交通、日常零售业务等各个领域的研究中，泊松过程是各类问题建模时最常用的一种输入模型。第72页/共97页第七十二页，共98页。7.4 泊松过程(guchng) 7.4.1 定义(dngy)与背景 定义7.16 如果随机(su j)过程 具有以下特性：（1） 是一个初值为的计数过程，即（2）具有独立增量，即任取 （3）增量平稳性，即（4）当 很小时，有相互独立；第73页/共97页第七十三页，共98页。7.4 泊松过程(guchng)第74页/共97页第七十四页，共98页。7.4 泊松过程(guchng)第75页/共97页第七十五页，共98页。7.4 泊松过程(guchng)解：齐次泊松过程(guchng)是零初值平稳独立增量过程(guchng)，有第76页/共97页第七十六页，共98页。7.4 泊松过程(guchng) 到达时间指泊松事件(shjin)发生的时刻。 表示第i个事件(shjin)到达的时刻。 时间间隔指相邻两个泊松事件发生时刻之间的间隔。 表示(biosh)第n-1次事件到达和第n次事件到达之间的时间间隔。 两者的关系为：第77页/共97页第七十七页，共98页。7.4 泊松过程(guchng)第78页/共97页第七十八页，共98页。7.4 泊松过程(guchng)第79页/共97页第七十九页，共98页。7.4 泊松过程(guchng)第80页/共97页第八十页，共98页。7.4 泊松过程(guchng)第81页/共97页第八十一页，共98页。7.4 泊松过程(guchng)第82页/共97页第八十二页，共98页。7.4 泊松过程(guchng)第83页/共97页第八十三页，共98页。7.4 泊松过程(guchng)第84页/共97页第八十四页，共98页。7.4 泊松过程(guchng)第85页/共97页第八十五页，共98页。7.4 泊松过程(guchng)第86页/共97页第八十六页，共98页。7.4 泊松过程(guchng)第87页/共97页第八十七页，共98页。7.4 泊松过程(guchng)第88页/共97页第八十八页，共98页。7.4 泊松过程(guchng)第89页/共97页第八十九页，共98页。7.4 泊松过程(guchng)第90页/共97页第九十页，共98页。7.4 泊松过程(guchng)第91页/共97页第九十一页，共98页。7.4 泊松过程(guchng)第92页/共97页第九十二页，共98页。7.4 泊松过程(guchng)第93页/共97页第九十三页，共98页。7.4 泊松过程(guchng)第94页/共97页第九十四页，共98页。7.4 泊松过程(guchng)第95页/共97页第九十五页，共98页。7.4 泊松过程(guchng)第96页/共97页第九十六页，共98页。感谢您的观看(gunkn)！第97页/共97页第九十七页，共98页。NoImage内容(nirng)总结1。7.1.2 转移概率与切普曼-科尔莫戈罗夫方程。简称C-K（Chapman-Kolmogorov）方程。定理 齐次马尔可夫链满足(mnz)：。1. 可达、互通：。2. 首达时间的取值空间为:。同理可得，状态3、4、5也是遍历态。（1）均值与方差是 t 的线性函数，即：。时间间隔指相邻两个泊松事件发生时刻之间的间隔。感谢您的观看第九十八页，共98页。