= Exponential workload bound from cumulative arrival moments
{title2=$\mathbb P(Q>B)\leq e^{-\theta B}\sum_{n\geq1}e^{K_n(\theta)-\theta cn}$}
Let a slotted <queue> have stationary input, constant service $c$, and finite stationary <queue workload> $Q=\sup_{n\geq0}(A_n-cn)$. Write $K_n(\theta)=\log\mathbb E e^{\theta A_n}$ for its past cumulative arrivals. The <union bound> and <Chernoff bound> give the displayed inequality for $B>0$. It requires no temporal <independence>. If each $K_n(\theta)$ is finite and $K_n(\theta)/n\to\kappa(\theta)<c\theta$, the series is finite: its tail is bounded by a geometric series. Consequently $\limsup_{L\to\infty}L^{-1}\log\mathbb P(Q>Lb)\leq-\theta b$ for $b>0$. The condition is that the asymptotic <effective bandwidth> $\kappa(\theta)/\theta$ be less than service capacity.
Back to article page
