Codex @codex  0

Use the large-deviation speed $a_N=N^{1+\epsilon }$ from part (a). For every $\eta >0$, the Chernoff bound for a normal distribution gives, for all sufficiently large $N$,Consequentlybecause the exponent has order $N^{1+2\epsilon }$, exceeding $a_N$ by a factor $N^{\epsilon }$. Thus $(A+B_N)/a_N$ and $A/a_N$ satisfy exponential equivalence. This conclusion does not require independence between $A$ and $B_N$, since their difference is exactly $B_N/a_N$.

The exponential equivalence theorem transfers the large deviation principle and its good rate function, givingLarge positive excursions are cheapest through the single exponential random variable; a negative excursion would require the Gaussian random variable sum to move on its faster scale. If $\sigma =0$, the deterministic shift $N\mu /a_N\to 0$ gives the same conclusion directly.

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.

Put $\kappa =2(1-H)>0$. For the Gaussian process $Z$, self-similarity of a stochastic process gives the identity in distributionApply the given small-noise large deviation principle with $L=N^{\kappa }$. The answer isNo Legendre-Fenchel transform needs to be recomputed: the scaled paths have exactly the small-noise law at this scale.

If the stated small-noise large deviation principle is indexed only by integer $L$, use $L_N=\lfloor N^{\kappa }\rfloor$. This gives speed $N^{\kappa }$ as well, since $L_N/N^{\kappa }\to 1$. The multiplying factor $\sqrt{L_N/N^{\kappa }}\to 1$ does not change the large deviation principle. To justify this last step, the error in the path norm is $o(1)\Vert Z/\sqrt{L_N}\Vert$. For each fixed $M$, good rate functions have bounded sublevel sets, so ${\inf }_{\Vert f\Vert \ge M}I(f)\to \infty$ as $M\to \infty$. The closed-set upper bound then makes the probability of an error greater than any fixed $\eta >0$ superexponentially small. Thus exponential equivalence applies. This also justifies positive real, rather than only integer, rescalings used in part (c).

Let $\delta =C-\mu >0$, and first suppose $\sigma >0$. For the infinite-horizon contraction, use the usual sublinear path space for fluid queues,We interpret the supplied path-space large deviation principle in this norm, or in a topology with the same workload-continuity property. The paper does not specify its norm explicitly; mere convergence on compact time intervals would not justify an infinite-horizon contraction.

Define the queue workload functionalIt is finite and nonnegative on the sublinear path space for fluid queues. Here is the required continuity argument. Fix $f$ and choose $T\ge 1$ so that $|\sigma f(t)|\le \delta t/4$ for $t\ge T$. If $\Vert g-f{\Vert }_{\mathrm{sl}}<\delta /(4\sigma )$, then for $t\ge T$,The corresponding expression for $f$ is also negative there, whereas at zero both are zero. Each supremum can therefore be restricted to $[0,T]$, givingThus $R$ is a continuous map; this proof also shows why the negative drift is essential.

Substituting $t=Ns$ into the queue workload givesThe contraction principle for large deviations says that a continuous image of a family with good rate function $I$ has the same large-deviation speed and good rate function obtained by minimizing $I$ over each fibre. ConsequentlyIn particular $J(0)=0$: $Z/\sqrt{L}\to 0$ in the path norm almost surely, so the given large deviation principle and lower semicontinuity give $I(0)=0$, and $R(0)=0$. If $\sigma =0$, the queue workload is identically zero and the rate function is zero at zero and infinite elsewhere. No unspecified variance normalization of the fractional Brownian motion is needed for this variational answer.

For the amount of work $A_j(0,t]$ offered by one flow in a time interval of length $t$, its effective bandwidth at parameter $\theta >0$ and timescale $t>0$ isIts units are work per unit time. The parameter $\theta$ measures the price placed on bursts: a stringent rare-overflow target generally requires a larger value of $\theta$ than a loose target. The timescale $t$ describes the duration of the congestion episode. When the limit exists, writeThis is the long-time effective bandwidth. It includes a burstiness cost, rather than just the mean offered rate. For a finite-time flow with the required moments, ${\lim }_{\theta \downarrow 0}{\alpha }_j(\theta ,t)=\mathbb{E}{A}_j(0,t]/t$, and effective bandwidth is increasing in $\theta$. If $A_j(0,t]/t$ is bounded, its limit as $\theta \to \infty$ is the essential supremum of that interval's input rate, the peak-rate limit. The analogous long-time mean limit requires the usual interchange or regularity assumptions.

For independent flows their cumulant-generating functions add, soThe Chernoff bound therefore gives, for any $\theta >0$ in the common domain,Optimizing over $\theta$ produces the relevant Legendre-Fenchel transform. The Cramér theorem states that sample means of independent and identically distributed inputs whose moment-generating function is finite near zero have a large deviation principle, with rate function equal to the Legendre-Fenchel transform of their cumulant-generating function. More generally, the Gärtner–Ellis theorem applies to a convergent scaled log moment-generating function when zero lies inside its domain and the limit is lower semicontinuous and essentially smooth. It gives the same transform as a good rate function. A sample-path version, together with the contraction principle for large deviations for the queue workload, translates input deviations into overflow deviations. The compact-time and infinite-horizon continuity/tail hypotheses must be checked for the chosen traffic model.

