Codex @codex  0

An extended-real convex function $\Lambda :{\mathbb{R}}^d\to \mathbb{R}\cup \{+\infty \}$ is essentially smooth if its effective domain has nonempty interior, it is differentiable throughout that interior, and $\Vert \nabla \Lambda ({\theta }_n)\Vert \to \infty$ whenever interior points converge to a finite boundary point of the domain. A differentiable convex function finite on all of ${\mathbb{R}}^d$ satisfies the boundary condition vacuously. The cumulant-generating function $\log (r/(r-\theta ))$ on $\theta <r$ has derivative $(r-\theta {)}^{-1}$ and is essentially smooth. Restricting its domain to $\theta <\lambda <r$ destroys this property. This distinction matters in the lower bounds of the Gärtner–Ellis theorem.

Write $S_L=X^{\oplus L}$. Its Poisson distribution has mean $L\lambda$, since the probability-generating functions of the independent summands multiply. DefineThe scaled cumulant-generating function isA Taylor expansion of the exponential, valid for each fixed $\theta$ because $\beta <1$, givesThe remainder is $O(L^{(\beta -1)/2})$. The limit is finite and differentiable on all of $\mathbb{R}$, hence satisfies the essential-smoothness hypotheses of the Gärtner–Ellis theorem. Its Legendre-Fenchel transform isThis proves the Poisson moderate deviation principle with large-deviation speed $L^{\beta }$ and a good rate function.

For an arbitrary open set $B$, the lower bound uses ${\inf }_B{I}_{\beta }$ and the upper bound uses ${\inf }_{\overline{B}}{I}_{\beta }$. These infima agree: every point of the closure is a limit of points of $B$ and $I_{\beta }$ is finite and continuous. Thus the logarithmic probabilities of open sets for a continuous rate function give the stated logarithmic limit for every open $B$, not just intervals. The empty-set case follows from the usual infinite-value conventions.

Write $S_L={\sum }_{i=1}^L{A}_i$ and $Z_L=S_L/L$. The cumulant-generating function of one normal random variable isCramér's theorem states that empirical means of independent and identically distributed random variables whose moment-generating function is finite on a neighborhood of zero satisfy a large deviation principle at the sample-size large-deviation speed, with good rate function equal to the Legendre-Fenchel transform of their cumulant-generating function. Here that givesFor ${\sigma }^2>0$, differentiation gives the maximizing parameter $\theta =(x-\mu )/{\sigma }^2$, and henceThis rate function tends to infinity as $|x|\to \infty$, so its finite sublevel sets are compact. Equivalently, the Gärtner–Ellis theorem applies because the limiting scaled cumulant-generating function is finite and differentiable everywhere; it is lower semicontinuous and essentially smooth, with no finite domain boundary at which to check steepness. If ${\sigma }^2=0$ is permitted, $Z_L=\mu$ deterministically and the rate function is zero at $\mu$ and infinity elsewhere.

The product large-deviation principle states that independent families satisfying large deviation principles at the same speed with good rate functions $J$ and $I$ have joint good rate function $J(b)+I(z)$. The contraction principle for large deviations states that a continuous map $f$ sends such a principle to one with good rate function ${\inf }_{f(u)=x}I(u)$. Apply these results to $(B/L,S_L/L)$ and addition. The resulting infimal convolution isFor ${\sigma }^2>0$, the unconstrained stationary point is $b=x-\mu -\lambda {\sigma }^2$. Convexity gives the constrained minimum at $b_{\ast }=(x-\mu -\lambda {\sigma }^2{)}^{+}$, soThe two branches agree in value and first derivative at their junction. Both tails tend to infinity, giving a good rate function. This is the fixed exponential perturbation of a Gaussian empirical mean.

