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

Let $N=4700$ and let the daily distances be independent and identically distributed random variables with probabilities $p_1=p_3=0.4995$, $p_{100}=0.001$. The unconditioned mean daily distance is $2.098$, whereas the observed trip requires a daily average near $10$. Conditioning on that rare average changes the typical frequencies substantially. It does not determine an exact boost count.

Use the method of types: for a fixed finite alphabet, the probability of an empirical distribution $q$ iswhere $D(q\Vert p)={\sum }_i{q}_i\log (q_i/p_i)$ is relative entropy, using natural logarithms. This follows directly from Stirling's approximation. There are only polynomially many types, so the empirical distribution conditional on a mean constraint concentrates at its unique relative entropy minimizer, when admissible lattice types approximate that minimizer. Any fixed neighborhood of it has a strictly smaller minimum cost than its complement.

Minimize $D(q\Vert p)$ subject to ${\sum }_i{q}_i=1$ and $q_1+3q_3+100q_{100}=10$. The entropy minimization under a prescribed sample mean gives the exponential tiltingTo verify minimization without relying only on Lagrange multipliers, any feasible distribution $r$ satisfiesRelative entropy nonnegativity makes $q$ the unique minimizer. Its mean determines $\theta$ through $Z^{\prime }(\theta )/Z(\theta )=10$, orThe derivative of the tilted mean is the tilted variance, which is strictly positive. The mean rises from $2.098$ at $\theta =0$ to $100$ as $\theta \to \infty$, so this equation has one positive solution. Numerically,The predicted boost count is $N{q}_{100}=381.6597211$. Thus the conditional large-deviation estimate is about 382 boosts.

For exact arrival at total distance $47000$, let $k,m,l$ count days of distances $100,3,1$. The constraints giveConsequently $k$ can be any even integer from $340$ to $426$. In particular, a unique count cannot be inferred from the return time. The exact conditional weights are proportional toTheir most probable count is $k=382$, consistent with the exponential tilting calculation. This finite-sample inference is a conditional probability statement, not an assertion that all journeys with the stated duration have that count.

If returning home means first crossing the distance threshold on day $4700$, the final total instead lies between $47000$ and $47099$. The last increment must exceed the overshoot; for fixed counts this selects the corresponding fraction of possible last days. Near the tilted optimum that factor is bounded away from zero, so it does not alter the leading exponential type cost. The same approximate answer follows. Exact conditional enumeration of this first-arrival interpretation also has mode $382$.

Use the positive-integer geometric distribution, $\mathbb{P}(X=k)=p(1-p{)}^{k-1}$ for $k\ge 1$, initially with $0<p<1$. Put $a=-\log (1-p)>0$. The precise good rate function on $\mathbb{R}$ isThe large-deviation speed is $L\to \infty$. We prove both bounds of the large deviation principle for $X^L=X/L$.

For $x>0$, the geometric tail gives the exact expressionLet $F$ be a closed set. If it does not meet $[0,\infty )$ its probability is zero. If it contains zero, $\mathrm{limsup}{L}^{-1}\log \mathbb{P}(X^L\in F)\le 0=-{\inf }_{F}I$. Otherwise, if it meets the nonnegative half-line, its least possible nonnegative value $r$ is positive: a sequence in $F$ approaching zero would force zero into the closed set. Its event is contained in $\{X^L\ge r\}$, giving

For an open set $G$ containing $x>0$, choose positive integers $k_L$ with $k_L/L\to x$. Eventually $k_L/L\in G$, andIf $0\in G$, the event $X=1$ alone gives lower exponential rate zero; alternatively the probability of a neighborhood of zero tends to one. Optimizing over $x\in G$ proves the open-set lower bound. Sets containing no nonnegative point require only the trivial lower bound $-\infty$.

The rate function is lower semicontinuous at zero as well as elsewhere, and $\{I\le r\}=[0,r/a]$ for finite $r\ge 0$ is compact. Hence the large deviation principle has a good rate function. This establishes the large deviations of a scaled geometric random variable. For $p=1$, $X=1$ deterministically and the rate instead is zero at $x=0$ and infinite elsewhere; the displayed logarithmic coefficient must not be treated as an ordinary finite number in that case.

