CH7马尔可夫链与泊松过程.ppt

1,随机信号分析,第7章 马尔可夫链与泊松过程,第7章 马尔可夫链与泊松过程,马尔可夫过程是研究信号多级传输、分子的布朗运动、顾客服务、计算机网络流量等等诸多问题时使用的经典模型。 本章讨论： 1）马尔可夫过程的基本概念 2）转移概率与C-K方程 3）状态分类及极限特性 4）独立增量过程定义及性质 5）泊松过程定义及相关问题,第7章 马尔可夫链与泊松过程,7.1 马尔可夫链 7.2 马尔可夫链的状态分类 7.3 独立增量过程 7.4 泊松过程,7.1 马尔可夫链,第7章 马尔可夫链与泊松过程,7.1.1 基本定义,定义7.1 随机序列 的状态空间 E 为可数集，如果对任意 ，有：,则称该序列是马尔可夫链（Markov Chain）。,上式刻画了马尔可夫链的特性，称为马尔可夫性（简称马氏性），也称无后效性。,7.1 马尔可夫链,第7章 马尔可夫链与泊松过程,7.1.1 基本定义,定义7.2 任取 ，则条件概率,称为（n时刻的）一步转移概率（One Step Transition Probability）。,如果在任意时刻n， 都相同，则记为：,称这时的马尔可夫链为齐次马尔可夫链。,7.1 马尔可夫链,性质 转移概率满足：,为了直观地理解马尔可夫性，设想一质点在某直线的整数格点上随机运动的情形： 表示在 n 时刻质点位于 i 位置这一随机事件，如果把时刻 n 看做现在，时刻 0,1,2,n-1 表示过去，时刻 n+1 表示将来，那么马尔可夫性表明：此时位于 i 的质点将来会出现在哪里与它过去曾经在哪些位置停留过没有关系。简言之，将来完全由现在决定，与过去无关。转移概率 表示质点在时刻 n 从位置 i 向 j 转移的可能性，而齐次性表明在所有时刻质点的转移特性是相同的。,7.1 马尔可夫链,证明：,例7.1 设 是独立随机序列，随机序 列 中，相邻两个随机变量满足递归方程：,式中， 。试证明随机序列 是马尔可夫链。,彼此独立，,与 独立，,与 独立，,与 独立。因此，上式的条件部分可如下简化：,7.1 马尔可夫链,所以， 是马尔可夫链。,7.1 马尔可夫链,7.1 马尔可夫链,证明：级联的二进制传输信道中，前一节的输出即为后一节的输入。每节基本信道是彼此独立的，因此，在给定任意第n节输出X(n)的条件下，第n+1节的输出X(n+1)不再依赖于第n节以前所有(0,1,2,n-1)节的输出结果，即：,所以，X(n)是马尔可夫链。又由于每节信道的转移概率都相同，所以，它是齐次的。,7.1 马尔可夫链,（2）因为每节的转移概率是相同的，于是，一步转移概率为：,7.1 马尔可夫链,7.1 马尔可夫链,7.1 马尔可夫链,例7.3 在直线上有一质点作随机游动，质点在不同时刻 k 的随机运动 Z(k), k=1,2, 是统计独立的，取值为 +1, 0, -1 ， 相应的取值概率为 p, r, q ，p+r+q=1 。质点初始时刻位于原点，n 时刻的绝对位置为 ，试证明 是马尔可夫链。,证明：,该式是例7.1中当函数 时的一个特例。因此， 是马尔可夫链。,7.1 马尔可夫链,它的一步转移概率矩阵为：,状态转移图为：,7.1 马尔可夫链,7.1.2 转移概率与切普曼-科尔莫戈罗夫方程,对 n 时刻的一步转移概率与一步转移概率矩阵做简单的扩展，可定义 m 时刻到 n 时刻的转移概率为：,转移概率矩阵为：,显然，该矩阵所有元素非负，并且任取第 i 行满足：,7.1 马尔可夫链,7.1.2 转移概率与切普曼-科尔莫戈罗夫方程,定义7.3 若 是马尔可夫链，称行向量,为 n 时刻的概率分布向量。,对于 ，n时刻的概率分布可由全概率公式求出,写成向量形式为：,其中， 是 n 时刻 取 i 的概率。当n=0 时，称 p(0) 为初始分布。,7.1 马尔可夫链,定理7.1 （切普曼-科尔莫戈罗夫方程）设 ， 马尔可夫链的转移概率满足：,简称C-K（Chapman-Kolmogorov）方程。,矩阵形式为：,注：可由马尔可夫性和全概率公式证明,7.1.2 转移概率与切普曼-科尔莫戈罗夫方程,7.1 马尔可夫链,证明：,7.1 马尔可夫链,7.1 马尔可夫链,C-K方程的特点：,如果马尔可夫链是齐次的，且一步转移概率矩阵为P，则,可见： 与绝对时刻无关，而只与两时刻之差有关，这时称转移概率是平稳的，并将它们简记为：,分别称为k步转移概率和k步转移概率矩阵。这时，C-K方程表示为：,定理7.2 齐次马尔可夫链满足：,7.1 马尔可夫链,7.1 马尔可夫链,解：,所以， 是马尔可夫链。,该转移概率与n无关，,7.1 马尔可夫链,7.1 马尔可夫链,7.1 马尔可夫链,7.1 马尔可夫链,解：因为随机游动粒子的位置 是马尔可夫过程，其状态空间 E=0,1,2 ，由一步状态转移矩阵可得到如下的状态转移图：,7.1 马尔可夫链,（2）根据齐次马尔可夫链的性质，可得：,因此：时刻n处于状态0，时刻n+3处于各个状态的概率为：,7.1 马尔可夫链,（3）根据齐次马尔可夫链的性质，可得：,故有：时刻n处于状态0，时刻n+4处于各个状态的概率为：,7.1 马尔可夫链,7.1 马尔可夫链,解：由状态转移图可知：进入状态0或3后，该链永远停留在那里，形象地称这两个状态为吸收壁或吸收态。,由状态转移图可得一步转移矩阵为：,7.1 马尔可夫链,7.1.3 平稳分布与极限分布,定义7.4 对于一步转移概率矩阵为 的马尔可夫链 ，如果存在一种分布 ，使得,则称 为 的一个平稳分布。,显然，一旦 进入某个平稳分布后，它就一直处于该分布上，不再改变。,在 时收敛于某个分布，则称该分布为 的极限分布或最终分布。,7.1 马尔可夫链,7.1 马尔可夫链,解：（1）根据齐次马尔可夫链的性质，可知n=3时刻的概率分布向量为：,7.1 马尔可夫链,7.1 马尔可夫链,解：n级级联的二进制传输系统可描述为一个取值为（0,1）的马尔可夫链，易见，该链的一步状态转移概率为：,7.1 马尔可夫链,因此有:,7.1 马尔可夫链,7.1 马尔可夫链,结论：本例说明了一个有趣的结果,不论原始信息的分布如何，经过很多次有错(0q1)传播后,即使错误概率很小，其分布总趋于均匀分布,信息趋于未知。,7.2 马尔可夫链的状态分类,7.2.1 可达、互通、首达与首达概率,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,解：由一步状态转移概率矩阵可得如下的状态转移图：,1. 可达、互通：,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,2. 首达时间的取值空间为:,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,（1） 表示从状态i出发经过n步首次返回i的概率，简称为n步首返概率。,（2） 表示从状态i出发迟早返回i的概率，简称为最终返回概率。,7.2 马尔可夫链的状态分类,7.2.2 常返、非常返、周期与遍历,7.2 马尔可夫链的状态分类,7.2.2 常返、非常返、周期与遍历,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,解：该马尔可夫链有4个状态，分别设为0,1,2,3，其状态转移图为：,对状态0：,所以状态0是非常返态。,7.2 马尔可夫链的状态分类,对状态1：,所以状态1是非周期的正常返态，是遍历态。,同理，状态2和状态3也是遍历态。,因此，该马尔可夫链不是遍历链，但有三个遍历态。,7.2 马尔可夫链的状态分类,它指示 是否停留在 j 状态，则：,可以证明：常返状态平均返回次数为无穷多次，非常返状态平均返回次数为有限多次。,7.2 马尔可夫链的状态分类,7.2 马尔可夫链的状态分类,解：该链的状态转移图为：,7.2 马尔可夫链的状态分类,状态0：,所以状态0是常返态， 为遍历态。,状态1：,是遍历态。,状态2：,是非常返态。,7.2 马尔可夫链的状态分类,同理可得，状态3、4、5也是遍历态。,因此，所有状态可以分为常返状态集 和非常返状态集 。,7.3 独立增量过程,如果连续参量随机过程 具有无后效性，即任取 n 与 ，条件概率满足：,则称 是连续参数马尔可夫过程。,如果 的取值状态空间是离散的，有限（或无限）可列的，这种随机过程也称为连续参数马尔可夫链。,独立增量过程是一种重要的马尔可夫过程，其参数和状态可以是连续的，也可以是离散的。,7.3 独立增量过程,所谓独立增量是指非重叠时段的增量是彼此独立的。针对此特点，一般总是按顺序地安排时刻点： ，并令初值为零，即 ，使得,7.3 独立增量过程,考察如下的条件概率,由于 彼此独立，,所以，独立增量过程是马尔可夫过程。,7.3 独立增量过程,增量的平稳性使得 与 有着相同的概率分布，因此：,性质1 平稳独立增量过程 的一维特征函数为：,7.3 独立增量过程,性质2 平稳独立增量过程 满足：,（1）均值与方差是 t 的线性函数，即：,（2）协方差函数,（3）自相关函数,（4）相关系数函数,其中， 与 为正常数，分别称为均值变化率与方差变化率。,7.3 独立增量过程,证明：,（1）任取 ，有,已被表示为两段不重叠时段上的增量，因此相互独立。于是：,如果函数 对任意 t 与 s 恒有： ，由数学知识可证明 必是 线性函数，并通过原点。令方差变化率为 ，有,7.3 独立增量过程,（2）任取 ，有,先考虑 ，同样将 表示为两段不重叠增量，并利用独立性，有,综合考虑 的情况，得到：,注意：平稳独立增量过程本身是非平稳过程，只是其增量具有平稳性，并且彼此独立。,7.3 独立增量过程,解：,7.3 独立增量过程,例7.13 设 是 0-1分布的伯努利序列，其取值为0、1的概率分别为q、p。令 则 称 为二项（计数）过程。证明该过程是平稳独立增量过程，并讨论其基本特性。,解：由于 是彼此独立的，因此， 的任意非重叠增量是独立的。又因 是同分布的，使得增量的分布与它的起始时刻无关。于是， 是平稳独立增量过程。,7.3 独立增量过程,平稳独立增量过程 的典型样本序列与增量如图所示：,（a）二项过程,（b）增量,7.3 独立增量过程,（1）特征函数为：,（2）将其展开为：,（3）由特征函数定义可知，其各种可能的概率取值为：,。即：,注意到 ，均值与方差的变化率为：,（4）均值和方差为：,注意到 ，均值与方差的变化率为：,（4）均值和方差为：,结论：如果说 是独立随机序列，则其累加过程 是独立增量序列。特别地，若 是相互独立且同分布的随机变量，则其累加过程 是平稳独立增量过程。,7.4 泊松过程,泊松过程是一种典型的独立增量过程，它具有连续参数t与分离散状态取值，因而也是连续参数马尔可夫链。在通信、交通、日常零售业务等各个领域的研究中，泊松过程是各类问题建模时最常用的一种输入模型。,7.4 泊松过程,7.4.1 定义与背景,定义7.16 如果随机过程 具有以下特性：,（1） 是一个初值为的计数过程，即,（2）具有独立增量，即任取,（3）增量平稳性，即,（4）当 很小时，有,相互独立；,7.4 泊松过程,7.4 泊松过程,7.4 泊松过程,解：齐次泊松过程是零初值平稳独立增量过程，有,7.4 泊松过程,到达时间指泊松事件发生的时刻。 表示第i个事