Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 36 / 2

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.