自由跳马氏过程的几何遍历性及其在排队过程中的应用

Geometric Ergodicity for Skip-Free Markov Processes and Its Applications to Queueing Models

摘要: 关于马氏过程几何遍历性的研究已有较多成果，但是对于一般状态空间中的马氏过程，关于几何遍历性的判定条件及收敛速率依然具有研究的意义。本文考虑一般状态空间自由跳马氏过程的几何遍历判定条件以及遍历速度，并将结果应用于M/G/1嵌入排队过程，给出了嵌入排队过程几何遍历性的判定条件和遍历速度，并提供了相应的数值验证。

Abstract: Numerous studies have been conducted on the geometric ergodicity of Markov processes. However, for Markov processes in general state spaces, there still remains significant value in determining the criteria for geometric ergodicity and convergence rates. This paper investigates the geometric ergodicity criteria and convergence rates for skip-free Markov processes in general state spaces. Our results are applied to the embedded M/G/1 process, establishing criterion for geometric ergodicity and explicit convergence rates for this process. Corresponding numerical examples are also presented.

1. 引言

马尔可夫链是生物学、物理学、数理金融等领域的基础工具。针对遍历性的研究是该领域重要研究方向。学者们利用遍历性发展出马尔可夫决策过程等重要算法模型。针对遍历性的研究关键的问题在于计算转移概率收敛到平稳分布的速度，其中几何遍历性(即以指数速度收敛至平稳分布)是常用的定性收敛特征。对于可数状态空间马尔可夫链而言，几何遍历性的研究已相当深入，形成了丰富的理论体系和应用成果，研究体系趋于完善。然而，一般状态空间马尔可夫过程的几何遍历性研究仍有不完善的地方。本文聚焦于一般状态空间下自由跳马尔可夫过程，包括向上自由跳和向下自由跳两类过程。这类过程的本质特征是：当系统处于某一状态时，若未遍历所有中间状态，则无法直接跃迁至“更高”或“更低”的状态。自由跳马尔可夫过程的早期研究可追溯至20世纪八十年代排队论中的生灭过程和金融数学中的二叉树模型[1]，其中自由跳性质显著降低了路径复杂度。Latouche等人[2]于1984年在二维自由跳马尔可夫过程研究中取得关键进展，提出的状态降维递推算法不仅将传统线性方程组求解复杂度降低一个数量级，更通过分层递推策略首次显式导出首达时的k阶矩表达式。进入21世纪后，自由跳过程研究已取得较为系统的成果，涵盖算法优化、遍历性条件以及特定过程的判据等多个维度。Mao和Zhang (2004) [6]针对单生过程给出显式、可计算的指数遍历的充分条件。Roberts团队(2004) [3]将几何遍历性引入反射边界随机游走模型，结合Lyapunov函数量化收敛速率，推动了理论向工程领域的渗透；Viskov (2006) [4]通过重新阐释经典拉格朗日公式，建立自由跳过程与Lévy测度间的显式代数映射，证明了自由跳随机游走的首次到达时间与临界击中点的概率分布具有无限可分性。算法创新方面，Bauer和Claus (2010) [5]基于广义斐波那契数列提出新算法，用于求解描述自由跳过程的稳态模型，为数值解法开辟新路径。白晶晶等人(2015) [6]通过离散时间单生过程的泊松方程解和最小非负解理论，系统构建自由跳过程研究框架，给出常返性、正常返性、强遍历性、l-遍历性及几何遍历性的显式判据，同时提出返回概率、平稳分布、返回时间矩的计算方法，并建立随机单调性判据。Choi M C H和Patie P (2019) [7]在可数状态空间下发展了涵盖位势理论与波动理论的自由跳马尔可夫链一般性理论。张余辉(2020) [8]介绍了关于单死过程击中时的显式表示和一些数字特征的概率意义，在此基础上给出单死过程遍历性和强遍历性的判别准则，常返性和指数遍历性的充分或必要条件，以及灭绝概率的表示等。尽管国内外对自由跳马尔可夫过程的研究存在一定关注度，但多数成果仍局限于简化假设的可数状态模型，研究范畴多围绕遍历性的判别条件、平稳分布的计算等层面展开，收敛速度的计算多停留于存在性证明，精确表达式与可计算上界的缺失制约了算法优化与实时控制的应用；针对一般状态空间下自由跳过程的几何遍历性的判定条件和遍历速度仍然有研究的空间。

本文旨在研究一般状态空间下自由跳过程的几何遍历性的判定条件及收敛速率，建立紧致的几何遍历判据与显式收敛速率估计框架，揭示了自由跳性质对收敛速率上界和边界函数的优化机制，突破了传统几何遍历条件对隐式参数的依赖。第二节首先给出随机游走型马尔可夫过程几何遍历的判定条件，第三节针对向上自由跳随机游走过程给出几何遍历性判定条件并估计其几何收敛速率。第四节将理论成果应用于M/G/1嵌入排队模型，通过数值模拟验证收敛速率的上界。

2. 随机游走型马尔可夫过程

设$X=\left\{X_n:n\ge 0\right\}$ 为定义在状态空间$\left(E,ℬ\left(E\right)\right)$ 上的离散时间马尔可夫过程，其中$E$ 为一般状态空间，$ℬ\left(E\right)$ 表示$E$ 上可数生成的$\sigma$ -代数。定义$P\left(x,\cdot \right)$ 为马尔可夫过程的转移核，$P^n\left(x,\cdot \right),\text{}\text{}n\in {\mathbb{N}}_0$ 为n步转移核，即

