1、第5章 马尔可夫过程第5章 马尔可夫过程5.1 马尔可夫过程的定马尔可夫过程的定义义5.2 马氏链的刻马氏链的刻画画5.3 马氏链的状态空间分马氏链的状态空间分解解5.4 转移概率的极限与平稳分转移概率的极限与平稳分布布5.5 连续时间马氏过程的转移概连续时间马氏过程的转移概率率5.6 马氏过程的状态空间分解和平稳分马氏过程的状态空间分解和平稳分布布5.7 应用举例应用举例 习题五习题五第5章 马尔可夫过程马尔可夫过程是由前苏联数学家 A.A.Markov 首先提出和研究的一类随机过程，至今已成为内容十分丰富、理论上相当完整、应用也十分广泛的一门数学分支，其应用领域涉及计算机、通信、自动控制、
2、随机服务、可靠性、生物学、经济学、管理学、教育学、气象学、物理、化学等。本章只介绍状态集可列或有限的离散时间和连续时间马尔可夫过程。离散时间的简称为马氏链。第5章 马尔可夫过程5.1 马尔可夫过程的定义马尔可夫过程的定义设有一随机过程X(t)，t T，其状态空间 S 可列或有限(统称为可数)，我们考虑其有限维分布函数。对 n 0，t1 t 2 t n+1，t k T，(k=1，2，n+1)，及状态 i 1，i 2，in+1 S，由乘法公式我们有第5章 马尔可夫过程根据条件概率的定义，上式中自然要求从而于是(5.1.1)式中各式均有定义。以后在涉及到条件概率时，我们总如此假定，不再一一声明。第5
3、章 马尔可夫过程对于(5.1.1)式，最简单的莫过于以下情形:此时第5章 马尔可夫过程显然，(5.1.3)式对任意的 i 1，i 2，i n+1 都成立意味着 X(t 1)，X(t 2)，X(t n+1)相互独立。但相互独立在实际中是非常少见的，而且从数学上来说用不着作为随机过程来研究它。比独立稍为复杂一点的则是以下情形:第5章 马尔可夫过程此时第5章 马尔可夫过程(5.1.4)式所示的性质，我们称之为无后效性，它表示在已知系统现在所处的状态之下，系统将来的演变与过去无关。很多实际问题都具有这种无后效性。例如，生物基因遗传从这一代到下一代的转移中仅依赖于这一代而与以往各代无关。再如，每当评估一
4、个复杂的计算机系统的性能时，就要充分利用系统在各个时刻的状态演变所具有的通常概率特性:即系统下一个将到达的状态，仅依赖于目前所处的状态，而与以往处过的状态无关。此外，诸如某公司的经营状况等等也常常具有或近似地具有无后效性。我们给出如下定义。第5章 马尔可夫过程定义定义 5.1.1 设 X=X(t)，t T 是定义在概率空间(，F，P)上，取值于可数集合 S中的一个随机过程，如果对任意的正整数 n，t1 t 2 t n+1，t k T，(k=1，2，n+1)及状态 i1，i 2，i n+1 S 均有则称此过程为马尔可夫过程，简称为马氏过程。称(5.1.6)式为马尔可夫性，简称为马氏性，也称为无后
5、效性。第5章 马尔可夫过程马氏性的直观含义可以解释如下:将 tn 看作为现在时刻，那末，t 1，t 2，t n-1 就是过去时刻，而 tn+1 则是将来时刻，于是，(5.1.6)式是说，当已知系统现时情况的条件下，系统将来的发展变化与系统的过去无关。第5章 马尔可夫过程我们称马氏过程 X 取值的全体所组成的集合 S 为过程的状态空间，它可以是任意的一个集合，但为了数学上的处理，往往要对它加以某种可测性的结构。本章只讨论 S 为可列或有限(称为可数)的情形。(5.1.6)式是关于 S 可数时给出的。马氏过程的参数集 T 常用的有两种情形:连续的区间和可列集，常称前一情形的 X 为马氏过程，称后一
6、情形的 X 为马氏链。这些是本章下面将要分别介绍的。我们常称 X(t)=i 为“系统在 t 时处于状态 i”。第5章 马尔可夫过程对于 T=0，1，2，的马氏链 X=X(0)，X(1)，X(2)，我们常将它记为 X=X n，n 0。对此，容易证明，马氏性(5.1.6)式等价于对任一 n 0，i 0，i 1，i n+1 S 均有与(5.1.6)式等价的形式还有不少，详细的可见参考文献 12 第 1 章的定理 1，那儿共给出了10 种形式及其互相等价的证明。第5章 马尔可夫过程5.2 马氏链的刻画马氏链的刻画本节讨论如何刻画一个马氏链。为方便起见，我们记状态空间 S=1，2，3，它可以是有限的或可
7、列的，记 T=0，1，2，马氏链 X=X n，n 0。首先引入概率向量和随机矩阵。第5章 马尔可夫过程定义定义 5.2.1 (1)称可数维的向量 p=(p 1，p 2，p 3，)为概率(行)向量，如果其各元均非负且 j p j=1。概率列向量可类似定义。(2)称可数维的矩阵 P=p(ij)为随机矩阵，如果它的每一行均是概率向量，即容易验证，随机矩阵具有如下性质。第5章 马尔可夫过程性质性质 5.2.1 (1)随机矩阵 P 的任意次幂 P m(m 0)均是随机矩阵;(2)如果随机矩阵 P 的各行皆对应相等，即 pij=p j，(i，j)，则为了描述马氏链 X，由其定义(5.1.6)式，我们引入记
8、号我们进一步约定第5章 马尔可夫过程定义定义 5.2.2 系统在 n 时处于状态 i 的条件下经过 k 步转移，于 n+k 时转移到 j 的条件概率 p(k)ij(n)称为 X(在 n 时)的 k 步转移概率;第(i，j)个元素为 p(k)ij(n)的矩阵 P(k)(n)称为 X(在 n 时)的 k 步转移概率矩阵。特别地，k=1 时(在 n 时)的一步转移概率和一步转移概率矩阵分别简记为 pij(n)和 P(n)。称 p(k)ij(n)，i，j S，n，k 0 为 X 的有限步转移概率族。由(5.2.2)式知 P(0)(n)=I 为单位矩阵。第5章 马尔可夫过程对于 X 的 k 步转移概率矩
9、阵 P(k)(n)，由概率的定义易知 p(k)ij(n)0，进而，由完全可加性可得因此 P(k)(n)均是随机矩阵。第5章 马尔可夫过程从马氏链的定义(5.1.6)式出发，我们在(5.2.1)式中引入了 X 的 k 步转移概率，而由马氏链的等价定义(5.1.7)式知，我们似乎只需要引入 X 的一步转移概率即可。由于定义(5.1.6)式和(5.1.7)式是等价的，因此易于猜测 k 步转移概率与一步转移概率之间应是等价的，即可以互相表示。为此，我们先来证明以下称之为 Chapman-Kolmogorov(简称为 CK)方程的一个公式。第5章 马尔可夫过程定理定理 5.2.1其中(5.2.3 )式是
10、(5.2.3)式的矩阵形式。第5章 马尔可夫过程证明证明 由转移概率定义、全概率公式及马氏性，有第5章 马尔可夫过程 CK 方程(5.2.3)式的直观意义如下:系统 n 时从状态 i 出发，经过 k+m 步于 n+k+m时转移到状态 j，可以先在 n 时从 i 出发经过 k 步于 n+k 时转移到某个中间状态 l，再在n+k 时从状态 l 出发经 m 步于 n+k+m 时转移到状态 j，而中间状态 l 取遍全空间 S。但需要指出的是，CK 方程并非对所有随机过程均成立，因为在证明的第三个等式中用到了马氏性。第5章 马尔可夫过程在(5.2.3 )式中取 m=1，可得由此递推，即得以下公式:其分量
11、形式为(5.2.4 )式说明，对于马氏链 X，其 k 步转移概率由一步转移概率所完全确定。因此，两者等价。第5章 马尔可夫过程马氏链 X 的转移矩阵列 P(n)(n=0，1，2，)只刻画了随机系统在转移过程中的概率法则，并不能由它决定出系统初始所处状态的概率，因此有必要引进概率 qi=P X 0=i，i S，并称 q i，i S 为 X 的初始分布，称第 i 个分量为 q i 的向量 q 为 X 的初始分布向量。第5章 马尔可夫过程定理定理 5.2.2 马氏链 X 的有限维分布函数族由其初始分布和一步转移概率矩阵列 P(n)(n=0，1，2，)所唯一确定。第5章 马尔可夫过程证明证明 对任给的
12、 n，非负整数 t1 t 2 0。称此图为马氏链的状态转移概率图。于是从 i 到 j 有一条路意指有正整数 n使得 p(n)ij0。由于随机矩阵 P 的行和为 1，因此在有向图中我们可以去掉节点自身到其自身的弧(在图论中称为自环)。下面我们讨论几个马氏链的例子。第5章 马尔可夫过程例例 5.2.1 (双壁随机游动)设有一质点只能在 S=0，1，2，N 中各点上作随机游动，移动的规则如下:移动前若在 n 1，2，N-1 上，则以概率 p 向右移动一格到 n+1，以概率 q 向左移动一格到 n-1 处，而以概率 r 停留在原处，自然，p、q、r 非负且 p+q+r=1;移动前若在 0 处，则质点以
13、概率 p 0 反射回 1 处，以概率 r 0 继续停留在 0 处;移动前若在 N 处，则质点分别以概率 q N 和 r N 反射回 N-1 处或停留在 N 处。0 和 N 是限制质点运动的两道墙壁，当 r 0=1、p 0=0 时，称 0 为吸收壁;当 r 0=0、p 0=1 时，称 0 为反射壁;在一般情形，称 0 为部分反射壁。第5章 马尔可夫过程壁 N 也有类似的多重含义。以 X n表示质点在时刻 n 所处的位置，则容易看出，X=X n 是一以 S 为状态空间的齐次马氏链，其转移概率矩阵为它是一个三对角矩阵。上例可描述多种实际问题。第5章 马尔可夫过程实例一实例一 赌徒输光问题。设某赌徒与
14、一赌金足够多的对手进行赌博。将状态 i S 解释为赌徒在某时刻所拥有的资金，p 是每局赌博中赌徒赢的概率，q 为输的概率，而 r 则为和的概率;每局中赢或输的赌金为 1 个单位。假定 0 和 N 均为吸收壁，于是吸收壁 0 表示赌徒已经输光，不能再赌，从而赌博结束;吸收壁 N 可表示赌徒已赢得较多的钱因而停止赌博。于是 X n 表示赌徒在第 n 局赌博后的赌金，其初始分布表示赌徒开始时所拥有的赌金情况。第5章 马尔可夫过程实例二实例二 参照实例一，只是将其中的术语“赌徒”改为“投资家”、“赌博”改为“投资”、“第n 局”改为“第 n 次投资”，此时，读者将会得到全新的另一种解释。实例三实例三(
15、随机徘徊滤波器)对一系统接连不断地输入一串脉冲序列，自然脉冲相位可能超前可能滞后，也可能恰好不超前也不滞后。经过一段时间之后的叠加，相位可能出现过于超前或过于滞后的现象，因而造成较大的误差，于是必需设法加以恢复，那么首先应建立一个准则，判断何时过于超前何时过于滞后，以便随时修正。第5章 马尔可夫过程为此可利用双吸收壁的随机游动模型设计计数器。状态集 S=0，1，2，2 N，计数器的初始值置为 N;在计数器中，p表示有一相位超前的输入脉冲(此时计数器施行加法运算)的概率，q 表示有一相位滞后的输入脉冲(此时计数器施行减法运算)的概率，r 表示相位既不超前也不滞后的输入脉冲(计算器保持不动)的概率
16、。一旦计数器上的计数达到 0(相当于质点未达到 2 N 处之前先到达 0处)，这表示净相位滞后的脉冲个数达到 N，此时，计数器判断相位过于滞后，输出一需提前的控制脉冲，同时将计数器上记数重新置为 N;第5章 马尔可夫过程一旦计数器上的记数达到达 2 N(相当于未达到 0 之前先到达 2 N)，这表示净相位超前的脉冲个数达到 N，此时，计数器判断相位过于超前，输出一需推后的控制脉冲，同时将计数器上记数重新置为 N。如此周而复始地工作可达到控制的目的。第5章 马尔可夫过程与例 5.2.1 中类似，可以考虑只有一个壁的随机游动问题。例如，0 为部分反射壁，则状态集为 S=0，1，2，相应的转移概率矩
17、阵为一可列维矩阵第5章 马尔可夫过程例例 5.2.2 (市场预测)公司 A、B、C 是某地区三家主要灭虫剂厂商。根据历史资料得知，公司 A、B、C 的市场占有率分别为 50%、32%、20%。由于 C 公司实行了改善销售与服务方针的经营管理策略，使其产品销售额逐期稳定上升，而 A 公司却下降。通过市场调查发现三个公司间的顾客流动情况如表 5.1 所示。其中产品销售周期是季度。现在的问题是按照目前的趋势发展下去，A 公司的产品销售额或客户转移的影响将严重到什么程度?更全面的，三个公司的产品销售额的占有率将如何变化?第5章 马尔可夫过程第5章 马尔可夫过程将表中数据化为转移概率，对研究分析未来若干
18、周期的顾客流向更为有利。表 5.2 中列出了各公司顾客流动的转移概率。表 5.2 的数据是每家厂商在一个周期的顾客数与前一个周期的顾客数相除所得。表中每一行表示某公司从一个周期到下个周期将能保住的顾客数的百分比，以及将要丧失给竞争对手的顾客数的百分比。表中每一列表示各公司在下一周期将能保住的顾客数的百分比，以及该公司将要从竞争对手那里获得的顾客数的百分比。第5章 马尔可夫过程第5章 马尔可夫过程如用矩阵来表示表 5.2 中的数据，就得到如下的转移概率矩阵:P 中数据表示一个随机挑选的顾客，从一个周期到下一个周期仍购买某一公司产品的可能性或概率。如，随机挑选一名 A 公司的顾客，他在下一周期仍购
19、买 A 公司产品的概率为 0.7，购买 B 公司产品的概率为 0.1，购买 C 公司产品的概率为 0.2。第5章 马尔可夫过程考虑未来各周期市场占有率的计算。以 A、B、C 公司作为我们要分析的系统的状态，那么状态概率向量就分别为三家公司的产品销售额的市场占有率。初始状态概率向量为第5章 马尔可夫过程转移矩阵由(5.2.6)式给出。于是可用(5.2.5)式来计算未来各期的市场占有率。如状态转移一次后第一周期的市场占有率向量为可用 q(k+1)=q(k)P，k 0 递推地求得未来各期的市场占有率。第5章 马尔可夫过程5.3 马氏链的状态空间分解马氏链的状态空间分解为了揭示齐次马氏链的基本结构，需
20、对其状态按某些概率特性来分类，分类也是研究 n步转移概率 p(n)ij当 n 时的极限性态的基础。第5章 马尔可夫过程5.3.1 状态类型的定义状态类型的定义首先我们引入刻画状态特性的若干特征量。定义定义 5.3.1 对 i，j S，记f(n)ij表示系统在 0 时从状态 i 出发经过 n 步转移后首次到达状态 j 的概率。再记第5章 马尔可夫过程这里 fij表示在 0 时从 i 出发，系统经有限步转移后终究要到达状态 j 的概率，而 f()ij则是在0 时从 i 出发，系统在有限步转移内不可能到达状态 j 的概率。我们将 f(n)ij和 fij统称为首达概率。不难看出，f()ij+fij=1
21、。下面讨论首达概率与一步转移概率 pij之间的关系，同时，也给出首达概率的计算。第5章 马尔可夫过程引理 5.3.1(2)首达概率可以用一步转移概率来表示:(3)任意 n 步转移概率与首达概率之间有如下重要的关系式:第5章 马尔可夫过程证明证明(1)显然。显然。(2)由定义 5.3.1 及(5.1.5)式可得第5章 马尔可夫过程(3)由 n 步转移概率的定义可得第5章 马尔可夫过程对 j S，记矩阵 P j 是第 j 列为零，其余同 P。则式(5.3.4)可写为公式(5.3.5)是基本而又重要的，它在下面将多次被引用。第5章 马尔可夫过程引理引理 5.3.2 (Doeblin 公式)对任意的
22、i，j S，有第5章 马尔可夫过程证明证明 由(5.3.5)式可得于是第5章 马尔可夫过程令 N 取上极限，可得任取正整数 1 N 0 非空，则定义其最大公约数(GCD)为状态 i 的周期，记为 d i，即类似地，若正整数集n|n 1，f(n)ii 0 非空，则记其最大公约数(GCD)为 h i，即特征量 d i和 h i反映了在系统的发展变化过程中状态 i 重复出现的概率周期规律，它们具有如下性质。第5章 马尔可夫过程引理引理 5.3.3 (1)若 p(n)ii 0，则有正整数 m，使得 n=md i;且 d i 是满足以上性质的最大整数。hi 也具有类似的性质。(2)h i 和 d i 中
23、若一个有定义，则另一个也有定义，且两者相等。证明证明(1)显然。(2)对任一给定的状态 i，不难看出正整数集 N 1 =n|n 1，p(n)ii 0 和 N 2=n|n 1，f(n)ii 0 中若有一个非空，则另一个也非空。因此，我们下面假定这两个集合 N 1、N 2均非空。第5章 马尔可夫过程首先，由于 f(n)ii p(n)ii，所以 N 2 N 1，从而 d i h i。如果 h i=1，那么必有 h ii=d i=1。如果 h i 1，则，对每个 l=1，2，h i-1 必有 f(l)ii=0，再由(5.3.5)式知 p(l)ii=0。对 n=h i+l，l=1，2，h i-1，由(1
24、)知，当 n 不是 h i的倍数时 f(n)ii=0，于是由(5.3.5)式得第5章 马尔可夫过程现作归纳假设:对每个 l=1，2，h i-1，当 n=l，h i+l，(M-1)h i+l 时，已有 p(n)ii=0。再由 h i的定义，同样道理知利用归纳法可断言，如果 n 不是 h i的整数倍，必有 p(n)ii=0，故 N 1 中的数都可被 h i整除，从而 h i能整除 d i，所以 h i d i。综上，证得结论。有了上述准备工作之后，我们就可以来划分状态了。第5章 马尔可夫过程定义定义 5.3.4 对状态 i S，若 f ii=1，则称状态 i 是常返的(或返回的);否则(f ii
25、1)，称状态 i 是非常返的(或不返回的或滑过的、瞬时的)。由 f ii的定义知，f ii=1 表示系统从状态 i 出发必定要返回状态 i ，实际上，可以进一步证明，i常返意指从 ii 出发将无穷多次地返回 i;而 i 非常返意指从 i 出发，至多返回 i有穷多次。这就分别是“常返”和“滑过”的含义。第5章 马尔可夫过程定义定义 5.3.5 对常返状态 i S，若 ii 1)，称 i 是有周期的，且其周期为 d i。(2)称非周期正常返的状态为遍历状态。综上，我们从状态是否常返，如常返的话是否正常返，如正常返的话是否非周期等三个层次上将状态区分为以下的类型:第5章 马尔可夫过程5.3.2 状态
26、类型判别状态类型判别上面，我们根据状态的首次返回概率、平均返回时间和周期性将状态进行了分类。但直接从定义出发来判别状态的类型，虽然是件十分困难的事情。下面我们通过不同类型状态所具有的不同性质来区别它们。以下定理给出了判别一个状态是常返的或非常返的准则。第5章 马尔可夫过程定理定理 5.3.1 状态 i S 是常返状态，当且仅当以下三个条件之一成立:第5章 马尔可夫过程证明证明 由定义 5.3.5、(5.3.10)式及引理 5.3.2 即知该定理成立。定理定理 5.3.2 对任意给定的状态 i，如果 i 是常返的且有周期 d i，则存在极限:其中规定当 ii=时，1/ii=0。第5章 马尔可夫过
27、程证明证明 因为状态 i 固定，不妨将 p(n)ii、f(n)ii、di、ii 分别简记为 p n、f n、d、。令由于 i 是常返的及(5.3.5)式，则有第5章 马尔可夫过程从而对一切 n=1，2，第5章 马尔可夫过程由于 i 是常返的，f ii=1，故必有某正整数 t 使 f t 0，由引理 5.3.3 知 d 可整除 t，再利用(5.3.5)式得第5章 马尔可夫过程第5章 马尔可夫过程在(5.3.15)式中取 n=(n m-N 0)d，并注意到 d 不能整除 v 时，p v=0，便有第5章 马尔可夫过程由定义 5.3.3、引理 5.3.3，当 d 不能整除 v 时，f v=0，再依 r
28、 n 的定义便知于是第5章 马尔可夫过程利用傅比尼定理还有将(5.3.22)式和(5.3.21)式代入(5.3.20)式中得 =d/。若令对应地仿照前面的方法可证 =d/。综合两者断言存在并为d/。以下定理给出了常返状态的 3 种类型的判别准则。第5章 马尔可夫过程以下定理给出了常返状态的 3 种类型的判别准则。定理定理 5.3.3 设状态 i 是常返状态，则(1)i 为零常返的充要条件是存在极限(2)i 为正常返非周期(遍历)的充要条件是存在极限(3)i为正常返有周期的充要条件是极限 不存在，但此时有一收敛于某正数的收敛子列，即。第5章 马尔可夫过程第5章 马尔可夫过程定理定理 5.3.4
29、对状态 i S:(1)若有正整数 n 使得 p(n)ii 0，p(n+1)ii 0，则 i 无周期。(2)如果存在正整数 m 使得在 m 步转移概率矩阵 P m 中相应于某状态 j 的那列元素全不为零，则状态 j 无周期。(3)设状态 i 有周期 d，则必存在正整数 N 0，使得对所有 N N 0均有 p(Nd)ii 0。第5章 马尔可夫过程证明证明(1)显然。(2)由假设知对一切 i S，p(m)ii 0。于是由(5.3.4)式知有 i 1 S 使得 p ii 1 0，进而由CK 方程及假设有 p(m+1)ij p ii 1 p(m)i 1 j 0，i S。特别地，便有 p(m+1)jj0，
30、p(m)jj 0，由(1)知j 是非周期的。第5章 马尔可夫过程(3)正整数集 n:n 1，p(n)ii 0 总可写成 n m，m=1，2，记 d m =GCD n t，t=1，2，m，m 1。依此定义易知 d 1 d 2 d 1。显然 d 1 是一有限正整数，故必存在正整数 l 使得 d l=d l+1=d，因此 d=GCD n t，t=1，2，l，应用初等数论知识知必存在正整数 N 0，使得对任一 N N 0 都有第5章 马尔可夫过程其中 N m，m=1，2，l 皆为正整数。由 n m 的含义及 CK 方程便有当 i 为正常返时，由定理 5.3.2 可立得结论(3)。第5章 马尔可夫过程5
31、.3.3 状态间的关系状态间的关系上一小节讨论了状态类型的判别问题，现在我们进一步讨论状态之间的关系以及具有一定关系的两个状态的类型之间的关系。首先引入状态之间的可达和互通。第5章 马尔可夫过程定义定义 5.3.7 对给定的两个状态 i，j S，若存在正整数 n 使得 p(n)ij0，则称从 i 可到达 j(简称为 i 可达 j)，并记为 i j。如果 i j 和 j i 同时成立，则称 i 与 j 互通，记为 i j。从马氏链的转移概率图来说，所谓 i 可达 j，是指从节点 i 出发存在一条路可到达节点j;i 与 j 互通则是指从节点 i 出发存在一条路可到达节点 j，同时从节点 j 出发也
32、存在一条路可到达节点 i(对于有向图，这两条路一般是不同的)。利用(5.3.5)式容易证明可达和互通的如下性质:第5章 马尔可夫过程引理引理 5.3.4 (1)(可达的传递性)若 i j，j k，则 i k;(2)(互通的传递性)若 i j，j k，则 i k;(3)(互通的对称性)若 i j，则 j i。我们也可用首达概率来刻画可达与互通。第5章 马尔可夫过程引理 5.3.5 对 i，j S，i j 当且仅当 fij0;从而 i j 当且仅当 fijfji0。证明 设 i j，则存在 n 1 使得 p(n)ij0。由此及(5.3.5)式知，必有 l=1，2，n 使得 f(l)ij0，所以 f
33、ij0。反过来，由(5.3.5)式也容易证明。由此即知后一结论也成立。下面我们来证明，互通的两个状态必具有相同的状态类型。定理定理 5.3.5 设 i 和 j 互通，则 i 和 j 或者都是非常返的，或者都是零常返的，或者都是正常返非周期的(遍历)，或者都是正常返有周期的且具有相同的周期。第5章 马尔可夫过程证证明明 由于 i j，所以必存在 l 1 和 n 1，使得 =p(l)ij0，=p(n)ji0。由 CK方程有上式右边取 k=s=j 的那一项，得同理可证得第5章 马尔可夫过程如果 j 为常返状态，则由定理 5.3.1 知由此及(5.3.26)式知，所以 i 也是常返状态。反过来，若 i
34、 是常返状态，则由(5.3.27)式可类似证得 j 也是常返状态。所以 i 和 j 或者同为非常返，或者同为正常返。由定理 5.3.3 的(3)及式(5.3.26)和式(5.3.27)可证得 i 和 j 中有一个零常返时另一也是零常返，有一个是正常返时另一个也是正常返的。第5章 马尔可夫过程剩下所要证明的是 d i=d j。由上可知 p(n+l)jj 0，因此 d j必能整除 n+l。任取 m 0，使得 p(m)ii 0，由(5.3.27)式有由此可知 d j必能整除 l+m+n，于是也必能整除 m。所以 d j为集合 m|p(m)ii 0 的公约数，即 d j d i。同样可证得 d i d
35、 j。因此，d i=d j。对于常返状态，我们从可达可推得互通。第5章 马尔可夫过程定理定理 5.3.6 设 i j S，j 是常返态，j i，则 j i，且 fij=fji=1，从而 i 也是常返态。证证明明 令 j fji表示从状态 j 出发最终到达状态 i 而中间不经过 j 的概率，由于 j i，由引理 5.3.5 知 fji0，从而推出自 j 出发，最终到 i 而中间不经过 j 的概率 j fji 0。因此，必须在 N 1 使得从 j 出发在 N 时首达 i 而中间不经过 j 的概率 j f(N)ji0。假若 fij0，故 7 D，而可达 7 的状态都属于 D，从 P 的第 7 列可知
36、 8，9 D;划去 P 中的第 1，7，8，9 行和 1，7，8，9 列，在所得的子矩阵中，可以看出 C 2=2，3 和 C 3=4，5，6 均是正常返类;C 2 的周期为 2，其分解为2 和 3，C 3 的周期为 1，因为 p 55 0。第5章 马尔可夫过程例例 5.3.4 设一齐次马氏链的状态空间为 S=0，1，2，其转移矩阵如下(状态转移图如图 52 所示):试讨论此链是常返链的充分必要条件。第5章 马尔可夫过程图 52 状态转移图第5章 马尔可夫过程链是不可约的，因此只要确定其中某一个状态是常返的条件即可。为此我们选择其中较为特殊的状态 0。由矩阵 P 可得第5章 马尔可夫过程因此，状
37、态 0 是常返态(f 00=1，从而链是常返链)的充要条件是 p 0 p 1 p N=0。此条件相当于以下正项级数发散:反之，如果级数收敛，则该链为非常返链。例如，此时的马氏链为常返链。第5章 马尔可夫过程此时的马氏链为非常返链，而且第5章 马尔可夫过程5.4 转移概率的极限与平稳分布转移概率的极限与平稳分布本节探讨马氏链 X=X 0，X 1，的稳定性，即P X n=j 是否存在，若存在是否是一个概率分布。为此，主要考察 n 步转移概率 p(n)ij当 n 时的极限是否存在，若存在则是否与初始态 i 无关，进而，若 j=p(n)ij存在且与 i 无关，则 j，j S 是否构成一概率分布?第5章
38、 马尔可夫过程5.4.1 转移概率的极限为讨论 n 步转移概率 p(n)ij的极限情况，由(5.3.29)式可知我们只须讨论 i 是非常返态或者 i 是常返态且 j 与 i 属同一常返类(某 C m)的情形。首先，我们有定理定理 5.4.1 设 j S 是非常返状态或零常返状态，则第5章 马尔可夫过程第5章 马尔可夫过程基于此定理，下面假定 j 是正常返态且 i 非常返或者 i 与 j 属同一常返类。注意到定理5.3.3，p(n)jj当 j 有周期时极限不存在，因此一般地讨论 p(n)ij的极限将无意义。考虑到周期链的性质(定理 5.3.9)，我们转而考虑 p(nd j+r)ij当 n 时的极
39、限问题，r=1，2，d j。为此，引进如下概念:第5章 马尔可夫过程fij(r)表示从状态 i 出发，在某时刻 n r(mod d j)首先到达状态 j 的概率。不难看出第5章 马尔可夫过程定理定理 5.4.2 设 j 为正常返态，则以下极限存在，且第5章 马尔可夫过程第5章 马尔可夫过程关于(5.4.4)式中的 fij(r)，由定理 5.3.9 我们有以下推论。第5章 马尔可夫过程推论推论 5.4.1 设 X 是有周期 d 的不可约马氏链，状态空间的分解 J 1，J 2，J d 如定理5.3.9 中所示，则对 r=1，2，d，i J i，j J m，我们将上面的结果总结如下。第5章 马尔可夫
40、过程定理 5.4.3 设 S=D C 0 C+1 C+2 ，其中 D 为非常返态集，C0为零常返态集，C+1，C+2，为正常返状态闭集，则第5章 马尔可夫过程第5章 马尔可夫过程但 j C+m时的收敛子列要由定理 5.4.2 和推论 5.4.1 给出。第5章 马尔可夫过程上面我们基本上解决了 n 步转移概率的极限问题，其中如上所述对某些类型的 i 与 j，p(n)ij，n 1 中有 d j 个收敛子列。极限不存在的原因是周期的影响。因此如能消除周期的影响，极限也就存在了。为此，我们考虑 p(n)ij算术平均的极限。第5章 马尔可夫过程定理定理 5.4.5 对任意的 i，j S，如下极限存在且证
41、证明明 首先注意到数学分析中的一个结论:设数列 a n 有极限 a，则第5章 马尔可夫过程由此及定理 5.4.3 即知(5.4.7)式中的第一式。对于第二式，设 N=Md j+R，R=1，2，d j，则由定理 5.4.2 及以上结论知如记 是第(i，j)元为 ij的矩阵，则 有如下性质。第5章 马尔可夫过程第5章 马尔可夫过程(2)由法都引理，对 i，j S但故前式中恒成立等号。因此 P=。第5章 马尔可夫过程(3)由已证结果知令 N ，由控制收敛定理可得从而可得 n=。第5章 马尔可夫过程最后，由已证结果可证得(P-)2=P 2-P-P+2=P2-2，用归纳法可证得(P-)n=P n-n。关
42、于矩阵 ，注意到 P 的标准形式(5.3.28)式，结合(5.4.7)式，不难给出 的分块形式为第5章 马尔可夫过程对 n，由(5.4.7)式知它的每一行均相同，为由于它是从 P 得到的。我们要问它是否是概率分布。我们有以下进一步的结果。第5章 马尔可夫过程定理定理 5.4.7 设 C+h为马氏链的一个正常返子类，则构成一概率分布。从而(5.4.8)式中相应的 h 各行均相同且为(h)，即 h=e(h)，e 是分量全为 1 的列向量，维数同|C+h|。第5章 马尔可夫过程证明证明 简记 C+h为 C，设 C 有周期 d，则由法都引理及定理 5.4.2 可知对 i C 有从而第5章 马尔可夫过程
43、第5章 马尔可夫过程我们说其中均成立等号，因为否则，取 n=md+r，令 m ，由控制收敛定理，得第5章 马尔可夫过程以上定理说明 m 是各行相同均为 (m)的一个随机矩阵。至此，我们对 n 步转移概率的极限性态作了较为全面的研究。关于 D 1，D 2，的进一步讨论可见参考文献 14。第5章 马尔可夫过程第5章 马尔可夫过程进而，若 X 是不可约正常返的，则它与初始状态 i 无关。与例 5.2.1 一样，r(i)和 v(i)可有多种不同的解释，如 r(i)可解释为系统在 i 处运行一个周期的报酬(如服务系统所得的服务报酬)、运行一个周期的平均时间等;相应地，v(i)则分别是长期运行每周期平均期
44、望报酬和平均期望时间。第5章 马尔可夫过程5.4.2 平稳分布平稳分布首先，我们给出平稳分布的定义。定义定义 5.4.1 称概率分布 i，i S 是马氏链 X 的一个平稳分布，如果上式用向量形式可写为第5章 马尔可夫过程由(5.2.5)式知，若马氏链的初始分布是一个平稳分布 ，则 X n 的概率分布向量 q(n)为亦即当马氏链的初始分布为平稳分布时，其绝对概率分布将保持不变。注意到第 2 章中所定义的严平稳过程，(5.4.10)式相当于说 X 的一维分布是平稳的。实际上，我们有以下结论。第5章 马尔可夫过程定理定理 5.4.8 设马氏链的初始分布 是平稳分布，则 X 是严平稳随机过程。证明证明
45、 任取非负整数 t1，t 2，t n 及 m，状态 i 1，i 2，i n S，由(5.4.10)式易知由此可知 X 是一严平稳随机过程。第5章 马尔可夫过程以上定理给出了平稳分布的含义。从平稳分布的定义知，我们可从求解以下线性方程组:的过程中得到关于平稳分布的存在性、唯一性以及计算(如存在)等三方面的有关结论。但纯粹从线性代数来讨论不一定可行，也未必能得到很好的结果，特别是状态可数时。下面，我们运用前面所得的结论，特别是马氏链的状态分解定理和极限理论来讨论这三个方面的问题。第5章 马尔可夫过程注意到 P 的标准(5.3.28)式，我们自然也应该将 作相应的分块。但由(5.4.10)式及控制收
46、敛定理可知再注意到 的分块形式(5.4.8)式(注:其中分块与(5.3.28)式中不同)，我们将 按 S=D C0 C+1 C+2 (见定理 5.4.3)分块第5章 马尔可夫过程其中 (D)，(0)，(1)，(2)，分别对应于非常返态闭集 D，零常返态闭集 C 0，正常返态闭集C+1，C+2，。由此及式(5.4.8)和式(5.4.12)即知第5章 马尔可夫过程基此，我们将平稳分布的求解(即解线性方程组(5.4.11)式)化为求解一系列规模较小的线性方程组(5.4.14)式。而由定理 5.4.7 可知 m 的每一行都相同，故(m)=(m)m 等价于记则由 满足的条件(5.4.11)式知，反之也成
47、立。现在，我们就可来阐明平稳分布的存在性及其结构的定理了。第5章 马尔可夫过程定理定理 5.4.9 设 S=D C 0 C+1 C+2 ，N 为正常返类个数，=j 0，j S 满足 j j ，则 为平稳分布的充要条件是存在非负数列 m，1 m 0，ri 0，i=0，1，q i 0，i=1，2，r 0+p 0=1，q i+r i+p i=1，i=1，2，。从以上矩阵 P 可以看出，所有状态互通，X 不可约。其平稳分布满足的方程(5.4.9)式为第5章 马尔可夫过程第5章 马尔可夫过程其中由此及定理 5.4.10 知，X 有平稳分布的充要条件是级数第5章 马尔可夫过程如果还有 p 0=p，那么 X
48、 的平稳分布转化为几何分布:第5章 马尔可夫过程例例 5.4.3 设有状态空间为 S=1，2，7 的一齐次马氏链，其转移概率矩阵为第5章 马尔可夫过程由 P 的标准形式(5.3.28)式)及有关性质可知，此马氏链的非常返态集 D=7，正常返类有三个:且均是遍历的。对应于 C 1，C 2，C 3 的转移概率矩阵分别为第5章 马尔可夫过程的非负解可得第5章 马尔可夫过程由定理 5.4.9 知本马氏链的平稳分布有无穷多个，其通解表达式为(请读者予以验证)同时，常返状态的平均返回时间为最后，我们请读者比较转移概率的极限问题与平稳分布的异同点及其相互关系。第5章 马尔可夫过程5.5 连续时间马氏过程的转
49、移概率连续时间马氏过程的转移概率本节开始讨论连续时间马氏过程 X=X(t)，t 0，其状态空间 S 仍假定可数。与马氏链中完全对应的，由马氏过程的定义(5.1.6)式)可知，我们需要引入第5章 马尔可夫过程它表示在 s 时从状态 i 出发的条件下于 t 时到达状态 j 的条件概率，我们称之为转移概率函数，简称为转移概率。在此，我们总假定 P X(s)=i 0。对应于(5.2.2)式，这里也约定作为条件概率，自然有第5章 马尔可夫过程相应的 CK 方程为(请读者给予证明):如果我们记 P(s，t)是第(i，j)元为 pij(s，t)的矩阵，则(5.5.2)式和(5.5.3)式分别是说P(s，s)
50、=I 是单位矩阵，P(s，t)是随机矩阵(s t)。而 CK 方程为第5章 马尔可夫过程我们称 X(0)的分布为马氏过程 X 的初始分布。当已知马氏过程的初始分布 q 和转移概率 pij(s，t)时，X(t)的分布就可按下式求得:第5章 马尔可夫过程反过来，任给一个满足式(5.5.2)(5.5.4)式的矩阵函数 P(s，t)及初始分布 q，可唯一地确定一个以 P(s，t)为转换概率，以 q 为初始分布的马氏过程(详见参考文献 13，139 页定理 2)。与马氏链相同，我们只考虑以下称之为齐次马氏过程的情形:第5章 马尔可夫过程与平稳过程的协方差函数类似，这里的 pij(s，t)和 pij(t-
