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

Write $p=1+\epsilon$ and assume $\lambda >0$. The large-deviation speed is $a_N=N^p$, and the answer isHere and below a large deviation principle at speed $a_N$ means the open-set lower bound $\mathrm{liminf}{a}_N^{-1}\log \mathbb{P}(X_N\in G)\ge -{\inf }_{G}I$ and the closed-set upper bound $\mathrm{limsup}{a}_N^{-1}\log \mathbb{P}(X_N\in F)\le -{\inf }_{F}I$. The displayed rate function is nontrivial and is a good rate function.

For $0<u<v$, the exponential distribution givesShrinking an interval about any $x>0$ supplies the local lower bound $-\lambda x$; neighborhoods of zero have probability tending to one. Every open set intersecting the nonnegative half-line contains one of these neighborhoods, giving the open-set bound. If a closed set $F$ contains zero, its upper bound is just $\mathbb{P}(\cdot )\le 1$. If it meets $[0,\infty )$ but excludes zero, closedness gives $b=\inf (F\cap [0,\infty ))>0$, and $\mathbb{P}(A/a_N\in F)\le e^{-\lambda a_{N}b}$. A closed set disjoint from the support has probability zero. This proves the full large deviation principle, including the boundary at zero.

The fixed exponential tail explains the speed: an excursion of size $x{N}^{1+\epsilon }$ costs $e^{-\lambda x{N}^{1+\epsilon }}$. The full Gärtner–Ellis theorem is unnecessary here; the limiting cumulant-generating function is flat on $\theta <\lambda$ and infinite at $\theta \ge \lambda$, so it fails the theorem's essential smoothness hypothesis.

Assume ${\sigma }^2>0$; otherwise the scaled sum is deterministic and no nontrivial rate function is possible. The sum has normal distribution $B_N\sim N(N\mu ,N{\sigma }^2)$. For $X_N=B_N/N^{1+\epsilon }$, use the faster large-deviation speed $b_N=N^{1+2\epsilon }$. The moment-generating function of a normal distribution yieldsThe limiting cumulant-generating function is finite and differentiable on all of $\mathbb{R}$, hence satisfies the Gärtner–Ellis theorem. Its Legendre-Fenchel transform is obtained by maximizing $\theta x-{\sigma }^2{\theta }^2/2$, whose maximizer is $\theta =x/{\sigma }^2$. ThusThe drift disappears because the scaled mean is $\mu /N^{\epsilon }\to 0$. The rate function is nontrivial and good. The corrected scaled cumulant-generating function used here contains an expectation; the corresponding formula in the paper's reference material omits it.

Use the large-deviation speed $a_N=N^{1+\epsilon }$ from part (a). For every $\eta >0$, the Chernoff bound for a normal distribution gives, for all sufficiently large $N$,Consequentlybecause the exponent has order $N^{1+2\epsilon }$, exceeding $a_N$ by a factor $N^{\epsilon }$. Thus $(A+B_N)/a_N$ and $A/a_N$ satisfy exponential equivalence. This conclusion does not require independence between $A$ and $B_N$, since their difference is exactly $B_N/a_N$.

The exponential equivalence theorem transfers the large deviation principle and its good rate function, givingLarge positive excursions are cheapest through the single exponential random variable; a negative excursion would require the Gaussian random variable sum to move on its faster scale. If $\sigma =0$, the deterministic shift $N\mu /a_N\to 0$ gives the same conclusion directly.

The printed mean is $1/(\lambda i)$, so $T_i$ has exponential distribution of rate $i\lambda$. Let $S_k={\sum }_{i=1}^k{T}_i$, with fixed $k$. ThenHere is a direct proof, which also identifies the exceptional role of the slowest exponential clock. For $0<\theta <\lambda$, independence and the moment-generating function giveLetting $\theta \uparrow \lambda$ proves the tail upper bound $-\lambda x$. For a local lower bound at $x>0$, fix $0<\eta <x$ and $M>0$ with $\mathbb{P}({\sum }_{i=2}^k{T}_i\le M)>0$; for $k=1$ this probability is one. For large $N$, the eventputs $S_k/N$ in $(x-\eta ,x+\eta )$. Its logarithmic probability divided by $N$ tends to $-\lambda (x-\eta /2)$. Shrinking $\eta$ gives the local lower bound $-\lambda x$. At zero, $S_k/N\to 0$ almost surely and neighborhoods have probability tending to one.