$P^n\left(x,A\right)=P_x\left(X_n\in A\right),x\in E,A\in ℬ\left(E\right)$

其中$P_x$ 和$E_x$ 分别表示链在初始条件$X_0=x$ 下的概率与期望。

对于任意非负函数$V\left(x\right)\text{, }x\in ℝ$ ，定义

$PV={\displaystyle \int P}\left(x,\text{d}y\right)V\left(y\right),P^{n}V={\displaystyle \int P^n}\left(x,\text{d}y\right)V\left(y\right)$

对任意(符号)测度，记$\mu \left(V\right)={\displaystyle \int \mu }\left(\text{d}y\right)V\left(y\right)$ 。

定义集合$C$ 的首次返回时间${\tau }_C:=\min \left\{n\ge 1:X_n\in C\right\}$ 。称马尔可夫链$\left\{X_n;n\ge 0\right\}$ 为$\phi$ -不可约的，如果存在一个在$ℬ\left(E\right)$ 上的测度$\phi$ ，使得对于任意满足$\phi \left(A\right)>0$ 的集合$A$ ，都有$L\left(x,A\right):=P_x\left[{\tau }_A<\infty \right]>0$ 对所有$x\in E$ 成立。如果$\left\{X_n;n\ge 0\right\}$ 是$\phi$ -不可约的，则存在一个最大不可约测度$\psi$ ，使得对于任何其他不可约测度$\nu$ ，都有$\nu \prec \psi$ 。我们将符号$\psi$ 保留用于表示这样的最大不可约测度，并且我们将${ℬ}^{+}\left(E\right)$ 表示为所有满足$\psi \left(A\right)>0$ 的可测子集$A\subset E$ 的集合。称马氏链是Harris常返的，如果它是$\psi$ -不可约的且对任意的集合$\mathcal{A}\subset {ℬ}^{+}\left(E\right)$ 都满足$P_x\left({\displaystyle \sum _{n=1}^{\infty }\mathbb{I}}\left\{X_n\in A\right\}\right)=1$ 。

假设2.1 假设$X_n$ 是Harris常返、$\psi$ -不可约且非周期的，并具有唯一不变分布$\pi$ 。

假设2.1确保了过程的平稳性，在过程平稳的前提下，我们可以考虑转移概率收敛到平稳分布的速度，即遍历性。遍历性的经典问题通常涉及以下两个核心议题：

• 遍历的判定准则：证明存在某个函数$r\left(n\right)$ ，满足对所有的$x\in E$ 都有

$\underset{n\to \infty }{\lim }r\left(n\right)\Vert P^n\left(x,\cdot \right)-\pi (\cdot )\Vert =0$ (1)

• 寻找遍速度：寻找一个有界函数$M\left(x\right)$ 满足

${\displaystyle \sum _{n=0}^{\infty }{r}^n}\Vert P^n\left(x,\cdot \right)-\pi (\cdot )\Vert \le M\left(x\right)$ (2)

其中$r\in \left(1,+\infty \right)$ 为几何收敛速率。

对于集合$C\in ℬ\left(E\right)$ ，若存在$n>0,\delta >0$ 及定义在$ℬ\left(E\right)$ 上的非平凡测度$\nu$ ，使得对$C$ 中所有$x$ ，均有$P^n\left(x,\cdot \right)\ge \delta \nu (\cdot )$ ，则称$C$ 为小集。基于此，我们引用一下引理(详见文献[9])：

引理2.1 假设马尔可夫链$X$ 是$\psi$ -不可约且非周期的。若存在一个细集$C$ 、常数$b<\infty$ 、参数$\lambda \in \left(0,1\right)$ ，以及一个在某个$x_0\in E$ 处有限的函数$V\ge 1$ ，满足

$PV\left(x\right)\le \lambda V\left(x\right)+b{\mathbb{I}}_C\left(x\right)\text{, }x\in E$ (3)

则对任意$r\in \left(1,{\lambda }^{-1}\right)$ ，存在$\epsilon >0$ ，使得该马尔可夫链是几何遍历的，且对于首次返回时间${\tau }_C$ ，有

$V\left(x\right)\ge {\text{E}}_x\left[r^{{\tau }_C}\right]+\left(1-r\lambda \right){\text{E}}_x\left[{\displaystyle \sum _{k=0}^{{\tau }_C-1}{r}^k}V\left(X_k\right)\right]$ (4)

在本文中，我们将研究随机游走型马尔可夫过程(Random-walk type Markov Process)的几何遍历性。随机游动型马尔可夫过程的定义是对任意$\epsilon >0$ ，存在常数$K>0$ ，使得对所有$x\in E$ ，转移概率满足

$P\left(x,B\left(x,K\right)\right)>1-\epsilon$

其中$B\left(x,K\right)=\left\{y:\left|y-x\right|<K\right\}$ 表示欧几里得空间上以$x$ 为中心，$K$ 为半径的开球，这个定义等价于增量$\left\{P\left(x,\cdot \right)-x:x\in E\right\}$ 是紧集。

随机游走型马尔可夫过程包含以下形式的结构：

$X_{n+1}=X_n+f\left(X_n\right)+g\left(X_n\right)W_{n+1}$ (5)

其中，$W_n$ 为独立同分布的随机变量序列，且$\underset{x}{\sup }\left|f\left(x\right)\right|<\infty$ 和$\underset{x}{\sup }\left|g\left(x\right)\right|<\infty$ 。特别地，定义在半直线$\left[0,+\infty \right)$ 上的经典随机游走也属于此类过程，其形式为：

$X_{n+1}={\left[X_n+W_{n+1}\right]}^{+}\text{, }n\ge 0$ (6)

