Finite-time Convergence to Stationarity of M/M/n queues: a Lyapunov-Poincaré Approach
1
2
Model
3
Motivations
4
M/M/n behavior
5
Heavy-traffic parameter
M/M/1
M/M/n
M/M/n behavior
6
Phase transition
Halfin, Whitt (1981)
Heavy-traffic parameter
Mean field
Heavy Traffic
Super-HW
Sub-HW
Related works: Finite-time
7
Gamarnik , Goldberg (’13)
Spectral method
| | | |
Roberts (2003)
Hitting time
Zeifman (1991)
Log-norm
Chafai (2006)
Binomial-Poisson
Can we get tight convergence bounds for all regimes using a unifying method?
Main results: All regimes (NVM 2025)
8
Initial distribution
stationary distribution
First convergence to stationarity result for queuing systems in Chi-square distance!
| | | | M/M/1 |
| | | | |
NVM 2025, Zeifman
NVM 2025
NVM 2025
Heavy Traffic
Mean field
- Moment bound
- Tail bound
Proof Framework
9
Proof framework
10
Approach: Lyapunov drift
Generator
Proof framework
11
Step 1: Lyapunov drift
Step 2: Local mixing
Step 3:
Stitching error
Minorization: Rosenthal et al. (1995)
Atom set: Meyn et al. (1996)
Canonical path method: NVM (2025)
Truncation method: NVM (2025)
Proof framework
12
Step 1: Lyapunov drift
Step 2: Local mixing
Step 3:
Step 1: Lyapunov drift
13
Strong
Two-sided drift!
K
M/M/1 |
|
Proof framework
14
Step 1: Lyapunov drift
Step 2: Local mixing
Step 3:
Step 2: Local mixing
15
K
+
Canonical path method
Super-HW regime proof sketch
16
Step 1: Lyapunov drift
Step 2: Local mixing
Step 3:
Summary
17
| | | | M/M/1 |
| | | | |
Unifying Lyapunov-Poincaré method!
Applicable to reversible Markov chains
Takeaway
18
Finite state space
Countable
- Coupling/Coupling from the past
- Conductance
- Spectral Independence
- Evolving sets
- Wilson’s method
- Isoperimetry inequalities
- Eigenvalue method
Lyapunov drift method
Stitching Theorem
Coupling/hitting time method
Log-norm
Spectral method
Thank you for listening!
19
Check out our paper here: