Method of Types and Finite Large Deviations — Examples

For $q(1)=1\mathrm{/}5$, the counts are $(8,2)$, so $\mathrm{\mid }{T}_q\mathrm{\mid }=10!\mathrm{/}(8!2!)=45$ and $e^{10H(q)}=(1\mathrm{/}5{)}^{-2}(4\mathrm{/}5{)}^{-8}=5^{10}\mathrm{/}{4}^8$.

For $q(1)=1\mathrm{/}2$, the counts are $(5,5)$, so $\mathrm{\mid }{T}_q\mathrm{\mid }=10!\mathrm{/}(5!5!)=252$ and $e^{10H(q)}=2^{10}=1024$. Since $1024\le 252\cdot 11=\mathrm{2,772}$ and $252\le \mathrm{1,024}$, we have $1024\mathrm{/}11\le 252\le 1024$, retaining the polynomial factor in [F3].

Since $5^{10}=\mathrm{9,765,625}$, $4^8=\mathrm{65,536}$, $45\cdot 11\cdot 4^8=\mathrm{32,440,320}$, and $45\cdot 4^8=\mathrm{2,949,120}$, cross-multiplication in step 1.1 gives $e^{10H(q)}\mathrm{/}11\le 45\le e^{10H(q)}$, as [F3] states.

At endpoint types $q=(1,0)$ and $q=(0,1)$, each type class is a singleton and $H(q)=0$, so the lower cardinality bound is $1\mathrm{/}11$, while the class size and upper bound equal $1$; thus [F3] also covers zero-coordinate boundary cases.

If $p=0$, every coordinate equals $0$ almost surely by [F10], so the tail is zero and $d(q_n\mathrm{\parallel }p)=d(a\mathrm{\parallel }p)=+\mathrm{\infty }$; both finite bounds have right-hand sides zero. If $0<p<1$, the tail is the union of binary type classes with $q\ge a$, and the attainable type $q_n=\lceil na\rceil \mathrm{/}n$ belongs to the event, so [F3] gives the lower bound.

Suppose $0<p<1$ and $0<a<1$. For every $x\in (p,1)$, [F7] gives $\frac{d}{dx}d(x\mathrm{\parallel }p)=\ln \frac{x(1-p)}{p(1-x)}>0$. For any $a\le u<v<1$, the finite logarithmic formula is continuous on $[u,v]$ and differentiable on $(u,v)$, so [F8] gives $d(v\mathrm{\parallel }p)>d(u\mathrm{\parallel }p)$. Thus $d(\cdot \mathrm{\parallel }p)$ is increasing on $[a,1)$, and continuity [F4] extends $d(q\mathrm{\parallel }p)\ge d(a\mathrm{\parallel }p)$ to $q=1$.

For $0<p<1$ and $0<a<1$, there are at most $n+1$ binary types by [F9]. Each tail type has probability at most $e^{-nd(q\mathrm{\parallel }p)}$ by [F3], and step 1.2 gives $d(q\mathrm{\parallel }p)\ge d(a\mathrm{\parallel }p)$, so summing the types proves the finite upper bound.

If $0<p<a<1$, then for $\mathrm{\Gamma }=[a,1]$ the relative interior in $[0,1]$ is $(a,1]$ and the closure is $[a,1]$. By step 1.2 and continuity [F4], both divergence infima equal $d(a\mathrm{\parallel }p)$, so [F5] gives the stated limit. If $a=1$ and $0<p<1$, the event is exactly all ones and has probability $p^n=e^{-nd(1\mathrm{\parallel }p)}$, giving the limit directly. The case $p=0$ is in step 1.1.

For $0<p<1$ and $0<a<1$, summing the type upper bounds from step 2.1 yields the displayed finite upper bound; when $a=1$ and $0<p<1$, step 2.2 gives the exact value $p^n\le (n+1)p^n$, while $p=0$ is covered in step 1.1.

For $p=1\mathrm{/}2$, $a=3\mathrm{/}4$, and $n=4$, the event contains four words with three ones and one with four, so its probability is $5\mathrm{/}16$. By [F10], the four coordinates are independent and take values in $[0,1]$, hence are integrable. Thus [F6] applies with ${\sum }_i(X_i-\mathbb{E}{X}_i)\ge 1$ on the event and ${\sum }_i(b_i-a_i{)}^2=4$ for bounds $a_i=0,b_i=1$. Its exponent is $-2(1{)}^2\mathrm{/}4=-1\mathrm{/}2$, giving $b_{1\mathrm{/}2}^{\otimes 4}({\widehat{p}}_4\ge 3\mathrm{/}4)\le e^{-1\mathrm{/}2}$. This comparison uses [A1]; the finite type and Sanov calculations in steps 1.1–3.1 are choice-free.

The words with type $q$ are $01$ and $10$, so $\mathrm{\mid }{T}_q\mathrm{\mid }=2$.

By [F2], $H(q)=\ln 2$, and therefore $e^{2H(q)}=4\mathrm{\ne }2=\mathrm{\mid }{T}_q\mathrm{\mid }$. This single attainable type refutes the universal exact-equality claim.

At the boundary type $q=(1,0)$, the only word is $00$, and both $\mathrm{\mid }{T}_q\mathrm{\mid }$ and $e^{2H(q)}$ equal $1$; this boundary equality does not rescue the refuted universal claim and is consistent with [F3].