Method of Types and Finite Large Deviations

For $0<t\le 1$, put $u=1\mathrm{/}t\ge 1$. Then $\mathrm{\mid }t\ln t\mathrm{\mid }=(\ln u)\mathrm{/}u$, and by [F2], $0\le (\ln u)\mathrm{/}u=(1\mathrm{/}u){\int }_1^{u}ds\mathrm{/}s\le (1\mathrm{/}u){\int }_1^{u}ds\mathrm{/}\sqrt{s}\le 2\mathrm{/}\sqrt{u}\to 0$. Thus $g(t)=t\ln t$ extends continuously to $t=0$ by $g(0)=0$.

Since every $p(a)>0$, the number $\ln p(a)$ is finite, and $D(q\mathrm{\parallel }p)={\sum }_{a\in \mathcal{A}}g(q(a))-{\sum }_{a\in \mathcal{A}}q(a)\ln p(a)$. Each summand is continuous in $q(a)$ by step 1.1; the second sum is linear and has finitely many terms. Hence $D(q\mathrm{\parallel }p)$ is finite and continuous on the whole simplex, including its boundary.

Every $x^n\in {\mathcal{A}}^n$ has the single type ${\widehat{P}}_{x^n}$ from [F1], hence lies in $T_{{\widehat{P}}_{x^n}}$. If $x^n\in T_q\cap T_r$, its empirical vector equals both $q$ and $r$, so $q=r$. Thus the type classes are a disjoint cover of ${\mathcal{A}}^n$.

Fix a listing $a_1,\dots ,a_k$ of $\mathcal{A}$. A type is determined by the first $k-1$ counts $N(a_i\mid x^n)\in \{0,\dots ,n\}$, since the final count is $n-{\sum }_{i<k}N(a_i\mid x^n)$. There are at most $(n+1{)}^{k-1}$ such tuples; for $k=1$ the tuple is empty and determines the unique type.

Fix a listing $a_1,\dots ,a_k$ of $\mathcal{A}$. Set $m_i=\lfloor nq(a_i)\rfloor$ and $r=n-{\sum }_i{m}_i={\sum }_i(nq(a_i)-m_i)$. Thus $r$ is an integer with $0\le r<k$. If $r>0$, at least $r$ fractional parts are positive, since fewer than $r$ positive terms, each below $1$, cannot sum to $r$. Add $1$ to the first $r$ positive fractional-part coordinates in the fixed listing; if $r=0$, add nothing. The resulting integers $m_i^{\mathrm{\prime }}$ are nonnegative and sum to $n$. If $k=1$, then $q(a_1)=1$ and $r=0$, so this gives the unique type exactly.

Put $q_n(a_i)=m_i^{\mathrm{\prime }}\mathrm{/}n$. This is an $n$-type by [F1]. Each coordinate changes from $q(a_i)$ by less than $1\mathrm{/}n$: it is rounded down when not selected and rounded up when selected. Summing the $k$ coordinate errors gives $\mathrm{\parallel }{q}_n-q{\mathrm{\parallel }}_1<k\mathrm{/}n$, hence the stated weak bound. The construction also applies when some $q(a_i)=0$.

By [F1] and finite distributivity, ${\sum }_{x^n\in {\mathcal{A}}^n}{p}^{\otimes n}(\{x^n\})={\prod }_{i=1}^n{\sum }_{a\in \mathcal{A}}p(a)=1$ by [F2], and all atom weights are nonnegative. Thus [F3] makes the assignment $p^{\otimes n}$ a finite probability law with the event masses defined in [F1].

Each $X_i$ is measurable by [F4], because every target subset has preimage in the full power set of ${\mathrm{\Omega }}_n$; it is therefore a random element by [F5]. For arbitrary subsets $B_i\subseteq \mathcal{A}$, put $E_i=X_i^{-1}(B_i)\in \sigma (X_i)$ by [F6]. The product-mass formula [F1] and finite distributivity give $p^{\otimes n}({\bigcap }_{i=1}^n{E}_i)={\sum }_{x^n\in B_1\times \cdots \times B_n}{\prod }_{i=1}^{n}p(x_i)={\prod }_{i=1}^n{\sum }_{a\in B_i}p(a)$. By step 1.1 and [F2], each factor is $p^{\otimes n}(E_i)$ after summing the other coordinates over $\mathcal{A}$. Every event in each $\sigma (X_i)$ has this form by [F6]; setting omitted coordinates to $\mathcal{A}$ gives the same factorization for every finite subfamily. Thus [F7] and [F8] make the coordinate sigma-algebras independent, and [F9] makes the coordinate random elements independent. Taking $B_j=\mathcal{A}$ for $j\mathrm{\ne }i$ shows $X_i$ has law $p$.

