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

Basic Information

• Paper ID: 2510.27226
• Title: Sample Path Moderate Deviation Principle for Queues with Waiting-time Dependent Interarrival and Service Times
• Authors: Chang Feng (University of Texas at Austin), John J. Hasenbein (University of Texas at Austin), Guodong Pang (Rice University)
• Classification: math.PR (Probability Theory)
• Publication Date: November 3, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.27226v1

Abstract

This paper studies single-server queueing systems where interarrival times and service times depend linearly and randomly on customer waiting times. The authors establish a sample path moderate deviation principle (MDP) for the waiting time process. The waiting time can be expressed as a modified Lindley recursion with random weight coefficients. Under natural scaling of the random coefficients, the authors analyze the fluid behavior of the workload process, deriving stable equilibrium points (which can be zero or positive). The centered moderate deviation scale processes around stable equilibrium points are then represented as linear stochastic differential equations driven by two random walks, plus asymptotically negligible error terms and possible reflection at zero. The rate functions for MDP in both cases can be characterized explicitly, with the distinction that the zero-centered case involves a linear generalized Skorokhod reflection mapping, while the positive-centered case does not.

Research Background and Motivation

Problem Statement

In real queueing systems, arrival processes and service times often depend on system congestion or delay states:

• Healthcare Systems: Emergency departments become overcrowded when patients balk; intensive care units may accelerate patient throughput when overloaded
• Other Applications: Similar load-dependent behaviors exist in biological systems, manufacturing, inventory management, computer networks, and insurance

Significance

1. Theoretical Importance: Extends classical queueing theory to state-dependent systems, filling a gap in moderate deviation theory for such models
2. Practical Value: Provides theoretical tools for understanding rare events in congested systems, aiding risk assessment and system design
3. Methodological Contribution: Develops new techniques for analyzing reflected autoregressive processes with random coefficients

Limitations of Existing Methods

• Distribution Analysis Dominance: Existing research primarily focuses on stationary distributions and transform methods (Boxma et al. 2007, 2016, 2021)
• Limited Sample Path Results:
  • Whitt (1990)'s functional central limit theorem does not provide explicit forms of limiting diffusion processes
  • Large deviation principles established only in special cases (Vlasiou and Palmowski 2014)
  • Moderate Deviation Principle Completely Missing: This is the key gap filled by this paper

Research Motivation

1. Establish the first sample path moderate deviation principle for waiting-time dependent queueing systems
2. Provide refined probability approximations between large deviations and central limit theorem
3. Develop analysis techniques applicable to broader classes of reflected AR(1) processes

Core Contributions

1. First MDP Result: Establishes sample path moderate deviation principle for waiting-time dependent queueing systems, filling a theoretical gap in the field
2. Complete Fluid Analysis:
   • Systematically analyzes fluid limit behavior across different parameter regions (overloaded/critically loaded/underloaded, varying state dependence intensities)
   • Identifies all stable equilibrium points (zero or positive), summarized in Table 1
3. Explicit Rate Functions: Derives explicitly computable rate functions for both centered cases (Theorem 2.6):
   • Zero-centered: involves linear generalized Skorokhod reflection mapping
   • Positive-centered: no reflection involved, simpler rate function form
4. Novel Proof Techniques:
   • Develops MDP analysis methods for linear recursive Markov chains (Section 4)
   • Innovatively uses martingale techniques to prove exponential vanishing of error terms
   • Establishes systematic framework for exponential tightness and exponential equivalence arguments
5. Supplementary Diffusion Approximation: Proves functional central limit theorem in Appendix B with limits being OU or reflected OU processes, supplementing Whitt (1990)'s work

Methodology Details

Problem Setup

Consider a sequence of single-server FIFO queueing systems (indexed by n):

• Input: i.i.d. random vector sequences $\{(A^n_i, S^n_i, \mathcal{A}^n_i, \mathcal{B}^n_i), i \in \mathbb{N}_0\}$
• State Dependence Mechanism:
  • Actual interarrival time: $A'^{n}_i = A^n_i + \mathcal{A}^n_i W^n_i$
  • Actual service time: $S'^{n}_i = S^n_i + \mathcal{B}^n_i W^n_i$
• Objective: Establish sample path MDP for the moderate deviation scaled waiting time process $\tilde{W}^n(t) = \frac{\sqrt{n}}{b_n}(\bar{W}^n(t) - \bar{W}^*)$

Where:

• $b_n \to \infty$, $b_n/\sqrt{n} \to 0$ (moderate deviation scaling)
• $\bar{W}^n(t) = \frac{1}{n}W^n_{\lfloor nt \rfloor}$ (fluid scaling)
• $\bar{W}^*$ is the stable equilibrium point of the fluid limit