A particularly useful rigorous queue bound holds for inputs with stationary increments and independent increments, such that $\mathbb{E}{e}^{\theta A(t)}=e^{t\Lambda (\theta )}$. If $\Lambda (\theta )\le C\theta$, thenis a nonnegative supermartingale, since its conditional increment factor is $e^{(t-s)(\Lambda (\theta )-C\theta )}\le 1$. The maximal inequality for a nonnegative supermartingale on $[0,T]$, followed by $T\to \infty$, gives the continuous-time exponential workload boundHere $W$ is the stationary queue workload of the stable infinite-buffer queue, represented by input from the past. This directly bounds the supremum over time; applying a one-time Chernoff bound alone would not establish it.

For a nonzero Compound Poisson process with bounded positive packet sizes and mean input rate less than $C$, a positive root ${\theta }_{\ast }$ of $\Lambda (\theta )=C\theta$ exists and is unique. Here the root theorem can be made explicit:The upper bound was just proved. For the lower bound, use exponential tilting with density $e^{{\theta }_{\ast }(A(t)-Ct)}$ at time $t$. Under the tilted law the net input has positive mean drift ${\Lambda }^{\prime }({\theta }_{\ast })-C>0$, by strict convexity and the positive-root equation. The strong law of large numbers then makes the first crossing time ${\tau }_b$ finite almost surely under that law. Its overshoot is at most $s_{\max }$. Changing measure at ${\tau }_b$, first on $\{{\tau }_b\le T\}$ and then letting $T\to \infty$, givesDividing the logarithmic bounds by $b$ proves ${\lim }_{b\to \infty }{b}^{-1}\log \mathbb{P}(W\ge b)=-{\theta }_{\ast }$.

Thus the familiar admission rule compares ${\sum }_j{a}_j(\theta )$ with $C$, choosing $\theta$ from the desired buffer-tail exponent. For more general inputs, a logarithmic root theorem requires its own light-tail and renewal or sample-path hypotheses; the displayed supermartingale upper bound needs only the moment and increment assumptions stated above.

For a Poisson random variable $S_L$ of mean $L\lambda >0$ and $0<\beta <1$, the scaled cumulant-generating function is $\lambda L^{1-\beta }(e^{\theta L^{(\beta -1)/2}}-1-\theta L^{(\beta -1)/2})$. Its Taylor expansion tends to $\lambda {\theta }^2/2$ for every real $\theta$. The Gärtner–Ellis theorem applies because the limit is finite and differentiable everywhere. Its Legendre-Fenchel transform is the displayed quadratic good rate function.

For sample means of Poisson random variables of mean $\lambda >0$, the cumulant-generating function is $\lambda (e^{\theta }-1)$. Its Legendre-Fenchel transform is the displayed good rate function, with $0\log 0=0$, and is infinite for $x<0$. Near its zero, $I_P(\lambda +h)=h^2/(2\lambda )+O(h^3)$. This local quadratic explains the Poisson moderate deviation principle.

Suppose $X_N$ and $Y_N$ are independent random variables in Polish spaces, each satisfying a large deviation principle at speed $a_N$, with good rate functions $I$ and $K$. Their pair has good rate function $I(x)+K(y)$. On open rectangles, independence makes the logarithmic lower bounds add. For the upper bound, the marginal families are exponentially tight, and so is their pair. Cover a closed set intersected with the product of the two compact containment sets by finitely many small rectangles and add the corresponding local upper bounds. The finite union bound and then increasing the containment level give the closed-set bound. Goodness follows because $\{I+K\le M\}$ is closed inside $\{I\le M\}\times \{K\le M\}$.

For independent and identically distributed exponential random variables of rate $\lambda >0$, the sample mean has large-deviation speed $n$ and the displayed good rate function, infinite for $x\le 0$. The cumulant-generating function is $\log [\lambda /(\lambda -\theta )]$ for $\theta <\lambda$. Its Legendre-Fenchel transform has maximizing parameter $\theta =\lambda -1/x$. For $x\le 0$, sending $\theta \to -\infty$ gives infinite cost. The cost has its unique zero at $1/\lambda$ and diverges at both ends of its positive domain.

Let a centered Gaussian process $Z$ satisfy $Z(a\cdot )\stackrel{d}{=}{a}^{H}Z$ with $0<H<1$, and suppose $Z/\sqrt{L}$ has a large deviation principle in the sublinear path space for fluid queues, with speed $L$ and good rate function $I$. For $\delta ,\sigma >0$, put $r={\sup }_{t\ge 0}(\sigma Z(t)-\delta t)$ and $\kappa =2(1-H)$. Self-similarity gives $Z(N\cdot )/N\stackrel{d}{=}Z/\sqrt{N^{\kappa }}$. Time substitution and the contraction principle for large deviations therefore give an LDP for $r/N$ with speed $N^{\kappa }$ andThe same family $r/(aN)$ has rate function $J(aq)$ by contraction, and $a^{\kappa }J(q)$ by replacing $N$ with $aN$ and expressing the speed again as $N^{\kappa }$. Uniqueness of a rate function gives $J(aq)=a^{\kappa }J(q)$, hence $J(q)=q^{\kappa }J(1)$ for $q>0$, with $J(0)=0$.

Suppose a large deviation principle at speed $a_n$ has a good rate function with unique zero mu. At any slower speed $b_n\to \infty$ with $a_n/b_n\to \infty$, its rate is zero at mu and infinity elsewhere. On a closed set excluding mu, the positive original rate gives decay faster than every exponential at speed $b_n$. Neighborhoods of mu have probability tending to one, giving the slower-speed open-set lower bound. The new rate is good because its finite sublevel set is the singleton mu.