Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 26 (Large Deviations and Queueing Theory)

Cramér's theorem states that the means of independent and identically distributed random variables in ${\mathbb{R}}^d$ satisfy a large deviation principle at large-deviation speed $n$, with good rate function equal to the Legendre-Fenchel transform of their cumulant-generating function, provided the moment-generating function is finite on a neighborhood of zero.

Here the exponential distribution hasFor $x>0$, maximize $\theta x-\Lambda (\theta )$. Its derivative is $x-(\lambda -\theta {)}^{-1}$ and its second derivative is negative, so the maximizing parameter is ${\theta }_x=\lambda -x^{-1}$. Therefore the rate function of an exponential sample mean isFor $x\le 0$, letting $\theta \to -\infty$ in the same supremum gives $+\infty$, including the logarithmic divergence when $x=0$. The moment-generating function is finite near zero, so Cramér's theorem supplies the full large deviation principle.

The rate function is nonnegative, with its unique minimum at $\mu ={\lambda }^{-1}$; $I^{\prime \prime }(x)=x^{-2}>0$. It tends to infinity both as $x\downarrow 0$ and as $x\to \infty$. Its finite sublevel sets are closed bounded intervals contained in $(0,\infty )$, hence compact. Thus it is a good rate function.

For fixed $k$, independence and the product large-deviation principle give the vector $(Y_n(1),\dots ,Y_n(k))$ the good rate function ${\sum }_{j=1}^{k}I(y_j)$. Since the minimum is a continuous map, the contraction principle for large deviations givesIn every vector in this fibre, at least one coordinate equals $m$ and all others are at least $m$. The large-deviation rate of a minimum of independent copies therefore reduces the infimum toIf $0<m<\mu ={\lambda }^{-1}$, the other coordinates can equal $\mu$ and cost zero. If $m\ge \mu$, the rate function is increasing on $[\mu ,\infty )$, so every coordinate costs at least $I(m)$ and equality is achieved when all coordinates equal $m$. For $m\le 0$ the cost is infinite. ThusAt the threshold both expressions are zero. Goodness follows from the contraction principle for large deviations. A small minimum requires only one atypically small mean; a large minimum requires all $k$ means to be atypically large, which explains the two costs.

Varadhan's lemma states that if $U_n$ has a large deviation principle with good rate function $K$ and large-deviation speed $a_n$, then for every bounded continuous real function $h$,For a continuous function unbounded above, the same conclusion holds under the exponential tail extension of Varadhan's lemma, for example when the weighted contribution from $h>M$ is superexponentially negligible as $M\to \infty$.

The scalar clipping map $g(m)=\min (b,\max (a,m))$ is continuous. The rate function under scalar clipping has endpoint costs ${\inf }_{m\le a}J(m)$ and ${\inf }_{m\ge b}J(m)$. Since $a<\mu <b$ and the costs decrease towards $\mu$ from the left and increase to its right, both infima are attained at the corresponding endpoints. Thus the good rate function of $Z_n$ equals $J(z)$ on $[a,b]$ and is infinite outside. The function $\log z$ is bounded and continuous on that compact interval, soOn $[a,\mu ]$, the derivative of $\log z-I(z)$ is $2/z-\lambda >0$, so the maximum there is $\log \mu$. On $[\mu ,b]$, the derivative is $(k+1)/z-k\lambda$, with negative second derivative. Its unconstrained maximizer isIt lies in $[\mu ,b]$ whenever $k\ge (\lambda b-1{)}^{-1}$. The right-hand objective increases initially at $\mu$, so this maximizer dominates the whole left-hand interval. Substitution gives the limit for high moments of a clipped minimum of exponential sample meansThe moment here is the expectation of the $n$th power. If the printed notation were instead read as $(\mathbb{E}{Z}_n{)}^n$, its logarithmic limit would be $\log \mu =-\log \lambda$, since boundedness and convergence in probability give $\mathbb{E}{Z}_n\to \mu$.