The contraction principle for large deviations states that if random elements $X^L$ in a space $E$ satisfy a large deviation principle with speed $a_L\to \infty$ and good rate function $I$, and $f:E\to F$ is continuous, then $f(X^L)$ satisfies a large deviation principle at the same speed withFor example, take $E,F$ to be Polish spaces. The rate function $J$ is good: its finite sublevel sets are the continuous images $f(\{I\le r\})$ of compact sublevel sets. Compactness and lower semicontinuity ensure that a finite fibre infimum relevant to such a sublevel set is attained. The probability bounds follow by taking preimages of open and closed sets.

With $n$ fixed, the asymptotic family is the scaled sumAn unscaled fixed random variable alone has no diverging parameter for a large deviation principle; this scaling is the continuation of part (a). Suppose first $0<p_i<1$ and put $a_i=-\log (1-p_i)$. Independence and the product large-deviation principle give the vector $(X_1/L,\dots ,X_n/L)$ rateAddition is continuous, so the contraction principle for large deviations givesFor $s\ge 0$ every feasible vector has cost at least $s{a}_{\ast }$, where $a_{\ast }={\min }_i{a}_i$. Equality holds by assigning all scaled excess to an index attaining $a_{\ast }$. For $s<0$ the constraint set is empty. ThusEquivalently, the coefficient is $-\log (1-p_{\ast })$ with $p_{\ast }={\min }_i{p}_i$. On the exponential scale the rare large sum is carried by a variable having the slowest geometric tail. Several equal slowest tails can change polynomial prefactors, but not this rate function. This is the large deviations of a fixed sum of geometric random variables.

As a direct check of the tail exponent, for each $0<\theta <a_{\ast }$ the moment-generating function of the sum is finite, so the Chernoff bound gives an upper rate at most $-\theta s$ for $s>0$. Letting $\theta \uparrow a_{\ast }$ gives $-a_{\ast }s$. For a lower neighborhood bound, keep all other variables at fixed finite values and let a slowest-tail variable take an integer near $Ls$; its probability has rate $-a_{\ast }s$. If some $p_i=1$, their deterministic contributions disappear after division by $L$, so minimize over the nondeterministic variables. If all $p_i=1$, the rate is zero only at zero and infinite elsewhere.

A standard form of Varadhan's integral theorem is as follows. Let ${\mu }_L$ be probability measures on a Polish space $E$ satisfying a large deviation principle with speed $L\to \infty$ and good rate function $I$. If $F:E\to \mathbb{R}$ is continuous and bounded above, thenThe usual bounded-continuous version follows immediately. If $F$ is unbounded above, the same conclusion holds under the additional exponential tail conditionThis is the exponential tail extension of Varadhan's lemma. A convenient sufficient hypothesis isAn integrability hypothesis is essential for general unbounded functions; the ordinary large deviation principle alone does not control arbitrarily large exponential weights.

For example, let $X^L=L$ with probability $e^{-L^2}$ and $X^L=0$ otherwise. It satisfies the large deviation principle at speed $L$ with rate zero at zero and infinite elsewhere. But for $F(x)=x^2$, $\mathbb{E}{e}^{LF(X^L)}\ge e^{L^3-L^2}$, whose logarithmic rate diverges, while $\sup (F-I)=0$. This shows why the tail hypothesis cannot simply be omitted.

For the lower bound, fix $x$ with $I(x)<\infty$ and $\epsilon >0$. By continuity choose an open set $G$ containing $x$ on which $F(y)\ge F(x)-\epsilon$. ThenApply the open-set lower bound of the large deviation principle:Let $\epsilon \downarrow 0$ and take the supremum over $x$ to obtain the required lower bound. This argument also applies when $F$ is not bounded above.

For the upper bound, suppose $F\le M$ and set $S={\sup }_E(F-I)$, which is finite. Choose a large $K$ and partition $[-K,M]$ into finitely many closed intervals $[a_j,a_j+\epsilon ]$ of length at most $\epsilon$. The preimagesare closed sets. The overlapping endpoints do not matter for an upper estimate. Split off the lower tail and bound each remaining exponential weight:For a finite sum of nonnegative terms the upper logarithmic rate is at most the largest of their upper logarithmic rates. Applying the closed-set upper bound givesFor $x\in C_j$, $a_j+\epsilon \le F(x)+\epsilon$, hence every inner term is at most $S+\epsilon$. Empty preimages contribute no term. Let $K\to \infty$ and then $\epsilon \downarrow 0$ to get the upper bound $S$. Together with the lower bound this proves the bounded-above theorem.