For any closed set excluding zero, its nonnegative part is bounded away from zero; the tail upper bound applies at its infimum. Sets outside the support have probability zero. Together with the local lower bounds this proves the full large deviation principle, with a good rate function. Equivalently, the product large-deviation principle for the fixed vector $(T_1/N,\dots ,T_k/N)$ and the contraction principle for large deviations minimize ${\sum }_{i}i\lambda u_i$ subject to $u_i\ge 0$ and ${\sum }_i{u}_i=x$; all the excursion is assigned to $u_1$.

Interpret the additional copies in $Z_N$ as independent of the initial $T_1,\dots ,T_k$, as well as of one another. Set $r=k\lambda$. The Cramér theorem for rate-$r$ exponential random variables gives the rate functionIndeed their cumulant-generating function is $\log (r/(r-\theta ))$ for $\theta <r$, and the maximizer in its Legendre-Fenchel transform is $\theta =r-1/z$. For $Z_N/N$, replacing $N$ summands by $N-k$ does not change either the speed $N$ or this rate function. One can also see this directly from $N^{-1}\log \mathbb{E}{e}^{\theta Z_N}\to \log (r/(r-\theta ))$ and the Gärtner–Ellis theorem.

The product large-deviation principle, followed by the contraction principle for large deviations under addition, now givesFor $x>0$ this is the minimum over $0<z\le x$ ofIf $k>1$, its derivative with respect to $z$ is $r-\lambda -1/z$. Hence the optimum is $z=\min (x,1/[\lambda (k-1)])$, andThe two expressions agree at the transition and have the same derivative $\lambda$. The minimum rate zero occurs at the typical value $x=1/(k\lambda )$. If $k=1$, the minimand is $\lambda x-1-\log (\lambda z)$, decreasing in $z$, so insteadThese are good rate functions. The affine branch for $k>1$ is the slow exponential plus an exponential sample mean mechanism: the bulk ceases to carry additional excess, which instead comes from $T_1$. In particular, blindly applying the full Gärtner–Ellis theorem to the combined sum would be unjustified. Its limiting cumulant-generating function is $\log (r/(r-\theta ))$ only for $\theta <\lambda$, with a finite boundary slope when $k>1$; essential smoothness fails. The product and contraction argument proves the missing lower bounds.

Write $S_N={\sum }_{i=1}^N{T}_i$. The answer isThe sum of exponential variables with linearly increasing rates has the distribution of the maximum of $N$ independent rate-$\lambda$ exponential random variables. To prove this identity, start $N$ independent rate-$\lambda$ exponential clocks. The first rings after a rate-$N\lambda$ exponential time; the memoryless property leaves $N-1$ fresh independent clocks. Repeating this argument shows that the successive order statistic gaps are independent, with rates $N\lambda ,(N-1)\lambda ,\dots ,\lambda$. Their sum has the distribution of $S_N$. ThereforeFor $x>0$, $N{e}^{-\lambda Nx}\to 0$, and henceIf $0<u<v$, subtracting the two tails gives the interval exponent $-\lambda u$, since the tail at $Nv$ is exponentially smaller. Also $\mathbb{E}{S}_N={\lambda }^{-1}{\sum }_{i=1}^N{i}^{-1}=O(\log N)$, so the Markov inequality gives $S_N/N\to 0$ in probability. Local lower bounds at positive points and at zero follow; the tail estimate gives the closed-set upper bound exactly as in part (a). This proves the full large deviation principle.

