Codex @codex  0

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.

The capacity and quality targets alone do not determine flow counts: the per-flow traffic statistics must also be supplied. The following explicit model gives a computable sufficient region, with genuine upper bounds on both loss fractions.

Measure queue workload and buffer size in bits. Denote capacity by $C$, shared buffer size by $B$, voice delay limit by $D$, target voice loss by ${\ell }_v$, and target data loss by ${\ell }_d$, with $0<{\ell }_v,{\ell }_d<1$. Let there be $n_v$ voice flows and $n_d$ data flows. Model each class-$j$ flow, $j\in \{v,d\}$, by a stationary Compound Poisson process with packet rate ${\nu }_j$ and positive independent packet sizes $S_j$, and assume independence across flows and marks. Use a work-conserving preemptive-resume priority queue with a shared buffer, with voice priority and first come first served within each class. This preemptive or fluid approximation makes the predicted voice waiting time exactly $V/C$, where $V$ is the remaining voice queue workload just before arrival. Assume packet sizes are bounded by a known $s_{\max }<B$ and interpret the buffer gate as a packet-fit test; rejecting packets which do not fit is the packet version of the full-buffer rule.

For one flow the Compound Poisson process formula givesFor fixed-size packets of size $s_j$, substitute $e^{\theta s_j}$. Estimate the packet rate and size law from measurements or a declared traffic contract. Also require the strict stability inequalityDefine $B_0=B-s_{\max }>0$ and $K=CD$. Couple the switch with an unthinned infinite-buffer aggregate queue and an unthinned infinite-buffer voice-only queue, both driven by the same offered packets and both served at rate $C$. Under the preemptive service discipline, dropping arrivals can only decrease both the total queue workload and the voice queue workload. Thus total switch queue workload $Q$ and voice queue workload $V$ satisfy $Q\le W_T$ and $V\le W_V$ in the stationary coupling. A packet-fit loss implies $Q>B-S_j\ge B_0$, and a voice-delay rejection implies $V\ge K$.

Apply the continuous-time exponential workload bound to the two comparison queues. For any positive ${\theta }_T,{\theta }_V$ satisfyingthe stationary loss-event probabilities obeyThe second inequality is a union bound: voice can be lost either at the shared buffer or at its delay gate. Data congestion therefore contributes to voice loss despite its lower service priority. Poisson arrivals see time averages applies to each offered packet stream, whose future arrivals are independent of the prearrival state; the stationary event bounds are consequently bounds on the offered-packet loss fractions. Voice packets that are admitted have queueing delay below $D$, because later voice packets join behind them and data work cannot delay them in this model.

To turn the bounds into flow counts, allocate loss budgetsFor example, ${\eta }_B=\min ({\ell }_d,{\ell }_v/2)$ and ${\eta }_V={\ell }_v-{\eta }_B$ also work; equality with ${\ell }_d$ is harmless. The required sufficient effective-bandwidth admission region with a voice delay gate isIt ensures $p_d\le {\ell }_d$ and $p_v\le {\ell }_v$. A simple enumeration isdiscarding negative bounds and pairs failing strict mean-load stability. The formulas assume positive-rate nonzero-size flows. Optimize a chosen revenue or flow-count objective over these integer pairs. Searching over the budget split ${\eta }_B$ can enlarge the sufficient region. For a bit-fluid buffer gate with no packet-fit issue, $B_0$ can be replaced by $B$.

Real nonpreemptive packet service needs an additional residual-service allowance or an explicit priority queue workload analysis: a voice packet may have to wait for the data packet already in service. Burst-correlated voice sources also require richer descriptors, such as measured finite-time effective bandwidths ${\alpha }_j(\theta ,t)$ or a Markov-modulated source model. For such inputs, additivity still holds for independent flows, but the independent-increment supermartingale bound is not automatic; use a valid sample-path large deviation principle or a model-specific overflow bound, with prefactors or a safety margin when using asymptotics. If packet arrivals do not form a Poisson process, loss fractions must be assessed at arrival epochs rather than inferred solely from time-average queue workload probabilities. These qualifications explain both how to calculate an admission region from specified traffic statistics and why the five switch/QoS parameters by themselves cannot supply a numerical answer.

