Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 79 / 3

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.