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

At large-deviation speed $L$, the exponential distribution gives the large deviation principle on $\mathbb{R}$ with good rate functionIn particular, $\mathbb{P}(B/L\ge b)=e^{-\lambda Lb}$ for $b\ge 0$. Its finite sublevel sets are the compact sets $[0,r/\lambda ]$.

Write $S_L={\sum }_{i=1}^L{A}_i$ and $Z_L=S_L/L$. The cumulant-generating function of one normal random variable isCramér's theorem states that empirical means of independent and identically distributed random variables whose moment-generating function is finite on a neighborhood of zero satisfy a large deviation principle at the sample-size large-deviation speed, with good rate function equal to the Legendre-Fenchel transform of their cumulant-generating function. Here that givesFor ${\sigma }^2>0$, differentiation gives the maximizing parameter $\theta =(x-\mu )/{\sigma }^2$, and henceThis rate function tends to infinity as $|x|\to \infty$, so its finite sublevel sets are compact. Equivalently, the Gärtner–Ellis theorem applies because the limiting scaled cumulant-generating function is finite and differentiable everywhere; it is lower semicontinuous and essentially smooth, with no finite domain boundary at which to check steepness. If ${\sigma }^2=0$ is permitted, $Z_L=\mu$ deterministically and the rate function is zero at $\mu$ and infinity elsewhere.

The product large-deviation principle states that independent families satisfying large deviation principles at the same speed with good rate functions $J$ and $I$ have joint good rate function $J(b)+I(z)$. The contraction principle for large deviations states that a continuous map $f$ sends such a principle to one with good rate function ${\inf }_{f(u)=x}I(u)$. Apply these results to $(B/L,S_L/L)$ and addition. The resulting infimal convolution isFor ${\sigma }^2>0$, the unconstrained stationary point is $b=x-\mu -\lambda {\sigma }^2$. Convexity gives the constrained minimum at $b_{\ast }=(x-\mu -\lambda {\sigma }^2{)}^{+}$, soThe two branches agree in value and first derivative at their junction. Both tails tend to infinity, giving a good rate function. This is the fixed exponential perturbation of a Gaussian empirical mean.

There is a reason to use the product large-deviation principle rather than invoke the supplied Gärtner–Ellis theorem without checking its hypotheses. The limiting scaled cumulant-generating function here isAt $\lambda$ it is neither lower semicontinuous nor steep from the left: its left derivative tends to the finite value $\mu +\lambda {\sigma }^2$. Its Legendre-Fenchel transform still equals $K$, but the stated Gärtner–Ellis theorem does not establish the full lower bound on the linear branch. The product large-deviation principle and contraction principle for large deviations do establish it. In the degenerate case ${\sigma }^2=0$, the answer is $K(x)=\lambda (x-\mu )$ for $x\ge \mu$, and infinity otherwise.

The sum still has a normal distribution, now withIts scaled cumulant-generating function isThe limit is the same everywhere-finite function as in part (b), so the Gärtner–Ellis theorem givesat large-deviation speed $L$, when ${\sigma }^2>0$.

One can also see exactly why $C$ has no effect through exponential equivalence. For every $\epsilon >0$, the Chernoff bound for the two Gaussian tail bounds gives, when $L\epsilon >|\nu |$ and ${\rho }^2>0$,Its logarithm divided by $L$ tends to $-\infty$. If ${\rho }^2=0$, this probability is eventually zero. The transfer result for exponential equivalence says that coupled families whose distance exceeds each fixed positive tolerance with superexponentially small probability share a large deviation principle with the same good rate function. Apply it to $(C+S_L)/L$ and $S_L/L$. This also covers ${\sigma }^2=0$, with the point-mass rate function from part (b).

