Sample Path Moderate Deviation Principle for Queues with Waiting-time Dependent Interarrival and Service Times

基本信息

• 论文ID: 2510.27226
• 标题: Sample Path Moderate Deviation Principle for Queues with Waiting-time Dependent Interarrival and Service Times
• 作者: Chang Feng (University of Texas at Austin), John J. Hasenbein (University of Texas at Austin), Guodong Pang (Rice University)
• 分类: math.PR (Probability Theory)
• 发表时间: November 3, 2025 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2510.27226v1

摘要

本文研究单服务器排队系统中到达间隔时间和服务时间线性且随机地依赖于顾客等待时间的情形，建立了等待时间过程的样本路径中偏差原理(MDP)。等待时间可表示为带有随机权重系数的修正Lindley递归。在随机系数的自然尺度变换下，作者分析了工作负载过程的流体行为，导出稳定平衡点(可以是零或正值)。中偏差尺度过程围绕稳定平衡点中心化，然后表示为由两个随机游走驱动的线性随机微分方程，加上渐近可忽略的误差项和可能在零处的反射。两种情形下MDP的速率函数可以显式刻画，区别在于零中心化情形涉及线性广义Skorokhod反射映射，而正中心化情形不涉及。

研究背景与动机

问题提出

现实排队系统中，到达过程和服务时间往往依赖于系统拥塞或延迟状态：

• 医疗系统：急诊室过度拥挤时患者会放弃就医(balking)；重症监护室超载时医生可能加速患者流转
• 其他应用：生物系统、制造业、库存管理、计算机网络和保险等领域都存在类似的负载依赖行为

重要性

1. 理论意义：扩展经典排队理论到状态依赖系统，填补中偏差理论在此类模型中的空白
2. 实际价值：为理解拥塞系统的稀有事件提供理论工具，有助于风险评估和系统设计
3. 方法论贡献：开发了分析带随机系数反射自回归过程的新技术

现有方法的局限

• 分布分析主导：已有研究多关注稳态分布和变换方法(Boxma et al. 2007, 2016, 2021)
• 样本路径层面结果有限：
  • Whitt (1990)的泛函中心极限定理未给出极限扩散过程的显式形式
  • 大偏差原理仅在特殊情形建立(Vlasiou and Palmowski 2014)
  • 中偏差原理完全缺失：这是本文填补的关键空白

研究动机

1. 建立等待时间依赖排队系统的首个样本路径中偏差原理
2. 提供介于大偏差和中心极限定理之间的精细概率近似
3. 发展可应用于更广泛反射AR(1)过程的分析技术

核心贡献

1. 首个MDP结果：建立了等待时间依赖排队系统的样本路径中偏差原理，填补该领域理论空白
2. 完整的流体分析：
   • 系统分析了流体极限在不同参数区域(过载/临界负载/欠载，不同状态依赖强度)下的行为
   • 识别了所有稳定平衡点（零或正值），见表1总结
3. 显式速率函数：对两种中心化情形（零中心和正中心）导出了可显式计算的速率函数（定理2.6）：
   • 零中心化：涉及线性广义Skorokhod反射映射
   • 正中心化：不涉及反射，速率函数形式更简单
4. 新的证明技术：
   • 开发了线性递归Markov链的MDP分析方法（第4节）
   • 创新性地使用鞅技术证明误差项的指数消失性
   • 建立了指数紧性和指数等价性的系统性论证框架
5. 补充的扩散近似：在附录B中证明了泛函中心极限定理，极限为OU过程或反射OU过程，补充了Whitt (1990)的工作

方法详解

任务定义

考虑单服务器FIFO排队系统序列（索引为n）：

• 输入：i.i.d.随机向量序列 $\{(A^n_i, S^n_i, \mathcal{A}^n_i, \mathcal{B}^n_i), i \in \mathbb{N}_0\}$
• 状态依赖机制：
  • 实际到达间隔：$A'^{n}_i = A^n_i + \mathcal{A}^n_i W^n_i$
  • 实际服务时间：$S'^{n}_i = S^n_i + \mathcal{B}^n_i W^n_i$
