On large queue lengths in generalised Jackson networks
Anatolii A. Puhalskii · 2025
Read On large queue lengths in generalised Jackson networks 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-2512-19098.txt.
Introduction
Anatolii Puhalskii proves a large deviation principle for long queues in a generalized Jackson network, a standard model of linked service stations. The result describes the stationary distribution of queue lengths when the network runs below capacity. It assumes a Cramér condition on the gaps between arrivals and on service times. The rate function in the principle is the quasipotential, which prices how unlikely each large queue pattern is.
Catalog record
| CREATOR | Anatolii A. Puhalskii |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-19098
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On large queue lengths in generalised Jackson networks Anatolii A. Puhalskii Abstract This paper proves a large deviation principle (LDP) for the stationary distribution of queue lengths in a subcritical generalised Jackson network assuming a Cramer condition on the interarrival and service times. The deviation function is given by the quasipotential. 1 Introduction and summary We are concerned with the asymptotics of large deviations of stationary queue lengths in an ergodic generalised Jackson network. It is common to characterise large deviations of the stationary distributions of Markov processes in terms of quasipotentials, which involve trajectorial deviation functions, see Freidlin and Wentzell [ 4 ] , Shwartz and Weiss [ 15 ] . Although the queue length process in a generalised Jackson network is not Markovian, trajectorial LDPs for that process are available in the literature, see, e.g., Puhalskii [ 8 ] . Thus, a quasipotential can be defined, at least formally. In Theorem 2.2 in Puhalskii [ 9 ] it was asserted that the quasipotential governs large deviations of the stationary distribution. Unfortunately the proof there is flawed as to be detailed later. The purpose of this note is to give a correct proof. Our proof builds on the exponential tightness of the stationary distribution established in Puhalskii [ 14 ] and identifies the large deviation (LD) limit point as the time limit of the idempotent distribution of the transient LD limit of the queue length process. More specifically, the proof implements the following strategy, cf. Puhalskii [ 11 , 14 ] . Given a stationary stochastic process X_{n}(t) with invariant measure \mu_{n} , we have that for a bounded continuous nonnegative function f on the state space, \int f(x)^{n}\mu_{n}(dx)=\int\int f(x)^{n}\,\mathbf{P}(X_{n}(t)\in dx|X_{n}(0)=y)\mu_{n}(dy)\,. (1.1) Suppose \mu_{n} is exponentially tight and let \Pi represent an LD limit point of \mu_{n} . (A review of the basics of LD convergence, which is just a different form of the LDP, and of idempotent processes, can be found in Puhalskii [ 8 ] – [ 12 ] .) If, as n\to\infty , the transient distribution \mathbf{P}(X_{n}(t)\in dx|X_{n}(0)=y) continuously LD converges to certain deviability \Pi_{y,t}(x) (or obeys the continuous LDP with deviation function I_{y,t}(x)=-\ln\Pi_{y,t}(x) for that matter) and \mu_{n} LD converges to deviability \Pi (along a subsequence), then ( 1.1 ) implies that \sup_{x}f(x)\Pi(x)=\sup_{y}\sup_{x}f(x)\Pi_{y,t}(x)\Pi(y)\,. (1.2) If \Pi_{y,t}(x) converges to limit \hat{\Pi}(x) , as t\to\infty , which does not depend on y , then letting t\to\infty in ( 1.2 ) 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 \Pi(x)=\hat{\Pi}(x) . Thus, \Pi(x)=\lim_{t\to\infty}\Pi_{y,t}(x)\,. (1.3) In the setup of this paper, X_{n}(t)=Q(nt)/n , where Q(t) represents the queue length vector at t . In order to be able to work with the conditional distribution on the righthand side of ( 1.1 ), we need to append X_{n}(t) with a vector of initial residual service times and initial excess exogenous arrival times. Thus, y is a 3K -vector that records the initial queue lengths at the stations as well as the initial excess exogenous arrival times and residual service times. Therefore, the trajectorial LD convergence in Puhalskii [ 8 ] which concerned ordinary renewal processes needs to be extended to the case of delayed renewal arrival and service processes. The same device as in Puhalskii [ 8 ] of establishing exponential tightness and identifying the LD limit as a unique weak solution to a system of idempotent equations proves its worth. With regard to taking a limit as t\to\infty in ( 1.3 ), the case of ordinary renewal processes was dealt with in Puhalskii [ 9 ] . This paper extends the proof to the delayed case. In a nutshell, since the network is subcritical, the solution of the idempotent equations converges to a limit which implies the convergence of the solution’s idempotent distribution. The paper is organised as follows. In Section 2 a precise specification of the model is given and the main result is stated. In Section 3 the LD trajectorial convergence for the delayed case is addressed. The proof of the main result is discussed in Section 4 . 2 An LDP for stationary queue lengths We consider a queueing network with a homogeneous customer population which comprises K single server stations. Customers arrive exogenously and are served in the order of arrival, one customer at a time. Upon being served, they either join the queue at another station or leave the network. Let A_{k}(t) denote the cumulative number of exogenous arrivals at station k by time t , let S_{k}(t) denote the cumulative number of customers that are served at station k for the first t units of busy time of that station, and let R_{kl}(m) denote the cumulative number of customers among the first m customers departing station k that go directly to station l . Let A_{k}=(A_{k}(t),\,t\in\mathbb{R}_{+}) , S_{k}=(S_{k}(t),\,t\in\mathbb{R}_{+}) , and R_{k}=(R_{k}(m),\,m\in\mathbb{Z}_{+}) , where R_{k}(m)=(R_{kl}(m),\,l\in\mathcal{K}) and \mathcal{K}=\{1,2,\ldots,K\} . It is assumed that the A_{k} and S_{k} are possibly delayed nonzero renewal processes and R_{kl}(m)=\sum_{i=1}^{m}\mathbf{1}_{\{\zeta_{k}^{(i)}=l\}} , where \{\zeta_{k}^{(1)},\zeta_{k}^{(2)},\ldots\} is a sequence of i.i.d. random variables assuming values in \mathcal{K}\cup\{0\} , \mathbf{1}_{\Gamma} standing for the indicator function of set \Gamma . Let Q_{k}(t) represent the number of customers present at station k at time t . We denote Q(t)=(Q_{k}(t),\,k\in\mathcal{K}) and Q=(Q(t),\,t\in\mathbb{R}_{+}) , and refer to Q as to the queue length process. The random entities A_{k} , S_{l} , R_{m} and Q(0) are assumed to be defined on a common probability space (\Omega,\mathcal{F},\mathbf{P}) and be mutually independent, where k,l,m\in\mathcal{K} . All the stochastic processes are assumed to have piecewise constant right–continuous with left–hand limits trajectories. Accordingly, they are considered as random elements of the associated Skorohod spaces. We denote p_{kl}=\mathbf{P}(\zeta_{k}^{(1)}=l) and let P=(p_{kl})_{k,l=1}^{K} . The matrix P is assumed to be of spectral radius less than unity so that every arriving customer eventually leaves. For k\in\mathcal{K} and t\in\mathbb{R}_{+} , the following equations hold: Q_{k}(t)=Q_{k}(0)+A_{k}(t)+\sum_{l=1}^{K}R_{lk}\bigl(D_{l}(t)\bigr)-D_{k}(t), (2.1) where D_{k}(t)=S_{k}\bigl(B_{k}(t)\bigr) (2.2) represents the number of departures from station k by time t and B_{k}(t)=\int_{0}^{t}\mathbf{1}_{\{Q_{k}(u)>0\}}\,du (2.3) represents the cumulative busy time of station k by time t . For given realisations of Q_{k}(0) , A_{k} , S_{k} , and R_{k} , there exist unique Q_{k}=(Q_{k}(t),\,t\in\mathbb{R}_{+}) , D_{k}=(D_{k}(t),\,t\in\mathbb{R}_{+}) and B_{k}=(B_{k}(t),\,t\in\mathbb{R}_{+}) , that satisfy ( 2.1 ), ( 2.2 ) and ( 2.3 ), where k\in\mathcal{K} , see, e.g., Chen and Mandelbaum [ 2 ] . Let nonnegative random variables \xi_{k} and \eta_{k} represent generic times between exogenous arrivals and service times at station k , respectively. We assume that 0<\mathbf{E}\xi_{k}<\infty and 0<\mathbf{E}\eta_{k}<\infty . Let \lambda_{k}=1/\mathbf{E}\xi_{k} and \mu_{k}=1/\mathbf{E}\eta_{k} . We assume that the network is subcritical, i.e. \mu>(I-P^{T})^{-1}\lambda where \mu=(\mu_{1},\ldots,\mu_{K})^{T} and \lambda=(\lambda_{1},\ldots,\lambda_{K})^{T} . (Vector inequalities are understood entrywise.) In addition, it is assumed that the generic interarrival times are unbounded and spreadout. More specifically, it is assumed that 1. \mathbf{P}(\xi_{k}>u)>0 , for all k\in\mathcal{K} and u>0 , 2. for each k\in\mathcal{K} , there exist nonnegative function f_{k}(u) on \mathbb{R}_{+} with \int_{0}^{\infty}f_{k}(u)\,du>0 and m_{k}\in\mathbb{N} such that \mathbf{P}(\sum_{i=1}^{m_{k}}\xi_{k,i}\in[x,y])\geq\int_{x}^{y}f_{k}(u)\,du , provided 0\leq x\leq y , where \xi_{k,1},\ldots,\xi_{k,m_{k}} are i.i.d. and are distributed as \xi_{k} . Let U(t)=(U_{1}(t)\,,\ldots,U_{K}(t)) represent the K –vector of excess times of the exogenous arrival processes at t . To put it another way, U_{k}(t) is the length of time that elapses between t and the next