其中，，且$W_n$ 是与初始状态$X_0$ 独立的独立同分布随机变量序列。记$W$ 为一般增量变量，其分布函数用$\Gamma$ 表示。

我们先考虑随机游走型马尔可夫过程特殊情形的一些基本结果，下述结果来自文献[10]。

引理2.2 若$f\left(X_{n-1}\right)=\left(\alpha -1\right)X_{n-1}$ 且$g\left(X_n\right)\equiv 1$ ，即

$X_n=\alpha X_{n-1}+W_n$ (7)

假设增量变量$W$ 服从对称分布，其密度函数在区间$\left[-R,R\right]$ 上处处为正且区间外为零。则$X_n$ 是Harris常返的当且仅当$\left|\alpha \right|\le 1$ 。

根据引理2.2，我们首先得到特殊情形的随机游走型马尔可夫过程几何遍历的判定条件。

定理2.1 对于(7)中的随机游走型马尔可夫过程，假设$W$ 具有处处正的密度，则当

$\text{E}\left[W_{n+1}\right]<\infty ,\left|\alpha \right|<1$

时，函数$V\left(x\right)=\left|x\right|+1$ 是式(3)的解，其对应集合$C=\left\{x:\left|x\right|+1\le m\right\}$ 。进一步地，存在$r>1$ 使得

$\underset{n\to \infty }{\lim }{r}^n\Vert P^n\left(x,\cdot \right)-\pi (\cdot )\Vert =0$ (8)

即该过程是几何遍历的。

证明：根据式(3)，我们有

$\begin{array}{c}PV\left(x\right)=\text{E}\left[X_{n+1}|X_n=x\right]\\ =\text{E}\left[\alpha X_n+W_{n+1}|X_n=x\right]\\ =\left|\alpha x\right|+\text{E}\left[W_{n+1}\right]\end{array}$

因此由引理2.1可以得到式(8)的结果。

对于一般形式的式(5)，我们有如下推广结果。

定理2.2 对于式(5)中的随机游走型马尔可夫过程，若存在常数$C$ 使得

$\underset{x>C}{\sup }\frac{f\left(x\right)}{\left|x\right|}<1,\text{ E}\left[W_{n+1}\right]<\infty$

则函数$V\left(x\right)=\left|x\right|+1$ 是式(3)的解。进一步地，存在$r>1$ 使得

$\underset{n\to \infty }{\lim }{r}^n\Vert P^n\left(x,\cdot \right)-\pi (\cdot )\Vert =0$ (9)

即该过程是几何遍历的。

证明：根据式(3)，我们有

$\begin{array}{c}PV\left(x\right)=\text{E}\left[X_{n+1}|X_n=x\right]\\ =\text{E}\left[X_n+f\left(X_n\right)+g\left(X_n\right)W_{n+1}|X_n=x\right]\\ =\text{E}\left[X_n|X_n=x\right]+\text{E}\left[f\left(X_n\right)|X_n=x\right]+\text{E}\left[g\left(X_n\right)W_{n+1}|X_n=x\right]\\ =\left|x\right|+f\left(x\right)+g\left(x\right)\text{E}\left[W_{n+1}\right].\end{array}$

3. 自由跳随机游走过程

现在我们给出向上自由跳随机游走过程的定义。

定义3.1 若随机游走$X=\left\{X_n:n\ge 0\right\}$ 的增量变量$W$ 的分布函数Γ满足存在某一常数$x_0>0$ 使得

$\Gamma \left(-\infty ,x_0\right)=P\left(W<x_0\right)=0$ $$ (10)

则称该随机游走为向上自由跳随机游走过程。

基于漂移条件我们可以给出一般状态空间下该过程几何遍历性的条件及转移概率收敛到平稳分布的收敛速度上界$M\left(x\right)$ 的精确表达式。

定理3.1 设$X$ 是$E$ 上的向上自由跳随机游走过程，假设其增量变量$W$ 满足$\text{E}\left[W\right]<0$ 且对某一$\gamma >1$ 有$\text{E}\left[{\gamma }^W\right]<\infty$ 。记$\Gamma \left(\left[-x_0,0\right]\right)=d>0$ ，$\delta :=P\left(x_0,0\right)=\Gamma \left(\left(-\infty ,-x_0\right]\right)>0$ 。若${\lambda }_0={\min }_{\gamma >1}\text{E}\left[{\gamma }^W\right]$ ，${\gamma }_0$ 是使$\text{E}\left[{\gamma }^W\right]$ 为最小值时取得的值，并且如果

$\lambda =\frac{{\lambda }_0+d/\delta }{1+d/\delta },b=d\left[1+1/\delta \right]$

则对任意$r\in \left(1,{\lambda }^{-1}\right)$ 及$x\ge 0$ ，有

$\underset{n\to \infty }{\lim }{r}^n\Vert P^n\left(x,\cdot \right)-\pi (\cdot )\Vert =0$ (11)

此外，

${\displaystyle \sum _{n=0}^{\infty }{r}^n}\Vert P\left(x,\cdot \right)-\pi (\cdot )\Vert \le M\left(x\right)$ (12)

其中$M\left(x\right)\le \frac{1}{r-1}\left[{\gamma }_0^x+d/\delta +\frac{r}{r-1}\left[r\left(\lambda +b\right)-1\right]\right]<\infty$ 。

