马尔可夫链次几何遍历性的等价条件及其在M/G/1排队中的应用

Equivalences of Subgeometric Ergodicity of Markov Chains and Its Application to M/G/1 Queue

摘要: 马尔可夫链的遍历性研究在随机过程理论中占有重要地位，本文聚焦于马尔可夫链的次几何遍历性，提出了次几何遍历的六个等价判定条件，这些等价条件对进一步探索一般马尔可夫过程的次几何遍历性提供了理论基础，并将其应用于排队论中经典的M/G/1嵌入过程，得到了易验证的M/G/1嵌入排队过程次几何遍历的判定条件。

Abstract: The study of the ergodicity of Markov chains holds a significant position in the theory of stochastic processes. This paper focuses on the subgeometric ergodicity of Markov chains and proposes six equivalent criteria for subgeometric ergodicity of Markov chains. These equivalent conditions provide a theoretical foundation for further exploration of the subgeometric ergodicity of general Markov processes. In addition, this paper applies these criteria to the classical M/G/1 embedded process in queueing theory, obtaining easily verifiable conditions for determining the subgeometric ergodicity of the M/G/1 embedded queueing process.

1. 引言

马尔可夫过程在巡航控制系统、银行排队系统、货币汇率和动物种群动态等现实问题中广泛应用。在马尔可夫过程的研究中，关于稳定性的研究一直是学者们关注的问题，其中遍历性刻画了系统在长时间行为下收敛到平稳分布的速度，因此针对马氏过程遍历性的研究成为核心问题之一。根据收敛速度不同，我们将马尔可夫过程的遍历性分为了普通遍历、次几何遍历、几何遍历和强遍历等类型，即

$P^n\left(x,\cdot \right)-\text{Π}<C\left(x\right)\cdot r\left(n\right)$

其中，$r\left(n\right)$ 的形式反应了马氏过程的收敛速度，例如当$r\left(n\right)=n^{\ell },\ell <0$ 时，该过程具有次几何遍历性，当$r\left(n\right)={\rho }^n,0<\rho <1$ 时，该过程具有几何遍历性。显然，次几何遍历的马尔可夫过程收敛到平稳分布的速度要慢于几何遍历的马尔可夫过程。在某些具有复杂结构的系统中，过程的转移概率无法以几何速度(或指数速度)收敛到平稳分布，但可能以次几何遍历速度(如多项式速度)收敛，因此对此类系统进行研究可加深对马氏链遍历性的深入理解，并扩大其应用范围。

关于马尔可夫链次几何遍历速度的研究目前已有一些工作，例如Douc等[1]在漂移条件下给出了Harris回归马氏链在给定空间上全变差范数下的收敛界，并由此得到该链具有次几何遍历性的结论，并探讨了这些速度在不同实际应用中的意义，特别是在机器学习和贝叶斯统计模型中的应用。Liu等[2]研究了连续时间马尔可夫过程的次几何遍历性，得到了连续时间马尔可过程次几何遍历的判定准则。Deng [3]利用漂移条件建立离散时间一般状态空间马氏链范数意义下的多项式收敛速度。Durmusa等[4]研究了一般状态空间马氏链Wasserstein距离的次几何收敛速度的充分条件。Roberts等[5]考虑了逐段决定的马氏过程在全变差范数意义下，在一维和高维状态空间上的转移概率收敛到平稳分布的多项式收敛速度的界。然而可以看出，以上这些研究要么只能给出漂移条件下的次几何遍历判定条件，要么只研究次几何遍历速度，并没有文献给出次几何遍历的等价判别条件，本文对等价判定条件的研究能够进一步完善马尔可夫过程次几何遍历判定条件的研究，并帮助学者们在面对不同的模型时选择更加合适的次几何判定条件。

本文内容主要分为两小节，第一节我们将给出六条马氏链次几何遍历性的等价判别，并证明这些条件的等价性，第二节我们将利用M/G/1嵌入过程验证六条等价，并得出易于验证的M/G/1嵌入过程次几何遍历的判定条件。

2. 马尔可夫链次几何遍历性的等价判定条件

在探讨马尔可夫链次几何遍历性的判定条件之前，我们首先需要给出一些通用假设。