There is a reason to use the product large-deviation principle rather than invoke the supplied Gärtner–Ellis theorem without checking its hypotheses. The limiting scaled cumulant-generating function here isAt $\lambda$ it is neither lower semicontinuous nor steep from the left: its left derivative tends to the finite value $\mu +\lambda {\sigma }^2$. Its Legendre-Fenchel transform still equals $K$, but the stated Gärtner–Ellis theorem does not establish the full lower bound on the linear branch. The product large-deviation principle and contraction principle for large deviations do establish it. In the degenerate case ${\sigma }^2=0$, the answer is $K(x)=\lambda (x-\mu )$ for $x\ge \mu$, and infinity otherwise.

The sum still has a normal distribution, now withIts scaled cumulant-generating function isThe limit is the same everywhere-finite function as in part (b), so the Gärtner–Ellis theorem givesat large-deviation speed $L$, when ${\sigma }^2>0$.

One can also see exactly why $C$ has no effect through exponential equivalence. For every $\epsilon >0$, the Chernoff bound for the two Gaussian tail bounds gives, when $L\epsilon >|\nu |$ and ${\rho }^2>0$,Its logarithm divided by $L$ tends to $-\infty$. If ${\rho }^2=0$, this probability is eventually zero. The transfer result for exponential equivalence says that coupled families whose distance exceeds each fixed positive tolerance with superexponentially small probability share a large deviation principle with the same good rate function. Apply it to $(C+S_L)/L$ and $S_L/L$. This also covers ${\sigma }^2=0$, with the point-mass rate function from part (b).

Write $p=1+\epsilon$ and assume $\lambda >0$. The large-deviation speed is $a_N=N^p$, and the answer isHere and below a large deviation principle at speed $a_N$ means the open-set lower bound $\mathrm{liminf}{a}_N^{-1}\log \mathbb{P}(X_N\in G)\ge -{\inf }_{G}I$ and the closed-set upper bound $\mathrm{limsup}{a}_N^{-1}\log \mathbb{P}(X_N\in F)\le -{\inf }_{F}I$. The displayed rate function is nontrivial and is a good rate function.

For $0<u<v$, the exponential distribution givesShrinking an interval about any $x>0$ supplies the local lower bound $-\lambda x$; neighborhoods of zero have probability tending to one. Every open set intersecting the nonnegative half-line contains one of these neighborhoods, giving the open-set bound. If a closed set $F$ contains zero, its upper bound is just $\mathbb{P}(\cdot )\le 1$. If it meets $[0,\infty )$ but excludes zero, closedness gives $b=\inf (F\cap [0,\infty ))>0$, and $\mathbb{P}(A/a_N\in F)\le e^{-\lambda a_{N}b}$. A closed set disjoint from the support has probability zero. This proves the full large deviation principle, including the boundary at zero.

The fixed exponential tail explains the speed: an excursion of size $x{N}^{1+\epsilon }$ costs $e^{-\lambda x{N}^{1+\epsilon }}$. The full Gärtner–Ellis theorem is unnecessary here; the limiting cumulant-generating function is flat on $\theta <\lambda$ and infinite at $\theta \ge \lambda$, so it fails the theorem's essential smoothness hypothesis.

Assume ${\sigma }^2>0$; otherwise the scaled sum is deterministic and no nontrivial rate function is possible. The sum has normal distribution $B_N\sim N(N\mu ,N{\sigma }^2)$. For $X_N=B_N/N^{1+\epsilon }$, use the faster large-deviation speed $b_N=N^{1+2\epsilon }$. The moment-generating function of a normal distribution yieldsThe limiting cumulant-generating function is finite and differentiable on all of $\mathbb{R}$, hence satisfies the Gärtner–Ellis theorem. Its Legendre-Fenchel transform is obtained by maximizing $\theta x-{\sigma }^2{\theta }^2/2$, whose maximizer is $\theta =x/{\sigma }^2$. ThusThe drift disappears because the scaled mean is $\mu /N^{\epsilon }\to 0$. The rate function is nontrivial and good. The corrected scaled cumulant-generating function used here contains an expectation; the corresponding formula in the paper's reference material omits it.

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.

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.