Large deviation principle

A sequence $(Z_n)$ satisfies a large deviation principle with speed $n$ and rate function $I$ when probabilities of measurable sets $A$ decay exponentially between the bounds

If a large deviation principle has a finite continuous rate function, then the infima on any open set and its closure agree. Approximate every closure point by points of the set and use continuity. The open-set lower and closed-set upper bounds consequently match, giving the displayed logarithmic limit, including the empty-set convention. A single-point event need not obey such an equality.

A large deviation principle for fluctuations larger than the usual central limit theorem scale but smaller than a fixed displacement of the empirical mean. For the displayed sum scaling, the natural large-deviation speed is $b_n^2$. Under suitable exponential-moment hypotheses and positive variance ${\sigma }^2$, its rate function is the quadratic $x^2/(2{\sigma }^2)$.

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 a fixed finite number of nonnegative terms and $a_L\to \infty$, use ${\max }_j{p}_{j,L}\le {\sum }_j{p}_{j,L}\le r{\max }_j{p}_{j,L}$. The logarithm of $r$, divided by the large-deviation speed, tends to zero, and a finite maximum commutes with the limit superior. If all individual logarithmic limits exist, the limit of the sum is their maximum.

For a geometric random variable $X$ with $\mathbb{P}(X=k)=p(1-p{)}^{k-1}$, $0<p<1$, the family $X/L$ has large-deviation speed $L$ and good rate function $I(x)=ax$ for $x\ge 0$, infinite otherwise, where $a=-\log (1-p)$. The exact tail $\mathbb{P}(X/L\ge x)=(1-p{)}^{\lceil Lx\rceil -1}$ gives the upper bound. A lattice point tending to any positive $x$ supplies the open-neighborhood lower bound; neighborhoods of zero have probability tending to one. Finite sublevel sets are compact intervals.

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.

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

Suppose a weak large deviation principle with rate function $I$ holds on a Hausdorff space, at speed $a_n\to \infty$, and the random elements are exponentially tight. For a finite $r$, choose a compact set $K$ whose complement has upper exponential rate strictly below $-M$, with $M>r$. The open-set lower bound on $K^c$ implies ${\inf }_{K^c}I>M$, so $\{I\le r\}\subset K$. Lower semicontinuity makes this sublevel set closed, hence compact. For any closed set $F$, split its probability between the compact $F\cap K$ and $K^c$. The upper exponential rate is at most $\max \{-{\inf }_{F}I,-M\}$. Letting $M\to \infty$ proves the full large deviation principle with a good rate function.

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.

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.

For a continuous $F$ and a family satisfying a large deviation principle at speed $L$, the displayed exponential tail condition extends Varadhan's lemma to $F$ unbounded above. Apply the bounded-above result to $\min (F,M)$ and split the full integral into $F\le M$ and its tail; the tail is negligible and the truncated variational suprema increase to ${\sup }_x(F(x)-I(x))$. A sufficient condition is ${\mathrm{limsup}}_L{L}^{-1}\log \mathbb{E}{e}^{\gamma LF(X_L)}<\infty$ for some $\gamma >1$, since the tail is at most $e^{-(\gamma -1)LM}\mathbb{E}{e}^{\gamma LF(X_L)}$.

The exponential integral of a fixed measurable function is controlled, on its logarithmic scale, by the function's essential infimum. Suppose $0<{\int }_A{e}^{-\varphi }dx<\infty$ and $\alpha ={\mathrm{essinf}}_A\varphi$ is finite. For $\theta \ge 1$, the integral is at most $e^{-(\theta -1)\alpha }{\int }_A{e}^{-\varphi }dx$. For every $\epsilon >0$, the set $A_{\epsilon }=\{x\in A:\varphi (x)<\alpha +\epsilon \}$ has positive finite Lebesgue measure, and the integral is at least $|A_{\epsilon }|e^{-\theta (\alpha +\epsilon )}$. Taking logarithms, dividing by $\theta$, and then letting $\epsilon \downarrow 0$ proves the displayed limit. The argument needs no isolated or nondegenerate minimizer. The Laplace principle for probability measures treats families whose distributions also change with the scaling parameter.

A family satisfies this principle with speed $a_n\to \infty$ and rate function $I$ when the displayed variational identity holds for every bounded continuous real function $f$. A large deviation principle implies it by the Varadhan lemma. The lower bound restricts the expectation to a neighborhood of a chosen point; the upper bound partitions the bounded range of $f$ into small intervals and applies the closed-set probability bounds.

For nonnegative $X_n$, the identity also givesFor $\mu >0$, truncate $f(s)=-\mu s$ below at $-\mu R$. The resulting bounded-function identity applies, while the difference of the two exponential expectations is at most $e^{-\mu R{a}_n}$. Choosing $R$ sufficiently large makes this error negligible on the claimed exponential scale. The case $\mu =0$ is immediate. This extension identifies moment-decay rates of a passive scalar from fluctuations of its logarithmic stretching.

Let $X_N\in {\mathbb{R}}^d$ and $a_N\to \infty$. Define the scaled cumulant-generating functionSuppose its pointwise limit $\Lambda$ exists, is lower semicontinuous, has $0$ in the interior of its effective domain, and is essentially smooth: it is differentiable on that interior, which is nonempty, and its gradient norm diverges at every finite boundary point approached from the interior. Then $X_N$ satisfies a large deviation principle with good rate function given by the Legendre-Fenchel transformThe Chernoff bound supplies the upper estimate. The lower estimate uses exponential tilting at a parameter whose gradient selects the required mean; essential smoothness supplies the boundary approximation needed for the full lower bound. A finite boundary slope can leave an affine branch of ${\Lambda }^{\ast }$ outside this argument, so a separate lower-bound proof is then necessary.

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