• 目标：建立中偏差尺度等待时间过程 $\tilde{W}^n(t) = \frac{\sqrt{n}}{b_n}(\bar{W}^n(t) - \bar{W}^*)$ 的样本路径MDP

其中：

• $b_n \to \infty$, $b_n/\sqrt{n} \to 0$（中偏差尺度）
• $\bar{W}^n(t) = \frac{1}{n}W^n_{\lfloor nt \rfloor}$（流体尺度）
• $\bar{W}^*$ 是流体极限的稳定平衡点

核心递归结构

修正Lindley递归： $W^n_{i+1} = (C^n_i W^n_i + X^n_i)^+$

其中：

• $X^n_i = S^n_i - A^n_i$（名义增量）
• $C^n_i = 1 + \mathcal{B}^n_i - \mathcal{A}^n_i$（随机权重系数）

关键尺度假设（Assumption 2.1）： $C^n_i = 1 - \frac{1}{n}\Theta_i$

其中$\{\Theta_i\}$是i.i.d.序列，均值$\theta$，方差$\sigma^2_\Theta$。这种尺度选择使得：

• 当$n$大时，$(C_i)^{1/n} \approx e^{-\Theta_i/n} \approx 1 - \Theta_i/n$
• 与Whitt (1990)和Boxma et al. (2016)的尺度相容

流体分析（第3节）

通过伸缩求和并引入误差项，得到流体尺度表示： $\bar{W}^n(t) = \bar{W}^n_0 + \frac{1}{n}\sum^{\lfloor nt \rfloor -1}_{i=0} X^n_i - \int^t_0 \theta \bar{W}^n(s)ds + \bar{\epsilon}^{n}_{1}(t) + \bar{\epsilon}^{n}_{2}(t) + \frac{1}{n}L^n_{\lfloor nt \rfloor -1}$

流体极限（定理3.2）： $\bar{W} = R_\theta(\bar{w}_0 + \mu e)$

其中$R_\theta$是线性广义Skorokhod反射映射，满足微分形式： $d\bar{W}(t) = \mu - \theta\bar{W}(t) + d\bar{L}(t)$

稳定平衡点分析（表1总结）：

线性递归Markov链的MDP（第4节）

为处理无反射的辅助系统： $V^n_{i+1} = C^n_i V^n_i + X^n_i$

中偏差尺度表示： $\tilde{V}^n(t) = \tilde{V}^n(0) + \tilde{R}^n_X(t) - \bar{V}^* \tilde{R}^n_\Theta(t) - \int^t_0 \theta \tilde{V}^n(s)ds + \sqrt{n}(\mu_n - \mu)t + \tilde{\epsilon}^{n}_{1,V}(t) + \tilde{\epsilon}^{n}_{2,V}(t) + \tilde{\epsilon}^{n}_{3,V}(t)$

其中$\tilde{R}^n_X$, $\tilde{R}^n_\Theta$是中偏差尺度的随机游走。

关键技术步骤：

1. 指数界（引理4.5）：证明流体尺度过程的指数随机有界性
2. 误差项分析（引理4.6）：使用鞅技术证明$\tilde{\epsilon}^{n}_{2,V}$的指数紧性
3. 指数紧性（定理4.7）：组合所有项证明$\{\tilde{V}^n\}$的指数紧性
4. 指数等价（引理4.9）：证明误差项与零过程指数等价

等待时间过程的MDP（第5节）

中偏差尺度表示： $\tilde{W}^n(t) = \tilde{W}^n(0) + \tilde{R}^n_X(t) - \bar{W}^* \tilde{R}^n_\Theta(t) - \int^t_0 \theta \tilde{W}^n(s)ds + \sqrt{n}(\mu_n - \mu)t + \tilde{\epsilon}^{n}_{1}(t) + \tilde{\epsilon}^{n}_{2}(t) + \tilde{\epsilon}^{n}_{3}(t) + \tilde{L}^n(t)$

关键创新：

1. 辅助系统界（引理5.1-5.2）：通过构造上下界系统控制$W^n$
2. 反射项分析：
   • 正中心化（$\bar{W}^* > 0$）：$\tilde{L}^n \xrightarrow{P^{1/b^2_n}} 0$（反射不激活）
   • 零中心化（$\bar{W}^* = 0$）：$\tilde{L}^n$作为Skorokhod映射的调节过程

