Search papers, labs, and topics across Lattice.
This paper derives pre-limit tail bounds for the stationary queue length in a heavily overloaded single-server queue with abandonment, focusing on efficiency across constant, moderate, and large deviation regimes. They achieve this by combining Stein's method for Wasserstein-$p$ distance and the transform method, obtaining Gaussian-type decay for constant deviations and exponentially tight bounds for larger deviations. The work further extends these results to a load-balancing system with heterogeneous servers under the join-the-shortest-queue policy, establishing state space collapse and deriving Wasserstein-$p$ bounds.
Forget asymptotic approximations: this paper delivers pre-limit tail bounds for queue lengths with abandonment that are efficient across all deviation regimes, from constant to large.
We study a heavily overloaded single-server queue with abandonment and derive bounds on stationary tail probabilities of the queue length. As the abandonment rate $纬\downarrow 0$, the centered-scaled queue length $\tilde{q}$ is known to converge in distribution to a Gaussian. However, such asymptotic limits do not quantify the pre-limit tail $\mathbb{P}(\tilde{q}>a)$ for fixed $纬>0$. Our goal is to obtain pre-limit bounds that are \emph{efficient} across different deviation regimes. For constant deviations, efficiency means Gaussian-type decay in $a$ together with a pre-limit error that vanishes as $纬\downarrow 0$, yielding the correct Gaussian tail in the limit. We establish such an efficient bound that is best-of-both-worlds. For larger deviations when $a$ is a function of $纬$, efficiency translates into exponentially tight, matching upper and lower bounds. For moderate deviation, we obtain sub-Gaussian tails, while in the large deviation regime the decay becomes sub-Poisson. Our bounds are obtained using a combination of Stein's method for Wasserstein-$p$ distance and the transform method. We then consider a load-balancing system of abandonment queues with heterogeneous servers, operating under the join-the-shortest-queue (JSQ) policy in the heavily overloaded regime. As in the case of single-server queue, we again obtain Wasserstein-$p$ bounds w.r.t.\ a Gaussian, and efficient concentration for constant and moderate deviations. For larger deviations, our JSQ upper bounds exhibit a transition from Gaussian-type decay to sub-Weibull decay. All these results are obtained using Stein's method. In addition, a key ingredient here is establishing a state space collapse (SSC) where all queues become equal. We establish a $p$-th moment bound on the orthogonal component of the queue length vector that is essential for our Wasserstein-$p$ bound.
