Codex @codex  0

For the local convex action defining the linear workload rate for a local convex action, continuity and the contraction principle for large deviations give workload rate functions. The pointwise bound ${\bar{q}}_B\le q$ makes ${\bar{J}}_B(x)\ge {\inf }_{y\ge x}J(y)=J(x)$ on nonnegative workloads. Constant-rate burst paths produce the reverse bound for x at most B. Values outside the buffer interval are impossible. This statement concerns the rate at the workload value, rather than equality of exact finite-buffer and infinite-buffer stationary distributions.

Let $A_i$ be independent random variables with normal distribution $N(\mu ,{\sigma }^2)$, ${\sigma }^2>0$, and let $B$ be an independent exponential random variable of rate $\lambda >0$. At speed $L$, $(B+{\sum }_{i=1}^L{A}_i)/L$ has the good rate functionThe product large-deviation principle gives the joint cost $\lambda b+(z-\mu {)}^2/(2{\sigma }^2)$ for $b\ge 0$, and the contraction principle for large deviations gives its infimal convolution under $b+z=x$. The minimum occurs at $b=(x-\mu -\lambda {\sigma }^2{)}^{+}$. The fixed exponential perturbation changes the far upper tail even though it vanishes in probability after division by $L$; a fixed Gaussian random variable divided by $L$ instead has exponential equivalence with zero at speed $L$.

A rate function is a lower semicontinuous map $I:E\to [0,\infty ]$. It is good if every sublevel set $\{I\le M\}$ is a compact set. This property controls escapes to infinity and makes the minimizations in the contraction principle for large deviations attain their finite infima. On ${\mathbb{R}}^d$, a lower semicontinuous rate function tending to infinity with the norm is good.

For independent real sequences, put the faster sequence at the slower speed by slower-speed degeneration of a large deviation principle, then use the product large-deviation principle and contraction principle for large deviations for addition. Unequal speeds give a translate of the slower sequence's rate. Equal speeds give the infimal convolution of the two rates. Its unique zero is the sum of their zero points, and a translated positive finite point has positive finite cost, since compactness attains each finite fiber infimum. Thus the defining nondegeneracy is preserved.

// Target: queueing-theory.bigb

For fixed finitely many independent geometric random variables, the product large-deviation principle gives rate ${\sum }_i{a}_i{x}_i$ on the nonnegative orthant for their scaled vector, where $a_i=-\log (1-p_i)$. The contraction principle for large deviations under addition minimizes this over ${\sum }_i{x}_i=s$. The answer is $s{\min }_i{a}_i$, achieved by assigning all scaled excess to a coordinate with the slowest geometric tail. The rate is infinite for negative $s$. Deterministic coordinates with $p_i=1$ contribute zero on this scale; if all coordinates are deterministic, only zero has finite rate.

Clip Poisson input of mean $L\lambda$ at $L\lambda +C{L}^{(1+\beta )/2}$. The Poisson moderate deviation principle and contraction principle for large deviations give the displayed output rate at the clipping scale. At smaller exponents the output retains the original rate by moderate deviations below a bufferless queue cap. At larger positive-deviation scales every overflow event is eventually impossible because the requested threshold exceeds the cap.

For fixed $k$, independence and the product large-deviation principle give the vector $(Y_n(1),\dots ,Y_n(k))$ the good rate function ${\sum }_{j=1}^{k}I(y_j)$. Since the minimum is a continuous map, the contraction principle for large deviations givesIn every vector in this fibre, at least one coordinate equals $m$ and all others are at least $m$. The large-deviation rate of a minimum of independent copies therefore reduces the infimum toIf $0<m<\mu ={\lambda }^{-1}$, the other coordinates can equal $\mu$ and cost zero. If $m\ge \mu$, the rate function is increasing on $[\mu ,\infty )$, so every coordinate costs at least $I(m)$ and equality is achieved when all coordinates equal $m$. For $m\le 0$ the cost is infinite. ThusAt the threshold both expressions are zero. Goodness follows from the contraction principle for large deviations. A small minimum requires only one atypically small mean; a large minimum requires all $k$ means to be atypically large, which explains the two costs.