There is also a deduction from part (b). For fixed $k$ and $i>k$, a rate-$i\lambda$ exponential random variable is stochastically smaller than a rate-$k\lambda$ one. Coupling by the same uniform variables therefore gives $S_N\le S_k+Z_N$ with independent additional copies. For fixed $x>0$ and sufficiently large $k$, the upper-tail exponent from part (b) is $-\lambda x-\log ((k-1)/k)$. Let $k\to \infty$ to obtain $-\lambda x$; the lower tail estimate $\mathbb{P}(S_N>Nx)\ge \mathbb{P}(T_1>Nx)=e^{-\lambda Nx}$ matches it. The exact maximum identity additionally supplies all local lower bounds.

Put $\kappa =2(1-H)>0$. For the Gaussian process $Z$, self-similarity of a stochastic process gives the identity in distributionApply the given small-noise large deviation principle with $L=N^{\kappa }$. The answer isNo Legendre-Fenchel transform needs to be recomputed: the scaled paths have exactly the small-noise law at this scale.

If the stated small-noise large deviation principle is indexed only by integer $L$, use $L_N=\lfloor N^{\kappa }\rfloor$. This gives speed $N^{\kappa }$ as well, since $L_N/N^{\kappa }\to 1$. The multiplying factor $\sqrt{L_N/N^{\kappa }}\to 1$ does not change the large deviation principle. To justify this last step, the error in the path norm is $o(1)\Vert Z/\sqrt{L_N}\Vert$. For each fixed $M$, good rate functions have bounded sublevel sets, so ${\inf }_{\Vert f\Vert \ge M}I(f)\to \infty$ as $M\to \infty$. The closed-set upper bound then makes the probability of an error greater than any fixed $\eta >0$ superexponentially small. Thus exponential equivalence applies. This also justifies positive real, rather than only integer, rescalings used in part (c).

Let $\delta =C-\mu >0$, and first suppose $\sigma >0$. For the infinite-horizon contraction, use the usual sublinear path space for fluid queues,We interpret the supplied path-space large deviation principle in this norm, or in a topology with the same workload-continuity property. The paper does not specify its norm explicitly; mere convergence on compact time intervals would not justify an infinite-horizon contraction.

Define the queue workload functionalIt is finite and nonnegative on the sublinear path space for fluid queues. Here is the required continuity argument. Fix $f$ and choose $T\ge 1$ so that $|\sigma f(t)|\le \delta t/4$ for $t\ge T$. If $\Vert g-f{\Vert }_{\mathrm{sl}}<\delta /(4\sigma )$, then for $t\ge T$,The corresponding expression for $f$ is also negative there, whereas at zero both are zero. Each supremum can therefore be restricted to $[0,T]$, givingThus $R$ is a continuous map; this proof also shows why the negative drift is essential.

Substituting $t=Ns$ into the queue workload givesThe contraction principle for large deviations says that a continuous image of a family with good rate function $I$ has the same large-deviation speed and good rate function obtained by minimizing $I$ over each fibre. ConsequentlyIn particular $J(0)=0$: $Z/\sqrt{L}\to 0$ in the path norm almost surely, so the given large deviation principle and lower semicontinuity give $I(0)=0$, and $R(0)=0$. If $\sigma =0$, the queue workload is identically zero and the rate function is zero at zero and infinite elsewhere. No unspecified variance normalization of the fractional Brownian motion is needed for this variational answer.

Let $\kappa =2(1-H)$ and fix $a>0$. Starting with part (b), the contraction principle for large deviations under the map $q\mapsto q/a$ gives an LDP for $r(X)/(aN)$ with speed $N^{\kappa }$ and rate function $q\mapsto J(aq)$.

Alternatively, replace $N$ by $aN$ in parts (a) and (b), using the real-scale justification in part (a). The same family has large-deviation speed $(aN{)}^{\kappa }$ and rate function $J(q)$. When expressed at speed $N^{\kappa }$, that rate function is $a^{\kappa }J(q)$. The two descriptions of the same large deviation principle must agree:For clarity, uniqueness here is a general property of lower semicontinuous rate functions: at a point $x$, the shrinking-neighborhood logarithmic bounds recover $I(x)$, since ${\inf }_{B(x,\eta )}I\to I(x)$ as $\eta \downarrow 0$. Thus two rate functions for the same family and speed cannot differ.