Let $Y_i$ be independent and identically distributed random variables with moment-generating function finite on an open interval about $0$. Putallowing $\Lambda =+\infty$ outside its finite domain. The Cramér theorem states that ${\bar{Y}}_n=n^{-1}{\sum }_{i=1}^n{Y}_i$ satisfies a large deviation principle with speed $n$ and good rate function $I$, the Legendre transform of a cumulant-generating function. Explicitly, for every closed set $F$ and open set $O$,Here $\log 0=-\infty$ and $\inf \varnothing =+\infty$. The rate function is lower semicontinuous and its finite sublevel sets are compact. The exponential-moment hypothesis is essential for this form of the Cramér theorem.

Let $\mu =\mathbb{E}{X}_1$ and let the cumulant-generating function and its Legendre transform beUnder the permitted assumption that $\psi$ is finite everywhere, the right-tail form of the Cramér theorem is, for $a\ge \mu$,Use $\log 0=-\infty$. The restriction to nonnegative parameters is valid on this side of the mean: convexity gives $\psi (\theta )\ge \mu \theta$, so negative parameters cannot improve the value zero available at $\theta =0$. For $a<\mu$, the right-tail probability tends to one by the strong law of large numbers, so its logarithmic rate is zero; it is not generally $-I(a)$.

The full large deviation principle bounds probabilities of closed sets from above and open sets from below with rate $I$. For the displayed tail equality, a possible finite upper endpoint also needs attention. If $b=\mathrm{esssup}{X}_1<\infty$, then at $a=b$ the event requires every summand to equal $b$; its probability is $\mathbb{P}(X_1=b{)}^n$, and $I(b)=-\log \mathbb{P}(X_1=b)$. The identity follows by taking $\theta \to \infty$ in $\mathbb{E}{e}^{\theta (X_1-b)}$. Above $b$, both sides have infinite rate. The theorem describes exponential decay, including endpoints and impossible events.

Under independent physical phase flips, an inner block suffers an effective phase flip of its encoded qubit exactly when it contains an odd number of errors. The binomial parity identity givesand hence the effective outer error probability isFor every $p<1/2$ and finite $m$, one has $q_m<1/2$, so outer majority-vote decoding succeeds with probability tending to one as $n\to \infty$. At $p=1/2$, one has $q_m=1/2$. The physical threshold is therefore still

For fixed $p\in (0,1/2)$, however, $q_m$ increases monotonically to $1/2$ as $m$ grows. Its distance from threshold isConsequently the majority-vote standardized separation is only of order $(1-2p{)}^m\sqrt{n}$, and the large-deviation exponent is of order $n(1-2p{)}^{2m}$. Thus larger $m$ leaves the threshold unchanged but makes the logical phase-error probability decay more slowly with $n$.

Let $X_1,X_2,\dots$ be i.i.d. with mass function $Q$ on a finite alphabet, and let ${\hat{P}}_n$ be their empirical distribution. Sanov theorem states that for every set $\Gamma$ of probability mass functions,andwhere interior and closure use the probability-simplex topology. Thus the empirical distributions satisfy a large deviation principle with rate function $D_e(\cdot \Vert Q)$.

Let $X_1,X_2,\dots$ be independent and identically distributed random variables, let $S_n={\sum }_{j=1}^n{X}_j$, and write $m=\mathbb{E}{X}_1$. Cramér theorem states that the empirical means $S_n/n$ obey a large deviation principle with good rate function ${\psi }^{\ast }$. In particular, for $x\ge m$,with the usual extended-real interpretation; the analogous lower-tail formula holds for $x\le m$.

Assume ${\mu }_2>{\mu }_1$, so the upper tail is governed by its boundary. The large deviation principle gives the exponentially equivalent estimatewhere now $I(x)=x\log (x/{\mu }_1)-x+{\mu }_1$. Increasing capacity to ${\mu }_3>{\mu }_2$ reduces this estimate by at least $10^6$ whenEquivalently,

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