All three normalized sums converge in probability to $\mu$: the weak law of large numbers controls $S_L/L$, and the two fixed random variables vanish after division by $L$. Their rare fluctuations nevertheless differ. A fixed normal random variable would have to fluctuate by order $L$ to alter the mean by a fixed amount, and that costs $\exp (-\text{constant}{L}^2)$. A fixed exponential random variable can do the same for a cost of order $\exp (-\text{constant}L)$, exactly the large-deviation speed of the empirical mean.

Below $\mu +\lambda {\sigma }^2$, the optimal exponential contribution is zero, and the Gaussian empirical mean supplies the fluctuation. Above it, the optimal empirical mean remains at $\mu +\lambda {\sigma }^2$, while $B/L$ supplies $x-\mu -\lambda {\sigma }^2$. This explains the quadratic-to-linear change in the rate function and why only the upper tail is altered. Convergence to the same typical value does not imply the same large-deviation behavior.

Work in a Hausdorff space $E$, for example a metric space. A rate function is a lower semicontinuous map $I:E\to [0,\infty ]$. A good rate function additionally has compact finite sublevel sets $\{x:I(x)\le r\}$.

A large deviation principle at large-deviation speed $L$ requires, for every open set $G$ and closed set $F$,The conventions are $\log 0=-\infty$ and $\inf \varnothing =+\infty$. A weak large deviation principle imposes the same lower bound but only the upper bound for compact sets. Exponential tightness supplies compact sets $K_M$ with $\mathrm{limsup}{L}^{-1}\log \mathbb{P}(X_L\notin K_M)<-M$ for every $M\ge 0$. The strict inequality can equivalently be obtained from the common non-strict definition by choosing a larger containment level.

Fix a finite $r\ge 0$ and choose $M>r$. By exponential tightness, choose a compact set $K_M$ with outside probability having upper exponential rate strictly below $-M$. A compact set in a Hausdorff space is closed, so its complement is an open set. The lower bound of the weak large deviation principle givesConsequently ${\inf }_{K_M^c}I>M$, and $\{I\le r\}\subset K_M$. Lower semicontinuity makes this sublevel set closed in $E$, hence a closed subset of a compact set. Thus it is compact. Every finite sublevel set is compact, so $I$ is a good rate function.

Let $F$ be any closed set. For each $M>0$, choose $K_M$ as above. The probability decompositionreduces the first term to a compact set, where the weak upper bound applies. For nonnegative numbers $u_L,v_L$, the inequality $u_L+v_L\le 2\max (u_L,v_L)$ shows that the upper exponential rate of their sum is no larger than the maximum of their upper exponential rates. HenceLet $M\to \infty$. This proves the full closed-set upper bound, including when ${\inf }_{F}I=+\infty$. The open-set lower bound was already assumed. Combining with part (b), the weak principle upgrades to a large deviation principle with good rate function $I$. This is exponential tightness upgrades a weak large deviation principle.

Measure $Q_t$ immediately after service in slot $(t-1,t)$, and let $a_t\ge 0$ denote work eligible for that slot's service. Writing $x^{+}=\max (x,0)$, the Lindley recursion isStart with an empty queue at time $-N$. Repeated substitution gives its time-zero queue workloadwhere the empty sum is zero. The increasing limit defines the minimal causal queue workload:If the mean of the remote past is $\lambda <c$, then $A_n(a)/n\to \lambda$, so $A_n(a)-cn\to -\infty$. The supremum is then finite and is attained at a finite window. The same formula with indices shifted gives $Q_t(a,c)$ and satisfies the Lindley recursion directly: split the supremum into the zero-window term and all positive-window terms.

There is an indexing issue in the printed topology. Its cumulative sums omit $a_0$, whereas the post-slot workload of a queue in part (a) includes $a_0$. To see the problem, take all $a_t=\lambda$ for $t\le -1$, with $\lambda <c$, and compare two inputs with $a_0=\lambda$ and $a_0=c+1$. Their distance according to the printed cumulative-sum expression is zero, yetThus the post-slot workload is not continuous in the literal printed topology. On two-sided sequences that expression is a seminorm, since it also ignores future coordinates; the fixed-mean input class is not a vector space (if signed inputs are allowed, it is an affine set).