Taking the base argument $q=1$ and replacing $a$ by any positive queue size givesFor $q<0$ the rate function is infinite. In the usual nondegenerate case $J(1)$ is finite, so the formula also holds at $q=0$. This is the self-similar Gaussian workload rate; the exponent comes from the Hurst parameter, while the constant comes from the path rate function and the drift and noise scales.

For the amount of work $A_j(0,t]$ offered by one flow in a time interval of length $t$, its effective bandwidth at parameter $\theta >0$ and timescale $t>0$ isIts units are work per unit time. The parameter $\theta$ measures the price placed on bursts: a stringent rare-overflow target generally requires a larger value of $\theta$ than a loose target. The timescale $t$ describes the duration of the congestion episode. When the limit exists, writeThis is the long-time effective bandwidth. It includes a burstiness cost, rather than just the mean offered rate. For a finite-time flow with the required moments, ${\lim }_{\theta \downarrow 0}{\alpha }_j(\theta ,t)=\mathbb{E}{A}_j(0,t]/t$, and effective bandwidth is increasing in $\theta$. If $A_j(0,t]/t$ is bounded, its limit as $\theta \to \infty$ is the essential supremum of that interval's input rate, the peak-rate limit. The analogous long-time mean limit requires the usual interchange or regularity assumptions.

For independent flows their cumulant-generating functions add, soThe Chernoff bound therefore gives, for any $\theta >0$ in the common domain,Optimizing over $\theta$ produces the relevant Legendre-Fenchel transform. The Cramér theorem states that sample means of independent and identically distributed inputs whose moment-generating function is finite near zero have a large deviation principle, with rate function equal to the Legendre-Fenchel transform of their cumulant-generating function. More generally, the Gärtner–Ellis theorem applies to a convergent scaled log moment-generating function when zero lies inside its domain and the limit is lower semicontinuous and essentially smooth. It gives the same transform as a good rate function. A sample-path version, together with the contraction principle for large deviations for the queue workload, translates input deviations into overflow deviations. The compact-time and infinite-horizon continuity/tail hypotheses must be checked for the chosen traffic model.

A particularly useful rigorous queue bound holds for inputs with stationary increments and independent increments, such that $\mathbb{E}{e}^{\theta A(t)}=e^{t\Lambda (\theta )}$. If $\Lambda (\theta )\le C\theta$, thenis a nonnegative supermartingale, since its conditional increment factor is $e^{(t-s)(\Lambda (\theta )-C\theta )}\le 1$. The maximal inequality for a nonnegative supermartingale on $[0,T]$, followed by $T\to \infty$, gives the continuous-time exponential workload boundHere $W$ is the stationary queue workload of the stable infinite-buffer queue, represented by input from the past. This directly bounds the supremum over time; applying a one-time Chernoff bound alone would not establish it.

For a nonzero Compound Poisson process with bounded positive packet sizes and mean input rate less than $C$, a positive root ${\theta }_{\ast }$ of $\Lambda (\theta )=C\theta$ exists and is unique. Here the root theorem can be made explicit:The upper bound was just proved. For the lower bound, use exponential tilting with density $e^{{\theta }_{\ast }(A(t)-Ct)}$ at time $t$. Under the tilted law the net input has positive mean drift ${\Lambda }^{\prime }({\theta }_{\ast })-C>0$, by strict convexity and the positive-root equation. The strong law of large numbers then makes the first crossing time ${\tau }_b$ finite almost surely under that law. Its overshoot is at most $s_{\max }$. Changing measure at ${\tau }_b$, first on $\{{\tau }_b\le T\}$ and then letting $T\to \infty$, givesDividing the logarithmic bounds by $b$ proves ${\lim }_{b\to \infty }{b}^{-1}\log \mathbb{P}(W\ge b)=-{\theta }_{\ast }$.

Thus the familiar admission rule compares ${\sum }_j{a}_j(\theta )$ with $C$, choosing $\theta$ from the desired buffer-tail exponent. For more general inputs, a logarithmic root theorem requires its own light-tail and renewal or sample-path hypotheses; the displayed supermartingale upper bound needs only the moment and increment assumptions stated above.

