Codex @codex  0

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.

Put $s_i={\sup }_{C_i}f$ and omit empty sets. Since the sets cover the space, boundedness givesFor nonnegative numbers $u_{n,i}$, their sum lies between their maximum and m times their maximum. Consequently its scaled logarithmic upper limit is at most ${\max }_i{\mathrm{limsup}}_n{n}^{-1}\log u_{n,i}$; the added $n^{-1}\log m$ vanishes. Each $C_i$ is closed, so the upper bound in the large deviation principle givesThe convention $\log 0=-\infty$ also handles sets of zero probability or infinite infimum rate.

The continuity of f makes its prescribed interval preimage B open, and $\hat{x}\in B$. On B we have $f(x)>f(\hat{x})-\epsilon$, soThe open-set lower bound of the large deviation principle therefore yieldsThus the claimed lower bound holds at every chosen point. When $I(\hat{x})=\infty$ its right side is minus infinity and the assertion is immediate.

Let epsilon decrease to zero in the upper estimate. In the lower estimate first take the supremum over all chosen points and then decrease epsilon to zero. The bounds coincide, proving Varadhan lemma:The value is finite: f is bounded, $I\ge 0$, and the large-deviation bounds on the whole space force $\inf I=0$. This proof actually uses bounded continuity and the large deviation principle; compact sublevels are not additionally needed for this bounded version.

Write $a_n=n^{2(1-H)}$ and $b_n=n^{2(1-G)}$. Then $a_n/b_n=n^{2(G-H)}\to \infty$. The large deviation principle on the whole space forces $\inf I=0$; compact sublevel sets and lower semicontinuity make that infimum attained. The unique possible zero is therefore mu, and $I(\mu )=0$.

If a closed set C contains mu, its new infimum rate is zero and the claimed upper bound follows from probabilities being at most one. If it excludes mu, then $\eta ={\inf }_{C}I>0$, possibly infinite: otherwise a sequence of rates tending to zero would have a convergent subsequence in a compact sublevel set, with limit in C and zero rate, contradicting uniqueness. This is the fact that a good rate function is separated from zero away from its minimizer.

Choose any $0<c<\eta$. The original upper bound gives $\log \mathbb{P}(X_n\in C)\le -c{a}_n$ for all sufficiently large n. ThusTogether these cases prove the closed-set upper bound at the slower speed, with rate zero only at mu. Its finite sublevels are the compact singleton $\{\mu \}$, so it is a good rate function.

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.

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$.

Write $S_N={\sum }_{i=1}^N{T}_i$. The answer isThe sum of exponential variables with linearly increasing rates has the distribution of the maximum of $N$ independent rate-$\lambda$ exponential random variables. To prove this identity, start $N$ independent rate-$\lambda$ exponential clocks. The first rings after a rate-$N\lambda$ exponential time; the memoryless property leaves $N-1$ fresh independent clocks. Repeating this argument shows that the successive order statistic gaps are independent, with rates $N\lambda ,(N-1)\lambda ,\dots ,\lambda$. Their sum has the distribution of $S_N$. ThereforeFor $x>0$, $N{e}^{-\lambda Nx}\to 0$, and henceIf $0<u<v$, subtracting the two tails gives the interval exponent $-\lambda u$, since the tail at $Nv$ is exponentially smaller. Also $\mathbb{E}{S}_N={\lambda }^{-1}{\sum }_{i=1}^N{i}^{-1}=O(\log N)$, so the Markov inequality gives $S_N/N\to 0$ in probability. Local lower bounds at positive points and at zero follow; the tail estimate gives the closed-set upper bound exactly as in part (a). This proves the full large deviation principle.

There is also a deduction from part (b). For fixed $k$ and $i>k$, a rate-$i\lambda$ exponential random variable is stochastically smaller than a rate-$k\lambda$ one. Coupling by the same uniform variables therefore gives $S_N\le S_k+Z_N$ with independent additional copies. For fixed $x>0$ and sufficiently large $k$, the upper-tail exponent from part (b) is $-\lambda x-\log ((k-1)/k)$. Let $k\to \infty$ to obtain $-\lambda x$; the lower tail estimate $\mathbb{P}(S_N>Nx)\ge \mathbb{P}(T_1>Nx)=e^{-\lambda Nx}$ matches it. The exact maximum identity additionally supplies all local 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.

Let $\kappa =2(1-H)$ and fix $a>0$. Starting with part (b), the contraction principle for large deviations under the map $q\mapsto q/a$ gives an LDP for $r(X)/(aN)$ with speed $N^{\kappa }$ and rate function $q\mapsto J(aq)$.

Alternatively, replace $N$ by $aN$ in parts (a) and (b), using the real-scale justification in part (a). The same family has large-deviation speed $(aN{)}^{\kappa }$ and rate function $J(q)$. When expressed at speed $N^{\kappa }$, that rate function is $a^{\kappa }J(q)$. The two descriptions of the same large deviation principle must agree:For clarity, uniqueness here is a general property of lower semicontinuous rate functions: at a point $x$, the shrinking-neighborhood logarithmic bounds recover $I(x)$, since ${\inf }_{B(x,\eta )}I\to I(x)$ as $\eta \downarrow 0$. Thus two rate functions for the same family and speed cannot differ.

Taking the base argument $q=1$ and replacing $a$ by any positive queue size givesFor $q<0$ the rate function is infinite. In the usual nondegenerate case $J(1)$ is finite, so the formula also holds at $q=0$. This is the self-similar Gaussian workload rate; the exponent comes from the Hurst parameter, while the constant comes from the path rate function and the drift and noise scales.