第1章 预 备 知 识在这一章里，我们将首先介绍在本书中要用到的一些基础知识，包括随机过程和排队模型方面的相关概念和结论，然后简单地介绍一下本书所涉及领域的两种常用的研究方法，包括无穷小摄动分析方法和Markov 过程无穷小矩阵摄动方法及其相关概念和结果．1.1 随 机 过 程本节我们将复习一下随机过程的有关知识，包括概率论、Poisson 过程、Markov 链、Markov 过程、再生过程和Markov 更新过程等，着重于这些过程的状态特征描述及稳态性能方面的概念和结果．本节材料可参看文献[1~4]．1.1.1 概率论我们将以测度论的观点来简单地介绍一下概率论的一些基本概念和结论．定义1.1.1 设Ω是一个非空基本集，F 是Ω的一个子集族，且满足条件：(1) 若12,E E ∈F ，则12E E -∈F ；(2) 若n E ∈F ，1,2,n =L ，则1∞=∈U n n EF ，则称F 为Ω上的一个σ-环．若还有Ω∈F ，则称F 为Ω上的一个σ-域或σ-代数． 设G 是Ω的一个子集族，包含G 的最小σ-域称为由G 生成的σ-域．由实数空间R 上的所有开区间生成的σ-域称为Borel σ-域或Borel 集类，记为B ．定义1.1.2 设F 为Ω上的一个σ-域，μ是定义在F 上的一个非负的，允许取+∞，但不恒取+∞的集函数，若它满足可列可加性：当n E ∈F ，1,2,n =L ，i j E E =∅I(i j ≠)时，有11()()μμ∞∞===∑U n n n n E E ，则称μ是F 上的一个测度，(,,)ΩμF 称为一个测度空间，F 中的集合称为可测集，()E μ称为E 的测度．定理1.1.1 设μ是σ-域F 上的一个测度，则有(1) 规定性：()0μ∅=；(2) 有限可加性：若1,,n E E ∈L F ，i j E E =∅I (i j ≠)，则11()()n nk k k k E E μμ===∑U ；(3) 单调性：若12,E E ∈F ，12E E ⊂，则12()()E E μμ≤．定义1.1.3 设(,,)ΩμF 为一个测度空间，若()1μΩ=，并记()()P μ⋅=⋅， 称P 为σ-域F 上的一个概率测度，并称(,,)P ΩF 为一个概率空间，而F 中的任一元素称为一个事件．换句话说，定义在σ-域F 上的一个集函数称为一个概率测度，若它满足条件：(1) 对任意的A ∈F ，()0P A ≥；(2) ()1P Ω=，()0P ∅=；(3) 若n A ∈F ，1,2,n =L ，i j A A =∅I (i j ≠)，则有11()()n n n n P A P A ∞∞===∑U ．设(,,)P ΩF 为一个概率空间，则由定理1.1.1的（3）可以知道，对任意的A ∈F ，()1P A ≤．对A ∈F ，若()1P A =，则称A 为P 的支集．定义1.1.4 设(,,)P ΩF 为一个概率空间，B ∈F ，()0P B >，定义()()()P AB P A B P B = ，A ∈F ， （1.1.1） 则()()B P P B ⋅=⋅为定义在F 上的一个概率测度，称为给定事件B 的条件概率，而称(,,)B P ΩF 为给定事件B 的条件概率空间．条件概率除了具有概率的有关性质外，还具有以下一些特殊性质：(1) 设(,,)A P ΩF 为一条件概率空间，B ∈F ，()0A P B >，则有()()()A AB P C B P C AB P C ==； （1.1.2）(2) (乘法公式)设n A ∈F ，1,2,,n k =L ，且121()0k P A A A ->L ，则有12121312121()()()()()k k k P A A A P A P A A P A A A P A A A A -=L L ； （1.1.3）(3) (全概率公式)设A ∈F ，n B ∈F ，1,2,n =L ，i j B B =∅I (i j ≠)，()0n P B >，1n n B A ∞=⊃U ，则有1()()()n n n P A P B P A B ∞==∑； （1.1.4）(4) (Bayes 公式)设A ∈F ，n B ∈F ，1,2,n =L ，i j B B =∅I (i j ≠)，()0P A >，()0n P B >，1n n B A ∞=⊃U ，则有 1()()()()()n n n i ii P B P A B P B A P B P A B ∞==∑，1,2,n =L ． （1.1.5）定义 1.1.5 设(,,)P ΩF 为一个概率空间，n A ∈F ，1,2,,n k =L ，若对任意的n （1n k ≤≤）及任意的121n i i i k ≤<<<≤L ，都有1212()()()()n n i i i i i i P A A A P A P A P A =L L ， （1.1.6）则称事件12,,,n A A A L 是独立的．定义 1.1.6 设(,,)P ΩF 为一个概率空间，:X Ω→R ，若对任意的t ∈R ，均有{}{:()}X t X t ωΩω≤=∈≤∈F ，则称X 为(,,)P ΩF 上的一个随机变量．设X 为概率空间(,,)P ΩF 上的一个随机变量，称(){}F t P X t =≤ （1.1.7）为随机变量X 的分布函数．易见，()F t 不减，且()0F -∞=，()1F +∞=．若存在一个非负函数()f t ，使对任意的t ∈R ，均有()()d t F t f t t -∞=⎰， （1.1.8） 则称()f t 为随机变量X 的概率密度函数，并称X 为连续型随机变量．随机变量X 的数学期望或均值定义为 [](d )()d E X tF t tf t t +∞+∞-∞-∞==⎰⎰， （1.1.9） 它的方差定义为222[][([])][]([])D X E X E X E X E X =-=-， （1.1.10）风险率函数定义为()()1()f t h t F t =-． （1.1.11）如果()F t 在R 上绝对连续，则()()f t F't =，从而有()d ()()e th t t f t h t -∞-⎰=． （1.1.12） 如果X 表示一个事件的寿命，则()h t 表示该事件活到时刻t ，而将在时间段[,)t t t +∆内终结的比率．下面将简单介绍一下在本书中要用到的有关概率论的一些基本事实和结论．首先，我们来考虑所谓的逆变换方法，该方法可被用来从一个在[0,1)上服从均匀分布的随机变量，生成一个具有已知分布函数()F t 的随机变量，它在排队网络的仿真中有重要应用．已知随机变量X 的分布函数为()F t ，注意到()F t ξ=服从[0,1)上的均匀分布，为了生成随机变量X ，我们先产生一个随机变量ξ，它服从[0,1)上的均匀分布，然后令1()sup{:()}t F t F t ξξ-==≤， （1.1.13）这样生成的随机变量就一定具有分布函数()F t ．这是因为1{}{()}{()}()P X t P F t P F t F t ξξ-≤=≤=≤=．下面我们来考虑随机变量序列的收敛性．设(,,)P ΩF 为一个概率空间，n X ，1,2,n =L 及X 为定义在其上的随机变量，我们有下列四种收敛概念：(1) 以概率1收敛（几乎肯定收敛）：若{lim }1n n P X X →∞==，或等价地，对任意的0ε>，有lim {,}0ε→∞->≥=对某个k n P X X k n ，则称随机序列{}n X 以概率1收敛到X ，记为lim n n X X →∞=（w.p. 1），也称随机序列{}n X 几乎肯定收敛到X ，记为lim n n X X →∞=(a.s.)． (2) 以概率收敛：若对任意的0ε>，有lim {}0n n P X X ε→∞-≥=，则称随机序列{}n X 以概率收敛到X ，记为lim n n X X →∞=(P )． (3) r 阶收敛：设对0r >，[]r n E X <∞，[]r E X <∞，若lim []0rn n E X X →∞-=，则称随机序列{}n X r 阶收敛到X ，记为lim n n X X →∞=(r )．特别当1,2r =时，分别称为均值收敛和均方收敛．(4) 以分布收敛和弱收敛：设()n F t 和()F t 分别是n X 和X 的分布函数，1,2,n =L ，若lim ()()n n F t F t →∞=，则称随机序列{}n X 以分布收敛到X ，记为lim n n X X →∞=(d )，也称分布函数序列{()}n F t 弱收敛到()F t ．可以证明：lim n n X X →∞=(a.s.)⇒lim n n X X →∞=(P )⇒lim n n X X →∞=(d )；lim n n X X →∞=(r )⇒lim n n X X →∞=(P )． 定理 1.1.2（单调收敛定理） 设{}n X 为一个单调不降的非负随机变量序列，如果lim n n X X →∞=(a.s.)，则有 lim [][]n n E X E X →∞=． 定理1.1.3（Lebesgue 控制收敛定理） 设{}n X 为一随机变量序列，若存在一个具有有限均值的随机变量Y ，使对任意的n ，有n X Y ≤，且lim n n X X →∞=(P )，则 lim [][]n n E X E X →∞=． 定义 1.1.7 设{}n X 为定义在概率空间(,,)P ΩF 上存在均值的随机变量序列，若11lim {[]}0nk k n k X E X n →∞=-=∑(P )，则称{}n X 服从（弱）大数定律． 定理 1.1.4 设{}n X 为定义在概率空间(,,)P ΩF 上的随机变量序列，若对任意的自然数n ，1[]nk k D X =∑存在，且211lim []0n k n k D X n →∞==∑，则{}n X 服从大数定律． 定理1.1.5（辛钦大数定律） 设{}n X 为相互独立同分布的随机变量序列，则{}n X 服从大数定律的充分必要条件是1X 具有有限的均值．定义 1.1.8 设{}n X 为定义在概率空间(,,)P ΩF 上存在均值的随机变量序列，若11lim {[]}0nk k n k X E X n →∞=-=∑(a.s.)，则称{}n X 服从强大数定律． 定理1.1.6 设{}n X 为相互独立的随机变量序列，若21[]n n D X n ∞=<∞∑，则{}n X 服从强大数定律．定理1.1.7 设{}n X 为相互独立同分布的随机变量序列，则{}n X 服从强大数定律的充分必要条件是1X 具有有限的均值．设(,,)P ΩF 为一个概率空间，t X ，t T ∈为定义在(,,)P ΩF 上的一族随机变量，我们称{;}t X X t T =∈为定义在(,,)P ΩF 上的一个随机过程．这里，T ⊂R 称为随机过程X 的参数集．如果{0,1,2,}T +==L Z ，则称X 为离散时间的随机过程，一般用n 表示离散的时间参数；如果[,]T a b =，或R ，或[0,)+=+∞R ，则称X 为连续时间的随机过程，一般用t 表示连续的时间参数．令Φ为随机过程X 的所有可能取值组成的集合，我们称Φ为X 的状态空间，Φ中的元素称为状态．Φ可以是一个有限集，或可数无限集，或不可数无限集．我们也称X 为定义在状态空间Φ上的一个随机过程．1.1.2 Poisson 过程定义在概率空间(,,)P ΩF 上的一个随机过程{;0}t N N t =≥，如果它是非减的，纯跳跃的，右连续的，且00N =，则称其为一个到达过程．应用最广泛的一类到达过程是Poisson 过程．定义1.1.9 状态空间{0,1,2,}Φ=L 上的一个到达过程{;0}t N N t =≥称为Poisson 过程，如果它满足下列条件：(1) 对任意的,0s t ≥，t s t N N +-与{;}u N u t ≤独立；(2) 对任意的,0s t ≥，t s t N N +-的分布与t 无关．我们有下列引理，它描述了Poisson 过程的基本特征，通过它可给出Poisson 过程的多种定义．引理1.1.1 如果{;0}t N N t =≥是一个Poisson 过程，则(1) 存在一个常数0λ≥，使对所有的0t ≥，{0}e t t P N λ==；(2) 0{2}lim0t t P N t→≥=； (3) 0{1}lim t t P N t λ→==． 我们称引理1.1.1中的常数λ为Poisson 过程{;0}t N N t =≥的到达率．定理1.1.8 如果{;0}t N N t =≥是一个到达率为λ的Poisson 过程，则对任意的0t ≥，有e (){}!t kt t P N k k λλ-==，0,1,k =L ． （1.1.14） 设{;0}t N N t =≥是一个到达率为λ的Poisson 过程，Λ<<<=2100T T T 是相继的到达时刻，则我们有下列引理：引理 1.1.2 如果{;0}t N N t =≥是一个到达率为λ的Poisson 过程，则对任意的0≥n ，有10{,,}1e t n n n P T T t T T λ-+-≤=-L ，0t ≥． （1.1.15）由引理1.1.2可知，一个到达率为λ的Poisson 过程，其相继到达时间间隔n n T T -+1，Λ,1,0=n 相互独立，且具有共同的指数分布1e t λ--．由这个引理，可给出Poisson 过程的另一个等价定义：定理 1.1.9 设Λ<<<=2100T T T 是一个到达过程{;0}t N N t =≥的相继到达时刻，则N 是一个Poisson 过程的充分必要条件为到达时间间隔n n T T -+1，Λ,1,0=n 相互独立，且具有共同的指数分布1e t λ--．Poisson 过程还有许多其他等价的定义，请参看文献[2]．1.1.3 Markov 链如果一个随机过程在已知当前状态的情况下，它未来的行为与它过去的历史无关，则我们一般称该随机过程具有Markov 性．Markov 链和下一小节将要介绍的Markov 过程都是这样的随机过程．为叙述方便，以下如无特殊声明，均设状态空间{1,2,}Φ=L 为一个可数集．定义1.1.10 状态空间Φ上的一个随机过程}0;{≥=n X X n ，如果它对任意的j Φ∈及0≥n ，满足}{},,{101n n n n X j X P X X j X P ===++Λ， （1.1.16）则称X 为一个具有状态空间Φ的Markov 链．对Markov 链}0;{≥=n X X n ，条件概率}{1i X j X P n n ==+，,i j Φ∈称为Markov 链X 的转移概率，若它与n 无关，记ij n n P i X j X P ===+}{1，则称其为时间齐次的，简称齐次的．本书中出现的Markov 链均是齐次的．矩阵][ij P P =称为Markov 链X 的转移矩阵．显然，对任意的,i j Φ∈，0≥ij P ，且1ij j P Φ∈=∑．满足此条件的矩阵一般称为一个Markov 矩阵或随机矩阵．对,i j Φ∈，及0≥k ，令)(k ij P 为矩阵kP 的第),(j i 个元素，则易证 )(}{k ij n k n P i X j X P ===+ ． （1.1.17）因此，矩阵k P 称为Markov 链X 的k -步转移矩阵．这里，特别I P =0为单位矩阵．显然，对任意的0,≥m n ，有m n m n P P P =+， （1.1.18）或等价地()()()n m n m ij ik kj k P P P Φ+∈=∑， （1.1.19）上式称为Markov 链X 的Chapman-Kolmogorov 方程．设X 为一个具有状态空间Φ和转移矩阵P 的Markov 链，对j Φ∈，令T 是过程首次到达状态j 的时刻．以下用}{A P j 表示}{0j X A P =，}{A E j 类似．对,i j Φ∈，置(,){}i F i j P T =<∞，它表示Markov 链X 始于状态i 到达状态j 的概率．定义1.1.11 如果{}1j P T <∞=，则称状态j 是常返的，否则，如果{}0j P T =+∞>，则称j 是瞬态的或滑过的；一个常返态j 称为零常返的，如果∞=}{T E j ，否则，称为正常返的或非零常返的；一个常返态j 称为周期的，且具有周期δ，如果2≥δ，且是满足下式的最大整数：{,1}1j P T n n δ=≥=对某一个，否则，称为非周期的．一个正常返且非周期的状态称为遍历的．如果X 的所有状态都是正常返的，则称X 为正常返的；如果X 的所有状态都是非周期的，则称X 为非周期的．定理1.1.10 如果状态j 是瞬态的或零常返的，则对任意的i Φ∈，有0lim )(=∞→n ij n P ；如果状态j 是正常返非周期的（遍历的），则0lim )()(>=∞→n jj n P j π，且对任意的i Φ∈，有()lim (,)()n ij n P F i j j π→∞=． （1.1.20） 定义1.1.12 如果对某个0≥n ，0)(>n ij P ，则称状态i 可达状态j ，记为j i →；如果j i →，且i j →，则称状态i 与状态j 互通，记为j i ↔．显然，可达关系具有传递性，即若j i →，且k j →，则k i →．定义1.1.13 一个状态的集合称为闭的，如果它内部的状态都不能到达它外部的状态；仅有其本身构成一个闭集的状态称为一个吸收状态；一个闭集称为不可约的，如果它没有真闭子集；一个Markov 链称为不可约的，如果它的状态空间是惟一的闭集．易证，状态j 是吸收的当且仅当1=jj P ；一个Markov 链是不可约的当且仅当其所有状态相互可达；如果Markov 链X 是不可约的，且具有有限状态空间，则X 无瞬态和零常返态．而由定义1.1.12易见，一个Markov 链是不可约的当且仅当其转移矩阵P 是不可约的．一个随机矩阵P 称为可约的，如果通过对其指标重新排序后，P 可表为下列形式：1121220⎛⎫= ⎪⎝⎭P P P P ， （1.1.21）这里，11P 为一个有限阶方阵；否则，称P 为不可约的．定义1.1.14 概率分布((1),(2),)πππ=L 称为Markov 链X 的一个平稳分布或不变分布，如果P ππ=． （1.1.22）定理1.1.11 设Markov 链X 是不可约的，则X 为正常返的充分必要条件是X 存在惟一的平稳分布((1),(2),)πππ=L ，且()0i π>，i Φ∈．下面这个定理反映了Markov 链的平稳分布与其极限概率之间的关系．定理1.1.12 设Markov 链X 是不可约的和非周期的，则X 为正常返的充分必要条件是X 存在惟一的平稳分布((1),(2),)πππ=L ，且()()lim 0n ij n j P π→∞=>，,i j Φ∈．此时，我们也称((1),(2),)πππ=L 为X 的极限分布或稳态分布．由于具有有限状态空间的不可约Markov 链X 无瞬态和零常返态，故我们有下列推论：推论1.1.1 设Markov 链X 是不可约的和非周期的，且具有有限状态空间，则X 存在惟一的平稳分布((1),(2),)πππ=L ，且()()lim 0n ij n j P π→∞=>，,i j Φ∈．下面我们来简单介绍一下强遍历Markov 链的有关概念和结果．设Markov 链X 是不可约的，转移矩阵为][ij P P =，记0inf{0,}ij n T n X j X i =≥==为过程从状态i 出发首次到达状态j 的时间，[]ij ij M E T =为过程从状态i 出发首次到达状态j 的平均时间，[]ij M M =称为平均首达时矩阵．定义1.1.15 设不可约Markov 链{;0}n X X n =≥的转移矩阵为][ij P P =，0π>是X 的一个平稳分布，如果M π有限，则称Markov 链X 是强遍历的．定理1.1.13 如果Markov 链X 是不可约、非周期、正常返的和强遍历的，π是X 的稳态分布，则矩阵()I P e π-+非奇异，且10()()n n I P e P e ππ∞-=-+=-∑． 这里，e 为一个所有分量均为1的列向量．1.1.4 Markov 过程定义1.1.16 状态空间Φ上的一个随机过程{;0}t Y Y t =≥，如果它对任意的j Φ∈，及,0t s ≥，满足{;}{}t s u t s t P Y j Y u t P Y j Y ++=≤==， （1.1.23）则称Y 为一个具有状态空间Φ的Markov 过程．对Markov 过程{;0}t Y Y t =≥，（1.1.23）式中的条件概率一般依赖于t 和s ，如果对所有的,i j Φ∈及0s ≥，{}()t s t ij P Y j Y i P s +===与0t ≥无关，则称Markov 过程Y 是时间齐次的，简称齐次的．对固定的,i j Φ∈，称0(){}ij t P t P Y j Y i ===为转移函数；称矩阵()[()]ij P t P t =为Markov 过程Y 的转移概率矩阵．如果()P t I →(0t →+)，这里I 为单位矩阵，则称Markov 过程Y 具有标准转移概率矩阵．本书中出现的Markov 过程均是齐次的，以后不再声明．易见，对任意的,i j Φ∈及,0t s ≥，有()0ij P t ≥，()1ik k P t Φ∈=∑， （1.1.24） ()()()ik kj ijk P t P s P t s Φ∈=+∑． （1.1.25） （1.1.25）式称为Markov 过程Y 的Chapman-Kolmogorov 方程．设{;0}t Y Y t =≥为一个随机过程，T 是一个取值于+R 的随机变量，若对每一个有限的0t ≥，事件{}T t ≤的发生与否可以由过程Y 直到时刻t 的历史{;}u Y u t ≤来确定，则称T 为Y 的一个停时．定理 1.1.14 设Y 为一个Markov 过程，T 为Y 的一个停时，则对任意的j Φ∈及0s ≥，有{;}()T s u ij P Y j Y u T P s +=≤=，这里T Y i =．这个定理中的性质称为Markov 过程Y 在停时T 的强Markov 性．下面我们来讨论Markov 过程的结构．以下设状态空间Φ上的Markov 过程Y 具有标准转移概率矩阵，00T =，1T ，2T ，L 是过程Y 相继的状态转移时刻，0X ，1X ，2X ，L 是Y 相继到达的状态．若n X i =，则1n n T T +-为Y 在状态i 的逗留时间．我们设对几乎所有的ωΩ∈，()t Y ω在+R 上是右连续的，即0n n T X Y +=．定理1.1.15 对任意的0n ≥，,i j Φ∈及0t ≥，如果事件{}n X i =发生，则有()1100{,,,;,,}(1e)i t n n n n n ij P X j T T t X X T T P λ-++=-≤=-L L ， （1.1.26） 这里，0()i λ≤<∞．且有0ij P ≥，0ii P =，1ij j P Φ∈=∑． （1.1.27）该定理说明，序列0X ，1X ，2X ，L 构成一个具有转移矩阵[]ij P P =的Markov 链，称为Markov 过程Y 的嵌入Markov 链，记为{;0}n X X n =≥．定理中的()i λ称为Markov 过程Y 在状态i 的转移率．如果()0i λ=，则称i 为Y 的一个吸收状态．如果n X i =，则过程Y 在状态i 的逗留时间1n n T T +-具有参数为()i λ的指数分布．定义1.1.17 如果对几乎所有的ωΩ∈， ()sup ()n n T ζωω==+∞，则称Markov 过程Y 为正则的．下面两个定理是确定Markov 过程Y 是否正则的判别准则．定理1.1.16 如果Markov 过程Y 的转移率有界，即存在一个常数λ<∞，使对所有的i Φ∈，有()i λλ≤，则Y 正则．特别地，如果Φ有限，则Y 正则．定理1.1.17 如果Markov 过程Y 的嵌入Markov 链X 是常返的，则Y 正则．以下设Markov 过程Y 正则，具有标准转移概率矩阵()[()]ij P t P t =，{;0}n X X n =≥为其嵌入Markov 链，[]ij P P =为X 的转移矩阵，()i λ为Y 在状态i 的转移率，并记diag((1),(2),)Λλλ=L ．我们来讨论()P t 与P 及Λ之间的关系．定理1.1.18 ()P t 在+R 上连续可导，且d()()d P t P t A t =， （1.1.28） d()()d P t AP t t=， （1.1.29） 其中，矩阵[]ij A a =为()P t 在0t =点的导数，且()A P I Λ=-． （1.1.30）方程（1.1.28）和（1.1.29）分别称为Kolmogorov 前瞻方程和后顾方程，定理中的矩阵A 称为Markov 过程Y 的无穷小矩阵或无穷小生成子．由定理1.1.18可得0()e !n Atnn t P t A n ∞===∑． （1.1.31）由定理1.1.15，对所有的i Φ∈，0ii P =，即Markov 过程Y 的每一个状态都不一步转移到自己．但我们可以构造一个等价的嵌入Markov 链，使得Markov 过程Y 的每一个状态都可以转移到自己．任选01i p <<，i Φ∈，置ii i P p =，(1)ij ij i P P p =-，i j ≠．则以[]ij P P =为转移矩阵的Markov 链相对于Markov 过程Y 是一个等价的嵌入Markov 链．此时，Markov 过程Y 具有状态转移率()()(1)i i i p λλ=-，i Φ∈．这是因为diag((1),(2),)()()P I P I A λλΛ-=-=L ．设对所有的i Φ∈，()i λλ≤<∞．如果我们置1()i p i λλ=-，则对所有的i Φ∈，()i λλ=，这称为Markov 过程的一致化，而此时的等价Markov 链称为一致化Markov 过程的嵌入Markov 链．下面我们来讨论Markov 过程的极限行为．定义1.1.18 状态i 称为瞬态（常返的，零常返的，正常返的），如果i 在嵌入Makrov 链中是瞬态（常返的，零常返的，正常返的）．Markov 过程Y 称为不可约的（常返的，正常返的），如果其嵌入Makrov 链是不可约的（常返的，正常返的）．可以证明，上述定义与采用离散骨架的定义是一致的．由于我们总可以构造一个非周期的等价嵌入Markov 链，故Markov 过程总是非周期的．因此，对Markov 过程来说，正常返态就是遍历的．如果状态j 是瞬态的或零常返的，则对任意的i Φ∈，当t →+∞时，有()0ij P t →．此外易见，一个Markov 过程是不可约的当且仅当其无穷小矩阵A 是不可约的．一个无穷小矩阵称为不可约的定义与一个随机矩阵称为不可约的定义完全类似．定理1.1.19 如果Markov 过程Y 是不可约正常返的，则对任意的j Φ∈，极限()lim ()ij t p j P t →+∞= （1.1.32）存在，与i 无关，且()0p j >，j Φ∈．若嵌入链X 的稳态分布为((1),(2),)πππ=L ，Y 的状态转移率为()0j λ>，j Φ∈，则()()()()()i j m j p j i m i Φππ∈=∑， （1.1.33）这里，()1()m j j λ=为Y 在状态j 的平均逗留时间．定理中的概率分布()p j ，j Φ∈称为Markov 过程Y 的极限分布或稳态分布，记为((1),(2),)p p p =L ．由定理1.1.18和定理1.1.19可得1pe =， 0Ae =，0pA =， （1.1.34）这里，(1,1,)e τ=L ．注意到0pA =，p 也称为Markov 过程Y 的平稳分布或不变分布．这是因为，如果0Y 具有分布p ，则对任意的j Φ∈及0t ≥，{}()t P Y j p j ==．可以证明，在定理1.1.19的条件下，Markov 过程Y 具有惟一的平稳分布．置:f Φ→R ，称f 为一个性能函数，并记((1),(2),)f f f τ=L ，即f 既表示一个函数，也表示一个向量．定理1.1.20 如果Markov 过程Y 是不可约正常返的，((1),(2),)p p p =L 为其稳态分布，则01lim[()d ]()()T t T i E f Y t p i f i pf T Φ→∞∈==∑⎰． （1.1.35）设Markov 过程{;0}t Y Y t =≥是不可约的，记0inf{0,}ij t T t Y j Y i =≥==为过程从状态i 出发首次到达状态j 的时间，[]ij ij M E T =为过程从状态i 出发首次到达状态j 的平均时间，[]ij M M =称为平均首达时矩阵．定义1.1.19 设Markov 过程{;0}t Y Y t =≥是不可约的，0p >是Y 的稳态分布，如果pM 有限，则称Markov 过程Y 是强遍历的．定理1.1.21 设Markov 过程Y 是不可约正常返的和强遍历的，p 是Y 的稳态分布，如果Y 的状态转移率()i λ有界，即存在λ<∞，使()i λλ≤，i Φ∈，则对任意的0α≥，矩阵()I A ep αλ-+非奇异，且111()()()n n n I A ep A I ep αλλλλα∞-+=-+=+-+∑．下面简单介绍一下两类特殊的Markov 过程，即准生灭过程与生灭过程的有关结果．定义1.1.20 状态空间{(,);0,1}E i j i j m =≥≤≤上的一个Markov 过程Y ，如果它的无穷小矩阵可表示为001102102100B A B A A A A A A A A ⎛⎫ ⎪⎪⎪= ⎪⎪ ⎪⎝⎭L L M M O ， （1.1.36）这里，0B ，1B ，0A ，1A ，2A 均为m m ⨯阶矩阵，则称Y 为一个准生灭过程，简称QBD过程．定理1.1.22 如果QBD 过程Y 不可约，则Y 正常返的充分必要条件是2阶矩阵方程22100R A RA A ++= （1.1.37）的最小非负解R 的所有特征值都在单位圆的内部，且方程001()0x B RB +=，10()1x I R --= （1.1.38）具有惟一的一个正解0x ．如果QBD 过程Y 是不可约正常返的，则其平稳分布01(,,)x x x =L 由下式给出：0i i x x R =，0i ≥． （1.1.39）定义1.1.21 状态空间{0,1,}E =L 上的一个Markov 过程Y ，如果它的无穷小矩阵为11112222333()()()A λλμλμλμλμλμλμ-⎛⎫ ⎪-+ ⎪⎪=-+ ⎪-+ ⎪ ⎪⎝⎭L L M M O ， （1.1.40）则称Y 为一个生灭过程．特别地，如果0i μ=，1i ≥，则称Y 为一个纯生过程；如果0i λ=，0i ≥，则称Y 为一个纯灭过程．显然，当0i λ>，0i μ>时，生灭过程Y 是一个不可约的Markov 过程．若令01112i i ip λλλμμμ-=L L ，1i ≥，则生灭过程Y 存在平稳分布的充分必要条件是1δ∞==<∞∑i i p ．而其平稳分布为1(0)(1)p δ-=+，1()(1)i p i p δ-=+，1i ≥．特别地，当i λλ≡，i μμ≡时，若记ρλμ=，则生灭过程Y 存在平稳分布的充分必要条件是1ρ<，且平稳分布为()(1)i p i ρρ=-，0i ≥．此平稳分布也是Y 的稳态分布．1.1.5 再生过程考虑一个随机现象， 010T T =<<L 是该现象相继发生的时刻，则1n n n S T T +=-，0,1,n =L 为该现象相邻两次发生的时间间隔．定义1.1.22 如果01,,S S L 是独立同分布的非负随机变量，则称随机序列{;0}n T n ≥为一个更新过程，n T 称为更新时刻．若()F t 为n S 的分布函数，记t N 为一个更新过程在时间间隔[0,]t 内的更新次数，()[]t R t E N =为在[0,]t 内的期望更新次数，一般称()R t 为相应于分布函数()F t 的更新函数，则1()()n n R t F t ∞==∑． （1.1.41）这里，()nF t 表示()F t 的n 重卷积，即1()()F t F t =，10()()d ()tn n F t F t x F x -=-⎰，2n ≥．如果(0)1F <，则()R t <∞，0t ≥，且分布函数()F t 与更新函数()R t 相互惟一确定．定义1.1.23 如果n S <∞对每一个n 具有概率1成立，则称更新过程{;0}n T n ≥是常返的；否则，称其为瞬时的．如果随机变量01,,S S L 仅取离散值0,,2,δδL ，且δ是最大的这样的数，则称更新过程{;0}n T n ≥为周期的，且具有周期δ；否则，如果没有这样的0δ>，则称其为非周期的．易见，更新过程{;0}n T n ≥常返或瞬时，由()1F +∞=或1<决定．以下总设(0)1F <，()1F +∞=．令[](d )[1()]d >0μ∞∞===-⎰⎰n E S tF t F t t ，我们有下列基本更新定理：定理1.1.23 对更新过程{;0}n T n ≥，有()1limt R t t μ→+∞=． （1.1.42）定义 1.1.24 设00T =，1T ，L 为状态空间Φ上的随机过程{;0}t Y Y t =≥的一个停时序列，如果{;0}n T n ≥为一个更新过程，且对任意的正整数n ，m ，1,,n t t +∈L R 及定义在n Φ上的任意有界函数f ，有11[(,,),][(,,)]++≤=L L m m n n T t T t s m t t E f Y Y Y s T E f Y Y ， （1.1.43）则称Y 为一个再生过程．（1.1. 43）式称为再生性，0T ，1T ，L 称为再生时刻．由定义可知，一个再生过程始于任何再生时刻的行为与始于00T =的行为在统计上是完全相同的．下面我们简单介绍一下更新理论的有关结果．设()f t 和()g t 均为定义在+R 上的函数，()F t 为非负分布函数，且有()()()(d )tf tg t f t x F t =+-⎰， （1.1.44）如果()g t 和()F t 已知，()f t 未知，则()f t 可看作是上述积分方程的解，我们称这个积分方程为更新方程．研究更新方程解的理论就称为更新理论，它是研究再生过程的重要工具．定理1.1.24 更新方程（1.1.44）有惟一解()()()(d )tf tg t g t x R t =+-⎰， （1.1.45）其中，()R t 为相应于分布函数()F t 的更新函数．定义1.1.25 如果非负随机变量X 仅取离散值0,,2,δδL ，且δ是最大的这样的数，则称X 为格的，且具有周期δ；否则，如果没有这样的0δ>，则称X 为非格的．当X 为格（非格）随机变量时，其分布函数也称为格（非格）的．定理1.1.25 如果分布函数()F t 非格，则对任意的0τ>，有lim[()()]t R t R t ττμ→+∞+-=； （1.1.46）如果()F t 是格的，且具有周期δ，则（1.1.46）式仅对n τδ=，1,2,n =L 成立．上述定理称为Blackwell 定理．为了给出关键更新定理，我们先来介绍直接Riemman 可积的概念．定义 1.1.26 设()f t 为定义在+R 上的函数，且在任意有限区间上有界，0τ>，记()n M τ和()n m τ分别为()f t 在区间[(1),)n n ττ-上的上确界与下确界．如对任意的0τ>，级数1()nn Mτ∞=∑与1()n n m τ∞=∑均收敛，且1lim [()()]0n n n M m ττττ∞→+=-=∑， （1.1.47）则称()f t 在+R 上是直接Riemman 可积的．易证，如果()f t 非增，且()f t 在+R 上绝对可积，则()f t 直接Riemman 可积．当()f t直接Riemman 可积时，有11lim ()lim ()()d ττττττ∞∞∞→+→+====∑∑⎰n n n n M m f t t ，其中最后一个积分就是()f t 在+R 上的Riemman 积分．故直接Riemman 可积的函数一定是Riemman 可积的．定理1.1.26 如果分布函数()F t 非格，()f t 直接Riemman 可积，则1lim ()(d )()d tt f t x R x f t t μ∞→+∞-=⎰⎰； （1.1.48）如果()F t 是格的且具有周期δ，()f t 直接Riemman 可积，且对t +∈R ，级数0()n f t n δ∞=+∑收敛，则对任意的0τ≥，有lim ()(d )()n n n f n x R x f n τδδτδτδμ∞+→∞=+-=+∑⎰． （1.1.49）这个定理称为关键更新定理．下面这个定理是再生过程的主要极限定理，我们仅给出非周期的情况．定理1.1.27 设{;0}t Y Y t =≥为一个具有再生时刻{;0}n T T n =≥的再生过程，且对任意的i Φ∈，1(,){,}t f t i P T t Y i =>=在+R 上Riemman 可积，如果T 是非周期的，则1lim {}(,)d t t P Y i f t i t μ∞→+∞==⎰． （1.1.50）定义1.1.27 设{;0}n T T n =≥为一个随机变量序列，如果0{;0}n T T T n =-≥为一个更新过程，且00T ≥与T 独立，则称{;0}n T T n =≥为一个延时更新过程．1.1.6 Markov 更新过程在这一小节里，我们将介绍一下Markov 更新过程、半Markov 过程以及半再生过程的有关概念和结论．1.1.6.1 Markov 更新过程以下除非特别声明，状态空间{1,2,}Φ=L 为一个可数集．定义 1.1.28 设{;0}n X X n =≥与{;0}n T T n =≥分别为取值于Φ及+R 上的随机变量序列， 且0120T T T =<<<L ，若对任意的0≥n ，任意的Φ∈-j i i i n ,,,,10Λ和任意的实数0≥t ，均有110{,,0,1,,1,;,,}n n n k k n n P X j T T t X i k n X i T T ++=-≤==-=L L11{,}n n n n P X j T T t X i ++==-≤=)(t Q ij =， （1.1.51）则称随机过程(,){,;0}n n X T X T n =≥为Markov 更新过程；转移概率族{(),,}ij Q t i j ∈Φ称为空间Φ上的半Markov 核．若记()[()]ij Q t Q t =， lim ()t P Q t →+∞=，则0P ≥，Pe e =， （1.1.52） 即P 为一个随机矩阵．因此，{;0}n X X n =≥为一个具有状态空间Φ和转移矩阵P 的Markov 链，称为Markov 更新过程(,)X T 的嵌入Markov 链．以下设(,){,;0}n n X T X T n =≥为一个Markov 更新过程，其半Markov 核为()Q t ．对0n ≥，我们定义()0(){,}n ij n n Q t P X j T t X i ==≤=，,i j Φ∈，t +∈R ， （1.1.53）并记()()()[()]n n ij Q t Q t =，则(0)()Q t I =为单位矩阵．对一个固定的状态j Φ∈，事件{}n X j =发生的时刻n T 构成一个可能延时的更新过程{;0}j j n T T n =≥，该更新过程在时间段[0,]t 内的更新次数为[0,]01()()∞=∑j nt n n XI T ，这里，1()j ⋅与[0,]()t I ⋅均为市性函数．可以证明，对任意的,i j Φ∈，t +∈R ，函数[0,]00()[1()()]ij j n t n n R t E X I T X i ∞===∑00{,}n n n P X j T t X i ∞===≤=∑()()n ij n Q t ∞==∑ （1.1.54） 有限．我们称()ij R t 为Markov 更新函数，()[()]ij R t R t =为Markov 更新核．对0α≥，我们定义e (d )t Q Q t αα∞-=⎰， ()()0e (d )n t n Q Q t αα∞-=⎰， （1.1.55）且对0α>，定义e (d )t R R t αα∞-=⎰． （1.1.56）可以证明，对任意的0n ≥及0α≥，()n nQ Q αα=．故当0α>时nn R Q αα∞==∑． （1.1.57）因此有()R I Q I αα-=， ()I Q R I αα-=． （1.1.58）定理1.1.28 当0α>时，如果Φ有限，则1()R I Q αα-=-； （1.1.59）如果Φ无限，则R α是方程()I Q R I α-=，0R ≥ （1.1.60）的最小解．定义1.1.29 状态j Φ∈称为瞬时的，或常返的，或非周期的，或具有周期δ的周期的，如果相应的更新过程0{;0}j j jn T T T n =-≥是瞬时的，或常返的，或非周期的，或具有周期δ的周期的．可以证明，状态j Φ∈常返（瞬时）当且仅当j 是嵌入Markov 链X 的常返态（瞬态）．但这样定义的周期性却可能和在嵌入Markov 链X 中的周期性不同．不过，我们有下列结论：定理1.1.29 如果嵌入Markov 链X 是不可约的，则Markov 更新过程(,)X T 所有状态的周期性相同．为了讨论Markov 更新方程，我们先来引进一个函数类．设:f Φ+⨯→R R ，B 是满足下列条件的所有函数f 的集合：(1) 对每一个i Φ∈，函数(,)f i t 在+R 的任何有限区间上有界；(2) 对每一个t +∈R ，函数(,)f i t 在Φ上有界．显然，对每一个固定的j Φ∈，函数()ij Q t 和()ij R t 均属于B ．设f ∈B ，如果对所有的i Φ∈，t +∈R ，及某一个g ∈B ，均有(,)(,)(,)(d )tij j f i t g i t f j t s Q s Φ∈=+-∑⎰， （1.1.61）则称f 满足Markov 更新方程．下面我们将限定函数,{:0}f g f f +∈=∈≥B B ．定理1.1.30 Markov 更新方程（1.1.61）有解0(,)(,)(d )t ij j f i t g j t s R s Φ∈=-∑⎰，且每一个解可表为(,)(,)(,)(d )tij j f i t h i t g j t s R s Φ∈=+-∑⎰， （1.1.62）其中，h +∈B ，且满足(,)(,)(d )tij j h i t h j t s Q s Φ∈=-∑⎰．而其具有惟一解的充分必要条件是sup n T =+∞（w.p. 1）．我们称sup n T 为Markov 更新过程的寿命．下列定理是判别sup n T =+∞（w.p. 1）的几个准则：定理1.1.31 如果下列条件之一成立，则sup n T =+∞（w.p. 1）： (1) 所有状态都是常返的；(2) 仅有有限个瞬态，特别Φ有限；(3) 如果存在一个0τ>，及一个1c <，使对所有的i Φ∈，均有()ijj Q c Φτ∈≤∑．1.1.6.2 半Markov 过程定义 1.1.30 若状态空间Φ上的随机过程}0;{≥=t Y Y t 满足下列条件, 则称Y 为一个半Markov 过程：(1) 对任意的Φ∈j i ,，若已知过程处于状态i ，则它下一次转移到j 的概率是ij p ；(2) 若已知过程处于状态i 和下一次将转移到状态j ，则它在状态i 的逗留时间的分布为ij F ，即11(){,}ij n n n n F t P T T t X i X j ++=-≤==．设}0;{≥=t Y Y t 为状态空间Φ上的一个半Markov 过程，0120T T T =<<L 是Y 相继的状态转移时刻，0X ，1X ，2X ，L 是Y 相继到达的状态，则(,){,;0}n n X T X T n =≥是一个Markov 更新过程，且半Markov 核为)()(t F p t Q ij ij ij =，Φ∈j i ,．而{;0}n X X n =≥也称为半Markov 过程Y 的嵌入Markov 链，它的转移矩阵为[]ij P p =．设(,){,;0}n n X T X T n =≥为一个Markov 更新过程，其半Makrov 核为()[()]ij Q t Q t =，若设sup n T =+∞（w.p. 1），则由n t X Y =，1n n T t T +≤< （1.1.63）定义的随机过程}0;{≥=t Y Y t 为一个半Markov 过程，()[()]ij Q t Q t =也称为半Makrov 过程Y 的半Makrov 核．因此，我们可以认为，Makrov 更新过程和半Markov 过程不过是同一个过程的两种不同描述方式．现在设}0;{≥=t Y Y t 为一个半Makrov 过程，其半Makrov 核为()[()]ij Q t Q t =，(,){,;0}n n X T X T n =≥是相应的Markov 更新过程，P 是嵌入Markov 链的转移矩阵，()[()]ij R t R t =是相应于()Q t 的Markov 更新核．对任意的Φ∈j i ,及t +∈R ，令0(){}ij t P t P Y j Y i ===， （1.1.64） 则对任意的Φ∈j i ,及t +∈R ，我们有()(,)(d )tij ij P t h j t s R s =-⎰， （1.1.65）其中(,)1()jk k h j t Q t Φ∈=-∑，j Φ∈，t +∈R ． （1.1.66）设:f Φ→R ，对0α≥，我们定义00()[e ()d ]t t i E f Y t Y i ααη∞-==⎰， （1.1.67）并称其为f 在状态i 的α-势．特别地，如果0α=，我们省略下标，称为f 在状态i 的势．对0α>，令e ()d t U P t t αα∞-=⎰， （1.1.68）这里，()[()]ij P t P t =．则可得U R H ααα=， （1.1.69）其中，diag((1),(2),)H h h ααα=L ，而()e (,)d t h j h j t t αα∞-=⎰，j Φ∈． （1.1.70）若记((1),(2),)h h h ααατ=L ，则易知()h I Q e ααα=-． （1.1.71）记0()(,)d m j h j t t ∞=⎰为过程在状态j 的平均逗留时间，我们有下列极限定理：定理 1.1.32 如果(,)X T 是不可约、非周期和常返的，π是X 的一个不变测度，()m j <∞，则对任意的i Φ∈，有0()()lim {}t t j m j P Y j Y i mππ→∞===． （1.1.72）我们称0()lim {}t t p j P Y j Y i →∞===，j Φ∈为半Markov 过程Y 的稳态分布或极限分布，并记((1),(2),)p p p =L ．特别地，如果X 还是正常返的，则()0j π>，j Φ∈，故当m π<∞时，()0p j >，j Φ∈．。