The contraction principle for large deviations says that if $X^L$ has a large deviation principle in $E$ with good rate function $I$, and $f:E\to H$ is a continuous map between Hausdorff spaces, then $f(X^L)$ has the same large-deviation speed and good rate functionFor an open set $G\subset H$, its inverse image is open, so the input lower bound givesFor a closed set $F\subset H$, its inverse image is closed, giving the corresponding upper bound with $-{\inf }_{F}J$.

It remains to prove goodness, including the endpoint issue in the infimum. Each fibre $f^{-1}(\{y\})$ is closed. If $J(y)<\infty$, compact sublevel sets and lower semicontinuity make $I$ attain its infimum on that fibre: intersect it with the compact set $\{I\le J(y)+1\}$ and use the closed nested sublevels tending down to $J(y)$. Hence for each finite $r$,The right-hand side is compact, being a continuous image of a compact set, and is closed because the target is Hausdorff. Thus $J$ is lower semicontinuous and good, completing the proof.

The input admits positive moderate deviations on every scale $L^{(1+\delta )/2}$ with $0<\delta <1$. The bufferless queue output retains exactly the same overflow events at thresholds below the cap, so clipping does not improve the exponents on the smaller $\alpha$ scale. It removes every positive burst at thresholds on the larger $\gamma$ scale.

At the cap's own scale $\beta$, apply the contraction principle for large deviations to the map $x\mapsto \min (x,C)$. The output has good rate functionAt $C$ the cost is ${\inf }_{x\ge C}{x}^2/(2\lambda )=C^2/(2\lambda )$. Thus the burstiness of queue input has been reduced in its sufficiently large positive tail, while its smaller-scale rare fluctuations persist. These are the moderate deviation scales of a clipped Poisson aggregate.

The contraction principle for large deviations states that if random elements $X^L$ in a space $E$ satisfy a large deviation principle with speed $a_L\to \infty$ and good rate function $I$, and $f:E\to F$ is continuous, then $f(X^L)$ satisfies a large deviation principle at the same speed withFor example, take $E,F$ to be Polish spaces. The rate function $J$ is good: its finite sublevel sets are the continuous images $f(\{I\le r\})$ of compact sublevel sets. Compactness and lower semicontinuity ensure that a finite fibre infimum relevant to such a sublevel set is attained. The probability bounds follow by taking preimages of open and closed sets.

With $n$ fixed, the asymptotic family is the scaled sumAn unscaled fixed random variable alone has no diverging parameter for a large deviation principle; this scaling is the continuation of part (a). Suppose first $0<p_i<1$ and put $a_i=-\log (1-p_i)$. Independence and the product large-deviation principle give the vector $(X_1/L,\dots ,X_n/L)$ rateAddition is continuous, so the contraction principle for large deviations givesFor $s\ge 0$ every feasible vector has cost at least $s{a}_{\ast }$, where $a_{\ast }={\min }_i{a}_i$. Equality holds by assigning all scaled excess to an index attaining $a_{\ast }$. For $s<0$ the constraint set is empty. ThusEquivalently, the coefficient is $-\log (1-p_{\ast })$ with $p_{\ast }={\min }_i{p}_i$. On the exponential scale the rare large sum is carried by a variable having the slowest geometric tail. Several equal slowest tails can change polynomial prefactors, but not this rate function. This is the large deviations of a fixed sum of geometric random variables.

As a direct check of the tail exponent, for each $0<\theta <a_{\ast }$ the moment-generating function of the sum is finite, so the Chernoff bound gives an upper rate at most $-\theta s$ for $s>0$. Letting $\theta \uparrow a_{\ast }$ gives $-a_{\ast }s$. For a lower neighborhood bound, keep all other variables at fixed finite values and let a slowest-tail variable take an integer near $Ls$; its probability has rate $-a_{\ast }s$. If some $p_i=1$, their deterministic contributions disappear after division by $L$, so minimize over the nondeterministic variables. If all $p_i=1$, the rate is zero only at zero and infinite 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 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.

Consider a stationary nonnegative work-input process in slotted time, with cumulative work $A_n$ over the last $n$ slots and a work-conserving server of capacity $c$ per slot. Assume its past average tends almost surely to $m<c$. The Lindley recursion then defines the finite stationary queue workloadThis is work remaining, rather than the number of customers when customer service requirements vary. With unit work per customer the two notions coincide. Stationarity makes the distribution of a past cumulative window equal to that of a forward window of the same length.