For the unbounded extension, put $F_M=\min (F,M)$. This is continuous and bounded above, so the proved result applies, withThe full integral is at most the integral with $F_M$ plus the integral on $\{F>M\}$. The upper logarithmic rate is therefore at most the larger of $S_M$ and the tail rate. The tail hypothesis and then $M\to \infty$ give the upper bound $S$; the earlier local argument gives the lower bound. If $S=+\infty$, that lower argument already yields the asserted infinite limit.

Finally, the sufficient exponential-moment condition really implies the required tail estimate: on $F>M$,After integration the upper logarithmic rate is bounded by a finite constant minus $(\gamma -1)M$, which tends to $-\infty$. This completes the statement and proof of Varadhan's lemma, including the hypotheses needed for the unbounded version.

Work deterministically with nonnegative arrivals. Write $S_x(t)={\sum }_{k=1}^t{x}_{-k}$ for integer $t\ge 1$, and $S_x(0)=0$. The relevant metric isThis is the weighted cumulative-input topology for a slotted queue. It is a genuine norm on the ambient space of sequences with finite value: zero cumulative differences force every individual difference to vanish, since $x_{-k}=S_x(k)-S_x(k-1)$. Every input in the specified set $A$ has finite norm, because its long prefixes are bounded by $\lambda t$ and there are only finitely many earlier prefixes.

Use the conventional net-input slot boundary finite-buffer workload map, whose recursion is the clipped Lindley recursionArriving work in a slot is available to that slot's service, and the observed queue state is after service and upper clipping. This fixes the slot convention explicitly. The queue size $Q_B(x)$ is obtained by starting in the distant past and taking the present workload. We first prove that, under the stated strict drift condition, this is uniquely defined independently of the initial state.

Fix $x\in A$ and write $d_0=C-\lambda >0$. Choose a finite integer $T$ so large thatThen $S_x(T)-CT<-B$. Start at time $-T$ with a full buffer $q_{-T}=B$. The trajectory must hit zero by time zero. Otherwise lower clipping is never used, so for nonnegative lost-work amounts ${\ell }_t$ the total recursion would givecontradicting nonnegativity. If zero is attained even at the last update the desired conclusion still holds.

The update $F_B$ is monotone in the initial workload. Couple all starting values in $[0,B]$ using the same arrivals. When the trajectory starting at $B$ reaches zero, all smaller trajectories must also be zero, and they remain identical thereafter. Thus the present queue depends only on the last $T$ slots, not on any earlier state or arrivals. This is finite-memory continuity of a finite-buffer queue. In particular it proves the existence and uniqueness of $Q_B(x)$ without assuming a random stationary law.

The same memory horizon works in a neighborhood of $x$. If $\delta =\Vert x-y\Vert <d_0/2$, thenThe full-buffer trajectory for $y$ therefore also reaches zero within this horizon. Both $Q_B(x)$ and $Q_B(y)$ can consequently be calculated from initial workload zero at time $-T$, even though their respective reset times need not coincide.

Clipping to $[0,B]$ is Lipschitz continuous with constant one, soIterating from the common initial value zero givesThe cumulative-input norm bounds each summand:Summing proves the explicit local estimateGiven $\epsilon >0$, choose $\Vert x-y\Vert <\min \{(C-\lambda )/2,\epsilon /T^2\}$. Then the workload difference is less than $\epsilon$. Since $x\in A$ was arbitrary, the queue size function is continuous on $(A,\Vert \cdot \Vert )$.

The argument also handles the alternative slot ordering that clips arrivals to the buffer before serving them: its update is a composition of monotone one-Lipschitz clipping and service maps, and negative total net input forces a reset. Measuring immediately after arrivals instead adds one finite-coordinate update, which is likewise continuous in this norm. The essential point is strict subcritical drift and loss of dependence on the remote past, rather than incorrectly replacing a finite-buffer history by the minimum of $B$ and an infinite-buffer workload.