Sanov's theorem

In mathematics and information theory, Sanov's theorem gives a bound on the probability of observing an atypical sequence of samples from a given probability distribution. In the language of large deviations theory, Sanov's theorem identifies the rate function for large deviations of the empirical measure of a sequence of i.i.d. random variables.

Let A be a set of probability distributions over an alphabet X, and let q be an arbitrary distribution over X (where q may or may not be in A). Suppose we draw n i.i.d. samples from q, represented by the vector $x^n=(x_1,x_2,\dots ,x_n)$. Then, we have the following bound on the probability that the empirical measure ${\hat{p}}_{x^n}$ of the samples falls within the set A:

$q^n({\hat{p}}_{x^n}\in A)\le (n+1{)}^{|X|}{2}^{-n{D}_{\mathrm{K}\mathrm{L}}(p^{\ast }||q)}$,

where

• $q^n$ is the joint probability distribution on $X^n$, and
• $p^{\ast }$ is the information projection of q onto A.
• $D_{\mathrm{K}\mathrm{L}}(P\Vert Q)$, the KL divergence, is given by: $D_{\mathrm{K}\mathrm{L}}(P\Vert Q)=\sum _{x\in 𝒳}P(x)\log \frac{P(x)}{Q(x)}.$

In words, the probability of drawing an atypical distribution is bounded by a function of the KL divergence from the true distribution to the atypical one; in the case that we consider a set of possible atypical distributions, there is a dominant atypical distribution, given by the information projection.

Furthermore, if A is a closed set, then

$\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\log q^n({\hat{p}}_{x^n}\in A)=-D_{\mathrm{K}\mathrm{L}}(p^{\ast }||q).$

Technical statement

Define:

• $\mathrm{\Sigma }$ is a finite set with size $\ge 2$. Understood as “alphabet”.
• $\mathrm{\Delta }(\mathrm{\Sigma })$ is the simplex spanned by the alphabet. It is a subset of ${ℝ}^{\mathrm{\Sigma }}$.
• $L_n$ is a random variable taking values in $\mathrm{\Delta }(\mathrm{\Sigma })$. Take $n$ samples from the distribution $\mu$, then $L_n$ is the frequency probability vector for the sample.
• ${ℒ}_n$ is the space of values that $L_n$ can take. In other words, it is

$$\{(a_1/n,\dots ,a_{|\mathrm{\Sigma }|}/n):\sum _i{a}_i=n,a_i\in \mathbb{N}\}$$Then, Sanov's theorem states:

• For every measurable subset $S\in \mathrm{\Delta }(\mathrm{\Sigma })$,$$-\underset{\nu \in int(S)}{inf}D(\nu \Vert \mu )\le \underset{n}{lim\; inf}\frac{1}{n}\ln P_{\mu }(L_n\in S)\le \underset{n}{lim\; sup}\frac{1}{n}\ln P_{\mu }(L_n\in S)\le -\underset{\nu \in cl(S)}{inf}D(\nu \Vert \mu )$$
• For every open subset $U\in \mathrm{\Delta }(\mathrm{\Sigma })$,$$-\underset{n}{lim}\underset{\nu \in U\cap {ℒ}_n}{lim}D(\nu \Vert \mu )=\underset{n}{lim}\frac{1}{n}\ln P_{\mu }(L_n\in S)=-\underset{\nu \in U}{inf}D(\nu \Vert \mu )$$

Here, $int(S)$ means the interior, and $cl(S)$ means the closure.

Further reading

• Template:Cite book

• Sanov, I. N. (1957) "On the probability of large deviations of random variables". Mat. Sbornik 42(84), No. 1, 11–44.
• Санов, И. Н. (1957) "О вероятности больших отклонений случайных величин". МАТЕМАТИЧЕСКИЙ СБОРНИК 42(84), No. 1, 11–44.