A large deviation principle for random elements $X^L$ in a Hausdorff space $E$, at large-deviation speed $a_L\to \infty$, has a lower semicontinuous rate function $I:E\to [0,\infty ]$. For every open set $G$ and every closed set $F$,Equivalently, for every Borel set $A$, the lower and upper bounds use its interior and closure, respectively. The conventions are $\inf \varnothing =+\infty$ and $\log 0=-\infty$. A good rate function has compact sublevel sets $\{I\le r\}$ for every finite $r$. Here take $a_L=L$; the different speeds in the moderate deviation principle are stated explicitly when used.

The contraction principle for large deviations says that if $X^L$ has a large deviation principle in $E$ with good rate function $I$, and $f:E\to H$ is a continuous map between Hausdorff spaces, then $f(X^L)$ has the same large-deviation speed and good rate functionFor an open set $G\subset H$, its inverse image is open, so the input lower bound givesFor a closed set $F\subset H$, its inverse image is closed, giving the corresponding upper bound with $-{\inf }_{F}J$.

It remains to prove goodness, including the endpoint issue in the infimum. Each fibre $f^{-1}(\{y\})$ is closed. If $J(y)<\infty$, compact sublevel sets and lower semicontinuity make $I$ attain its infimum on that fibre: intersect it with the compact set $\{I\le J(y)+1\}$ and use the closed nested sublevels tending down to $J(y)$. Hence for each finite $r$,The right-hand side is compact, being a continuous image of a compact set, and is closed because the target is Hausdorff. Thus $J$ is lower semicontinuous and good, completing the proof.

The family is exponentially tight at large-deviation speed $a_L$ if for every $M>0$ there is a compact set $K_M\subset E$ such thatFor this question $a_L=L$. The definition says that escape from an appropriate compact set can be made negligible at any prescribed exponential rate. Requiring a strict inequality instead gives the same notion, by choosing a larger $M$.

Use the standard Hausdorff state-space convention, so compact sets are closed. Let $F$ be any closed set and choose $K_M$ from exponential tightness. The weak large deviation principle applies to the compact set $F\cap K_M$, whileThe principle of the largest exponential term givesLet $M\to \infty$. This is the full closed-set upper bound; the open-set lower bound was already present.

For goodness, fix $r<\infty$ and choose $M>r$. The complement $K_M^c$ is open. Its lower bound and its exponential-tightness upper estimate implyThus ${\inf }_{K_M^c}I\ge M$ and $\{I\le r\}\subset K_M$. Lower semicontinuity makes this sublevel set closed, so it is a closed subset of a compact set and therefore compact. This proves that exponential tightness upgrades a weak large deviation principle to the full principle with the same good rate function.

Write $S_L=X^{\oplus L}$. Its Poisson distribution has mean $L\lambda$, since the probability-generating functions of the independent summands multiply. DefineThe scaled cumulant-generating function isA Taylor expansion of the exponential, valid for each fixed $\theta$ because $\beta <1$, givesThe remainder is $O(L^{(\beta -1)/2})$. The limit is finite and differentiable on all of $\mathbb{R}$, hence satisfies the essential-smoothness hypotheses of the Gärtner–Ellis theorem. Its Legendre-Fenchel transform isThis proves the Poisson moderate deviation principle with large-deviation speed $L^{\beta }$ and a good rate function.

For an arbitrary open set $B$, the lower bound uses ${\inf }_B{I}_{\beta }$ and the upper bound uses ${\inf }_{\overline{B}}{I}_{\beta }$. These infima agree: every point of the closure is a limit of points of $B$ and $I_{\beta }$ is finite and continuous. Thus the logarithmic probabilities of open sets for a continuous rate function give the stated logarithmic limit for every open $B$, not just intervals. The empty-set case follows from the usual infinite-value conventions.