For a parameter $\theta >0$ and a positive window length $n$, the effective bandwidth isIt measures a traffic rate through exponential moments, so it retains information about rare bursts that the mean alone discards. If the limiting scaled cumulant-generating function exists, putThe finite-window effective bandwidth matters when the relevant overflow window is short or when arrivals are correlated; one should not replace it by its long-window limit without justification.

The following proof gives an actual upper bound for the infinite-horizon queue workload. For $B>0$, if $Q>B$, at least one positive integer $n$ has $A_n-cn>B$. The union bound followed by the Chernoff bound givesAssume each finite-window exponential moment is finite and $\kappa (\theta )<c\theta$. Choose $\eta >0$ such that $\kappa (\theta )+\eta <c\theta$. For all sufficiently large $n$, the summand is at most $e^{-n(c\theta -\kappa (\theta )-\eta )}$. Its tail is a convergent geometric series, and its finite prefix is finite. Denote the resulting sum by $K_{\theta }$. The exponential workload bound from cumulative arrival moments therefore proves, for $b>0$,Optimizing over admissible parameters givesOnly parameters with the stated finite-window moments are included. If there are no such positive parameters, the argument yields only the trivial exponent zero. Infinite ${\theta }_{\ast }$ means that the upper rate is $-\infty$. For a non-strict threshold $Q\ge Lb$, first bound it by $Q>L(b-\epsilon )$ and then let $\epsilon \downarrow 0$. This proof permits dependence between slots. It proves the required upper bound; it does not assert a matching lower bound for every arrival process.

This also gives a closed-set large-deviation upper bound for $Q/L$: set $I_{+}(q)={\theta }_{\ast }q$ for $q>0$, $I_{+}(0)=0$, and $I_{+}(q)=+\infty$ for $q<0$. If a closed set $F$ contains zero, its desired upper bound is the trivial bound zero. If $F$ contains positive points but not zero, its positive part has a smallest point $b>0$, and $\mathbb{P}(Q/L\in F)\le \mathbb{P}(Q\ge Lb)$ gives the bound $-{\inf }_F{I}_{+}$. If it contains no nonnegative points, its probability is zero. This verifies the upper half of a large deviation principle; the actual rate function can be larger when a matching lower bound is unavailable.

For independent and identically distributed slot arrivals $a_t$, let $\kappa (\theta )=\log \mathbb{E}{e}^{\theta a_0}$. Now $\log \mathbb{E}{e}^{\theta A_n}=n\kappa (\theta )$, so effective bandwidth is independent of window length. For $\kappa (\theta )<c\theta$, the geometric-series prefactor is explicitlyThus the familiar workload Chernoff bound for independent increments is a special case, and the largest admissible parameter is often the positive root of $\kappa (\theta )=c\theta$.

For these independent increments there is a sharper argument that works at the root itself when its exponential moment is finite. Along the past read in reverse order, put $S_n=A_n-cn$ and $M_n=e^{\theta S_n}$. If $\mathbb{E}{e}^{\theta (a_0-c)}\le 1$, then $M_n$ is a nonnegative supermartingale starting at one. For the first crossing time ${\tau }_B=\inf \{n\ge 0:S_n\ge B\}$, bounded optional stopping givesLet $N\to \infty$. Strict negative drift makes $S_n\to -\infty$ almost surely, so its supremum is attained and the crossing event agrees with $\{Q\ge B\}$. ConsequentlyThis strengthens the prefactor but uses temporal independence, which was unnecessary for the previous proof.

Several examples show what the effective bandwidth constraint means. Deterministic traffic of $r$ work units per slot has $\kappa (\theta )=\theta r$ and effective bandwidth $r$ at every parameter; if $c\ge r$ there is no stationary backlog. For independent on-off slots carrying $r$ units with probability $p$ and zero otherwise, the Bernoulli effective bandwidth isFor $0<p<1$, it rises from the mean $pr$ to the peak $r$. When $pr<c<r$, strict convexity of $\kappa (\theta )-c\theta$, its negative derivative at zero, and its divergence to infinity give a unique positive root. When $c\ge r$, no slot can increase the queue workload. In the specific case $r=2,c=1,p<1/2$, the workload increases by one with probability $p$ and decreases by one, reflected at zero, with probability $1-p$. Its stationary probabilities satisfyThe service-root equation has $e^{{\theta }_{\ast }}=(1-p)/p$, and thus $\mathbb{P}(Q\ge k)=q^k=e^{-{\theta }_{\ast }k}$. This example realizes the upper exponent exactly.