速率函数的显式形式（定理2.6）

正中心化情形（$\mu > 0, \theta > 0, \bar{W}^* = \mu/\theta$）： $I(\phi) = \frac{\theta^2}{2(\theta^2\sigma^2_X + \mu^2\sigma^2_\Theta)} \int^T_0 (\dot{\phi}(t) - r + \theta\phi(t))^2 dt$

对$\phi \in AC$且$\phi(0) = w_0$。

零中心化情形（$\mu = 0, \theta \geq 0, \bar{W}^* = 0$）： $I(\phi) = \int^T_0 \mathbb{1}_{\{\phi(t) > 0\}} \frac{1}{2\sigma^2_X}(\dot{\phi}(t) - r + \theta\phi(t))^2 dt + \frac{1}{2\sigma^2_X}r^2 \int^T_0 \mathbb{1}_{\{\phi(t)=0\}} \mathbb{1}_{\{r > 0\}} dt$

对非负$\phi \in AC$且$\phi(0) = w_0$。

技术创新点

1. 直接的样本路径方法

与Dupuis and Johnson (2015)的弱收敛方法不同，本文：

• 直接在$D_T$空间工作
• 通过有限维分布的MDP和指数紧性建立结果
• 应用收缩原理（contraction principle）

2. 鞅技术的创新应用

对误差项$\tilde{\epsilon}^{n}_{2}$（引理4.6）：

• 构造鞅：$Z^n_k = \sum^k_{i=0} (\theta - \Theta_i)(\bar{V}^n_i - \bar{V}^*)$
• 证明超鞅性质：$\zeta^n_k = \exp\{\frac{b_n}{\sqrt{n}}Z^n_k - \frac{b^2_n}{n}K^2_\alpha \sigma^2_\Theta k\}$
• 应用Doob不等式获得指数界

3. 系统性的指数等价性论证

建立递进式论证链（引理4.5 → 4.6 → 定理4.7 → 推论4.8 → 引理4.9）：

• 每一步建立更强的结果
• 利用前一步的结论简化后续证明
• 最终证明所有误差项与零过程指数等价

4. 辅助系统界技术

通过构造过程$\Upsilon^n$（引理5.1）： $\Upsilon^n_i = \max\{0, X^n_{i-1}, X^n_{i-1} + C^n_{i-1}X^n_{i-2}, \ldots, X^n_{i-1} + \cdots + C^n_1 X^n_0 + C^n_{i-1}\cdots C^n_0 W^n_0\}$

证明$0 \leq W^n_i \leq \Upsilon^n_i$，然后将$\Upsilon^n$与独立构造的线性递归系统联系。

5. C-指数紧性的刻画

在附录C中系统整理了：

• 指数紧性的充要条件（定理C.6, C.7）
• 连续映射下的保持性（引理C.8）
• 超指数收敛的刻画（引理C.9, C.10）
• 随机时间变换定理（定理C.11）

实验设置

注：本文是纯理论数学论文，不包含数值实验或仿真。所有结果都是严格的数学定理及其证明。

理论验证框架

论文通过以下方式验证理论的合理性：

1. 与已知结果的一致性：
   • 当$C^n_i = 1 - \alpha/n$（确定性）时，恢复Boxma et al. (2016)的结果
   • 扩散极限（附录B）与Whitt (1990)的稳态分布近似一致（Remark B.4）
2. 极端情形检验：
   • $\mu < 0$时证明$\tilde{W}^n \xrightarrow{P^{1/b^2_n}} 0$（系统稳定性极强）
   • 不同参数区域的流体极限行为符合直觉（图1-3）
3. 内在一致性：
   • MDP速率函数与扩散极限的协方差结构一致
   • 零中心化和正中心化的速率函数形式差异反映了反射映射的作用

实验结果

主要理论结果

定理2.5（主要MDP结果）： 在假设2.1和2.3下，$\{\tilde{W}^n, n \in \mathbb{N}\}$满足$D_T$中速率为$b^2_n$的MDP，速率函数为：