In this bufferless queue, queue overflow is the eventThe Poisson moderate deviation principle therefore givesThe same infimum is obtained for $x\ge C$, so replacing $Q_L>C$ by $Q_L\ge C$ gives the same logarithmic exponent. Any integer rounding of the service rate of a queue changes the scaled threshold by a quantity tending to zero.

The bufferless queue output isPut $r_L=L\lambda +B{L}^{(1+\alpha )/2}$. Since $\alpha <\beta$, we have $r_L<u_L$ for all sufficiently large $L$. Consequently the two queue overflow events are exactly equal eventually:Apply the Poisson moderate deviation principle with exponent $\alpha$ to obtainThere is also an exponential equivalence proof, which describes the whole output law at this smaller scale. For each $\epsilon >0$,The right side has strictly negative logarithmic exponent at speed $L^{\beta }$. Dividing instead by $L^{\alpha }$ multiplies that negative exponent by $L^{\beta -\alpha }\to \infty$, giving $-\infty$. Thus the centered, scaled input and output are exponentially equivalent and have the same good rate function. This is the moderate deviations below a bufferless queue cap.

The downstream service rate of a queue now exceeds the upstream cap for all sufficiently large $L$, sinceBut the bufferless queue output is always at most $u_L$. Therefore the downstream queue overflow probability is eventually exactly zero, andThis is a deterministic cap argument, stronger than merely proving superexponentially small probability.

The input admits positive moderate deviations on every scale $L^{(1+\delta )/2}$ with $0<\delta <1$. The bufferless queue output retains exactly the same overflow events at thresholds below the cap, so clipping does not improve the exponents on the smaller $\alpha$ scale. It removes every positive burst at thresholds on the larger $\gamma$ scale.

At the cap's own scale $\beta$, apply the contraction principle for large deviations to the map $x\mapsto \min (x,C)$. The output has good rate functionAt $C$ the cost is ${\inf }_{x\ge C}{x}^2/(2\lambda )=C^2/(2\lambda )$. Thus the burstiness of queue input has been reduced in its sufficiently large positive tail, while its smaller-scale rare fluctuations persist. These are the moderate deviation scales of a clipped Poisson aggregate.

Write $A_n$ for work arriving in slot $n$ and $c$ for the service rate of a queue. For a work-conserving single-server queue, the Lindley recursion is $Q_{n+1}=(Q_n+A_{n+1}-c{)}^{+}$. For stable independent and identically distributed random variables with mean $\mu <c$, its stationary workload supremum has the formDifferent scaling limits of a queue concern different quantities growing large; they need not share either a probability speed or a likely path to overflow.

For large-buffer queue scaling, fix the input law and $c>\mu$ and let the buffer size of a queue $b\to \infty$. Assume finite exponential moments around a positive root ${\theta }_{\ast }$ of ${\Lambda }_A(\theta )=c\theta$. An overflow accumulated in $n\simeq tb$ slots requires an average input about $c+1/t$, so Cramér's theorem assigns logarithmic cost $bt{I}_A(c+1/t)$. Optimizing the duration gives the Cramér-Lundberg workload exponentFor an interior root with ${\Lambda }_A^{\prime }({\theta }_{\ast })>c$, Fenchel–Young inequality verifies the minimization: the lower bound is ${\theta }_{\ast }$ because $I_A(x)\ge {\theta }_{\ast }x-{\Lambda }_A({\theta }_{\ast })$, and equality occurs at $t=[{\Lambda }_A^{\prime }({\theta }_{\ast })-c{]}^{-1}$. The exponential workload bound from cumulative arrival moments gives the upper exponent for every $\theta <{\theta }_{\ast }$; an exponentially tilted positive-drift path or the duration calculation gives the matching lower exponent. In effective bandwidth notation, ${\Lambda }_A({\theta }_{\ast })/{\theta }_{\ast }=c$. This regime measures long accumulation into a large buffer with a fixed positive stability margin.