If $q(a)>0=p(a)$ for some $a$, every word in $T_q$ contains $nq(a)>0$ copies of $a$, so each word has product mass zero by [F3] and the event mass is zero by [F4]. The right-hand side is also zero because $D(q\mathrm{\parallel }p)=+\mathrm{\infty }$.

Otherwise $p(a)>0$ whenever $q(a)>0$. Every $x^n\in T_q$ has mass ${\prod }_{a:q(a)>0}p(a{)}^{nq(a)}=\exp (n{\sum }_{a:q(a)>0}q(a)\ln p(a))$ by [F1, F3]. Expanding the finite sums in [F2] gives $H(q)+D(q\mathrm{\parallel }p)={\sum }_{a:q(a)>0}q(a)\ln (1\mathrm{/}p(a))$, so each word has mass $\exp (-n[H(q)+D(q\mathrm{\parallel }p)])$. Summing over the finite class proves the identity.

Put $m_a=nq(a)$. The class $T_q$ consists of the arrangements of $m_a$ copies of each $a$, so it has $n!\mathrm{/}{\prod }_a{m}_a!$ words: there are $n!$ position orders before dividing by the $m_a!$ permutations of identical copies for each letter. Under $q^{\otimes n}$ each word has mass ${\prod }_{a:m_a>0}q(a{)}^{m_a}=e^{-nH(q)}$ by [F3, F4].

For any nonnegative integer count vector $r=(r_a)$ summing to $n$, its class has $n!\mathrm{/}{\prod }_a{r}_a!$ arrangements, obtained by permuting $n$ labeled copies and dividing by the $r_a!$ permutations of identical letters; each word has product mass ${\prod }_{a:r_a>0}q(a{)}^{r_a}$ by [F4]. Thus its multinomial probability is $\frac{n!}{{\prod }_a{r}_a!}{\prod }_{a:r_a>0}q(a{)}^{r_a}$. It is zero if $r_a>0$ where $m_a=0$. Otherwise its ratio to the positive probability of count vector $m$ is ${\prod }_{a:m_a>0}\frac{m_a!}{r_a!}{m}_a^{r_a-m_a}$, since the powers of $n$ cancel using ${\sum }_a(r_a-m_a)=0$. For $r_a>m_a$ the factor is ${\prod }_{j=m_a+1}^{r_a}{m}_a\mathrm{/}j\le 1$; for $0\le r_a<m_a$ it is ${\prod }_{j=r_a+1}^{m_a}j\mathrm{/}{m}_a\le 1$; for equality it is $1$. Hence $m$ is a mode.

Since $q^{\otimes n}$ is a probability law by [F4], $q^{\otimes n}(T_q)=\mathrm{\mid }{T}_q\mathrm{\mid }{e}^{-nH(q)}\le 1$ by step 1.1. Rearranging gives $\mathrm{\mid }{T}_q\mathrm{\mid }\le e^{nH(q)}$.

The count-vector events are exactly the type classes in [F1], so they partition the sample space under the probability law $q^{\otimes n}$ from [F4]. By [F2] there are at most $(n+1{)}^{k-1}$ such vectors. Since $m$ is modal by step 1.2, its class has probability at least the average of the class probabilities, so $q^{\otimes n}(T_q)\ge (n+1{)}^{-(k-1)}$.

Step 1.1 gives $q^{\otimes n}(T_q)=\mathrm{\mid }{T}_q\mathrm{\mid }{e}^{-nH(q)}$. Combining this equality with step 2.2 and rearranging proves the lower bound.

If $D(q\mathrm{\parallel }p)<\mathrm{\infty }$, substitute [F1] and [F2] and cancel the finite factors $e^{nH(q)}{e}^{-nH(q)}$ to obtain both inequalities. The case $k=1$ is included: then $q=p=(1)$ and all three quantities equal $1$.

If $D(q\mathrm{\parallel }p)=+\mathrm{\infty }$, [F1] and [F3] give $p^{\otimes n}(T_q)=0$, and both stated bounds are zero by convention.

