第五章 连续时间的Markov链.doc

第五章连续时间的马尔可夫链第五章 连续时间的马尔可夫链 第四章我们讨论了时间和状态都是离散的链，本章我们研究的是时间连续、状态离散的过程，即连续时间的链. 连续时间的链可以理解为一个做如下运动的随机过程：它以一个离散时间链的方式从一个状态转移到另一状态，在两次转移之间以指数分布在前一状态停留. 这个指数分布只与过程现在的状态有关，与过去的状态无关（具有无记忆性），但与将来转移到的状态独立. 5.1 连续时间马尔可夫链的基本概念 定义 5.1 设随机过程，状态空间，若对任意的正整数及任意的非负整数，条件概率满足 （5.1）则称为连续时间的链.由定义知，连续时间的链是具有性（或称无后效性）的随机过程，它的直观意义是：过程在已知现在时刻及一切过去时刻所处状态的条件下，将来时刻的状态只依赖于现在的状态而与过去的状态无关.记(5.1)式条件概率的一般形式为 （5.2）它表示系统在时刻处于状态，经过时间后在时刻转移到状态的转移概率，通常称它为转移概率函数.一般地，它不仅与有关，还与有关.定义 5.2 若(5.2)式的转移概率函数与无关，则称连续时间链具有平稳的转移概率函数，称该链为连续时间的齐次（或时齐）链. 此时转移概率函数简记为.相应地，转移概率矩阵简记为.若状态空间，则有 （5.3） 假设在某时刻，比如说时刻0，链进入状态，在接下来的个单位时间内过程未离开状态（即未发生转移），我们要讨论的问题是在随后的个单位时间中过程仍不离开状态的概率是多少？由性知，过程在时刻处于状态的条件下，在区间中仍处于状态的概率正是它处在状态至少个单位时间的（无条件）概率，若记为过程在转移到另一状态之前停留在状态的时间，则对一切有可见，随机变量具有无记忆性，因此，服从指数分布.因此，一个连续时间的链，每当它进入状态，具有如下性质：（1） 在转移到另一个状态之前处在状态的时间服从参数为的指数分布；（2） 当过程离开状态时，接着以概率进入状态,且 .当时，称状态是瞬时状态，因为过程一旦进入状态就离开；若，称状态为吸收状态. 因为过程一旦进入永远不再离开.尽管瞬时状态在理论上是可能的，但我们以后还是假设一切，.因此，考虑连续时间链，可以按照离散时间的链从一个状态转移到另个状态，但在转移到另一状态之前，它在各个状态停留的时间服从指数分布，而且在状态停留的时间与下一个状态必须是相互独立的随机变量.定理5.1 齐次链的转移概率函数具有下列性质：（1）；（2）；（3）.（2）式表明转移概率矩阵中任一元素行和为1；（3）式称为连续时间齐次链的方程，简称方程.证明 （1）和（2）由概率定义及的定义易知，下面只证明（3）式由全概率公式和性可得 对于转移概率函数，我们约定 （5.4）称上式为连续性条件或正则性条件.连续性条件保证转移概率函数在边界点处右连续.它的直观意义在于：当系统经过很短时间，其状态几乎不变，也就是认为系统刚进入一个状态又立刻离开这个状态是不可能的. 定义 5.3 连续时间链在初始时刻（即零时刻）取各状态的概率 （5.5）称为它的初始分布.在时刻取各状态的概率 称为它在时刻的绝对（概率）分布.初始分布和绝对分布都是概率分布，对于任意，总满足：（1）；（2）.利用全概率公式容易得到 （5.6）（5.6）式表明：连续时间链的绝对概率分布完全由其初始分布和转移概率函数所确定.下面举一个简单的例子说明转移概率函数的计算方法.例5.1 证明过程是连续时间的齐次链.证明 先证明过程具有性.由过程的独立增量性和，对任意，有= 另一方面，因为=因此 =即过程是连续时间的链. 再证齐次性. 当时，由过程的定义，得到当时，由于过程的增量只取非负整数值，因此，故即转移概率函数只与有关，因此，过程具有齐次性.容易看出，固定时，是关于的连续可微函数。5.2 微分方程 对于离散时间齐次链，如果已知其一步转移概率矩阵，则步转移概率矩阵由一步转移概率矩阵的次方即可求得.但是，对于连续时间齐次链，由于“步长”的概念失效，转移概率函数的求法较为复杂，一般通过解微分方程求出转移概率函数.为此，我们首先讨论的可微性及所满足的微分方程.定理5.2 设齐次链满足连续性条件(5.4)，则对于任意固定的转移概率函数是的一致连续函数.证明 设，由方程，有由此可知 以及 因此 对于，可得到类似的不等式.因此 .由连续性条件，令可得到证明.定理5.3 设是齐次连续时间链的转移概率函数，则有； (5.7) (5.8)证明：略定理5.3中定义的是齐次连续时间链从状态到状态的转移概率密度或称转移速率（ ）.也可称为从状态到状态的跳跃强度.转移速率函数刻画了链的转移概率函数在零时刻对时间的变化率. 定理中极限的概率意义为：在长为的时间区间内，过程从状态转移到状态的概率，等于加上一个比高阶的无穷小量；从状态到转移到另一其它状态的转移概率等于加上一个比高阶的无穷小量.转移速率函数也可以表示为以下形式：当充分小时 推论 对有限齐次过程，有 （5.9）证明 由定理5.1，即由于求和是在有限集上进行，因此即.证毕.对于状态是无限的齐次过程，一般只有.若连续时间齐次链是具有有限状态空间，则其转移概率速率可构成以下形式的矩阵 （5.10）由(5.10)知，Q矩阵的每一行元素之和为0，主对角线元素为负或为0，其余时，.利用Q矩阵可以推出任意时间间隔的转移概率函数所满足的方程组，从而可以求出转移概率函数.下面我们给出转移概率函数满足的微分方程.定理5.4 (向后方程) 设是满足连续性条件的有限齐次链的转移概率函数，则对一切及，有 (5.11)证明 由方程于是，由速率函数的定义，得 定理5.4中满足的微分方程组称为向后方程（或称后退方程）（ ），是因为在计算时刻状态的概率分布时，我们对退后时刻的状态取条件，即我们从 开始计算. 对于时刻的状态取条件，类似地可以导出另一组方程，称为向前方程或前进方程（ ）. 定理5.5 (向前方程)在连续性条件下，有， (5.12)利用向后方程和向前方程及初始条件可以求出.向后方程和向前方程虽然形式上不同，但可以证明它们所求得解是相同的，在实际应用中，当固定最后所处状态,研究时，采用向后方程较为方便；当固定状态，研究，则采用向前方程较方便. 需要指出的是：对于状态空间为的齐次链，当时，向后方程和向前方程依然成立.向后方程和向前方程可以写成矩阵形式 （5.13） （5.14）此时Q矩阵为 （5.15）其中矩阵的元素为矩阵各元素的导数，而 （5.16）由此，连续时间链转移概率函数的求解问题就是矩阵微分方程的求解问题，其转移概率函数由其转移速率矩阵决定.特别地，若矩阵是一个有限维矩阵，则(5.13),(5.14)的解为 （5.17） 有关齐次链在时刻处在状态的绝对分布，我们有下面的定理定理5.6（方程） 齐次链在时刻处在状态的绝对分布满足下列方程： （5.18）证明 由于，将向前方程两边乘以，并对求和，得因此 由式（5.18）可得到任意时刻时链的一维分布.同离散链类似，在时的性质，如连续性、可微性，这些性质称为的无穷小性质.下面我们进一步讨论当时的性质（即遍历性）. 定义 5.4 设为连续时间链的转移概率，若存在时刻和，使得 （5.19）则称状态是互通的；若所有的状态都是互通的，则称此链是不可约的. 定义 5.5 设为连续时间链的转移概率函数，为一概率分布，如果对于一切，有 （5.20）则称概率分布为链的平稳分布. 我们知道，所谓平稳分布就是不因转移而变化的分布，与无条件概率相比较，当无条件概率是与有关的常数时，该链存在平稳分布. 如果连续时间的链存在平稳分布，记（常数）， （5.21）则用乘以向前方程的两边，再对相加，可得 （5.22）（5.22）给出了平稳分布所必须满足的方程. 定理5.7 设连续时间链是不可约的，则有下面的性质：（1） 若它是正常返的，则极限存在且等于，这里是方程组 （5.23）的唯一非负解，此时，称是该过程的平稳分布，且（2） 若它是零常返的或非常返的，则 （5.24）证明：略在实际应用中，有些问题可以直接用向前或向后方程求解，有些问题不能直接求解，我们用（5.23）来求解.例5.2 设链的状态空间为，当时，；当时，.求解 根据向前方程（5.12），由于，因此，所以 解得 利用初始条件 ，则当时，而当时，于是 ， 例5.3 （随机信号）设信号仅取两个可能值“”和“”，表示时刻接收到的信号.是状态空间为的齐次链.设在转移到状态之前在状态停留的时间是参数为的指数变量，而在回到状态之前它停留在状态的时间是参数为的指数变量，即转移概率函数为 ，由此并利用定理5.3，有，故得Q矩阵为 相应的向前方程为，初始条件为 化为一阶线性微分方程可解得，记，则，而 ，.令，可得 ，.由此可见，当时，存在且与无关，由定理5.7，平稳分布为 若取初始分布为平稳分布，即 则在时刻的绝对概率分布为在平稳状态时，此链的均值函数和协方差函数分别为 ， 例5.4 （机器维修问题）设在例5.3中，状态代表某机器正常工作，状态代表机器出现故障.状态转移概率与例5.3中相同，即在时间内，机器从正常工作变为出故障的概率为；在时间内，机器从有故障变修复后正常工作的概率为，求在时正常工作的机器，在时为正常工作的概率.解 由例5.3，要求机器最后所处的状态为正常工作，只需计算即可.由于 ，且 因此 例5.5 （排队问题）设有一随机服务系统到达服务台的顾客数是强度为的过程.服务台只有一个服务员，对顾客的服务时间是服从参数为的指数分布的随机变量.假定顾客接受服务的时间与顾客到达服务台的人数情况相互独立，如果服务员空闲时到达的顾客立刻接受服务；如果顾客到达时服务员正在为一顾客服务，则他必须排队等待；如果一顾客到达时发现已经有两个人在等待，则他就离开不再回来.设是时刻服务台里的顾客数（包括正在被服务的顾客和排队等待的顾客），这是一个连续时间的链，其状态空间为，假设在0时刻系统处在零状态，求在时刻系统处在状态的概率所满足的微分方程.解 考虑建立方程，为此，先求链的矩阵.若，当有一顾客来到服务台时，则状态由转移到，因到达服务台的顾客数是强度为的过程，因此，在内有一顾客达到服务台的概率为因此有 在有两个或两个以上顾客到达的概率为，故有又利用矩阵的性质，得到.若，表示在时刻有一顾客正在被服务，由于对顾客服务的时间是服从参数为的指数分布的随机变量，则在内完成服务的概率为.因此，在内系统由状态转移到状态的概率，也就是在这段时间内没有顾客到来，且完成对那个顾客的服务的概率为=因此 同理 =从而得到 ， 同理，=仿上面的做法，得到 若，则这时系统不能接受新顾客，则状态只能转移到状态或仍保持在状态，在此情况下，在内对顾客服务结束的概率为 ，从而，由此得到，.所求的Q矩阵为 根据方程得初始条件为5.3 生灭过程5.3.1 生灭过程的基本概念连续时间的链的一类重要的特殊情况是生灭过程，它的特征是在很短时间内，系统的状态只能从状态转移到状态或或保持不变，而且生灭过程的所有状态都是互通的，确切的定义如下： 定义5.6 设连续时间的齐次链的状态空间为，转移概率函数为，如果 （5.25）则称为生灭过程，为出生率，为死亡率.若，为正常数），则称为线性生灭过程；若，则称为纯生过程；若，则称为纯灭过程.从定义可以看出，如果不计高阶无穷小，则生灭过程的变化状态只有3种情形：或由变到，即增加1（如果是群体个数，则表明“生”了一个个体），其概率为；或由变到，即减少1（表明群体“死”了一个个体），其概率为；或群体个数没有变化，其概率为.因此，生灭过程所有状态是相通的，但在很短的时间内，只能在相邻的状态内变化：或状态无变化，或“生”一个，或“灭”一个，故有生灭过程之称.由定理5.3得，由此我们得到生灭过程的Q矩阵为 （5.26）相应地，向后方程， （5.27）向前方程是 （5.28）因为上述方程组的求解比较困难，同离散时间的链的情形一样，我们通过引进遍历性、极限分布来讨论其平稳分布，由定理5.7 （5.29）用递推法得利用，得到平稳分布， (5.30)上式也指出生灭过程平稳分布存在的充要条件是 （5.31） 生灭过程在计算机（通信网络）、系统更换（维修）、生态学等问题有广泛的应用，下面给出几个实例. 5.3.2 生灭过程的几个应用实例例5.6 (排队系统) （续例5.5）假设顾客按照参数为的过程来到一个有个服务员的服务站，即相继来到之间的时间是均值为的独立指数随机变量，每个顾客一来到，如果有服务员空闲，则直接进行服务，否则此顾客要加入排队行列（即在队中等待）.当一个服务员结束对一个顾客的服务时，顾客就离开服务系统，排队中的下一位顾客（若有顾客等待）进入服务.假定相继服务时间是相互独立的指数随机变量，均值为.如果记为时刻系统中的人数，则是生灭过程 （5.32）排队系统中表示过程，代表个服务员.特别地，在排队系统中，于是若，则由(5.25)式得要平稳分布（即极限分布）存在，必须小于是直观的.顾客按速率到来且以速率受到服务，因此，当时，他们到来的速率高于他们接受服务的速率，排队的长度趋于无穷；的情况类似于对称的随机游动，它是零常返的，从而没有极限概率.例5.7 （电话问题的爱尔朗（）公式）两个电话分局，假定它们之间有条线路，两电话局用户之间通话要占用这些中继线，每个电话局都有许多用户，其数量比大得多，因此，不管通话的用户占有几条中继线，不在通话的用户几乎总是不变的.因此，可以假定在中又有一用户要求通话的概率为，而与正在通话的用户无关，如此时有空着的中继线，则上述用户就可以占用空着的中继线路而进行通话，否则该用户的要求因线路占满而取消.再假定每一个时刻占用中继线通话的用户，在内将结束通话，从而空出一条中继线的概率为，并且各用户之间是相互独立的.在上述假定下，用表示时刻正在使用的中继线路的条数，则是一个齐次的有限链，记其转移概率为，则有 .这是一个生灭过程，相应的 由(5.30)知它的平稳分布为于是 （5.33）这就是著名的公式.例5.8 (机床维修) 设有台机床，个维修工人（），机床或者工作，或者等待维修.机床损坏后，如有维修工人空着，则空着的工人立即来维修，否则等待，直到有一个工人修好手中的一台机床后再来维修，机床按先坏先修的原则排队，如果进一步假定：（1） 在时刻正在工作的一台机床在中损坏的概率为；（2） 在时刻正在修理的一台机床在中被修好的概率为；（3） 各机床之间的状态（指工作或损坏）是相互独立的.在上述假定下，如用表示在时刻损坏了的（包括正在维修和等待维修的，即不在工作的）机床台数，则是一个齐次的有限链，用表示该链的转移概率，根据上述假设，有事实上，表明在时刻有台机床损坏的条件下，在中又有一台机床损坏且台正在修理的机床在该段时间内都未修好的概率为即 类似地，有 可见这是一个纯生过程，相应地有 因此，可以得到它的平稳分布如下：（1） 当时，有（2） 当时，有 而 由此可见，在给定的之后，对于不同的s就可用上述公式求出相应的，进而求出相应的均值（即安排s个维修工人时，平均不工作的机床台数）等，根据这些数据来确定合适的工人数.例5.9 (尤尔（）过程) 设群体中各个个体的繁殖是相互独立、强度为的过程.若假设没有任何成员死亡，以记时刻群体的总数量，则是一个纯生过程，其.称此纯生过程为尤尔过程，计算（1） 从一个个体开始，在时刻群体总量的分布；（2） 从一个个体开始，在时刻群体诸成员年龄之和的均值.解 记为第个与第个成员出生之前的时间，即是群体总数从变化到所花的时间.由尤尔过程的定义知道，是独立的具有参数为的指数分布，因此 由归纳法可以证明由于 因此 由此可见，从一个个体开始，在时刻群体的总量具有几何分布，其均值为.一般地，如果群体从个个体开始，在时刻群体总量是个独立同几何分布随机变量之和，具有负二项分布，即 （2）记为群体在时刻诸成员年龄之和，则可以证明其中是最初个体在的年龄，取期望得 例5.10 (传染模型) 有个个体的群体，在时刻