= Sanov theorem
{c}
{wiki}
Let $X_1,\ldots,X_n$ be <independent and identically distributed> on a <finite alphabet> with full-support <probability mass function> $Q$, and let $\widehat P_n$ be their <empirical distribution>. <Sanov theorem> gives a <large deviation principle> on the <probability simplex>, with rate <function>
$$
D_e(P\Vert Q)=\sum_aP(a)\log\frac{P(a)}{Q(a)},
$$
using <natural logarithms>. For any measurable <set> $A$, with <interior> $A^\circ$ and <closure> $\overline A$ relative to that <probability simplex>,
$$
-\inf_{P\in A^\circ}D_e(P\Vert Q)
\leq\liminf_n n^{-1}\log\Pr(\widehat P_n\in A)
\leq\limsup_n n^{-1}\log\Pr(\widehat P_n\in A)
\leq-\inf_{P\in\overline A}D_e(P\Vert Q).
$$
The <method of types> explains the exponent: a <type class> has roughly $e^{nH_e(P)}$ words, each with <probability> $e^{-n(H_e(P)+D_e(P\Vert Q))}$; the number of types grows only polynomially.<Information Theory and Statistics: A Tutorial by Imre Csiszár and Paul C. Shields>[Section 2.1, Large deviations via types, printed pp. 429–434]{ref}
For <Bernoulli distribution> observations with success <probability> $1/5$, the event $\overline X_n\geq1/2$ therefore has <probability> $\exp[-n\log(5/4)+o(n)]$. The exponent is $D_e(\operatorname{Bernoulli}(1/2)\Vert\operatorname{Bernoulli}(1/5))$; atypical empirical laws closest in <relative entropy> dominate the rare event.
Back to article page