Core Recursive Structure

Modified Lindley Recursion: $W^n_{i+1} = (C^n_i W^n_i + X^n_i)^+$

Where:

• $X^n_i = S^n_i - A^n_i$ (nominal increment)
• $C^n_i = 1 + \mathcal{B}^n_i - \mathcal{A}^n_i$ (random weight coefficient)

Key Scaling Assumption (Assumption 2.1): $C^n_i = 1 - \frac{1}{n}\Theta_i$

Where $\{\Theta_i\}$ is an i.i.d. sequence with mean $\theta$ and variance $\sigma^2_\Theta$. This scaling choice ensures:

• For large $n$, $(C_i)^{1/n} \approx e^{-\Theta_i/n} \approx 1 - \Theta_i/n$
• Compatibility with scaling in Whitt (1990) and Boxma et al. (2016)

Fluid Analysis (Section 3)

Through telescoping summation and introducing error terms, obtain the fluid-scaled representation: $\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}$

Fluid Limit (Theorem 3.2): $\bar{W} = R_\theta(\bar{w}_0 + \mu e)$

Where $R_\theta$ is the linear generalized Skorokhod reflection mapping, satisfying the differential form: $d\bar{W}(t) = \mu - \theta\bar{W}(t) + d\bar{L}(t)$

Stable Equilibrium Point Analysis (Table 1 Summary):

MDP for Linear Recursive Markov Chains (Section 4)

To handle the auxiliary system without reflection: $V^n_{i+1} = C^n_i V^n_i + X^n_i$

Moderate Deviation Scaled Representation: $\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)$

Where $\tilde{R}^n_X$, $\tilde{R}^n_\Theta$ are moderate deviation scaled random walks.

Key Technical Steps:

1. Exponential Bounds (Lemma 4.5): Prove exponential random boundedness of fluid-scaled processes
2. Error Term Analysis (Lemma 4.6): Use martingale techniques to prove exponential tightness of $\tilde{\epsilon}^{n}_{2,V}$
3. Exponential Tightness (Theorem 4.7): Combine all terms to prove exponential tightness of $\{\tilde{V}^n\}$
4. Exponential Equivalence (Lemma 4.9): Prove error terms are exponentially equivalent to zero process

MDP for Waiting Time Process (Section 5)

Moderate Deviation Scaled Representation: $\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)$

Key Innovations:

1. Auxiliary System Bounds (Lemmas 5.1-5.2): Control $W^n$ through constructed upper and lower bound systems
2. Reflection Term Analysis:
   • Positive-centered ($\bar{W}^* > 0$): $\tilde{L}^n \xrightarrow{P^{1/b^2_n}} 0$ (reflection inactive)
   • Zero-centered ($\bar{W}^* = 0$): $\tilde{L}^n$ serves as the regulating process of Skorokhod mapping

Explicit Form of Rate Functions (Theorem 2.6)

