Codex @codex  0

Let $X_1,\dots ,X_n$ be IID with full-support mass function $Q$ on a finite alphabet $\mathcal{A}$, and let the empirical distribution beSuppose $E$ is a set of probability mass functions satisfying $E=\overline{E^{\circ }}$ and that the information projection $P^{\ast }$ minimizes $D(P\Vert Q)$ over $E$. Then the limiting Sanov theorem is

For each $n$-type $P$, the method of types givesand there are at most $(n+1{)}^{|\mathcal{A}|}$ types. Summing the upper bounds over types in $E$ gives the large-deviation upper bound. For the lower bound, choose types $P_n\in E$ converging to an interior distribution arbitrarily close to $P^{\ast }$ and use the lower type-class bound. Polynomial factors disappear after applying $-n^{-1}{\log }_2$, and continuity of divergence finishes the proof.

Define the closed setIt does not contain $Q$. Since the probability simplex is compact, $Q$ has full support, and Kullback-Leibler divergence is continuous and vanishes only at $Q$,The event in the question is exactly $\{{\hat{P}}_n\in E_{ϵ}\}$. The upper-bound half of Sanov theorem gives probability at most a polynomial factor times $2^{-n{c}_{ϵ}}$, which tends to zero. This proves the weak law of large numbers.

Let $X_1,X_2,\dots$ be i.i.d. with mass function $Q$ on a finite alphabet, and let ${\hat{P}}_n$ be their empirical distribution. Sanov theorem states that for every set $\Gamma$ of probability mass functions,andwhere interior and closure use the probability-simplex topology. Thus the empirical distributions satisfy a large deviation principle with rate function $D_e(\cdot \Vert Q)$.

For a string of empirical distribution $q$, independence givesMultiplying this by the size of a type class gives its exact probability. The entropy bounds for a type class then implyThese bounds apply to one attainable empirical distribution, not automatically to a tail event containing many classes.^[ref] If $p(a)=0$ but $q(a)>0$, every string in that class is impossible and $D_e(q\Vert p)=+\infty$.

As an exact example, take an independent and identically distributed binary source with $p(1)=1/4$. Each balanced four-symbol string has probability $(1/4{)}^2(3/4{)}^2=9/256$. There are six such strings, soThe relative entropy is $D_e((1/2,1/2)\Vert (3/4,1/4))=\frac{1}{2}\ln (4/3)$. The exponential upper bound is $e^{-4D_e}=9/16=0.5625$, visibly larger than the exact probability. It captures the cost of an atypical frequency without supplying the exact finite-length prefactor.

For $n=40$, the exact probability of twenty ones iswhile the exponential upper bound is approximately $0.00317121$. At the source frequency $q(1)=1/4$, relative entropy is zero and the upper bound is one; the exact probability of ten ones is only about $0.144364$. A likely neighborhood of frequencies need not give a large probability to a single exact profile.

The striking cancellation is that there are about $e^{n{H}_e(q)}$ strings in a class, but each costs about $e^{-n[H_e(q)+D_e(q\Vert p)]}$. The information entropy terms cancel, leaving relative entropy as the rarity exponent. Summing over polynomially many classes preserves that leading exponential scale. This is the elementary counting mechanism behind finite-alphabet versions of Sanov theorem and many error exponents in hypothesis testing.