Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 31 (Large Deviations and Queues)

Put $s_i={\sup }_{C_i}f$ and omit empty sets. Since the sets cover the space, boundedness givesFor nonnegative numbers $u_{n,i}$, their sum lies between their maximum and m times their maximum. Consequently its scaled logarithmic upper limit is at most ${\max }_i{\mathrm{limsup}}_n{n}^{-1}\log u_{n,i}$; the added $n^{-1}\log m$ vanishes. Each $C_i$ is closed, so the upper bound in the large deviation principle givesThe convention $\log 0=-\infty$ also handles sets of zero probability or infinite infimum rate.

Take $m=\lceil (b-a)/\epsilon \rceil$. The ceiling, as printed in the PDF, makes the intervals cover the bounded range of f. If $a=b$, use the single set $\mathcal{X}$ instead, since f is constant. By continuity their preimages are closed. On every nonempty preimage $C_i$, the oscillation of f is at most epsilon. Hence for every $y\in C_i$,Taking the supremum over y in the second expression gives the bound for ${\sup }_{C_i}f-{\inf }_{C_i}I$; if that infimum is infinite, the bound is automatic. Apply the finite-cover estimate to obtainThis is the exponential-integral upper estimate in the bounded form of Varadhan lemma.

The continuity of f makes its prescribed interval preimage B open, and $\hat{x}\in B$. On B we have $f(x)>f(\hat{x})-\epsilon$, soThe open-set lower bound of the large deviation principle therefore yieldsThus the claimed lower bound holds at every chosen point. When $I(\hat{x})=\infty$ its right side is minus infinity and the assertion is immediate.

Let epsilon decrease to zero in the upper estimate. In the lower estimate first take the supremum over all chosen points and then decrease epsilon to zero. The bounds coincide, proving Varadhan lemma:The value is finite: f is bounded, $I\ge 0$, and the large-deviation bounds on the whole space force $\inf I=0$. This proof actually uses bounded continuity and the large deviation principle; compact sublevels are not additionally needed for this bounded version.

Write $a_n=n^{2(1-H)}$ and $b_n=n^{2(1-G)}$. Then $a_n/b_n=n^{2(G-H)}\to \infty$. The large deviation principle on the whole space forces $\inf I=0$; compact sublevel sets and lower semicontinuity make that infimum attained. The unique possible zero is therefore mu, and $I(\mu )=0$.

If a closed set C contains mu, its new infimum rate is zero and the claimed upper bound follows from probabilities being at most one. If it excludes mu, then $\eta ={\inf }_{C}I>0$, possibly infinite: otherwise a sequence of rates tending to zero would have a convergent subsequence in a compact sublevel set, with limit in C and zero rate, contradicting uniqueness. This is the fact that a good rate function is separated from zero away from its minimizer.

Choose any $0<c<\eta$. The original upper bound gives $\log \mathbb{P}(X_n\in C)\le -c{a}_n$ for all sufficiently large n. ThusTogether these cases prove the closed-set upper bound at the slower speed, with rate zero only at mu. Its finite sublevels are the compact singleton $\{\mu \}$, so it is a good rate function.

For an open neighborhood D of mu, its complement is closed and excludes mu. The preceding upper bound is minus infinity, so, for example, eventually $\mathbb{P}(X_n\notin D)\le e^{-b_n}\to 0$. Hence the sequence concentrates in every neighborhood of mu.

If an open E contains mu, its probability tends to one. Its logarithm divided by $b_n\to \infty$ therefore tends to zero, which equals $-{\inf }_E{I}^{\prime }$. If E does not contain mu, that latter value is minus infinity and its lower bound is automatic. ThusWith the closed-set upper bound this proves the slower-speed degeneration of a large deviation principle. This degenerate rate has no strictly positive finite value, so it does not give the sequence a different Hurstiness under the stated definition.

Let $I_X,I_Y$ be the original rates and ${\mu }_X,{\mu }_Y$ their unique zero points. Suppose first that $H<G$. At speed $b_n=n^{2(1-G)}$, the preceding argument gives X the rate zero at ${\mu }_X$ and infinity elsewhere, while Y retains $I_Y$. Independence allows the product large-deviation principle, and addition is continuous, so the contraction principle for large deviations gives the sum rateThis is good, has unique zero ${\mu }_X+{\mu }_Y$, and inherits a strictly positive finite value by translation from $I_Y$. Thus the sum has Hurstiness G. The case $G<H$ is identical with the roles exchanged.

