Cramér's theorem (large deviations)
Cramér's theorem, in the field of large deviations theory, provides an asymptotic estimate for the probability that the sample average of a sequence of independent and identically distributed (i.i.d.) random variables deviates significantly from its mean. It quantifies the exponential decay rate of this probability as the number of random variables in the sequence increases.
More formally, let X1, X2, ... be a sequence of i.i.d. random variables with mean μ, and let Sn = X1 + X2 + ... + Xn. The sample average is then given by An = Sn / n. Cramér's theorem states that, under certain conditions (typically requiring the existence of a moment generating function), for any closed set F that does not contain μ,
lim sup (1/n) log P(A<sub>n</sub> ∈ F) = -inf<sub>x ∈ F</sub> I(x)
where I(x) is the rate function (also known as the large deviation rate function or Cramér transform). The rate function is a non-negative function that characterizes the exponential decay rate. It satisfies I(μ) = 0, meaning that the probability of the sample average being close to the mean does not decay exponentially. The further x is from μ, the larger I(x) is, and the faster the probability decays.
The rate function I(x) is often expressed in terms of the Legendre-Fenchel transform of the cumulant generating function of the random variable X1. Let Λ(θ) = log E[exp(θX1)] be the cumulant generating function. Then the rate function is given by:
I(x) = sup<sub>θ</sub> { θx - Λ(θ) }
The conditions for Cramér's theorem to hold generally include the existence of the moment generating function in a neighborhood of zero. However, there are versions of the theorem that apply under weaker conditions.
Cramér's theorem is a fundamental result in large deviations theory and has applications in various fields, including statistics, probability, information theory, and risk management. It allows for the estimation of rare event probabilities and provides insights into the behavior of stochastic systems far from their typical operating regimes. It is the prototype and simplest version of a wide range of Large Deviation Principles (LDPs) that describe the probability of unlikely events in stochastic processes.