Positive-Centered Case ($\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$

For $\phi \in AC$ with $\phi(0) = w_0$.

Zero-Centered Case ($\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$

For non-negative $\phi \in AC$ with $\phi(0) = w_0$.

Technical Innovations

1. Direct Sample Path Method

Unlike Dupuis and Johnson (2015)'s weak convergence approach, this paper:

• Works directly in $D_T$ space
• Establishes results through finite-dimensional MDP and exponential tightness
• Applies contraction principle

2. Innovative Application of Martingale Techniques

For error term $\tilde{\epsilon}^{n}_{2}$ (Lemma 4.6):

• Construct martingale: $Z^n_k = \sum^k_{i=0} (\theta - \Theta_i)(\bar{V}^n_i - \bar{V}^*)$
• Prove supermartingale property: $\zeta^n_k = \exp\{\frac{b_n}{\sqrt{n}}Z^n_k - \frac{b^2_n}{n}K^2_\alpha \sigma^2_\Theta k\}$
• Apply Doob's inequality to obtain exponential bounds

3. Systematic Exponential Equivalence Argument

Establish progressive argument chain (Lemma 4.5 → 4.6 → Theorem 4.7 → Corollary 4.8 → Lemma 4.9):

• Each step establishes stronger results
• Utilize conclusions from previous steps to simplify subsequent proofs
• Finally prove all error terms exponentially equivalent to zero process

4. Auxiliary System Bound Technique

Through constructing process $\Upsilon^n$ (Lemma 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\}$

Prove $0 \leq W^n_i \leq \Upsilon^n_i$, then connect $\Upsilon^n$ with independently constructed linear recursive systems.

5. Characterization of C-Exponential Tightness

Systematically organize in Appendix C:

• Necessary and sufficient conditions for exponential tightness (Theorems C.6, C.7)
• Preservation under continuous mappings (Lemma C.8)
• Characterization of super-exponential convergence (Lemmas C.9, C.10)
• Random time change theorem (Theorem C.11)

Experimental Setup

Note: This is a pure theoretical mathematics paper with no numerical experiments or simulations. All results are rigorous mathematical theorems and their proofs.

Theoretical Verification Framework

The paper validates theoretical reasonableness through:

1. Consistency with Known Results:
   • When $C^n_i = 1 - \alpha/n$ (deterministic), recovers results from Boxma et al. (2016)
   • Diffusion limit (Appendix B) consistent with Whitt (1990)'s stationary distribution approximation (Remark B.4)
2. Extreme Case Verification:
   • When $\mu < 0$, proves $\tilde{W}^n \xrightarrow{P^{1/b^2_n}} 0$ (very strong system stability)
   • Fluid limit behavior in different parameter regions matches intuition (Figures 1-3)
3. Internal Consistency:
   • MDP rate function consistent with diffusion limit covariance structure
   • Difference in rate function forms between zero-centered and positive-centered cases reflects role of reflection mapping

Experimental Results

Main Theoretical Results

Theorem 2.5 (Main MDP Result): Under Assumptions 2.1 and 2.3, $\{\tilde{W}^n, n \in \mathbb{N}\}$ satisfies MDP in $D_T$ with rate $b^2_n$ and rate function:

1. Positive-Centered ($\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. Zero-Centered ($\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)$

Where $I_X(\psi) = \frac{1}{2\sigma^2_X}\int^T_0 |\dot{\psi}(t)|^2 dt$ for $\psi \in AC_0$, otherwise $\infty$.

Theorem 2.6 (Explicit Rate Functions): Optimization problems can be solved explicitly (see "Explicit Form of Rate Functions" above).

Fluid Limit Behavior (Section 3)

Theorem 3.2: $\bar{W}^n \to \bar{W}$ u.o.c. in probability, where $\bar{W} = R_\theta(\bar{w}_0 + \mu e)$.

Stability in Different Parameter Regions (Table 1):

• Overloaded + Strong State Dependence ($\mu > 0, \theta > 0$): Stable at positive value $\mu/\theta$
• Critically Loaded + Non-negative State Dependence ($\mu = 0, \theta \geq 0$): Stable at 0
• Underloaded ($\mu < 0$): Stable at 0 (arbitrary $\theta$)
• Unstable Cases: $\mu > 0, \theta \leq 0$ or $\mu = 0, \theta < 0$

Auxiliary Results

Theorems 4.3-4.4 (MDP for Linear Recursive Systems): Establish MDP for reflection-free system $V^n$, with rate function form similar but without reflection mapping.

Theorem B.3 (Functional Central Limit Theorem): Proved in Appendix B:

• Positive-Centered: $\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 process)
• Zero-Centered: $\hat{W}^n \Rightarrow \hat{W} = R_\theta(\hat{W}_0 + \eta e + \sigma_X B)$ (reflected OU process)

Where $\hat{W}^n(t) = \sqrt{n}(\bar{W}^n(t) - \bar{W}^*)$ (diffusion scaling).

Key Lemmas

1. Lemma 3.1: Error terms $\bar{\epsilon}^{n}_{1}, \bar{\epsilon}^{n}_{2} \to 0$ u.o.c. in probability
2. Lemma 4.5: $\lim_{K \to \infty} \limsup_{n \to \infty} \frac{1}{b^2_n} \log P(\|\bar{V}^n\|_T > K) = -\infty$
3. Lemma 4.6: $\{\tilde{\epsilon}^{n}_{2,V}\}$ is exponentially tight in $D_T$
4. Lemma 5.2: $\lim_{K \to \infty} \limsup_{n \to \infty} \frac{1}{b^2_n} \log P(\|\bar{W}^n\|_T > K) = -\infty$

Related Work

Waiting-Time Dependent Queueing Systems

• Early Work: Harris (1967), Callahan (1973), Brill (1988) studied basic models
• Recent Progress:
  • Boxma and Vlasiou (2007): Bernoulli case with $C_i \in \{-1, 1\}$
  • Boxma et al. (2016): Deterministic $C_i$ reflected AR(1) process, FCLT
  • Boxma et al. (2021), Huang (2023), Dimitriou and Fiems (2024): More general $C_i$ forms
  • Vlasiou and Palmowski (2014): Large deviation tail probabilities of stationary distribution

This Paper's Contribution: First sample path MDP result, filling gap in limit theorem spectrum.

Large and Moderate Deviation Theory

• Sample Path LDP:
  • Bazhba et al. (2025): Sublinear rate LDP for standard Lindley recursion ($C_i = 1$)
  • Chen et al. (2024): LDP for heavy-tailed affine recursion
• Sample Path MDP:
  • Puhalskii (1999): GI/GI/1 queues
  • Chang et al. (1999): Stochastic fluid queues with long-range dependent input
  • Anugu and Pang (2024a): Infinite-server queues with time-varying service times
  • Feng et al. (2025): GI/GI/1+GI queues

This Paper's Position: Extends MDP theory to state-dependent queueing systems.

Vervaat Perpetuity

The reflection-free recursion $V^n_{i+1} = C^n_i V^n_i + X^n_i$ is called Vervaat perpetuity in literature:

• Kesten (1973), Brandt (1986), Embrechts and Goldie (1994): Stationary distribution theory
• Vervaat (1979), Whitt (1990): Functional limit theorems
• Chen et al. (2024): LDP for heavy-tailed case

This Paper's Contribution: Establishes MDP for such processes (Section 4), serving as intermediate step for analyzing reflected processes.

MDP for Recursive Markov Systems

• Dupuis and Johnson (2015): Weak convergence method via variational formulas, allowing certain nonlinear recursions
  • Distinction: This paper develops direct method, explicitly handles reflection terms, works in $D_T$ space

Conclusions and Discussion

Main Conclusions

1. Theoretical Completeness: Establishes complete limit theorem framework for waiting-time dependent queueing systems (fluid limit, diffusion limit, moderate deviation principle)
2. Dichotomy of Rate Functions:
   • Positive equilibrium point: Simple rate function form, no reflection involved
   • Zero equilibrium point: Rate function involves Skorokhod reflection mapping, more complex
3. Methodological Contribution: Developed techniques (martingale methods, exponential tightness arguments, auxiliary system bounds) applicable to broader classes of reflected stochastic processes
4. Parameter Sensitivity: System behavior highly sensitive to nominal load $\mu$ and state dependence intensity $\theta$ (summarized in Table 1)

Limitations

1. Model Assumptions:
   • Requires linear dependence relationships (real systems may be nonlinear)
   • Specific scaling choice $C^n_i = 1 - \Theta_i/n$ (though consistent with existing literature)
   • Independence assumption ($\Theta_i$ independent of $X^n_i$) may be too strong
2. Stability Restrictions: Only analyzes stable equilibrium point cases; unstable cases (e.g., $\mu > 0, \theta < 0$) not covered
3. Single-Server Limitation: Methods not extended to multi-server or network systems
4. Technical Conditions:
   • Requires moment generating function existence (Assumption 2.3(ii))
   • Convergence rate requirements for initial conditions (Assumption 2.3(i))
5. Missing Numerical Verification: As pure theoretical work, no numerical examples or simulation verification provided

Future Directions

Potential Extensions Suggested by Paper:

1. Nonlinear Dependence: Extend to nonlinear state dependence $A'_i = A_i + f(W_i)$
2. Multi-Server Systems: Analyze state-dependent multi-server queues in Halfin-Whitt regime
3. Network Systems: Extend to Jackson networks or more general queueing networks
4. Heavy-Tailed Distributions: Study cases where $X^n_i$ or $\Theta_i$ have heavy-tailed distributions
5. Time-Varying Parameters: Consider $\mu_n(t)$, $\theta_n(t)$ varying over time
6. Optimization Applications: Utilize MDP results for rare event simulation and risk management

Selected References

1. Whitt, W. (1990). Queues with service times and interarrival times depending linearly and randomly upon waiting times. Queueing Systems, 6:335-351.
   • Classical work extended by this paper
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 results for deterministic state dependence
3. Dupuis, P. and Johnson, D. (2015). Moderate Deviations for Recursive Stochastic Algorithms. Stochastic Systems, 5(1):87-119.
   • Related MDP method (weak convergence approach)
4. Puhalskii, A. A. (1999). Moderate deviations for queues in critical loading. Queueing Systems, 31(3):359-392.
   • Classical MDP work for GI/GI/1 queues
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 for heavy-tailed recursive systems

Overall Assessment: This is a high-quality theoretical mathematics paper that rigorously establishes sample path moderate deviation principle for waiting-time dependent queueing systems, filling an important theoretical gap in the field. The methods are innovative, results are explicit, and proofs are complete. Main limitations are lack of numerical verification and application discussion, along with restrictiveness of certain technical assumptions. Valuable reference for researchers in queueing theory, large deviation theory, and stochastic processes, and provides theoretical tools for practical system risk analysis. Recommend future work supplement with numerical studies and explore practical applications.