For many-source queue scaling, superpose $L$ independent copies of an input process, give the server capacity $Lc$, and give it buffer size $Lb$. For each lookback horizon $n$, the average of the $L$ source cumulative arrivals has a large deviation principle with rate function $I_n$. Overflow at that horizon costs $L{I}_n(b+cn)$. Optimizing the lookback horizon suggestsFor independent slots, $I_n(x)=n{I}_A(x/n)$, giving $V(b)={\inf }_{n\ge 1}n{I}_A(c+b/n)$. The integer horizon is important in a slotted system. For temporally dependent sources, use the cumulative-input cumulant-generating function, rather than multiplying a one-slot formula by $n$. The heuristic needs uniform control of the tail of the stationary supremum to justify optimizing an unbounded set of horizons; stability and suitable exponential-moment estimates provide this in the usual models. The growing quantity here is the number of independent sources, while per-source capacity and buffer remain fixed.

For moderate-deviation queue scaling, consider a bufferless queue with aggregate Poisson input of mean $L\lambda$ and capacity $L\lambda +C{L}^{(1+\beta )/2}$, $0<\beta <1$. The spare capacity is much larger than the ordinary central limit theorem scale $\sqrt{L}$ but much smaller than $L$. The Poisson sample-mean rate function near its minimum has expansionWith $h=C{L}^{(\beta -1)/2}$, the cost $L{I}_P(\lambda +h)$ is asymptotic to $C^2{L}^{\beta }/(2\lambda )$. Hence Poisson moderate deviations give $\log \mathbb{P}(\mathrm{overflow})\sim -C^2{L}^{\beta }/(2\lambda )$. The quadratic cost comes from a shrinking neighborhood of the mean, rather than from a fixed macroscopic overload. The regime is useful for a large aggregate whose service margin lies between its typical fluctuation scale and its mean scale.

For a heavy-traffic limit of a queue, instead hold the input law fixed with mean $\mu$ and positive finite variance ${\sigma }^2$, and let $c_{\epsilon }=\mu +\epsilon d$ with $d>0$ and $\epsilon \downarrow 0$. In $t/{\epsilon }^2$ slots the net input has mean about $-dt/\epsilon$ and random fluctuation of size $\sigma \sqrt{t}/\epsilon$. Thus the functional central limit theorem, followed by the Skorokhod reflection map on the half-line, suggestswhere $R$ is reflected Brownian motion with negative drift $-d$ and variance parameter ${\sigma }^2$. The stationary law of negatively drifted reflected Brownian motion has tail $\mathbb{P}(R_{\infty }>b)=e^{-2db/{\sigma }^2}$. When passing the stationary distribution through the limit is justified, this predictsFor dependent input satisfying a suitable invariance principle, replace ${\sigma }^2$ by its long-run variance of a stationary process. This regime is appropriate near critical load and on long time scales; a functional transient limit alone does not automatically justify the stationary-limit interchange.

A different large-service regime holds the input law fixed. With Poisson distribution of mean $\lambda$ and bufferless capacity $c\to \infty$, let $m=\lfloor c\rfloor +1$. The single-point lower bound $\mathbb{P}(X=m)$ and the optimized Chernoff bound for $X\ge m$, using Stirling's formula, give the Poisson large-service overflow asymptoticHere the service rate grows while the input mean does not. A quadratic moderate-deviation approximation would describe the wrong part of the Poisson tail.

To choose a regime, compare the spare capacity, typical fluctuations, number of sources and buffer size before selecting a formula. Use the large-buffer exponent for a fixed stable input and a long overload episode; use the many-source variational cost when independent flows and resources grow together; use moderate deviations for an intermediate safety margin; use the heavy-traffic diffusion when the stability margin tends to zero; and use the fixed-input Poisson tail when service alone becomes very large. Check temporal dependence and exponential-moment assumptions. For heavy-tailed subexponential distributions, a single exceptionally large arrival can dominate overflow, so a finite exponential workload root and a Brownian approximation to the far tail need not apply. These comparisons explain why the same nominal queueing theory system can have different useful asymptotic descriptions.