= Continuous-time exponential workload bound
{title2=$\mathbb P(W\geq b)\leq e^{-\theta b}$}
For a nondecreasing process $A$ with <stationary increments> and <independent increments>, suppose $\mathbb E e^{\theta A(t)}=e^{t\Lambda(\theta)}$. If $\Lambda(\theta)\leq C\theta$, then $e^{\theta(A(t)-Ct)}$ is a nonnegative <supermartingale>. Applying the <maximal inequality for a nonnegative supermartingale> up to time $T$ and then letting $T\to\infty$ gives
$$
\mathbb P\!\left(\sup_{t\geq0}(A(t)-Ct)\geq b\right)\leq e^{-\theta b}.
$$
The stationary workload of a stable <queue> fed by $A$ has this supremum distribution, using the past input and <stationary increments> and <independent increments>. For <independent> flows, the constraint is $\sum_j a_j(\theta)\leq C$, where $a_j(\theta)=\Lambda_j(\theta)/\theta$ is the long-time <effective bandwidth>. The result bounds a continuous-time supremum directly; a one-time <Chernoff bound> by itself does not do that.
Back to article page
