Sanov's theorem explained

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,} \ldots, 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 ^{- nD _{KL} (p ^{*||q)}} ,

where

q ^{n} is the joint probability distribution on X ^{n} , andp ^{*} is the information projection of q onto A.

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

\lim _{n\toinfty} (1)/(n) log q ^{n(\hat{p}} _{x ^{n}} \in A) = - D _{KL} (p ^{*||q).}

Technical statement

Define:

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

$$\backslash$$Then, Sanov's theorem states:^[1]

• For every measurable subset $S\; \backslash in\; \backslash Delta(\backslash Sigma)$,$$-\backslash inf\_\; D(\backslash nu\backslash |\backslash mu)\; \backslash leq\; \backslash liminf\_n\; \backslash frac\; 1n\; \backslash ln\; P\_\backslash mu(L\_n\; \backslash in\; S)\; \backslash leq\; \backslash limsup\_n\; \backslash frac\; 1n\; \backslash ln\; P\_\backslash mu(L\_n\; \backslash in\; S)\; \backslash leq\; -\backslash inf\_\; D(\backslash nu\; \backslash |\; \backslash mu)$$
• For every open subset $U\; \backslash in\; \backslash Delta(\backslash Sigma)$,$$-\backslash lim\_n\; \backslash lim\_\; D(\backslash nu\backslash |\backslash mu)\; =\; \backslash lim\_n\; \backslash frac\; 1n\; \backslash ln\; P\_\backslash mu(L\_n\; \backslash in\; S)\; =\; -\backslash inf\_\; D(\backslash nu\backslash |\backslash mu)$$

Here,

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

References

• Book: Cover . Thomas M. . Thomas . Joy A. . Elements of Information Theory . limited . Wiley Interscience . 2 . 2006 . Hoboken, New Jersey . 362. 9780471241959 .
• 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.

Notes and References

1. Dembo . Amir . Zeitouni . Ofer . 2010 . Large Deviations Techniques and Applications . Stochastic Modelling and Applied Probability . 38 . en . 16–17 . 10.1007/978-3-642-03311-7 . 978-3-642-03310-0 . 0172-4568.