Hostname: page-component-669899f699-chc8l Total loading time: 0 Render date: 2025-04-25T23:09:34.263Z Has data issue: false hasContentIssue false
  • English
  • Français

Moderate deviations of many-server queues via idempotent processes

Part of: Special processes Limit theorems

Published online by Cambridge University Press:  20 December 2024

Anatolii Puhalskii
Anatolii Puhalskii*
Affiliation:
Institute for Problems in Information Transmission (IITP)
*
*Postal address: 19 B. Karetny, Moscow, Russia, 127051. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper obtains logarithmic asymptotics of moderate deviations of the stochastic process of the number of customers in a many-server queue with generally distributed inter-arrival and service times under a heavy-traffic scaling akin to the Halfin–Whitt regime. The deviation function is expressed in terms of the solution to a Fredholm equation of the second kind. A key element of the proof is the large-deviation principle in the scaling of moderate deviations for the sequential empirical process. The techniques of large-deviation convergence and idempotent processes are used extensively.

Keywords

Halfin–Whitt regimeheavy trafficlarge-deviation principlesequential empirical process

MSC classification

Primary: 60F10: Large deviations
Secondary: 60K25: Queueing theory
Type
Original Article
Information
Advances in Applied Probability , Volume 57 , Issue 2 , June 2025 , pp. 708 - 742
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Applied Probability Trust

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Aghajani, R. and Ramanan, K. (2020). The limit of stationary distributions of many-server queues in the Halfin-Whitt regime. Math. Operat. Res. 45, 1016–1055.CrossRefGoogle Scholar
Asmussen, S. (2003). Applied Probability and Queues, 2nd edition. Springer, New York.Google Scholar
Atkinson, K. E. (1997). The Numerical Solution of Integral Equations of the Second Kind. Cambridge University Press.CrossRefGoogle Scholar
Billingsley, P. (1968). Convergence of Probability Measures. John Wiley, New York.Google Scholar
Ekeland, I. and Temam, R. (1976). Convex Analysis and Variational Problems. North-Holland, Amsterdam.Google Scholar
Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. John Wiley, Hoboken, NJ.CrossRefGoogle Scholar
Feng, J. and Kurtz, T. G. (2006). Large Deviations for Stochastic Processes. American Mathematical Society, Providence, RI.CrossRefGoogle Scholar
Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Operat. Res. 29, 567–588.CrossRefGoogle Scholar
Jacod, J. and Shiryaev, A. N. (1987). Limit Theorems for Stochastic Processes. Springer, Berlin.CrossRefGoogle Scholar
Kallenberg, O. (2002). Foundations of Modern Probability, 2nd edition. Springer, New York.CrossRefGoogle Scholar
Kaspi, H. and Ramanan, K. (2013). SPDE limits of many-server queues. Ann. Appl. Prob. 23, 145–229.CrossRefGoogle Scholar
Krichagina, E. V. and Puhalskii, A. A. (1997). A heavy-traffic analysis of a closed queueing system with a $GI/\infty$ service center. Queueing Systems 25, 235–280.CrossRefGoogle Scholar
Liptser, R. S. and Shiryayev, A. N. (1989). Theory of Martingales. Kluwer, Dordrecht.CrossRefGoogle Scholar
Liptser, R. S. and Shiryaev, A. N. (2001). Statistics of Random Processes: I. General Theory. Springer, Berlin.Google Scholar
Petrov, V. V. (1987). Limit Theorems for Sums of Independent Random Variables, 2nd edition. Nauka, Moscow (in Russian).Google Scholar
Puhalskii, A. (1991). On functional principle of large deviations. In Proceedings of the Bakuriani Colloquium in Honour of Yu. V. Prohorov, Bakuriani, Georgia, USSR, 24 February–4 March, 1990 (New Trends in Probability and Statistics 1), eds V. Sazonov and Shervashidze, T., De Gruyter, Amsterdam, pp. 198–218.Google Scholar
Puhalskii, A. (1992). Weak convergence theory approach to large deviations. In Large Deviations and Applications (Workshop Report 1992.51), Mathematisches Forschungsinstitut Oberwolfach, p. 16.Google Scholar
Puhalskii, A. (1999). Moderate deviations for queues in critical loading. Queueing Systems 31, 359–392.CrossRefGoogle Scholar
Puhalskii, A. (2001). Large Deviations and Idempotent Probability. Chapman and Hall/CRC, Boca Raton.CrossRefGoogle Scholar
Puhalskii, A. A. (2022). Moderate deviation asymptotics of the $GI/G/n$ queue in the Halfin–Whitt regime. Queueing Systems 100, 341–343.CrossRefGoogle Scholar
Puhalskii, A. A. and Reed, J. E. (2010). On many-server queues in heavy traffic. Ann. Appl. Prob. 20, 129–195.CrossRefGoogle Scholar
Pukhalskii, A. A. (1994). On the theory of large deviations. Theory Prob. Appl. 38, 490–497.CrossRefGoogle Scholar
Reed, J. (2009). The G/GI/N queue in the Halfin–Whitt regime. Ann. Appl. Prob. 19, 2211–2269.CrossRefGoogle Scholar
Whitt, W. (1980). Some useful functions for functional limit theorems. Math. Operat. Res. 5, 67–85.CrossRefGoogle Scholar
Whittle, P. (1960). Bounds for the moments of linear and quadratic forms in independent variables. Theory Prob. Appl. 5, 302–305.CrossRefGoogle Scholar