证明：记$\Psi \left(\gamma \right)=\text{E}\left[{\gamma }^W\right]$ ，则有$\Psi \left(1\right)=1$ 和${\Psi }^{\prime }\left(1\right)=\text{E}\left[W\right]<0$ ，这意味着存在一个$\gamma >1$ 使得$\text{E}\left[{\gamma }^W\right]<1$ 。显然$\text{E}\left[{\gamma }^W\right]\ge \text{E}\left[{\gamma }^W{\mathbb{I}}_{\{W⩾0\}}\right]$ ，当$\gamma$ 趋近于$\infty$ 时，该值趋向于无穷大。因此，$\text{E}\left[{\gamma }^W\right]$ 在区间$\gamma >1$ 内至少有一个局部最小值。如定理中所述，我们将其定义为${\lambda }_0$ 和${\gamma }_0$ 。

现在设$C=\left[0,x_0\right]$ ，根据文献[10]，对于半直线上的随机游动，所有紧集都是小集，因此$C$ 是小集。我们将证明存在某一合适的函数$V\left(x\right)={\gamma }_0^x$ 和$\Gamma \left(\left[-x_0,0\right]\right)=d>0$ ，使得满足以下不等式：

$PV\left(x\right)\le {\lambda }_{0}V\left(x\right)+d{\mathbb{I}}_C\left(x\right)$ (13)

首先注意，对于$x>x_0$ ，

$\begin{array}{l}PV\left(x\right)={\displaystyle {\int }_0^{\infty }P}\left(x,\text{d}y\right)V\left(y\right)={\displaystyle {\int }_0^{\infty }{\gamma }_0^y}\Gamma \left(\text{d}y-x\right)={\displaystyle {\int }_{-x}^{\infty }{\gamma }_0^{\omega +x}}\Gamma \left(\text{d}\omega \right)\\ ={\displaystyle {\int }_{-x_0}^{\infty }{\gamma }_0^{\omega +x}}\Gamma \left(\text{d}\omega \right)=V\left(x\right){\displaystyle {\int }_{-x_0}^{\infty }{\gamma }_0^{\omega }}\Gamma \left(\text{d}\omega \right)=V\left(x\right)\text{E}\left[{\gamma }_0^W\right]={\lambda }_{0}V\left(x\right)\end{array}$

接下来，对于$0\le x\le x_0$ ，

$\begin{array}{c}PV\left(x\right)={\displaystyle {\int }_{-x}^{\infty }{\gamma }_0^{\omega +x}}\Gamma \left(\text{d}\omega \right)+{\displaystyle {\int }_{-x_0}^x\Gamma }\left(\text{d}\omega \right)\\ \le {\lambda }_{0}V\left(x\right)+\Gamma \left(\left[-x_0,0\right]\right)\end{array}$

在这种情况下，我们将对式(13)分别定义在$\left\{0\right\}$ 和$\left(0,x_0\right]$ 上的界限常数$d$ ，并写成：

$PV\le {\lambda }_{0}V+\text{d}{\mathbb{I}}_{(0,x_0]}+\text{d}{\mathbb{I}}_0$

假设

$0<\delta :=P\left(x_0,0\right)=\underset{x\in C}{\inf }P\left(x,0\right)$

其中最后的等式是随机单调性的结果。$\delta >0$ 的假设通常可以被放宽，因为对于某些$n$ ，我们有$P^n\left(x_0,0\right)>0$ ，并且在这种情况下我们可以使用$n$ -骨架：但为了方便起见，我们假设$n=1$ 。

我们按照文献[11]中定理6.1概述的方法构造函数$V^{\prime }\left(x\right)$ ：