1. 正中心化（$\mu > 0, \theta > 0, \bar{W}^* = \mu/\theta$）： $I(\phi) = \inf_{\psi_1, \psi_2 \in D_T, \phi = M_\theta(w_0 + \psi_1 - \frac{\mu}{\theta}\psi_2 + re)} [I_X(\psi_1) + I_\Theta(\psi_2)]$
2. 零中心化（$\mu = 0, \theta \geq 0, \bar{W}^* = 0$）： $I(\phi) = \inf_{\psi_1 \in D_T, \phi = R_\theta(w_0 + \psi_1 + re)} I_X(\psi_1)$

其中$I_X(\psi) = \frac{1}{2\sigma^2_X}\int^T_0 |\dot{\psi}(t)|^2 dt$对$\psi \in AC_0$，否则为$\infty$。

定理2.6（显式速率函数）： 优化问题可显式求解（见上文"速率函数的显式形式"）。

流体极限行为（第3节）

定理3.2：$\bar{W}^n \to \bar{W}$ u.o.c. in probability，其中$\bar{W} = R_\theta(\bar{w}_0 + \mu e)$。

不同参数区域的稳定性（表1）：

• 过载+强状态依赖（$\mu > 0, \theta > 0$）：稳定于正值$\mu/\theta$
• 临界负载+非负状态依赖（$\mu = 0, \theta \geq 0$）：稳定于0
• 欠载（$\mu < 0$）：稳定于0（任意$\theta$）
• 不稳定情形：$\mu > 0, \theta \leq 0$或$\mu = 0, \theta < 0$

辅助结果

定理4.3-4.4（线性递归系统的MDP）： 为无反射系统$V^n$建立MDP，速率函数形式类似但不涉及反射映射。

定理B.3（泛函中心极限定理）： 在附录B中证明：

• 正中心化：$\hat{W}^n \Rightarrow \hat{W} = M_\theta(\hat{W}_0 + \eta e + \sqrt{\sigma^2_X + \frac{\mu^2}{\theta^2}\sigma^2_\Theta}B)$（OU过程）
• 零中心化：$\hat{W}^n \Rightarrow \hat{W} = R_\theta(\hat{W}_0 + \eta e + \sigma_X B)$（反射OU过程）

其中$\hat{W}^n(t) = \sqrt{n}(\bar{W}^n(t) - \bar{W}^*)$（扩散尺度）。

关键引理

1. 引理3.1：误差项$\bar{\epsilon}^{n}_{1}, \bar{\epsilon}^{n}_{2} \to 0$ u.o.c. in probability
2. 引理4.5：$\lim_{K \to \infty} \limsup_{n \to \infty} \frac{1}{b^2_n} \log P(\|\bar{V}^n\|_T > K) = -\infty$
3. 引理4.6：$\{\tilde{\epsilon}^{n}_{2,V}\}$在$D_T$中指数紧
4. 引理5.2：$\lim_{K \to \infty} \limsup_{n \to \infty} \frac{1}{b^2_n} \log P(\|\bar{W}^n\|_T > K) = -\infty$

相关工作

等待时间依赖排队系统

• 早期工作：Harris (1967), Callahan (1973), Brill (1988)研究了基本模型
• 近期进展：
  • Boxma and Vlasiou (2007)：$C_i \in \{-1, 1\}$ Bernoulli情形
  • Boxma et al. (2016)：确定性$C_i$的反射AR(1)过程，FCLT
  • Boxma et al. (2021), Huang (2023), Dimitriou and Fiems (2024)：更一般的$C_i$形式
  • Vlasiou and Palmowski (2014)：稳态分布尾概率的大偏差

本文贡献：首个样本路径MDP结果，填补了极限定理谱系中的空白。

大偏差和中偏差理论

• 样本路径LDP：
  • Bazhba et al. (2025)：常规Lindley递归（$C_i = 1$）的次线性速率LDP
  • Chen et al. (2024)：重尾仿射递归的LDP