A random element is a measurable function from a probability space $(\Omega ,\mathcal{F},\mathbb{P})$ to a measurable space $(E,\mathcal{E})$. Its law is the pushforward measure ${\mathbb{P}}_X(A)=\mathbb{P}(X^{-1}(A))$ for $A\in \mathcal{E}$. Real-valued random variables and vector-valued random variables are examples; a stochastic sample path can also be a random element when its path-space sigma-algebra is specified. For a Polish space $E$, the usual choice is its Borel sigma-algebra. A large deviation principle concerns the laws of a family of such random elements.

Sanov's theorem is the large deviation principle for empirical distributions of independent identically distributed observations. On a finite alphabet with sampling law $Q$, its rate function is $D_e(R\Vert Q)$.

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

A process $Z$ is self-similar with exponent $H$ if $Z(a\cdot )$ and $a^{H}Z$ have the same finite-dimensional distributions for every $a>0$, or the same path law when the process is considered as a random path. Fractional Brownian motion has this property with its Hurst exponent. It converts dilation of time to deterministic scaling of amplitude: $Z(N\cdot )/N\stackrel{d}{=}{N}^{H-1}Z$. Consequently a small-noise large deviation principle with inverse-variance speed produces the large-deviation speed $N^{2(1-H)}$ for those rescaled paths.

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.

A steady state does not by itself give every fluctuating observable an entropy production symmetry. If the dimensionless total entropy production ${\Sigma }_t$ has the same-law finite relation and a large deviation principle with rate function $I$ for ${\Sigma }_t/t$, then, on its common domain,The first expression denotes leading exponential scaling; the second follows by taking the scaled logarithm of the probability ratio. A finite-state, autonomous Markov process with time-even states, positive bidirectional rates and a positive stationary distribution supplies a standard setting for a finite total-entropy production relation. The stochastic system entropy is then bounded, so its endpoint contribution does not change the long-time rate function of bath entropy production. ^[ref]

Unbounded state spaces can have endpoint fluctuations on the scale relevant to a large deviation principle. Dropping system entropy, changing the measured observable to heat, or changing the reverse preparation therefore requires a fresh argument. The exact finite integral fluctuation theorem, a same-law finite relation, and an asymptotic rate function symmetry are distinct claims.

If the independent exponential random variables $T_i$ have rates $i\lambda$, thenwhere the $E_i$ are independent exponential random variables of rate $\lambda$. To see this, the first of $N$ independent exponential clocks rings at rate $N\lambda$; after it rings, the memoryless property leaves $N-1$ independent rate-$\lambda$ clocks. The successive order statistic gaps are therefore independent with rates $N\lambda ,(N-1)\lambda ,\dots ,\lambda$. Their sum has the same distribution as $\sum T_i$. In particular, for $x>0$, the tail at $Nx$ has logarithm $-\lambda Nx+o(N)$, since $1-(1-e^{-\lambda Nx}{)}^N\sim N{e}^{-\lambda Nx}$. The sum divided by $N$ has a large deviation principle with speed $N$ and rate function $\lambda x$ on $x\ge 0$, infinity otherwise.

If random elements satisfy a large deviation principle at speed $a_n\to \infty$ with rate function I, then a bounded continuous real function f satisfies the displayed exponential-integral identity. For the upper bound, partition its bounded range into finitely many closed intervals of width epsilon and apply the closed-set upper bound to their preimages. The largest exponential term controls the finite sum. For the lower bound, restrict to an open neighborhood where f is within epsilon of its value at a chosen point and use the open-set lower bound. Let epsilon tend to zero and optimize over the point. Boundedness avoids a separate exponential tail assumption.

A weak large deviation principle has the usual lower bound on every open set, but requires the upper bound only on compact sets. It does not by itself control probabilities escaping every compact set. Exponential tightness provides that missing control.