If $X_N$ satisfies a large deviation principle in $E$ with good rate function $I$ and $f:E\to F$ is a continuous map, then $f(X_N)$ has the same large-deviation speed and good rate functionThe preimages of open and closed sets give the two large deviation principle inequalities. The identity $\{J\le M\}=f(\{I\le M\})$ follows from compactness and lower semicontinuity by taking minimizing sequences in the fibres; hence $J$ is good.

For $a<b$, the contraction principle for large deviations under scalar clipping gives $K(z)=I(z)$ in $(a,b)$, the displayed endpoint costs, and infinite cost outside $[a,b]$. The endpoint costs can differ from $I(a)$ and $I(b)$ because clipping collects a whole input tail into a single output atom.

For fixed $k$ independent random variables whose families have the same large deviation principle with good rate function $I$, the product large-deviation principle gives the sum of coordinate costs. Under the minimum map, one coordinate must equal $m$ and the others must be at least $m$, yielding the displayed rate function. If $I$ is convex with unique zero $\mu$, then $J(m)=I(m)$ for $m\le \mu$ and $J(m)=kI(m)$ for $m\ge \mu$.

Let $Z_n$ clip the minimum of $k$ independent exponential sample means into $[a,b]$, with $0<a<1/\lambda <b$. The rate function under scalar clipping is the minimum cost on this interval. Apply Varadhan's lemma to $\log z$. On the lower side its objective is increasing; on the upper side its derivative is $(k+1)/z-k\lambda$. Thus the optimum is $z_{\ast }=(k+1)/(k\lambda )$ once $k\ge (\lambda b-1{)}^{-1}$, giving the displayed limit. The expectation is of the high power, rather than a power of the mean; the latter has limit $-\log \lambda$.

Coupled random elements $X_N,Y_N$ in a metric space are exponentially equivalent at large-deviation speed $a_N$ if for every $\eta >0$If $X_N$ satisfies a large deviation principle with a good rate function $I$, then so does $Y_N$, with the same speed and rate function. For the upper bound, $\{Y_N\in F\}$ is contained in $\{X_N\in F^{\eta }\}\cup \{d(X_N,Y_N)>\eta \}$, where $F^{\eta }$ is the closed $\eta$-neighborhood. Goodness gives ${\inf }_{F^{\eta }}I\to {\inf }_{F}I$ as $\eta \downarrow 0$: otherwise bounded-rate almost minimizers have a convergent subsequence contradicting closedness and lower semicontinuity. For an open-set lower bound, choose a ball about any $x\in G$ with a slightly larger ball still in $G$, subtract the superexponentially small error from the probability that $X_N$ belongs to the smaller ball, and shrink the ball. No independence assumption is required.

A family with large-deviation speed $a_N$ is exponentially tight if for every $M>0$ there is a compact set $K_M$ such thatLocal upper bounds then imply the closed-set upper bound of a large deviation principle: intersect the closed set with $K_M$, cover that compact intersection by finitely many neighborhoods on which the local bounds hold, and use a finite union bound. The remaining probability has exponent at most $-M$; let $M\to \infty$.

A large deviation principle with speed $a_N\to \infty$ and rate function $I$ means that every open set $G$ and closed set $F$ satisfyMultiplying the large-deviation speed by $c>0$ divides the rate function by $c$. The speed must match the rare-event scale: a fixed exponential random variable divided by $N^p$ has speed $N^p$, whereas a sum of $N$ independent random variables with a normal distribution, divided by $N^p$, has speed $N^{2p-1}$ when $p>1$.

A sequence has Hurstiness H when it satisfies a large deviation principle at the displayed speed with a good rate function having a unique zero and at least one strictly positive finite value. This definition concerns a sequence's exponential probability scale; it does not assert a sample-path Hurst exponent or self-similarity. Larger H means slower rare-event decay. The positive finite value excludes the slower-speed degeneration of a large deviation principle.

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

A rate function is a lower-semicontinuous map $I$ into $[0,\infty ]$. It is good when every sublevel set $\{x:I(x)\le c\}$ is compact.

A local path action integrates a nonnegative convex cost g of the path's instantaneous input rate, assigning infinity to paths that are not absolutely continuous. When $g(\mu )=0$, the typical-rate path has zero cost. On any interval with prescribed total input, Jensen inequality makes a constant derivative minimize its cost. With a queue workload constraint this leads to constant-rate burst paths and the linear workload rate for a local convex action. Such a formula alone does not establish goodness in an unspecified path topology; goodness must be checked or assumed as part of the input large-deviation principle.

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.

If a good rate function has unique zero mu, every closed set missing mu has strictly positive infimum rate, possibly infinity. Otherwise a sequence of rates tending to zero lies eventually in the compact unit sublevel set; a subsequence converges to a point of the closed set, and lower semicontinuity makes that point another zero. Compactness also ensures existence of a zero whenever the infimum is zero.

For a small-noise diffusion $dX=a(X)dt+\sqrt{ϵ}\sigma (X)dW$, the Freidlin--Wentzell action of a smooth path is

On a zero-Hamiltonian infinite-time fluctuation path, the Freidlin--Wentzell action can be parametrized independently of time as $I=\int \Vert a\Vert ds-a\cdot d\varphi$ in the diffusion metric.