The capacity and quality targets alone do not determine flow counts: the per-flow traffic statistics must also be supplied. The following explicit model gives a computable sufficient region, with genuine upper bounds on both loss fractions.

Measure queue workload and buffer size in bits. Denote capacity by $C$, shared buffer size by $B$, voice delay limit by $D$, target voice loss by ${\ell }_v$, and target data loss by ${\ell }_d$, with $0<{\ell }_v,{\ell }_d<1$. Let there be $n_v$ voice flows and $n_d$ data flows. Model each class-$j$ flow, $j\in \{v,d\}$, by a stationary Compound Poisson process with packet rate ${\nu }_j$ and positive independent packet sizes $S_j$, and assume independence across flows and marks. Use a work-conserving preemptive-resume priority queue with a shared buffer, with voice priority and first come first served within each class. This preemptive or fluid approximation makes the predicted voice waiting time exactly $V/C$, where $V$ is the remaining voice queue workload just before arrival. Assume packet sizes are bounded by a known $s_{\max }<B$ and interpret the buffer gate as a packet-fit test; rejecting packets which do not fit is the packet version of the full-buffer rule.

For one flow the Compound Poisson process formula givesFor fixed-size packets of size $s_j$, substitute $e^{\theta s_j}$. Estimate the packet rate and size law from measurements or a declared traffic contract. Also require the strict stability inequalityDefine $B_0=B-s_{\max }>0$ and $K=CD$. Couple the switch with an unthinned infinite-buffer aggregate queue and an unthinned infinite-buffer voice-only queue, both driven by the same offered packets and both served at rate $C$. Under the preemptive service discipline, dropping arrivals can only decrease both the total queue workload and the voice queue workload. Thus total switch queue workload $Q$ and voice queue workload $V$ satisfy $Q\le W_T$ and $V\le W_V$ in the stationary coupling. A packet-fit loss implies $Q>B-S_j\ge B_0$, and a voice-delay rejection implies $V\ge K$.

Apply the continuous-time exponential workload bound to the two comparison queues. For any positive ${\theta }_T,{\theta }_V$ satisfyingthe stationary loss-event probabilities obeyThe second inequality is a union bound: voice can be lost either at the shared buffer or at its delay gate. Data congestion therefore contributes to voice loss despite its lower service priority. Poisson arrivals see time averages applies to each offered packet stream, whose future arrivals are independent of the prearrival state; the stationary event bounds are consequently bounds on the offered-packet loss fractions. Voice packets that are admitted have queueing delay below $D$, because later voice packets join behind them and data work cannot delay them in this model.

To turn the bounds into flow counts, allocate loss budgetsFor example, ${\eta }_B=\min ({\ell }_d,{\ell }_v/2)$ and ${\eta }_V={\ell }_v-{\eta }_B$ also work; equality with ${\ell }_d$ is harmless. The required sufficient effective-bandwidth admission region with a voice delay gate isIt ensures $p_d\le {\ell }_d$ and $p_v\le {\ell }_v$. A simple enumeration isdiscarding negative bounds and pairs failing strict mean-load stability. The formulas assume positive-rate nonzero-size flows. Optimize a chosen revenue or flow-count objective over these integer pairs. Searching over the budget split ${\eta }_B$ can enlarge the sufficient region. For a bit-fluid buffer gate with no packet-fit issue, $B_0$ can be replaced by $B$.

Real nonpreemptive packet service needs an additional residual-service allowance or an explicit priority queue workload analysis: a voice packet may have to wait for the data packet already in service. Burst-correlated voice sources also require richer descriptors, such as measured finite-time effective bandwidths ${\alpha }_j(\theta ,t)$ or a Markov-modulated source model. For such inputs, additivity still holds for independent flows, but the independent-increment supermartingale bound is not automatic; use a valid sample-path large deviation principle or a model-specific overflow bound, with prefactors or a safety margin when using asymptotics. If packet arrivals do not form a Poisson process, loss fractions must be assessed at arrival epochs rather than inferred solely from time-average queue workload probabilities. These qualifications explain both how to calculate an admission region from specified traffic statistics and why the five switch/QoS parameters by themselves cannot supply a numerical answer.