• 样本路径MDP：
  • Puhalskii (1999)：GI/GI/1队列
  • Chang et al. (1999)：长程相依输入的随机流体队列
  • Anugu and Pang (2024a)：时变服务时间的无穷服务器队列
  • Feng et al. (2025)：GI/GI/1+GI队列

本文定位：扩展MDP理论到状态依赖排队系统。

Vervaat永续性（Vervaat Perpetuity）

无反射递归$V^n_{i+1} = C^n_i V^n_i + X^n_i$在文献中被称为Vervaat永续性：

• Kesten (1973), Brandt (1986), Embrechts and Goldie (1994)：稳态分布理论
• Vervaat (1979), Whitt (1990)：泛函极限定理
• Chen et al. (2024)：重尾情形的LDP

本文贡献：为此类过程建立MDP（第4节），作为分析反射过程的中间步骤。

递归Markov系统的MDP

• Dupuis and Johnson (2015)：通过变分公式的弱收敛方法，允许某些非线性递归
  • 区别：本文开发直接方法，显式处理反射项，在$D_T$空间工作

结论与讨论

主要结论

1. 理论完备性：为等待时间依赖排队系统建立了完整的极限定理框架（流体极限、扩散极限、中偏差原理）
2. 速率函数的二分性：
   • 正平衡点：速率函数形式简洁，不涉及反射
   • 零平衡点：速率函数涉及Skorokhod反射映射，更复杂
3. 方法论贡献：开发的技术（鞅方法、指数紧性论证、辅助系统界）可应用于更广泛的反射随机过程
4. 参数敏感性：系统行为对名义负载$\mu$和状态依赖强度$\theta$高度敏感（表1总结）

局限性

1. 模型假设：
   • 要求线性依赖关系（实际系统可能非线性）
   • 特定的尺度选择$C^n_i = 1 - \Theta_i/n$（虽然与已有文献一致）
   • 独立性假设（$\Theta_i$与$X^n_i$独立）可能过强
2. 稳定性限制：仅分析稳定平衡点情形，不稳定情形（如$\mu > 0, \theta < 0$）未涉及
3. 单服务器限制：方法未扩展到多服务器或网络系统
4. 技术条件：
   • 需要矩生成函数存在（Assumption 2.3(ii)）
   • 初始条件的收敛速率要求（Assumption 2.3(i)）
5. 数值验证缺失：作为纯理论工作，未提供数值例子或仿真验证

未来方向

论文提出的潜在扩展：

1. 非线性依赖：扩展到非线性状态依赖$A'_i = A_i + f(W_i)$
2. 多服务器系统：分析Halfin-Whitt体制下的状态依赖多服务器队列
3. 网络系统：扩展到Jackson网络或更一般的排队网络
4. 重尾分布：研究$X^n_i$或$\Theta_i$具有重尾分布的情形
5. 时变参数：考虑$\mu_n(t)$, $\theta_n(t)$随时间变化
6. 优化应用：利用MDP结果进行稀有事件模拟和风险管理

深度评价

优点

1. 理论严谨性

• 证明完整：所有定理都有详细证明，技术细节充分
• 逻辑清晰：从流体分析到辅助系统再到主要结果，层次分明
• 附录丰富：附录A-C提供了必要的背景和技术引理

2. 方法创新

• 直接样本路径方法：相比弱收敛方法更直观，更适合处理反射
• 鞅技术的巧妙应用：在证明指数消失性时的鞅构造富有创造性
• 系统性框架：建立的指数紧性论证框架具有普适性

3. 结果显式性

• 速率函数完全显式（定理2.6），便于进一步分析和应用
• 流体极限行为完全刻画（表1），涵盖所有参数区域

4. 写作质量

• 结构清晰：引言充分动机，主体逻辑严密，附录支撑有力
• 符号规范：符号使用一致（如$\bar{x}^n$表示流体尺度，$\tilde{x}^n$表示中偏差尺度）
• 文献综述全面：充分讨论了与相关工作的联系和区别

不足

1. 实用性限制

• 无数值验证：缺乏数值例子说明理论结果的实际意义
• 应用讨论不足：未讨论如何利用MDP结果进行实际系统分析或设计
• 参数估计问题：未涉及如何从数据估计$\theta$, $\sigma^2_\Theta$等参数