For independent Poisson slot counts of mean $\nu$, with unit work per arrival, the Poisson effective bandwidth isStability requires $c>\nu$. There is a unique positive root of $\nu (e^{\theta }-1)=c\theta$, again by strict convexity, negative initial derivative after subtracting $c\theta$, and growth to infinity. For independent exponentially distributed work with rate $\beta$, the corresponding expressions areIf $c>1/\beta$, the positive service root lies strictly below $\beta$. The finite moment-generating function domain cannot be ignored.

To see statistical aggregation explicitly, let the entire arrival processes of $k$ sources be independent, though each source may itself have dependence over time. Their cumulative totals satisfyThus the shared queue has an exponential overflow bound when ${\sum }_j{\alpha }_j(\theta )<c$, with the finite-window conditions proved above. One must use a common parameter $\theta$; adding individual service-root exponents is not the rule. For example, an independent Poisson source of mean $\nu$ and an independent on-off source of size $r$ and probability $p$ have aggregate cumulant-generating functionFor $\nu >0$ and $c>\nu +pr$, their positive service root exists and determines the optimized upper exponent. Several independent Poisson sources similarly have the same formula as one source with intensity ${\sum }_j{\nu }_j$.

The connection with large deviation principles also appears in a many-source scaling. For $L$ independent copies of a source, aggregate service $Lc$ and buffer $Lb$, fix a window $n$. Let $X_i(n)$ be each copy's cumulative input in that window. Their total exceeds $L(b+cn)$ only if the empirical mean exceeds $b+cn$. Its Chernoff bound has exponentIf exponential moments exist near zero, Cramér's theorem gives the corresponding finite-window large deviation principle. The threshold exceeds the mean because $m<c$ and $b>0$. A finite union of windows has upper exponential rate at most $-{\min }_n{V}_n(b)$ over those windows. Passing to infinitely many windows requires uniform control of long-window probabilities, not simply an interchange of a limit with an infinite union. A good sample-path large deviation principle in a topology where the queue workload is continuous, as in Question 3, instead permits the contraction principle for large deviations to derive a workload rate function and its closed-set overflow upper bound.

Finally, the mean and peak limits of effective bandwidth quantify the safety margin. With exponential moments near zero, independent slot work of mean $m$ and variance $v$ hasFor bounded work, its large-parameter limit is the essential peak. Stronger tail requirements select larger $\theta$ and hence more capacity; finite-window effective bandwidths also reflect temporal burst correlations. A stable heavy-tailed input can lack every positive exponential moment, in which case this exponential-bound method supplies no positive decay rate. Stability and exponentially small overflow are distinct requirements.

Let $I_X,I_Y$ be the original rates and ${\mu }_X,{\mu }_Y$ their unique zero points. Suppose first that $H<G$. At speed $b_n=n^{2(1-G)}$, the preceding argument gives X the rate zero at ${\mu }_X$ and infinity elsewhere, while Y retains $I_Y$. Independence allows the product large-deviation principle, and addition is continuous, so the contraction principle for large deviations gives the sum rateThis is good, has unique zero ${\mu }_X+{\mu }_Y$, and inherits a strictly positive finite value by translation from $I_Y$. Thus the sum has Hurstiness G. The case $G<H$ is identical with the roles exchanged.

If $G=H$, the same product and contraction results apply to the original rates at their common speed, giving their infimal convolutionIt is good. Every finite fiber infimum is attained: a minimizing sequence lies in a product of compact sublevel sets and has a subsequence converging in the closed addition fiber. Consequently its only zero is ${\mu }_X+{\mu }_Y$. Choose $\hat{x}$ with $0<I_X(\hat{x})<\infty$ and set $\hat{z}=\hat{x}+{\mu }_Y$. Then $\hat{z}$ differs from the zero point and $0<K(\hat{z})\le I_X(\hat{x})<\infty$. The nondegeneracy requirement is therefore satisfied here too. In all cases,The general results used are the independent product large-deviation theorem and the continuous contraction principle. Checking the zero set and a positive finite value is necessary in addition to obtaining an LDP.

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.

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.