Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 31 / 4

Use the stated continuity of the infinite-buffer and finite-buffer queue workload maps on the input path space. The contraction principle for large deviations gives, at the same speed as the input sequence,Empty fibers have infimum infinity. Both rates are good because they are continuous contractions of the good rate function I. In particular, at speed L the infinite-buffer queue workload satisfies, for every Borel set E,and the identical bounds with bars give the finite-buffer queue workload LDP. This states the entire principles, not just an informal tail approximation.

Write $z(s)=a(-s,0]-Cs$. For each t the minimum in the finite-buffer formula is no greater than ${\sup }_{0\le s\le t}z(s)$. Taking the outer supremum gives $\bar{q}(a)\le {\sup }_{s\ge 0}z(s)=q(a)$. Also $z(0)=0$ ensures $0\le \bar{q}(a)\le B$: the choice $t=0$ gives zero, and each term is at most $B+{\inf }_{0\le s\le t}z(s)\le B$.

Every path in the fiber $\bar{q}(a)=x$ therefore lies in the set $q(a)\ge x$. Infima of its action giveThe last equality partitions that set by its queue workload fibers. It is a variational consequence of the pathwise order, without a questionable inference from probabilities of exact queue workload values.

Put $g={\Lambda }^{\ast }$ and $\gamma ={\inf }_{v>C}g(v)/(v-C)$, allowing gamma to be infinity if no rate above C has finite cost. We prove the linear workload rate for a local convex action, which in particular proves monotonicity on the physical domain $[0,\infty )$.

For an absolutely continuous finite-cost path and any interval of length t with positive net work $z(t)$, its average arrival rate is $C+z(t)/t$. Nonnegativity of g and Jensen inequality giveIf $q(a)=x>0$, choose intervals with $z(t)$ approaching its supremum x, obtaining $I(a)\ge \gamma x$. If gamma is infinite, the existence of any positive net interval instead forces infinite cost, giving the same extended-value conclusion.

Conversely, choose any $v>C$ of finite cost, use arrival rate v during the last $t=x/(v-C)$ time units and the typical rate mu before that. This constant-rate burst path has queue workload exactly x: the lookback net input increases to x over the burst and then decreases with slope $\mu -C<0$. Its action is $tg(v)=xg(v)/(v-C)$. Taking the infimum over v proves the matching upper bound. The typical-rate path has zero queue workload and zero cost. ThereforeStrict convexity and $g(\mu )=0$ ensure $\gamma >0$ whenever it is finite. Indeed, choose a finite-cost $v>C$ and some $u\in (\mu ,C)$; then $g(u)>0$, and convexity gives $g(v)/(v-C)\ge g(u)/(u-\mu )$ for every finite-cost $v>C$. Thus J is increasing on nonnegative queue workloads, and the preceding fiber bound yields $\boxed{\bar{J}(x)\ge J(x)\text{ for }x\ge 0}$. Negative values are impossible for both queue workloads and have infinite rate. No monotonicity is asserted across that impossible negative domain.

Take $0<x\le B$ and a finite-cost burst rate $v>C$. For the constant-rate burst path just constructed, let $t_0=x/(v-C)$. On $0\le s\le t_0$ its net input is $z(s)=(v-C)s$, so the supremum is x and the infimum is zero. The finite-buffer formula evaluated at $t=t_0$ is therefore $\min (x,B)=x$. Since $\bar{q}\le q=x$, we conclude $\bar{q}=x$ exactly: the burst never needs more space than the permitted capacity.

That path's action bounds the contracted finite-buffer rate, and optimizing givesAt zero use the typical-rate path to obtain $\bar{J}(0)=J(0)=0$. If the positive infinite-buffer rate is infinite, the asserted upper inequality is automatic. Approximating burst rates suffice, so the argument does not rely on an unproved existence of an optimal duration. Consequently $\boxed{\bar{J}(x)\le J(x)\text{ for }0\le x\le B}$.

For $0\le x\le B$, the two variational comparisons agree. Outside that interval the finite-buffer fiber is empty, since its queue workload always lies in $[0,B]$. The finite-buffer workload rate truncation is thereforeEquivalently this is J for $x\le B$ and infinity above B, since J already assigns infinity to negative queue workloads. Together with the contracted LDP from the first part, this proves the requested principle. The rate is good by contraction; alternatively its finite sublevel sets are the compact sets $\{J\le M\}\cap [0,B]$.