2. 技术假设

• 矩生成函数条件（Assumption 2.3(ii)）排除了重尾分布，限制了应用范围
• 尺度选择的唯一性：未充分讨论为何$C^n_i = 1 - \Theta_i/n$是"自然"的选择

3. 覆盖范围

• 不稳定情形缺失：$\mu > 0, \theta \leq 0$等不稳定情形未分析
• 瞬态行为：主要关注渐近行为，有限$n$的近似质量未讨论

4. 可读性

• 技术密度高：对非专家读者，证明细节可能难以跟随
• 直觉解释不足：某些技术步骤（如辅助系统$\Upsilon^n$的构造）缺乏直观解释

影响力

对领域的贡献

1. 填补理论空白：首次为状态依赖排队建立MDP，完善了该领域的极限定理体系
2. 方法论价值：开发的技术可应用于其他反射随机过程的分析
3. 桥梁作用：连接了排队理论、大偏差理论和随机过程理论

实用价值

1. 风险评估：MDP提供了比大偏差更精细的稀有事件概率估计
2. 系统设计：速率函数可用于优化系统参数以控制偏离概率
3. 仿真加速：MDP结果可指导重要性采样等方差缩减技术

可复现性

• 理论结果：定理陈述清晰，假设明确，原则上可验证
• 证明技术：步骤详细，引用充分，可作为学习MDP技术的范例
• 代码缺失：未提供数值实现代码（虽然作为纯理论工作这是可接受的）

适用场景

1. 直接应用

• 医疗系统：急诊室、ICU等拥塞敏感的医疗服务系统
• 呼叫中心：等待时间影响后续到达和服务速度的场景
• 计算机系统：负载依赖的任务调度和服务

2. 理论扩展

• 多服务器队列：方法可能扩展到$M/M/c$型状态依赖系统
• 排队网络：作为分析复杂网络的构建模块
• 金融数学：类似递归结构出现在某些金融模型中

3. 方法借鉴

• 反射扩散过程：鞅技术和指数紧性论证可用于其他反射过程
• 状态依赖系统：辅助系统界的方法具有普适性
• 中偏差理论：为其他随机系统的MDP分析提供范例

后续研究建议

1. 数值研究：通过仿真验证理论预测，探索有限$n$的收敛速度
2. 参数敏感性分析：系统研究速率函数对$\theta$, $\sigma^2_X$等参数的依赖
3. 重尾扩展：研究Assumption 2.3(ii)能否放松
4. 应用案例：选择具体应用场景（如急诊室数据）验证模型
5. 计算方法：开发计算速率函数和最优路径的数值算法

参考文献（精选）

1. Whitt, W. (1990). Queues with service times and interarrival times depending linearly and randomly upon waiting times. Queueing Systems, 6:335-351.
   • 本文扩展的经典工作
2. Boxma, O., Mandjes, M., and Reed, J. (2016). On a class of reflected AR(1) processes. Journal of Applied Probability, 53(3):818-832.
   • 确定性状态依赖的FCLT结果
3. Dupuis, P. and Johnson, D. (2015). Moderate Deviations for Recursive Stochastic Algorithms. Stochastic Systems, 5(1):87-119.
   • 相关的MDP方法（弱收敛途径）
4. Puhalskii, A. A. (1999). Moderate deviations for queues in critical loading. Queueing Systems, 31(3):359-392.
   • GI/GI/1队列的MDP经典工作
5. Chen, B., Rhee, C.-H., and Zwart, B. (2024). Sample-path large deviations for a class of heavy-tailed Markov additive processes. Electron. J. Probab., 29(1):1-44.
   • 重尾递归系统的LDP

总体评价：这是一篇高质量的理论数学论文，严谨地建立了等待时间依赖排队系统的样本路径中偏差原理，填补了该领域的重要理论空白。方法创新，结果显式，证明完整。主要不足在于缺乏数值验证和应用讨论，以及某些技术假设的限制性。对排队理论、大偏差理论和随机过程理论的研究者具有重要参考价值，也为实际系统的风险分析提供了理论工具。建议未来工作补充数值研究并探索实际应用。