Moderate deviations of many–server queues, idempotent processes and quasipotentials
Anatolii A. Puhalskii · 2025
Read Moderate deviations of many–server queues, idempotent processes and quasipotentials by Anatolii A. Puhalskii (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-20494.txt.
Introduction
Anatolii Puhalskii proves a large deviation principle for service systems, in a 2025 paper. The setting is a many-server queue in heavy traffic, under moderate deviation scaling akin to the Halfin-Whitt regime, where server numbers grow with demand. Arrival and service times may follow general distributions, not just exponential ones. The question is how unlikely backlogs build, and at what exact exponential rate the stationary queue length strays from its norm.
The answer comes from a quasipotential, a cost function borrowed from physics, tied to the long-run idempotent distribution of the queue's large deviation limit process. New trajectory-level results for that process support the proof, which uses exponential tightness and idempotent probability methods. A side result bounds the higher moments of counting renewal processes. The work sharpens the mathematics of rare-event risk in call centers, hospitals, and server farms.
Catalog record
| CREATOR | Anatolii A. Puhalskii |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-20494
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Moderate deviations of many–server queues, idempotent processes and quasipotentials Anatolii A. Puhalskii Abstract A Large Deviation Principle (LDP) is established for the stationary distribution of the number of customers in a many–server queue in heavy traffic for a moderate deviation scaling akin to the Halfin–Whitt regime. The interarrival and service times are assumed generally distributed. The deviation function is given by a quasipotential. It is related to the longterm idempotent distribution of the large deviation limit of the number-in-the-system process. New results on the trajectorial LDP for that process are also obtained. Proofs rely on the characterisation of large deviation relatively compact sequences as exponentially tight ones and use methods of weak convergence and idempotent processes. Another contribution of the paper concerns bounds on the higher–order moments of counting renewal processes. 1 Introduction The analysis of many–server queues with generally distributed interarrival and service times is challenging. In order to gain insight, various asymptotics have been explored, see, e.g., Borovkov [ 8 , 9 ] , Iglehart [ 18 , 19 ] and Whitt [ 46 ] . Of particular interest is the heavy–traffic asymptotic regime introduced in Halfin and Whitt [ 17 ] where the service time distribution is held fixed, whereas the number of servers, n , and the arrival rate, \lambda_{n} , grow without a bound in such a way that \sqrt{n}(1-\rho_{n})\to\beta\in\mathbb{R}\,, where \rho_{n}=\lambda_{n}/(n\mu) is the traffic intensity, \mu representing the service rate. With Q_{n}(t) denoting the number of customers present at time t , the sequence of processes (Q_{n}(t)-n)/\sqrt{n} , considered as random elements of the associated Skorohod space, under fairly general hypotheses, converges in law to a continuous–path process. In their pioneering contribution, Halfin and Whitt [ 17 ] assumed renewal arrivals and exponentially distributed service times. The limit process then is an Ito diffusion with a piecewise linear drift. In addition, for the case where \beta>0 , the stationary distribution of the centred and normalised number–in–the–system process converges to the stationary distribution of the limit, which has a continuous density with an exponential upper tail and a normal lower tail. The limiting probability of a customer having to await service is strictly between zero and one, which sets the Halfin–Whitt regime apart and renders it useful for producing approximations. An extension of the process–level convergence to the case of generally distributed service times is due to Reed [ 42 ] , see also Puhalskii and Reiman [ 37 ] , Puhalskii and Reed [ 41 ] . The limit process, however, is not easily tractable, being a solution to a nonlinear renewal equation. In an attempt at ”Markovisation”, Kaspi and Ramanan [ 23 ] incorporated elapsed service times into state descriptions and arrived at infinite–dimensional limits. Convergence of the stationary distribution of the Markovised number of customers was addressed in Aghajani and Ramanan [ 1 ] . It was assumed that the service time cdf has a density with certain smoothness and integrability properties. The limit infinite–dimensional distribution is quite involved. Special cases of the convergence of the stationary distribution were treated in Jelenković, Mandelbaum and Momčilović [ 21 ] 1 1 1 Theorem 1 in Jelenković, Mandelbaum and Momčilović [ 21 ] is missing a Lindeberg condition on the interarrival times. , who assumed deterministic service times and in Gamarnik and Momčilović [ 15 ] , who assumed lattice–valued service times of finite support. This paper undertakes a study of moderate deviations of the stationary number of customers. It assumes the heavy–traffic condition \frac{\sqrt{n}}{b_{n}}(1-\rho_{n})\to\beta\,, (1.1) where b_{n}\to\infty and b_{n}/\sqrt{n}\to 0 . The main result is a Large Deviation Principle (LDP) for the stationary distribution of the process X_{n}=(X_{n}(t)\,,t\in\mathbb{R}_{+}) , where X_{n}(t)=(Q_{n}(t)-n)/(b_{n}\sqrt{n}) , provided \beta>0 . Unlike in Aghajani and Ramanan [ 1 ] , no fine properties of the service time cdf are assumed, moment conditions being imposed instead. It is noteworthy that deviation functions, a.k.a. rate functions, a.k.a. action functionals, for moderate deviations may capture exponents in the corresponding weak convergence limits, see Puhalskii [ 32 ] . It has been an established practice to describe large deviation asymptotics of the invariant measures of Markov processes in terms of quasipotentials, which involve trajectorial deviation functions, see Freidlin and Wentzell [ 13 ] , Schwarz and Weiss [ 44 ] . In Puhalskii [ 35 ] it was shown that a similar recipe may work for non–Markov processes that are Markovian ”in the large deviation limit”, the latter meaning that the integrand in the expression for the trajectorial deviation function depends only on the state variable and its derivative. For many–server queues with generally distributed service times, however, not only is the process X_{n} non–Markov but the trajectorial deviation function is essentially ”non–Markov” either in that the integrand depends on the entire past of the trajectory, see Puhalskii [ 36 ] . Notwithstanding, this paper shows that moderate deviations of the stationary distribution of X_{n} are still governed by the associated quasipotential. A standard approach to establishing an LDP for the invariant measures of a Markov process has been to use formulas that relate the invariant measure to the cycle lengths of appropriately chosen Markov chains and verify the bounds in the definition of the LDP, a change of probability measure playing a prominent role, cf. Freidlin and Wentzell [ 13 ] , Schwarz and Weiss [ 44 ] . In Puhalskii [ 30 ] it was proposed to model large deviation theory on weak convergence theory and an analogue of Prohorov’s theorem was proved stating that exponentially tight sequences of probability measures on metric spaces are Large Deviation (LD) relatively compact, see also Puhalskii [ 31 ] . That result opened up a direction of research that attempts to approach the task of proving an LDP by using global relations for the processes involved rather than by directly verifying the bounds in the definition. The idea is to identify the deviation function of an exponentially tight sequence through equations that arise as limits of equations satisfied by the stochastic processes in question, e.g., by taking a limit in a martingale problem, cf. Puhalskii [ 33 , 39 ] . In relation to invariant measures, it was proposed in Puhalskii [ 34 ] to take LD limits in the invariance relations. By definition, an invariant measure can be written as a mixture of transient distributions against the invariant measure itself so that, given a stationary stochastic process \overline{X}_{n}(t) with invariant measure \mu_{n} , for a bounded continuous nonnegative function f on the state space, \int f(x)^{n}\mu_{n}(dx)=\int\int f(x)^{n}P(\overline{X}_{n}(t)\in dx|\overline{X}_{n}(0)=y)\mu_{n}(dy)\,. (1.2) Loosely speaking, if the transient distribution P(\overline{X}_{n}(t)\in dx|\overline{X}_{n}(0)=y) LD converges to certain deviability \Pi_{y,t}(x) (or obeys the LDP with deviation function I_{y,t}(x)=-\ln\Pi_{y,t}(x) for that matter) 2 2 2 A review of the basics of Large Deviation (LD) convergence, which is just a different form of the LDP, and of idempotent processes, can be found in Puhalskii [ 36 , 40 ] and \mu_{n} LD converges to deviability \Pi , then ( 1.2 ) implies that \sup_{x}f(x)\Pi(x)=\sup_{y}\sup_{x}f(x)\Pi_{y,t}(x)\Pi(y)\,. (1.3) If \Pi_{y,t}(x) converges to limit \hat{\Pi}(x) , as t\to\infty , that does not depend on y , then letting t\to\infty in ( 1.3 ) and noting that \sup_{y}\Pi(y)=1 implies, modulo certain technical conditions, that \sup_{x}f(x)\Pi(x)=\sup_{x}f(x)\hat{\Pi}(x) so that