假设A. 令$\text{Φ}={\left\{{\text{Φ}}_n\right\}}_{n=0}^{\infty }$ 是一个取值一般状态空间$\text{X}$ 的离散时间马氏过程，$\text{Φ}$ 对应的转移概率为$P$ 且满足对所有的$x\in \text{X},A\in \text{F},n\in \text{N}$ 有$P\left(x,A\right)=P[{\text{Φ}}_n\in A|{\text{Φ}}_{n-1}=x]$ ，$\text{F}$ 表示可数生成的$\sigma$ 代数，即存在$A_1,A_2,\cdots \in \text{F}$ ，使得$\text{F}=\sigma \left(A_1,A_2,\cdots \right)$ ，$\text{F}$ 是包含所有$A_i$ 的最小$\sigma$ 代数。

A.1. $\text{Φ}$ 是$\varphi$ -不可约的，即在$\left(\text{X},\text{F}\right)$ 上存在一个非零的$\sigma$ 有限测度$\varphi$ ，使得对所有$x\in \text{X}$ 以及满足$\varphi \left(A\right)>0$ 的集合$A\subseteq \text{X}$ ，存在$n\in \text{N}$ 满足$P^n\left(x,A\right)>0$ 。

A.2. $\text{Φ}$ 是非周期的，即不存在$d\ge 2$ 且不相交的${\text{X}}_1,\cdots ,{\text{X}}_d\subseteq \text{X}$ 的正$\pi$ 测度，使得对所有$x\in {\text{X}}_i\left(i=1,\cdots ,d-1\right),P\left(x,{\text{X}}_{i+1}\right)=1$ 且对于所有$x\in {\text{X}}_d,P\left(x,{\text{X}}_1\right)=1$ 。

假设A保证了马尔可夫过程$\text{Φ}$ 具有唯一的平稳分布$\pi$ 且。现在我们将给出转移概率$P^n\left(x,A\right)$ 会以次几何的速度趋于$\pi \left(A\right)$ 的判定准则。在具体给出准则之前，我们需要介绍细集以及范数距离的定义，这些定义有助于我们后续的证明推导。在漂移条件中，示性函数下标的集合在实例中也需要具体表示出来，因此我们引入细集，为找到具体的漂移条件右边示性函数下标的集合做准备。

定义2.1. 一个子集$S\in \text{F}$ 被称为细集，如果$\pi \left(S\right)\ge 0$ 并且存在$n>0$ ，$a=\left\{a_n,n\in {\text{N}}_{+}\right\}$ 和$\left(\text{X},\text{F}\right)$ 上的一个非零测度${\nu }_a$ ，使得对于所有。

接下来我们将给出三种不同的范数定义，这些定义在文献[6]中已有详细讨论。

定义2.2. 两个概率测度${\mu }_1$ 和${\mu }_1$ 之间的全变差距离定义为：

给定一个正函数$V:\text{X}\to \text{R}$ ，我们定义$V$ -范数(不是测度范数)

对于一个测度$\mu$ ，我们定义${\Vert \mu \Vert }_{L^p}\left(\pi \right)$ ，其中$1\le p<\infty$ ，

$\parallel \mu {\parallel }_{L^p\left(\pi \right)}^p=\{\begin{array}{ll}{\mu }^{+}\left(\text{X}\right)+{\mu }^{-}\left(\text{X}\right),\hfill & p=1\hfill \\ {\displaystyle {\int }_{\text{X}}{\left|\frac{\text{d}\mu }{\text{d}\pi }\right|}^p}\text{d}\pi ,\hfill & \mu \ll \pi \hfill \\ \infty ,\hfill & 其他\hfill \end{array}$

设$L^P\left(\pi \right)$ 是$\left(\text{X},\text{F}\right)$ 上所有带符号测度$\mu$ 的集合，${\Vert \mu \Vert }_{L^P(\pi )}<\infty$ 。定义$L^p\left(\pi \right)$ 范数为：

在明确了相关的假设和定义之后，我们现在给出一般状态空间马尔可夫链代数遍历性的六条等价判定条件。

定理2.1. 若假设A成立，那么以下六条都是马尔可夫链代数遍历的等价条件：

(1) 对任意的$j\in \text{N}$ ，存在一个$\pi$ -a.e.有限可测函数$V:\text{X}\to \left[1,\infty \right],\pi \left(V^j\right)<\infty$ ，使得$\text{Φ}$ 是$V$ 一致遍历的，即存在$\ell <0,C<\infty$ 使得

(2) 对任意的$j\in \text{N}$ ，存在一个$\pi$ -a.e.有限可测函数$V:\text{X}\to \left[1,\infty \right],\pi \left(V^j\right)<\infty$ ，且常数$\ell <0,C<\infty$ ，使得$\text{X}$ 上的概率测度$\mu$ 满足$\mu \left(V\right)<\infty$ 且

(3) 对所有的$p\in \left(1,\infty \right)$ ，$\Phi$ 从$L^p\left(\pi \right)$ 中所有概率测度出发是次几何遍历的，且次几何速率仅依赖于$p$ ，这意味着对于每一个$p\in \left(1,\infty \right)$ ，有${\ell }_p<0$ ，使得对于每个概率测度$\mu \in L^p\left(\pi \right)$ ，有$C_p<\infty$ 满足

${\Vert \mu P^n\left(x,\cdot \right)-\pi (\cdot )\Vert }_{TV}\le C_p{n}^{{\ell }_p},n\in \text{N}$ (1)

(4) 存在一个细集$S\in \text{F}$ ，使得从限制于$S$ 的平稳分布开始，$\text{Φ}$ 是次几何遍历的，这意味着存在常数${\ell }_S<0$ 和$C_S<\infty$ 满足

${\Vert {\pi }_S{P}^n\left(x,\cdot \right)-\pi (\cdot )\Vert }_{TV}\le C_S{n}^{{\ell }_S},n\in \text{N}$

其中，${\pi }_S\left(A\right)=\frac{\pi \left(S\cap A\right)}{\pi \left(S\right)},A\in \text{F}$ 。

(5) 存在一个细集$S\in \text{F}$ 和常数${\ell }_S>0$ 满足

其中，${\tau }_s=\text{inf}\left\{n\ge 0;{\tau }_n\in S\right\},{\text{E}}_x[\cdot ]=\text{E}\left[\cdot |{\text{Φ}}_0=x\right]$ 。

(6) 存在一个细集$S\in \text{F}$ ，常数$0\le \alpha <1$ 以及$b<\infty$ ，一个函数$V:\text{X}\to \left[1,\infty \right]$ 满足

$PV\left(x\right)\le V\left(x\right)-C{V}^{\alpha }\left(x\right)+b{\text{I}}_S\left(x\right),x\in \text{X}$

证明：先由(1)推(2)。首先我们有，那么

因为，根据上式可知

得证。

(2)推导(3)。对任意概率測度$\mu \in L^P\left(\pi \right)$ ，根据定义可知${\displaystyle \int {}_X}{\left|\frac{\text{d}\mu }{\text{d}\pi }\right|}^p\text{d}\pi <\infty$ ，因此通过赫尔德不等式可知，对任意的$p,q>1$ 满足$\frac{1}{p}+\frac{1}{q}=1$ ，我们有

因此，根据(2)可知对任意概率测度$\mu \in L^P\left(\pi \right)$ 有

则

因此，我们有

(3)推导(4)。对于细集$S\subset \text{X}$ ，我们现证${\pi }_S\in L^P\left(\pi \right)$ 。因为对任意$A\in \text{F}$ 有${\pi }_S\left(A\right)=\frac{\pi \left(S\cap A\right)}{\pi \left(S\right)}$ ，所以

$\frac{\text{d}{\pi }_S}{\text{ d}\pi }=\frac{{\pi }_S\left(\text{d}x\right)}{\pi \left(\text{d}x\right)}=\frac{\text{I}}{\pi \left(S\right)}$

因此

${\displaystyle {\int }_{\text{X}}{\left|\frac{\text{ d}{\pi }_S}{\text{ d}\pi }\right|}^p\text{d}\pi ={\displaystyle {\int }_{\text{X}}\frac{\text{I}}{\pi {\left(S\right)}^p}\text{d}\pi }}=\frac{1}{\pi {\left(S\right)}^{p-1}}<\infty$

故${\pi }_S$ 符合(3)的条件，因此

${\Vert {\pi }_S{P}^n(\cdot )-\pi (\cdot )\Vert }_{\text{TV}}\le C{n}^{\ell }$

现证(4)推导(5)。(4)式等价于

那么若$n=mh$ ，根据文献[7]中骨架链的基本定义可知，对任意的$h>0$ 有

由此得证。

最后我们要证(5)推导(6)。已知${\text{sup}}_{x\in S}{\text{E}}_x\left[{\tau }_s^{\ell }\right]<\infty$ 。对任意的初始点$x$ 及非负函数$f$ ，根据${\sigma }_S$ 与${\tau }_S$ 的关系可知：

又因为

故

(2)

取序列，令且。根据式子(2)可知

(3)

由的定义及的条件可知，若，则因此

因为，所以一定存在一个满足。据上述结论，我们可从(3)中推出存在满足

其中，。

最后我们从(6)推出(5)，再推出(1)。令，当时，且满足

根据文献[8]中的引理3.5，我们可知由条件可以推出对任意的，存在常数使得

因此对于，都有

由式子(3)及比较定理可知，

又因为

所以

由此我们完成了(6)推出(5)，最后根据文献[9]中的定理3.6，我们可得对任意的，存在满足

显然由上式可得(1)式成立。

注意：尽管定理中的六个条件在理论上是等价的，但它们在实际应用中的可操作性存在一定差异。例如，条件(1)和(2)依赖于构造一个满足特定增长条件的Lyapunov函数V，然而这一函数的构造在很多实际问题中并不容易。特别是当状态空间较为复杂，或者缺乏简单的解析表达式时，找到一个合适的V函数可能会非常困难。相比之下，条件(5)和(6)在实际应用中可能更容易验证。例如，条件(5)通过对首次返回时间的估计来表征遍历性，而条件(6)只需要在某个细集上验证一个期望不等式。在具体应用中，这些条件更容易得到验证和计算。

3. M/G/1嵌入排队过程

排队模型在多个领域中具有广泛的实际应用背景，例如医疗问诊、共享单车、银行柜台服务、网络流量管理等。在这些应用中，排队模型不仅有助于理解系统的运行机制，还能为优化资源配置、提升服务效率提供理论依据。接下来，我们将详细讨论一种具体的排队模型，分析其在实际系统中的表现。

定义3.1. 若一个模型符合以下三个假设：

1) 顾客以的时间间隔到达系统，其中是独立同分布的随机变量序列且都服从均值为的指数分布；

2) 第个顾客的服务时间为随机变量，每个顾客的服务时间都是相互独立且同分布，且与顾客的到达间隔时间独立。随机变量服从均值为的一般分布；

3) 系统里只有一个服务台，且顾客按照先到先服务的原则接受服务；

那么我们称这个模型为M/G/1排队模型。

从定义中可以看出M/G/1排队模型刻画了一个顾客到达速率为，服务速率为的排队问题。为了保证系统的稳定性，我们有下述基础假设：

引理3.1. 若，则M/G/1排队模型是稳定的。

令表示M/G/1排队模型的队长，即时刻下系统中的顾客数。当服从指数分布时，是一个马氏过程，若服从其他分布，则不是一个马氏过程，这种情况下我们可以构造的嵌入过程。我们选取第个顾客离开系统的时刻，令，那么表示队长的嵌入过程且是一个马氏过程，它的转移概率矩阵可以写为：

其中

引理3.2. 若，则嵌入过程是遍历的。

接下来我们将给出M/G/1嵌入排队过程的代数遍历条件。

定理3.3. 若，则以下论述等价

(1) ；

(2) 令，存在常数满足

(3) 令有

上述(1)~(3)中任意一条都能推出过程是多项式遍历的，且对某个有

证明. 首先证明。若有，对任意的，有

根据首达时转移概率分解，我们可得

(4)

对式子(1)两边分别对求导，并令，现在我们用数学归纳法证明对任意的有限。当时，

因此，。当时，

因此，。以此类推，当时，

其中，汇集了所有包含的总和，且常数项都小于，故，由定理2.1可知，存在函数满足

现证满足上式。对任意的，有

因为且，所以可以挑选合适的与使得

那么对于任意的常数，我们可得

当时，因为，所以

综上所述，对于，我们能找到常数满足

令，则根据模型的随机单调性可知

证毕。

最后，我们对等价条件与M/G/1模型的稳定性条件之间的关系进行探讨。在经典的M/G/1排队模型中，稳定性条件通常由到达率和服务率的关系决定，即当时，系统为稳定。然而，这一条件仅仅考虑了系统的平均行为，未涉及服务时间分布的具体形态或到达模式的复杂性。相比之下，本文推导的判定条件则能够在更广泛的情境下应用，考虑到服务时间的分布情况以及系统的动态特性，因此，它提供了比传统稳定性条件更为细致的性能评估工具。

基金项目

湖南师范大学计算与随机数学教育部重点实验室开放课题(202504)；西安电子科技大学学科交叉拓展特支计划项目(TZJH2024004)；陕西省自然科学基础研究计划青年项目(2025JC-YBQN-078)。

NOTES

^*通讯作者。