马尔可夫链与泊松过程.doc

Ch.7 马尔可夫链与泊松过程马尔可夫过程是研究信号多级传输、分子的布朗运动、顾客服务、计算机网络流量等等诸多问题时使用的经典模型。本章讨论：1）马尔可夫过程的基本概念2）转移概率与C-K方程3）状态分类及极限特性4）独立增量过程定义及性质5）泊松过程定义及相关问题Ch.7 马尔可夫链与泊松过程7.1 马尔可夫链7.2 马尔可夫链的状态分类7.3 独立增量过程7.4 泊松过程7.1 马尔可夫链 此句作为后面每页ppt的标题 定义7.1 随机序列，可数集状态空间，如果下式恒成立，则称是马尔可夫链（Markov chain）。上式称为马尔可夫性（马氏性）、无后效性。定义7.2 任意，称条件概率 为(时刻的)一步转移概率(One step transition probability)。齐次马尔可夫链(Homogeneous Markov chain) ：满足下式条件的马尔可夫链：转移概率性质：（1）非负性： （2）归一性：步转移概率：时刻到时刻的转移概率转移概率矩阵：并且： （1）（2） 。齐次马尔可夫链：例7.1 设，其中是独立随机序列，试说明是马尔可夫链。解： 例7.2 级联的独立二进制传输系统如图所示试说明是齐次马尔可夫链，并求（一步）转移概率。解：（1）是齐次马尔可夫链，因为 （2）一步转移概率矩阵为时刻的转移概率矩阵：对于齐次马尔可夫链：状态转移图：用带符号的圆圈表示状态，带箭头的弧线表示可能的转移及其概率的一种有向图。例7.3 直线上作随机游动的质点：时刻的游动位移为且统计独立，。相应取值概率为。令，试说明是马尔可夫链。解：是例7.1中函数时的一个特例。定义7.3 若是马尔可夫链，称行向量 为时刻的概率分布向量。设，则： 向量形式：定理7.1 （查普曼-柯尔莫哥洛夫方程）设，马尔可夫链的转移概率矩阵满足简称C-K（Chapman-Kolmogorov）方程。矩阵形式：证明思路：运用全概率公式和马尔可夫性证明：当时方程特点：一步转移概率矩阵为的齐次马尔可夫链（1）（2）步转移概率：（3）步转移概率矩阵： （4） （5）（6）例7.4 随机序列，取值(0，1)，概率，经过累加器后得到随机过程。（1） 证明是齐次马尔可夫链；（2）给出的转移概率矩阵与状态图；（3）求步转移概率。解：（1）证： 且为独立平稳序列，是例7.1的特例； 因此是齐次马尔可夫链。（2）的一步状态转移概率矩阵（3）利用二项分布特性例7.5 记为在两个反射壁之间作一维随机游动粒子的位置，状态空间为，（1） 绘出状态图；（2） 求时刻处于状态0且时刻处于各状态的概率；（3） 求时刻处于状态0且时刻处于各状态的概率。解：（1）状态图反射壁(Reflecting barrier)：由于在0与2状态上，以概率1转移（弹回）到下一状态。（2）,（4） ,例7.6 某个具有双吸收壁的质点随机运动的状态图如下，试给出它的一步转移矩阵。解：吸收壁（Absorbing barrier）：进入状态0或3后，该链永远停留在那里。也称为吸收态(Absorbing state)。一步转移概率矩阵：定义7.4 马尔可夫链的一步转移概率矩阵为，如果存在一种分布，下式恒成立则称为的一个平稳分布。因为一旦进入该分布后，它就永远处于该分布上。也称为的极限分布或最终分布。例7.7 的齐次马尔可夫链， ，求：（1） 时刻的状态概率向量；（2） 给出其中的一个可能序列；（3） 当时是否存在？解：（1） （2）的可能样本序列为010101或101010。（3）当为偶数时：当为奇数时：所以，不存在极限。例7.8 取值为的有噪声对称二进制传输系统， ，其中，和分别是输入输出随机变量。将该类型传输系统进行级级联，并设输入到该级联系统的信源数据概率为。求：（1）系统的转移概率。（2）信源经过级联系统后，输出符号的取值概率。（3）当趋于无穷大时，上述两问的结果又如何？解：该系统是一个齐次马尔可夫链，（1）级级联后系统的转移概率为特征分解，故有，（2）信源经过该级联系统后，输出符号的取值概率为=（3）令趋于无穷大，当时，并且当时，如果，因此，而；如果，与都不存在。本例说明了一个有趣的结果：不论原始信息的分布如何，经过很多次有错（）传播后，即使错误概率很小，其分布总趋于均匀分布，信息趋于未知。7.2 马尔可夫链的状态分类 此句作为后面每页ppt的标题定义7.5 齐次马尔可夫链，对任意给定的两个状态，存在整数使,则称状态可达状态，简记为；若同时还存在整数，使也成立，则称状态和状态是互通的，简记为。包含了从状态出发到达状态的所有可能轨道。定义7.6 对于两个状态，从状态出发，经过步转移后首次到达状态的步数，称为从状态出发后首次到达状态的时间，简称为首达时间。如果从状态出发，永远不能状态，则标记为。的取值空间：。例7.9 齐次马氏链， 分析三个状态之间的可达、互通及首达时间的取值空间。解： 可达、互通：（1） ，故状态0可达状态1和2。（2） 任意，故状态1和2不可达状态0。（3） ，故状态1和2互通。首达时间的取值空间：取值空间为 取值空间为取值空间为 取值空间为取值空间为。定义7.7 任意，称为状态出发到达状态的步首达概率。定义7.8 任意，称为从状态出发到达状态的最终到达概率。注意：求和式中上标不包括，因此有，显然，当时有， （1）简称为步首返概率；（2）简称为最终返回概率。定义7.9 对状态，若，则称状态是常返的(Recurrent or persistent)；若，则称状态是非常返的或滑过的(Transient)。定义7.10 对于状态，称为从状态出发的平均返回步数。如果i是常返态，则；否则，因，。定义7.11 对常返状态，若，则称状态是正常返状态(Positive recurrent state)；若，则称状态是零常返状态(Null recurrent state)。即：（1），且，则是正常返状态；（2），且，则是零常返状态。定义7.12 非空集合，记其最大公约数为，则称为状态的周期。通常，如果，则称状态是非周期状态，否则称为周期状态。且仅当时，有。定义7.13 非周期的正常返状态称为遍历态(Ergodic state)。如果一个马尔可夫链的所有状态都是遍历态，则称该马尔可夫链是遍历马尔可夫链。例7.10 设齐次马氏链转移矩阵为判断该链所有状态的遍历性。解：分别设为状态,状态0是非常返状态：。状态1是遍历态：，状态2和状态3也是遍历态。因此，该链不是遍历链，但有三个遍历状态。令，则是平均返回次数。常返状态平均返回次数为无穷多次，非常返状态平均返回次数为有限多次。例7.11 设，转移矩阵为对状态进行分类。=解：状态0为遍历状态：，。状态1为非常返态：。状态2为遍历状态： ，。同理可得，状态3、状态4和状态5也是遍历状态。所有状态可以分为常返状态集和非常返状态集。7.3 独立增量过程 此句作为后面每页ppt的标题推论1：连续参数马尔可夫过程：如果具有无后效性，即条件概率满足 推论2：连续参数的马尔可夫链：如果的取值状态空间是离散的，有限（或无限）可列的。定义7.14 随机过程，,记增量，。若彼此独立，则称为独立增量过程（Independent increment process）。令，则增量也可以表示为独立增量过程是马尔可夫过程：条件概率为彼此独立，与所有都独立，有定义7.15 若是独立增量过程且对任意与，与恒有相同的概率分布，则称该过程为平稳独立增量过程。性质1 设，则的一维特征函数为性质2 平稳独立增量过程的基本矩（1） ：均值变化率 ：方差变化率（2） （3）（4）证明（3）：任取，利用均值和方差特性因此有：例7.10 零初值累积平稳独立噪声过程。均值与方差变化率为和。试求：的均值和方差，。解： 例7.11 设与，其中取值（0-1）概率分别为的伯努利序列，则为二项（计数）过程（Binomial counting process）。说明该过程是平稳独立增量过程，并讨论其基本特性。解：因是独立同分布的，故是平稳独立增量过程。(1) 特征函数：(2) 展开式：(3) 概率取值为： ， (4) 均值、方差与协方差函数为：， 7.4 泊松过程 此句作为后面每页ppt的标题定义7.16 如果随机过程具有以下特性（1） 是一个的计数过程；（2） 增量独立；（3）增量平稳：即,；（4）当很小时 和 则称是参数为的（齐次）泊松过程（Poisson Process）。定义7.17 如果随机过程具有以下特性（1） 是一个的计数过程；（2） 具有平稳独立增量；（3） 其概率密度函数是泊松的则称是参数为的（齐次）泊松过程。上述两个定义是完全等价的，证明略。泊松过程是一种典型的独立增量过程泊松过程是非平稳过程泊松过程是连续参数马尔可夫链应用于通信、交通、日常零售业务等各个领域泊松过程是各类问题建模时最常用的一种输入模型泊松过程是一种典型的独立增量过程，有： 故：均值与方差： ； 相关函数： 协方差函数： 相关系数函数： 例7.12 N(t)参数为的齐次泊松过程，求，。解：定义7.18 泊松事件：泊松计数过程中被统计的事件。如顾客到达、服务器收到申请等。到达时间（arrival time）：泊松事件发生的）时刻。表示第个事件得到达时间。时间间隔（Interarrival time）：相邻两个泊松事件发生（或称到达）时刻之间的间隔。表示第次事件到达和第次事件到达之间的的时间间隔。关系：两个序列都是随机的（1） 事件发生时刻随机序列： 。（2） 事件发生的间隔时间随机序列： 。性质1 时间间隔序列的独立指数分布，概率密度函数为 证明：事件等价于事件，有，（） 之间的独立性证明略。性质2 到达时间服从分布，其概率密度函数为：也称为爱尔朗（Erlang）分布。证明：事件等价：至时刻至少发生次泊松事件 于是有： ,()特征函数法：特征函数：上式的傅立叶反变换，即得的概率密度函数式。定义7.19 称为泊松过程在时间到的平均变化率。也称为泊松增量。其物理函数是在时间到时间上，泊松计数事件的平均次数。在时，统计独立。的统计特性：1 一阶概率：2 均值： 3 相关函数： 由可知是广义平稳过程。例7.13 设是某电话交换台受理的呼叫次数，它是泊松过程，求在任意5分钟里平均呼叫次数的均值与方差。解：均值：方差：定义7.20 若泊松事件发生时刻为，称为泊松冲激序列(Poisson impulse train)，是广义平稳序列。也称为瞬时增长率。其另外两种描述形式的微分描述： 极限式描述： 泊松冲激序列的基本矩特性：1 均值： 和 2 相关函数 = 和 3协方差函数：= 例7.14 雷电、电火花等突发放电对电子设备造成的干扰是一种泊松冲激序列，干扰的平均功率为6个单位，而每个泊松冲击的平均功率为3个单位。求单位时间内出现3次泊松冲激的概率。解：。于是。定义7.21 记第个泊松事件发生的随机时刻引起的响应为，则所有响应的输出和称为过滤泊松过程（Filtered Poisson process），记为：冲激序列描