Each type class is nonempty because $q$ is attainable, so $\mathrm{\mid }{T}_q\mathrm{\mid }>0$. Taking natural logarithms in [F1] gives $nH(q)-(k-1)\ln (n+1)\le \ln \mathrm{\mid }{T}_q\mathrm{\mid }\le nH(q)$.

Divide by $n$ and subtract from $H(q)$ to get the uniform error interval in the statement. For $x\ge 1$, [F3] and $1\mathrm{/}s\le 1\mathrm{/}\sqrt{s}$ give $\ln x\le {\int }_1^{x}ds\mathrm{/}\sqrt{s}=2(\sqrt{x}-1)$, hence $\ln (n+1)\mathrm{/}n\to 0$. The bound is independent of $q$, so convergence is uniform.

By [F7], $p^{\otimes n}$ is a probability law on ${\mathcal{A}}^n$. Every word outside $S^n$ has a coordinate $a\mathrm{\notin }S$, so its product mass is zero by [F8]; hence $p^{\otimes n}(S^n)=1$ and ${\widehat{P}}_n\in \mathrm{\Delta }(S)$ almost surely by [F1]. The event $\{{\widehat{P}}_n\in \mathrm{\Gamma }\}$ is the disjoint union of the type classes $T_q$ with $q\in \mathrm{\Gamma }\cap {\mathcal{P}}_n(S)$, so its probability is the sum of those finitely many class probabilities.

Fix $q\in {\mathrm{\Gamma }}^{\circ }$. By the definition of relative interior in the topology on $\mathrm{\Delta }(S)$ induced by ${\mathrm{\ell }}^1$, some $\epsilon >0$ has the property that every $r\in \mathrm{\Delta }(S)$ with $\mathrm{\parallel }r-q{\mathrm{\parallel }}_1<\epsilon$ belongs to $\mathrm{\Gamma }$. By [F5], the fixed rounding rule supplies an $n$-type $q_n$ with $\mathrm{\parallel }{q}_n-q{\mathrm{\parallel }}_1\le k\mathrm{/}n$ for every $n$, so $q_n\in \mathrm{\Gamma }$ for all sufficiently large $n$.

Every $q\in \mathrm{\Gamma }\cap {\mathcal{P}}_n(S)$ lies in $\bar{\mathrm{\Gamma }}$, so [F2] and the upper half of [F4] give $p^{\otimes n}(T_q)\le e^{-n{\inf }_{r\in \bar{\mathrm{\Gamma }}}D(r\mathrm{\parallel }p)}$. There are at most $(n+1{)}^{k-1}$ such types by [F3]; summing the classes from step 1.1 proves the finite upper bound, including the empty-set case.

For all sufficiently large $n$, the event contains $T_{q_n}$ from step 1.2, so [F4] gives probability at least $(n+1{)}^{-(k-1)}{e}^{-nD(q_n\mathrm{\parallel }p)}$. By [F6], $D(q_n\mathrm{\parallel }p)\to D(q\mathrm{\parallel }p)$; taking normalized logarithms and the liminf gives at least $-D(q\mathrm{\parallel }p)$.

If the event probability is positive, take logarithms of the finite upper bound in step 2.1 and divide by $n$. If it is zero, its normalized logarithm is $-\mathrm{\infty }$ by convention. Since $(k-1)\ln (n+1)\mathrm{/}n\to 0$, both cases yield the limsup inequality.

Since step 2.2 holds for every $q\in {\mathrm{\Gamma }}^{\circ }$, the liminf is at least $-{\inf }_{q\in {\mathrm{\Gamma }}^{\circ }}D(q\mathrm{\parallel }p)$. If ${\mathrm{\Gamma }}^{\circ }=\mathrm{\varnothing }$, the right-hand side is $-\mathrm{\infty }$, so the inequality is automatic.

When the interior and closure infima agree, steps 3.1 and 3.2 bound the limsup above and the liminf below by the same value. Since every liminf is at most the corresponding limsup, the limit exists and equals that common value. The proof covers the empty event by the stated extended-real conventions and uses the explicit rounding construction from step 1.2.

If $k=1$, then $\mathrm{\Delta }(S)=\{p\}$. For $p\in \mathrm{\Gamma }$, the empirical law is always $p$ under the product law [F7], both infima are $D(p\mathrm{\parallel }p)=0$, and the normalized log probability is $0$; for $p\mathrm{\notin }\mathrm{\Gamma }$, both infima are $+\mathrm{\infty }$ and the probability is zero. Thus the one-letter support boundary also satisfies the statement.