The appropriate repair for the post-slot convention is to use one-sided past inputs including time zero and the weighted cumulative-input topology for a slotted queue:This is a finite metric on the fixed-mean class, since cumulative differences are $o(n)$; equality of all cumulative sums implies equality of all past coordinates. It is equivalent to augmenting the printed cumulative-difference distance by $|a_0-b_0|$: their cumulative sums differ only by this extra coordinate and a one-step shift.

Here is the full corrected continuity proof. Fix $a$ with $A_n(a)/n\to \lambda <c$, and let $\epsilon =(c-\lambda )/4$. Choose $N\ge 1$ such that $A_n(a)/n\le \lambda +\epsilon$ whenever $n\ge N$. If $d_{\#}(a,b)<\epsilon /2$, then, for all such $n$,Both queue workloads therefore maximize over the same finite collection $0\le n<N$, containing the value zero. For any two finite lists, the difference of their maxima is at most the maximum absolute difference of corresponding entries. Thusin this neighborhood. In particular the queue workload is locally Lipschitz continuous and hence continuous.

An alternative indexing repair retains the printed topology but interprets the time-zero function as the workload before slot $(-1,0)$, namely ${\sup }_{n\ge 0}\{{\sum }_{j=1}^n{a}_{-j}-cn\}$. The same finite-window argument proves its continuity. One must then shift the time labels consistently in the later recursions. The remaining answers use the post-slot convention and $d_{\#}$.

The work passed downstream in slot $(t-1,t)$ isBecause this work is eligible for downstream service in the same slot, the downstream Lindley recursion isPut $T_t=Q_t+R_t$. If $R_{t-1}+D_t\ge d$, thenIf $R_{t-1}+D_t<d$, then $D_t<d<c$, so the upstream server did not use its full capacity. Consequently $D_t=Q_{t-1}+a_t$ and $Q_t=0$. Also $R_t=0$ and $Q_{t-1}+R_{t-1}+a_t-d<0$. Both cases yieldThis slower-server tandem workload identity uses both $d<c$ and eligibility for same-slot downstream service. It would not describe a system with an obligatory one-slot transfer delay.

Define the downstream queue workload by starting both queues empty at time $-N$ and taking the increasing remote-past limit. For each finite $N$, part (c) makes their total queue workload exactly the single-server workload with service $d$, while the upstream queue workload is the single-server workload with service $c$. ThereforeThe downstream limit is increasing: the coupled upstream and downstream recursions are increasing in their initial state, because $D_t=\min (c,Q_{t-1}+a_t)$ is increasing in $Q_{t-1}$. With finite upstream queue workload, taking the limit givesThe result is nonnegative because reducing service cannot reduce queue workload. It can be $+\infty$ when the slower server is unstable; under $\lambda <d<c$, both quantities are finite. The finite-upstream condition matters: subtracting two infinite queue workloads would not define a downstream queue.

The indexing defect also affects the downstream claim. For the two inputs in part (b), now choose $\lambda <d<c$. The constant input has zero downstream queue workload, while the input with $a_0=c+1$ hasTheir printed distance is zero, so the literal post-slot downstream continuity assertion is false as well.

In the corrected weighted cumulative-input topology for a slotted queue, apply the finite-window proof of part (b) separately with services $d$ and $c$. Both have strictly negative long-window drift because $\lambda <d<c$. There are a neighborhood of $a$ and finite constants $C_d,C_c$ such thatThis proves continuity, and indeed local Lipschitz continuity, for the intended downstream function.

Suppose a family of random arrival paths $a^{(L)}$ has a large deviation principle in this corrected input space, at speed $L$ with good rate function $\mathcal{I}$. The contraction principle for large deviations then gives the downstream good rate functionIt is infinity for $r<0$. The path large deviation principle, its topology, and its subcritical domain must actually be established for the chosen stochastic model: a collection of finite-dimensional large deviation principles alone does not control infinitely long workload windows. Nor should upstream departures be assumed independent; the path contraction avoids that unjustified assumption.

Consider a stationary nonnegative work-input process in slotted time, with cumulative work $A_n$ over the last $n$ slots and a work-conserving server of capacity $c$ per slot. Assume its past average tends almost surely to $m<c$. The Lindley recursion then defines the finite stationary queue workloadThis is work remaining, rather than the number of customers when customer service requirements vary. With unit work per customer the two notions coincide. Stationarity makes the distribution of a past cumulative window equal to that of a forward window of the same length.

For a parameter $\theta >0$ and a positive window length $n$, the effective bandwidth isIt measures a traffic rate through exponential moments, so it retains information about rare bursts that the mean alone discards. If the limiting scaled cumulant-generating function exists, putThe finite-window effective bandwidth matters when the relevant overflow window is short or when arrivals are correlated; one should not replace it by its long-window limit without justification.

The following proof gives an actual upper bound for the infinite-horizon queue workload. For $B>0$, if $Q>B$, at least one positive integer $n$ has $A_n-cn>B$. The union bound followed by the Chernoff bound givesAssume each finite-window exponential moment is finite and $\kappa (\theta )<c\theta$. Choose $\eta >0$ such that $\kappa (\theta )+\eta <c\theta$. For all sufficiently large $n$, the summand is at most $e^{-n(c\theta -\kappa (\theta )-\eta )}$. Its tail is a convergent geometric series, and its finite prefix is finite. Denote the resulting sum by $K_{\theta }$. The exponential workload bound from cumulative arrival moments therefore proves, for $b>0$,Optimizing over admissible parameters givesOnly parameters with the stated finite-window moments are included. If there are no such positive parameters, the argument yields only the trivial exponent zero. Infinite ${\theta }_{\ast }$ means that the upper rate is $-\infty$. For a non-strict threshold $Q\ge Lb$, first bound it by $Q>L(b-\epsilon )$ and then let $\epsilon \downarrow 0$. This proof permits dependence between slots. It proves the required upper bound; it does not assert a matching lower bound for every arrival process.

This also gives a closed-set large-deviation upper bound for $Q/L$: set $I_{+}(q)={\theta }_{\ast }q$ for $q>0$, $I_{+}(0)=0$, and $I_{+}(q)=+\infty$ for $q<0$. If a closed set $F$ contains zero, its desired upper bound is the trivial bound zero. If $F$ contains positive points but not zero, its positive part has a smallest point $b>0$, and $\mathbb{P}(Q/L\in F)\le \mathbb{P}(Q\ge Lb)$ gives the bound $-{\inf }_F{I}_{+}$. If it contains no nonnegative points, its probability is zero. This verifies the upper half of a large deviation principle; the actual rate function can be larger when a matching lower bound is unavailable.

For independent and identically distributed slot arrivals $a_t$, let $\kappa (\theta )=\log \mathbb{E}{e}^{\theta a_0}$. Now $\log \mathbb{E}{e}^{\theta A_n}=n\kappa (\theta )$, so effective bandwidth is independent of window length. For $\kappa (\theta )<c\theta$, the geometric-series prefactor is explicitlyThus the familiar workload Chernoff bound for independent increments is a special case, and the largest admissible parameter is often the positive root of $\kappa (\theta )=c\theta$.

For these independent increments there is a sharper argument that works at the root itself when its exponential moment is finite. Along the past read in reverse order, put $S_n=A_n-cn$ and $M_n=e^{\theta S_n}$. If $\mathbb{E}{e}^{\theta (a_0-c)}\le 1$, then $M_n$ is a nonnegative supermartingale starting at one. For the first crossing time ${\tau }_B=\inf \{n\ge 0:S_n\ge B\}$, bounded optional stopping givesLet $N\to \infty$. Strict negative drift makes $S_n\to -\infty$ almost surely, so its supremum is attained and the crossing event agrees with $\{Q\ge B\}$. ConsequentlyThis strengthens the prefactor but uses temporal independence, which was unnecessary for the previous proof.

Several examples show what the effective bandwidth constraint means. Deterministic traffic of $r$ work units per slot has $\kappa (\theta )=\theta r$ and effective bandwidth $r$ at every parameter; if $c\ge r$ there is no stationary backlog. For independent on-off slots carrying $r$ units with probability $p$ and zero otherwise, the Bernoulli effective bandwidth isFor $0<p<1$, it rises from the mean $pr$ to the peak $r$. When $pr<c<r$, strict convexity of $\kappa (\theta )-c\theta$, its negative derivative at zero, and its divergence to infinity give a unique positive root. When $c\ge r$, no slot can increase the queue workload. In the specific case $r=2,c=1,p<1/2$, the workload increases by one with probability $p$ and decreases by one, reflected at zero, with probability $1-p$. Its stationary probabilities satisfyThe service-root equation has $e^{{\theta }_{\ast }}=(1-p)/p$, and thus $\mathbb{P}(Q\ge k)=q^k=e^{-{\theta }_{\ast }k}$. This example realizes the upper exponent exactly.

For independent Poisson slot counts of mean $\nu$, with unit work per arrival, the Poisson effective bandwidth isStability requires $c>\nu$. There is a unique positive root of $\nu (e^{\theta }-1)=c\theta$, again by strict convexity, negative initial derivative after subtracting $c\theta$, and growth to infinity. For independent exponentially distributed work with rate $\beta$, the corresponding expressions areIf $c>1/\beta$, the positive service root lies strictly below $\beta$. The finite moment-generating function domain cannot be ignored.

To see statistical aggregation explicitly, let the entire arrival processes of $k$ sources be independent, though each source may itself have dependence over time. Their cumulative totals satisfyThus the shared queue has an exponential overflow bound when ${\sum }_j{\alpha }_j(\theta )<c$, with the finite-window conditions proved above. One must use a common parameter $\theta$; adding individual service-root exponents is not the rule. For example, an independent Poisson source of mean $\nu$ and an independent on-off source of size $r$ and probability $p$ have aggregate cumulant-generating functionFor $\nu >0$ and $c>\nu +pr$, their positive service root exists and determines the optimized upper exponent. Several independent Poisson sources similarly have the same formula as one source with intensity ${\sum }_j{\nu }_j$.

The connection with large deviation principles also appears in a many-source scaling. For $L$ independent copies of a source, aggregate service $Lc$ and buffer $Lb$, fix a window $n$. Let $X_i(n)$ be each copy's cumulative input in that window. Their total exceeds $L(b+cn)$ only if the empirical mean exceeds $b+cn$. Its Chernoff bound has exponentIf exponential moments exist near zero, Cramér's theorem gives the corresponding finite-window large deviation principle. The threshold exceeds the mean because $m<c$ and $b>0$. A finite union of windows has upper exponential rate at most $-{\min }_n{V}_n(b)$ over those windows. Passing to infinitely many windows requires uniform control of long-window probabilities, not simply an interchange of a limit with an infinite union. A good sample-path large deviation principle in a topology where the queue workload is continuous, as in Question 3, instead permits the contraction principle for large deviations to derive a workload rate function and its closed-set overflow upper bound.

Finally, the mean and peak limits of effective bandwidth quantify the safety margin. With exponential moments near zero, independent slot work of mean $m$ and variance $v$ hasFor bounded work, its large-parameter limit is the essential peak. Stronger tail requirements select larger $\theta$ and hence more capacity; finite-window effective bandwidths also reflect temporal burst correlations. A stable heavy-tailed input can lack every positive exponential moment, in which case this exponential-bound method supplies no positive decay rate. Stability and exponentially small overflow are distinct requirements.