If $G=H$, the same product and contraction results apply to the original rates at their common speed, giving their infimal convolutionIt is good. Every finite fiber infimum is attained: a minimizing sequence lies in a product of compact sublevel sets and has a subsequence converging in the closed addition fiber. Consequently its only zero is ${\mu }_X+{\mu }_Y$. Choose $\hat{x}$ with $0<I_X(\hat{x})<\infty$ and set $\hat{z}=\hat{x}+{\mu }_Y$. Then $\hat{z}$ differs from the zero point and $0<K(\hat{z})\le I_X(\hat{x})<\infty$. The nondegeneracy requirement is therefore satisfied here too. In all cases,The general results used are the independent product large-deviation theorem and the continuous contraction principle. Checking the zero set and a positive finite value is necessary in addition to obtaining an LDP.

Let $\rho =\lambda /C<1$ and measure payload in kilobytes. A unit-mean exponential payload requires an exponential service time of rate C. Headers remain until service is complete, so Q counts all unfinished packets, including the packet in service. Its process is an M/M/1 queue with birth rate lambda and death rate C whenever nonempty.

The detailed balance equations give ${\pi }_{k+1}=\rho {\pi }_k$, and normalization gives ${\pi }_k=(1-\rho ){\rho }^k$. In the stationary infinite-space approximation,For a noninteger positive threshold replace q by its ceiling. At capacity 1000 the requested tail estimate is ${\rho }^{1000}$; literal exceedance of that capacity uses the adjacent integer threshold 1001. We compare the stated capacity-tail proxies consistently below.

Let U be the total payload arriving in one slot. Conditional on its Poisson packet count, use the exponential moment of each independent payload to get, for $\theta <1$,For net work $Z=U-C\delta$, its cumulant-generating function isThe mean net work is $\delta (\lambda -C)<0$. Under the arrivals-before-service slot convention the Lindley recursion gives stationary queue workload $R_{\delta }\stackrel{d}{=}{\sup }_{m\ge 0}{\sum }_{j=1}^m{Z}_j$. The positive root of the exponential-moment equation is ${\theta }_{\ast }=1-\rho$. Thus $\exp ({\theta }_{\ast }{\sum }_{j=1}^m{Z}_j)$ is a nonnegative martingale. Stop it at the first crossing of r or a finite horizon; its value on the crossing event is at least $e^{{\theta }_{\ast }r}$. Increasing the horizon provesThis is an infinite-horizon bound, not a one-slot Chernoff estimate.

A useful refinement identifies both the exponential rate and the small-slot prefactor. Couple the random walk to the continuous compound Poisson input U(t), and write $W={\sup }_{t\ge 0}(U(t)-Ct)$ and $W_{\delta }={\sup }_{k\ge 0}(U(k\delta )-Ck\delta )$. Their laws are the continuous and slot-boundary stationary queue workloads. Monotonicity of U implies the grid-sampled compound Poisson workload bound: $W_{\delta }\le W\le W_{\delta }+C\delta$, by rounding each t up to the next grid point.

The continuous queue workload law can be obtained directly from the stationary packet count. Conditional on Q=k, the k remaining payloads are independent unit-mean exponentials: unserved payloads have not affected earlier service completions, and the in-service residual uses the memoryless property. HenceThus W has mass $1-\rho$ at zero, and its positive part is exponential with rate $1-\rho$. Combining this stationary workload of an exponential-payload queue with the grid bound gives the explicit estimateIn particular ${\lim }_{r\to \infty }{r}^{-1}\log \mathbb{P}(R_{\delta }\ge r)=-(1-\rho )$, and for small delta the estimate is $\rho e^{-(1-\rho )r}$. The exact continuous-time tail is that latter expression. Another slot convention may shift queue workload by the within-slot input/service timing; its convention must be specified before asserting a prefactor, while this exponential tail rate is unchanged.

At a common large threshold b, the header tail has exponent $-\log \rho$, whereas the payload tail has exponent $1-\rho$. Since $-\log \rho >1-\rho$ for $0<\rho <1$, the payload queue has the heavier tail and dominates overflow on the large-buffer exponential scale at fixed load. The inequality follows from the strict convexity of minus the logarithm, or from integrating $1/u>1$ between rho and one.

The explanation is that a header always consumes one slot, while a payload can be unusually large. A rare accumulation of work can therefore overflow the byte buffer without accumulating as many as 1000 packets. Replacing every payload by its mean would lose precisely this source of variability.

For the actual capacity 1000, retaining the exact continuous-time prefactors gives a qualification that a tail-exponent comparison alone cannot detect. The two infinite-buffer proxies are $p_H={\rho }^{1000}$ and $p_P=\rho e^{-1000(1-\rho )}$, andThus payload overflow is more likely under this proxy exactly when the displayed expression is positive. For ordinary loads it is positive; for example it is positive at $\rho =0.9$. At $\rho =0.999$ it is approximately $-0.00050017$, so the header proxy is slightly larger. Consequently, without a numerical load, there is no universal exact ordering for the fixed capacity, although the large-buffer exponential ordering is unambiguous. Very near full utilization both 1000-unit buffers have substantial tail probabilities, so equal numerical capacities alone do not establish that the design is sensible. These are the requested infinite-space estimates, rather than an exact loss model for the interacting finite buffers.