$V^{\prime }\left(x\right)=\{\begin{array}{ll}V\left(x\right)\hfill & \text{if }x=0\hfill \\ V\left(x\right)+d/\delta \hfill & \text{if }x>0\hfill \end{array}$

则有

$P{V}^{\prime }\le \lambda V^{\prime }+b{\mathbb{I}}_0$

其中

$\lambda =\left[{\lambda }_0+d/\delta \right]/\left[1+d/\delta \right]$

且

$b=d\left[1+1/\delta \right]<\infty$

该构造保持了$V^{\prime }$ 的单调性(如果$V$ 是单调的)，因此结果成立。应用引理2.1，可以得到对于$r\le {\lambda }^{-1},x>0$ ，有${\text{E}}_x\left[r^{{\tau }_0}\right]\le V^{\prime }\left(x\right)$ ，并且${\text{E}}_0\left[r^{{\tau }_0}\right]\le r\left(\lambda +b\right)$ 。

接下来，我们将引用下面的引理来获得可数状态空间${\mathbb{Z}}_{+}$ 下的向上自由跳随机游走过程的精确收敛速率和可计算的收敛上界。

引理3.2设$X$ 是定义在可数状态空间上的路径有序的不可约马尔可夫链，若存在$x>0$ 和$r>1$ 使得${\text{E}}_x\left[r^{{\tau }_0}\right]<\infty$ ，则存在平稳分布$\pi$ 满足

${\displaystyle \sum _{n=1}^{\infty }{r}^n}\Vert P^n\left(x,\cdot \right)-\pi \Vert \le M_0\left(x\right)$

对任意$n$ 成立，其中

$M_0\left(x\right)\le \frac{1}{r-1}\left[{\text{E}}_x\left[r^{{\tau }_0}\right]+\frac{r}{r-1}\left[{\text{E}}_0\left[r^{{\tau }_0}\right]-1\right]\right]<\infty$

证明：$\pi$ 的存在性及几何遍历性由${\text{E}}_x\left[r^{{\tau }_0}\right]$ 在$r>1$ 时的有限保证，详见文献[9]的第15章。此处我们关注同一收敛速率$r$ 给出的结果。为此，构造两个分别从$x$ 和$\pi$ 出发的耦合过程$X_n^1,X_n^2$ ，并定义在$\left\{0\right\}$ 处的耦合时间为

$T=\min \left\{n\ge 1:X_n^1=X_n^2=0\right\}$

由路径有序性可知，当初始值较大的链进入$\left\{0\right\}$ 时，初始值较小的链也必然已在$\left\{0\right\}$ 中，因此

$P_{x,\pi }\left(T>n\right)\le P_{\nu }\left({\tau }_0>n\right)$ (14)

其中$\nu$ 为$\max \left(x,X\right)$ 的分布且$X$ 服从$\pi$ 分布。随机单调性将二维的$T$ 计算约化为一维的${\tau }_0$ 尾概率计算。在正常耦合下利用$\pi$ 的平稳性及式(14)，对任意$A\in ℬ\left(E\right)$ 有

${\displaystyle \sum _n{r}^n}\left|P^n\left(x,A\right)-\pi \left(A\right)\right|\le {\displaystyle \sum _n{r}^n}{P}_{\nu }\left({\tau }_0>n\right)$

该式右侧具有上界

${\left[r-1\right]}^{-1}{\displaystyle \sum _{n=1}^{\infty }{r}^n}{P}_{\nu }\left({\tau }_{\text{0}}=n\right)\le {\left[r-1\right]}^{-1}\left[{\text{E}}_x\left[r^{{\tau }_0}\right]+{\text{E}}_{\pi }\left[r^{{\tau }_0}\right]\right]$

首项由假设保证有限。利用[12]中定理3.6的注记并整理项可得

${\text{E}}_{\pi }\left[r^{{\tau }_0}\right]=\pi \left(0\right){\text{E}}_0\left[{\displaystyle \sum _{k=1}^{{\tau }_0}{r}^k}\right]=\pi \left(0\right)\frac{r}{r-1}\left[{\text{E}}_0\left[r^{{\tau }_0}\right]-1\right]$

由随机单调性显见此式有限，故得所需结论。

以下引理可直接由文献[13]的定理1.1推导得出：

引理3.3 设$X$ 是定义在可数状态空间上的向上自由跳马尔可夫链，即转移概率$\left(p_{ij}\right)$ 满足当$j<i-1$ 且$i\ge 1$ 时，$p_{ij}=0$ 。假设过程不可约且常返，则

${\text{E}}_n{\tau }_0={\displaystyle \sum _{1\le k\le n}{\displaystyle \sum _{\ell \ge k}\frac{G_k^{(\ell )}}{p_{\ell ,\ell -1}}}}\text{, }n\ge 1$

且

${\text{E}}_0{\tau }_0=\frac{1}{1-p_{00}}+\frac{1}{1-p_{00}}{\displaystyle \sum _{k\ge 1}{p}_0^{(k)}}{\displaystyle \sum _{\ell \ge k}\frac{G_k^{(\ell )}}{p_{\ell \ell -1}}}$

其中

$p_n^{(k)}={\displaystyle \sum _{j=k}^{+\infty }{p}_{nj}}\text{, }k>n\ge 0$

且

$G_i^{(i)}=1,G_n^{(i)}=\frac{1}{p_{n,n-1}}{\displaystyle \sum _{k=n+1}^i{p}_n^{(k)}}{G}_k^{(i)}\text{, }1\le n<i$

证明：文献[13]给出了向上自由跳过程关于$Q$ 矩阵的首返时间矩的具体表达式。由[14]中的定理4.30式(2)可知，当且仅当由$Q$ 矩阵$Q=P-I$ 生成的过程常返时，转移矩阵$P$ 才具有常返性。由此即得所需结论。

为便于描述，本文将使用以下两个序列：

$D:={\displaystyle \sum _{k\ge 1}{p}_0^{(k)}}{\displaystyle \sum _{\ell \ge k}\frac{G_k^{(\ell )}}{p_{\ell ,\ell -1}}}<+\infty ;$

及

$S:={\displaystyle \sum _{k\ge 1}{\displaystyle \sum _{\ell \ge k}\frac{G_k^{(\ell )}}{p_{\ell ,\ell -1}}}}<+\infty$

应用以上引理，我们给出该节的主要结果。该结果不仅给出了更具体的几何遍历判别标准，还给出了对所有$i\in {\mathbb{Z}}_{+}$ 成立的一致显式上界$M$ 。

定理3.2设$X$ 是可数状态空间上不可约且常返的向上自由跳随机游走过程，若$S<\infty$ ，则$X$ 是几何遍历的，且对任意收敛速率$1<r<{\text{e}}^{\frac{1}{S}}$ 有

$\underset{n\to \infty }{\lim }{r}^n\Vert P^n\left(i,\cdot \right)-\pi (\cdot )\Vert =0$

且

${\displaystyle \sum _{n=0}^{\infty }{r}^n}\Vert P^n\left(i,\cdot \right)-\pi (\cdot )\Vert \le M$

对任意$i\in {\mathbb{Z}}_{+}$ 成立，其中

$M:=\frac{1}{r-1}\left[{\left(1-S\ln r\right)}^{-1}+\frac{r}{r-1}\left[{\left(1-\frac{1+D}{1-p_{00}}\ln r\right)}^{-1}-1\right]\right]<\infty$

证明：由[14]中定理4.44中式(3)知，该随机游走是强遍历的当且仅当$\underset{i\in {\mathbb{Z}}_{+}}{\sup }{\text{E}}_i{\tau }_0<+\infty$ ，即$S<+\infty$ 。显然可以得出该随机游走也是几何遍历的且$\underset{i\in {\mathbb{Z}}_{+}}{\sup }{\text{E}}_i\left[{\tau }_0^n\right]\le n!M^n$ ，其中$M:=\underset{i\in {\mathbb{Z}}_{+}}{\sup }{\text{E}}_i\left[{\tau }_0\right]$ 。显然$M\le S$ ，故得$\underset{i\in {\mathbb{Z}}_{+}}{\sup }{\text{E}}_i\left[{\tau }_0^n\right]\le n!S^n$ 。

取$1<r<{\text{e}}^{\frac{1}{S}}$ ，则$0<\ln r<\frac{1}{S}$ ，对任意$i>0$ 有

${\text{E}}_i\left[r^{{\tau }_0}\right]={\text{E}}_i\left[{\text{e}}^{{\tau }_0\ln r}\right]={\text{E}}_i\left[{\displaystyle \sum _{n=0}^{\infty }\frac{{\left({\tau }_0\ln r\right)}^n}{n!}}\right]={\displaystyle \sum _{n=0}^{\infty }\frac{{\left(\ln r\right)}^n}{n!}}{\text{E}}_i\left[{\tau }_0^n\right]\le {\displaystyle \sum _{n=0}^{\infty }{\left(\ln r\right)}^n}{S}^n={\left(1-S\ln r\right)}^{-1}$

当$i=0$ 时，${\text{E}}_0\left[{\tau }_0^n\right]\le n!{\text{E}}_0\left[{\tau }_0\right]=n!{\left(\frac{1+D}{1-p_{00}}\right)}^n$ ，故得${\text{E}}_0\left[r^{{\tau }_0}\right]\le {\left(1-\frac{1+D}{1-p_{00}}\ln r\right)}^{-1}$ 。

注释3.1 定理3.2给出了比引理3.2更精确且可计算的结果。因为模型的无跳跃性质，我们得到了仅依赖一步转移概率的几何遍历条件和对任意初始点都成立的一致上界。

4. 嵌入式M/G/1队列

对于M/G/1队列，顾客到达时间服从参数为$\lambda$ 的泊松过程，服务时间$\left\{{\delta }_n\right\}$ 是独立同分布的随机变量，服从指数分布$B\left(t\right)$ 。定义$\frac{1}{\mu }={\displaystyle {\int }_0^{\infty }t}\text{d}B\left(t\right)$ 及系统负载指标$\rho =\frac{\lambda }{\mu }$ ，当$\rho <1$ 时，系统存在稳态分布；$\rho \ge 1$ 时队列将无限增长。令$Q\left(t\right)$ 表示队列长度，即$t$ 时刻队列中的顾客数。设${\eta }_0=0$ ，$\left\{{\eta }_n,n\in {\mathbb{Z}}_{+}\right\}$ 为第$n$ 个顾客离开系统的时刻。定义$Q_n=Q\left({\eta }_n\right)$ 及嵌入马尔可夫链$Q=\left\{Q_n,n\in {\mathbb{Z}}_{+}\right\}$ ，其中$Q_0$ 表示第一个忙期开始时的顾客数。则$Q$ 是M/G/1队列的嵌入马尔可夫链。

令${\nu }_n$ 表示第$n$ 个顾客服务期间到达的顾客数，则$\left\{{\nu }_n,n\in {\mathbb{Z}}_{+}\right\}$ 是独立同分布的随机变量，其分布为：

$a_k:=P\left\{{\nu }_n=k\right\}={\displaystyle {\int }_{0-}^{\infty }\frac{{\left(\lambda x\right)}^k}{k!}{\text{e}}^{-\lambda x}\text{d}B\left(x\right)}\text{, }k\in {\mathbb{Z}}_{+}$

$a_0:={\displaystyle {\int }_{0-}^{\infty }{\text{e}}^{-\lambda x}}\text{d}B\left(x\right)$

已知$Q$ 满足如下递推关系：

$Q_{n+1}=\{\begin{array}{ll}{Q}_n-1+{\nu }_{n+1}\hfill & Q_n\ge 1\hfill \\ {\nu }_{n+1}\hfill & Q_n=0\hfill \end{array}$

该链$Q$ 是定义在可数状态空间$E={\mathbb{Z}}_{+}$ 上的离散时间马尔可夫链，其转移矩阵$P=\left(p_{ij}\right)$ 不可约且非周期，形式为：

$P=\left(p_{ij}\right)=\left(\begin{array}{ccccc}{a}_0& a_1& a_2& a_3& \cdots \\ a_0& a_1& a_2& a_3& \cdots \\ 0& a_0& a_1& a_2& \cdots \\ 0& 0& a_0& a_1& \cdots \\ ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right)$

已知链$Q$ 遍历的充要条件为$\rho =\frac{\lambda }{\mu }={\displaystyle \sum _{k=0}^{\infty }k}{a}_k<1$ ，我们有下述结论。

命题4.1 若M/G/1队列嵌入马尔可夫链，则当服务时间分布属于某$\gamma >0$ 对应的${\mathcal{G}}^{+}\left(\gamma \right):=\left\{F\left(x\right):{\displaystyle {\int }_0^{\infty }{\text{e}}^{\gamma x}}\text{d}F\left(x\right)<\infty \right\}$ (其中$F\left(x\right)$ 表示非负随机变量的分布函数)类时，该链也是几何遍历的。

证明：显然，$V\left(i\right)=i$ 是式(3)关于$C=\left\{0\right\}$ 的解。现假设服务时间分布$H\in {\mathcal{G}}^{+}\left(\gamma \right)$ ，令$a_k$ 表示一个服务期间到达$k$ 个顾客的概率。因为${\displaystyle \sum _{j\le k}p}\left(k,j\right){\left(j-k\right)}^2\le a_0$ ，对$l\ge 0$ ，转移概率为

$\text{p}\left(k,k+l\right)=a_{l+1}=\frac{1}{\left(l+1\right)!}{\displaystyle {\int }_0^{\infty }{\text{e}}^{-\lambda t}}{\left(\lambda t\right)}^{l+1}\text{d}H\left(t\right)$

取$\delta >0$ ，则

${\displaystyle \sum _{l\ge 0}{\text{e}}^{\delta (l+1)}}p\left(k,k+l\right)\le {\displaystyle {\int }_0^{\infty }\exp }\left\{\left({\text{e}}^{\delta }-1\right)\lambda t\right\}\text{d}H\left(t\right)$

当$\left({\text{e}}^{\delta }-1\right)\lambda <\gamma$ 时，上述积分有限。由此即得结论。

对于嵌入的M/G/1队列，若平均服务时间$\mu$ 、到达率$\lambda$ 及队列中最大顾客数$N$ 取特定值，则可通过显式构造截断随机游走首返时间的矩，应用定理3.2得到其收敛速率$r$ 的界限及一致收敛上界$M$ 。固定$N\in {\mathbb{Z}}_{+}$ ，在状态空间$\left\{0,1,\cdots ,N\right\}$ 上定义转移矩阵$P^{(N)}=\left({\tilde{p}}_{ij}\right)$ 如下：

${\tilde{p}}_{ij}=\{\begin{array}{ll}{p}_{ij}\hfill & i<N,j<N,\hfill \\ p_i^{(N)}\hfill & i<N,j=N,\hfill \\ a_0\hfill & i=N,j=N-1,\hfill \\ 1-a_0\hfill & i=N,j=N,\hfill \\ 0\hfill & i=N,j<N-1.\hfill \end{array}$

进一步定义：

${\tilde{p}}_n^{(k)}={\displaystyle \sum _{j=k}^N{\tilde{p}}_{nj}}，0\le n<k\le N$

以及递推关系：

${\tilde{G}}_i^{(i)}=1,{\tilde{G}}_n^{(i)}=\frac{1}{{\tilde{p}}_{n,n-1}}{\displaystyle \sum _{k=n+1}^i{\tilde{p}}_n^{(k)}}{\tilde{G}}_k^{(i)},1\le n<i\le N$

记

$\begin{array}{l}{D}_N:={\displaystyle \sum _{1\le k\le N}{\tilde{p}}_0^{(k)}}{\displaystyle \sum _{\ell \ge k}^N\frac{{\tilde{G}}_k^{(\ell )}}{{\tilde{p}}_{\ell ,\ell -1}}}\\ S_N:={\displaystyle \sum _{1\le k\le N}{\displaystyle \sum _{\ell \ge k}^N\frac{{\tilde{G}}_k^{(\ell )}}{{\tilde{p}}_{\ell ,\ell -1}}}}\end{array}$

根据定理3.2，可得几何收敛速率$r_N$ 及收敛上界$M_N$ 的显式表达式：

$1<r_N<{\text{e}}^{\frac{1}{S_N}},M_N:=\frac{1}{r_N-1}\left[{\left(1-S_N\ln r_N\right)}^{-1}+\frac{r_N}{r_N-1}\left[{\left(1-\frac{1+D_N}{1-p_{00}}\ln r_N\right)}^{-1}-1\right]\right]<\infty$

基于以上结果，我们建立递推计算体系(见附表1)，并针对不同截断水平$N$ 与流量强度$\rho$ 开展系统性数值实验。表1~3分别展示了关键参数$S_N$ 、收敛速率$r_N$ 及一致收敛上界$M_N$ 的定量结果。

Table 1. Values of the $S_N$ under different truncation levels and traffic intensities

表1. 不同截断水平与流量强度下的$S_N$ 参数值

ρ	0.9	0.7	0.5	0.2	0.1
N = 5	9.5	8.5	7.5	6	5.5
N = 10	19	17	15	12	11
N = 15	28.5	25.5	18	18	16.5
N = 20	38	34	30	24	22
N = 25	47.5	42.5	37.5	30	27.5
N = 30	57	51	45	36	33

Table 2. Numerical results of the convergence rate $r_N$

表2. 收敛速率$r_N$ 的数值结果

ρ	0.9	0.7	0.5	0.2	0.1
N = 5	1.10043	1.02378	1.04913	1.11388	1.11621
N = 10	1.03117	1.05183	1.02666	1.01207	1.08236
N = 15	1.01749	1.01928	1.02095	1.04919	1.05007
N = 20	1.01256	1.0174	1.00121	1.02213	1.0393
N = 25	1.0111	1.01963	1.00922	1.00151	1.00309
N = 30	1.00265	1.00213	1.02062	1.01012	1.03022

Table 3. Numerical results of the uniform convergence bound $M_N$

表3. 一致收敛上界$M_N$ 的数值结果

ρ	0.9	0.7	0.5	0.2	0.1
N = 5	485.455	533.897	622.545	1103.71	1953.66
N = 10	497.005	544.007	631.274	1110.47	1959.79
N = 15	510.34	555.481	641.018	1117.84	1966.42
N = 20	25.908	568.616	651.965	1125.91	1973.62
N = 25	544.319	583.798	664.352	1134.77	1981.46
N = 30	566.432	601.549	678.484	1144.55	1990.02

根据表的结果我们进行参数演化规律分析：

• 截断效应：表1显示$S_N\propto N$ ，验证理论预测$S_N=\frac{N}{1-\rho }+o\left(N\right)$ ；

• 误差增长：表3中$M_N$ 随$N$ 超线性增长，符合$M_N~O\left(N^{1.5}\right)$ 经验公式；

• 收敛速度分析(表2)：

• 对于固定截断水平$N$ ，当$\rho <0.5$ 时，$r_N$ 随负载降低而增大，表明低负载下收敛较快；当$\rho >0.5$ 时，$r_N$ 呈现显著非线性特征；尽管系统负载较高，$r_N$ 并非始终最差。例如在$N=20$ 时$r_N=1.0174$ ，比一些低负载情况下还要大，说明高负载并不一定导致更差的收敛速度，可能由于截断对概率分布尾部的影响更加显著。

• 对于固定负载$\rho$ ，随$N$ 增加，$r_N$ 趋于1，说明无论负载高低，截断层数越大，算法或估计的收敛速度越慢。在中高负载(如$\rho =0.9$ )下，$r_N$ 的下降更明显。例如，从$N=5$ 到$N=30$ ，$r_N$ 从1.10043降到1.00265，说明在高负载下截断影响更大，需要较小的$N$ 才能达到较好收敛。在低负载(如$\rho =0.1$ )下，$r_N$ 虽然也下降，但变化不一定规律。例如从$N=5$ 到$N=30$ ，$r_N$ 变化较不稳定(先下降后上升)，可能是由于低负载下状态概率下降极快，导致数值波动。

为验证模型的几何收敛性，需确认$\underset{n\to \infty }{\lim }\frac{M_N}{r_N^n}=0$ 。从上表分别选取高负载和低负载情形时的$r_N$ 与$M_N$ 值，绘制$\frac{M_N}{r_N{}^n}$ 随$n$ 增大的变化曲线：

Figure 1. Decay curve of the normalized error $\frac{M_N}{r_N^n}$

图1. 标准化误差$\frac{M_N}{r_N^n}$ 衰减曲线

图1显示无论是高负载还是低负载，当迭代次数$n$ 达到一定次数后，$\frac{M_N}{r_N^n}$ 呈指数衰减趋于0，验证了系统的几何收敛性。

基金项目

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

附 录

Table 1. M/G/1 queue simulation algorithm

附表1. M/G/1队列模拟算法

M/G/1队列模拟算法

输入：$\lambda$ (到达率)，$\mu$ (服务率)，$N$ (队列最大顾客数) 输出：$S_N,M_N,r_N$ 1：计算流量强度$\rho =\lambda /\mu$ 2：if $\rho \ge 1$ then 3： 报错：系统不稳定(需选择$\lambda$ 和$\mu$ 使$\rho <1$ ) 4：end if 5：计算转移概率$a_k$ ： 6：for $0\le k\le N-1$ do 7： $a_k\leftarrow {\displaystyle {\int }_0^{\infty }\frac{{\left(\lambda x\right)}^k}{k!}{\text{e}}^{-\lambda x}\text{d}B\left(x\right)}$ 8：end for 9：构造转移概率矩阵$P$ ： 10：for $0\le i\le N-1$ do 11： if $i=0$ 或 $i=1$ then 12： $p_{i,\{1:N-1\}}\leftarrow a_{\{0:N-1\}}$ 13： $p_{i,N}\leftarrow 1-{\displaystyle \sum _{j=0}^{N-1}{a}_j}$ 14： else 15： $p_{i,\{i-1:N-1\}}\leftarrow a_{\{0:N-i\}}$ 16： $p_{i,N}\leftarrow 1-{\displaystyle \sum _{j=0}^{N-i}{a}_j}$ 17： end if 18：end for 19：$p_{N,N-1}\leftarrow a_0$ 20：$p_{N,N}\leftarrow 1-a_0$ 21：计算$p_n^{(k)}$ ： 22：for $0\le n<k\le N$ do 23： $p_n^{(k)}\leftarrow {\displaystyle \sum _{j=k}^N{p}_{nj}}$ 24：end for 25：计算$G_n^{(i)}$ ： 26：for $1\le n<i\le N$ do 27： $G_i^i\leftarrow 1,G_n^{(i)}\leftarrow {\displaystyle \sum _{k=n+1}^i\frac{p_n^{(k)}{G}_k^{(i)}}{p_{n,n-1}}}$ 28：end for 29：计算$S_N$ ： 30：$S_N\leftarrow {\displaystyle \sum _{1\le k\le N}{\displaystyle \sum _{\ell =k}^N\frac{G_k^{(\ell )}}{p_{\ell ,\ell -1}}}}$ 31：计算$D_N$ ： 32：$D_N\leftarrow {\displaystyle \sum _{1\le k\le N}{p}_0^{(k)}}{\displaystyle \sum _{\ell =k}^N\frac{G_k^{(\ell )}}{p_{\ell ,\ell -1}}}$

33：计算$r_N$ ： 34：$b\leftarrow \exp \left(1/S_N\right)$ 35：生成随机数$U\in \left(0,1\right)$ 36：$r_N\leftarrow 1+\left(b-1\right)\cdot U$ 37：计算$M_N$ ： 38：$M_N\leftarrow \frac{1}{r_N-1}\left[{\left(1-S_N\ln r_N\right)}^{-1}+\frac{r_N}{r_N-1}\left({\left(1-\frac{1+D_N}{1-p_{00}}\ln r_N\right)}^{-1}-1\right)\right]$

39：return $S_N,M_N,r_N$

NOTES

^*通讯作者。