Use the stated continuity of the infinite-buffer and finite-buffer queue workload maps on the input path space. The contraction principle for large deviations gives, at the same speed as the input sequence,Empty fibers have infimum infinity. Both rates are good because they are continuous contractions of the good rate function I. In particular, at speed L the infinite-buffer queue workload satisfies, for every Borel set E,and the identical bounds with bars give the finite-buffer queue workload LDP. This states the entire principles, not just an informal tail approximation.

Write $z(s)=a(-s,0]-Cs$. For each t the minimum in the finite-buffer formula is no greater than ${\sup }_{0\le s\le t}z(s)$. Taking the outer supremum gives $\bar{q}(a)\le {\sup }_{s\ge 0}z(s)=q(a)$. Also $z(0)=0$ ensures $0\le \bar{q}(a)\le B$: the choice $t=0$ gives zero, and each term is at most $B+{\inf }_{0\le s\le t}z(s)\le B$.

Every path in the fiber $\bar{q}(a)=x$ therefore lies in the set $q(a)\ge x$. Infima of its action giveThe last equality partitions that set by its queue workload fibers. It is a variational consequence of the pathwise order, without a questionable inference from probabilities of exact queue workload values.

Put $g={\Lambda }^{\ast }$ and $\gamma ={\inf }_{v>C}g(v)/(v-C)$, allowing gamma to be infinity if no rate above C has finite cost. We prove the linear workload rate for a local convex action, which in particular proves monotonicity on the physical domain $[0,\infty )$.

For an absolutely continuous finite-cost path and any interval of length t with positive net work $z(t)$, its average arrival rate is $C+z(t)/t$. Nonnegativity of g and Jensen inequality giveIf $q(a)=x>0$, choose intervals with $z(t)$ approaching its supremum x, obtaining $I(a)\ge \gamma x$. If gamma is infinite, the existence of any positive net interval instead forces infinite cost, giving the same extended-value conclusion.

Conversely, choose any $v>C$ of finite cost, use arrival rate v during the last $t=x/(v-C)$ time units and the typical rate mu before that. This constant-rate burst path has queue workload exactly x: the lookback net input increases to x over the burst and then decreases with slope $\mu -C<0$. Its action is $tg(v)=xg(v)/(v-C)$. Taking the infimum over v proves the matching upper bound. The typical-rate path has zero queue workload and zero cost. ThereforeStrict convexity and $g(\mu )=0$ ensure $\gamma >0$ whenever it is finite. Indeed, choose a finite-cost $v>C$ and some $u\in (\mu ,C)$; then $g(u)>0$, and convexity gives $g(v)/(v-C)\ge g(u)/(u-\mu )$ for every finite-cost $v>C$. Thus J is increasing on nonnegative queue workloads, and the preceding fiber bound yields $\boxed{\bar{J}(x)\ge J(x)\text{ for }x\ge 0}$. Negative values are impossible for both queue workloads and have infinite rate. No monotonicity is asserted across that impossible negative domain.

Take $0<x\le B$ and a finite-cost burst rate $v>C$. For the constant-rate burst path just constructed, let $t_0=x/(v-C)$. On $0\le s\le t_0$ its net input is $z(s)=(v-C)s$, so the supremum is x and the infimum is zero. The finite-buffer formula evaluated at $t=t_0$ is therefore $\min (x,B)=x$. Since $\bar{q}\le q=x$, we conclude $\bar{q}=x$ exactly: the burst never needs more space than the permitted capacity.

That path's action bounds the contracted finite-buffer rate, and optimizing givesAt zero use the typical-rate path to obtain $\bar{J}(0)=J(0)=0$. If the positive infinite-buffer rate is infinite, the asserted upper inequality is automatic. Approximating burst rates suffice, so the argument does not rely on an unproved existence of an optimal duration. Consequently $\boxed{\bar{J}(x)\le J(x)\text{ for }0\le x\le B}$.

For $0\le x\le B$, the two variational comparisons agree. Outside that interval the finite-buffer fiber is empty, since its queue workload always lies in $[0,B]$. The finite-buffer workload rate truncation is thereforeEquivalently this is J for $x\le B$ and infinity above B, since J already assigns infinity to negative queue workloads. Together with the contracted LDP from the first part, this proves the requested principle. The rate is good by contraction; alternatively its finite sublevel sets are the compact sets $\{J\le M\}\cap [0,B]$.