1. The Method of Types

The method of types refers to a set of combinatorial arguments used to establish Large Deviation Principles (LDP) for i.i.d. random variables taking values in a finite alphabet $Σ = {𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{| Σ |}}$ .

To demonstrate the argument, we consider i.i.d. random variables ${(𝑌_{𝑖})}_{𝑖 = 1}^{\infty}$ taking values in $Σ$ . Let $𝑀_{1} (Σ)$ (which can be identified as a subset of $ℝ^{| Σ |}$ ) denote the space of all probability measures (laws) on $Σ$ . Assuming the law of each $𝑌_{𝑖}$ is $𝜇 \in 𝑀_{1} (Σ)$ , we denote by $𝑃_{𝜇}$ the joint law of $(𝑌_{𝑖})_{𝑖 = 1}^{\infty}$ on the product space $Σ^{ℕ}$ .

Definition 1.1. The empirical measure $𝐿_{𝑛}^{𝐲}$ of a finite sequence $𝐲 = (𝑦_{1}, 𝑦_{2}, \dots, 𝑦_{𝑛}) \in Σ^{𝑛}$ is the measure in $𝑀_{1} (Σ)$ that records the frequency of occurrences of each $𝑎_{𝑖}$ ; namely, $𝐿_{𝑛}^{𝐲} = (𝐿_{𝑛}^{𝐲} (𝑎_{1}), \dots, 𝐿_{𝑛}^{𝐲} (𝑎_{| Σ |}))$ with

𝐿_{𝑛}^{𝐲} (𝑎_{𝑖}) = \frac{1}{𝑛} \sum_{𝑗 = 1}^{𝑛} 𝟙_{{𝑎_{𝑖}}} (𝑦_{𝑗}) .

Below are some related notions:

(Support) $Σ_{𝜈} = {𝑎_{𝑖} \in Σ : 𝜈 (𝑎_{𝑖}) > 0}$ for a measure $𝜈$ .
(Empirical distribution) ${ℒ︀}_{𝑛} = {𝐿_{𝑛}^{𝐲} : 𝐲 \in Σ^{𝑛}}$ .
(Types) $𝑇_{𝑛} (𝜈) = {𝐲 \in Σ^{𝑛} : 𝐿_{𝑛}^{𝐲} = 𝜈}$ for $𝜈 \in 𝑀_{1} (Σ)$ .
(Variational distance) For $𝜈, 𝜈' \in 𝑀_{1} (Σ)$ , $𝑑_{𝑉} (𝜈, 𝜈') ≔ \frac{1}{2} \sum_{𝑎 \in Σ} | 𝜈 (𝑎) - 𝜈' (𝑎) |$ .

We have the following fundamental estimates of the size of $𝑇_{𝑛} (𝜈)$ and ${ℒ︀}_{𝑛}$ .

Lemma 1.2.

$| 𝑇_{𝑛} (𝜈) | = (\binom{𝑛}{𝑛 𝜈 (𝑎_{1}), 𝑛 𝜈 (𝑎_{2}), \dots, 𝑛 𝜈 (𝑎_{| Σ |})})$ .
$1 \leq | {ℒ︀}_{𝑛} | \leq {(𝑛 + 1)}^{| Σ |}$ .

Proof. (1) It follows from a combinatorial argument.

(2) Note that

𝑛 \cdot {ℒ︀}_{𝑛} = {(𝑘_{𝑎})_{𝑎 \in Σ} : 𝑘_{𝑎} \in ℤ_{+}, \sum_{𝑎 \in Σ} 𝑘_{𝑎} = 𝑛},

where the latter set has cardinality

(\binom{𝑛 + | Σ | - 1}{| Σ | - 1}) = \prod_{𝑖 = 1}^{| Σ | - 1} \frac{𝑛 + 𝑖}{𝑖} \leq {(𝑛 + 1)}^{| Σ |},

as desired. $□$

In the following, we estimate the large deviation probabilities.

Definition 1.3 (entropy). Let $𝜈, 𝜂 \in 𝑀_{1} (Σ)$ .

The entropy of $𝜈 \in 𝑀_{1} (Σ)$ is
$𝐻 (𝜈) = - \sum_{𝑎 \in Σ} 𝜈 (𝑎) log 𝜈 (𝑎) .$
The relative entropy (or Kullback–Leibler divergence) of $𝜈$ with respect to $𝜂$ is
$𝐻 (𝜈 | 𝜂) = \sum_{𝑎 \in Σ} 𝜈 (𝑎) log \frac{𝜈 (𝑎)}{𝜂 (𝑎)} .$

We adopt the convention that $0 log 0 = 0$ and $0 log (\frac{0}{0}) = 0$ .

Remark 1.4. Let $𝑀_{1} (Σ)$ be endowed with the variational distance. Then,

$𝑀_{1} (Σ)$ is compact.
$𝐻 (\cdot)$ is continuous on $𝑀_{1} (Σ)$
$𝐻 (\cdot | 𝜇)$ is continuous on the compact set ${𝜈 \in 𝑀_{1} (Σ) : Σ_{𝜈} \subset Σ_{𝜇}}$ .

Lemma 1.5. If $𝐲 \in 𝑇_{𝑛} (𝜈)$ , then the following hold.

$𝑃_{𝜇} ((𝑌_{1}, \dots, 𝑌_{𝑛}) = 𝐲) = 𝑒^{- 𝑛 (𝐻 (𝜈) + 𝐻 (𝜈 | 𝜇))}$ .
${(𝑛 + 1)}^{- | Σ |} 𝑒^{𝑛 𝐻 (𝜈)} \leq | 𝑇_{𝑛} (𝜈) | \leq 𝑒^{𝑛 𝐻 (𝜈)}$ .
${(𝑛 + 1)}^{- | Σ |} 𝑒^{- 𝑛 𝐻 (𝜈 | 𝜇)} \leq 𝑃_{𝜇 (𝐿_{𝑛}^{𝐘} = 𝜈)} \leq 𝑒^{- 𝑛 𝐻 (𝜈 | 𝜇)}$ .

Proof. (1) The case $Σ_{𝜈} ⊈ Σ_{𝜇}$ is trivial, as $𝑃_{𝜇} ((𝑌_{1}, \dots, 𝑌_{𝑛}) = 𝐲) = 0$ and $𝐻 (𝜈 | 𝜇) = \infty$ . Assuming $Σ_{𝜈} \subseteq Σ_{𝜇}$ , we have by definition

𝑃_{𝜇} ((𝑌_{1}, \dots, 𝑌_{𝑛}) = 𝐲) = \prod_{𝑎 \in Σ} {𝜇 (𝑎)}^{𝑛 𝜈 (𝑎)} = 𝑒^{- 𝑛 (𝐻 (𝜈) + 𝐻 (𝜈 | 𝜇))} .

(2) The second inequality follows immediately from

1 \geq 𝑃_{𝜈} (𝐿_{𝑛}^{𝐘} = 𝜈) = 𝑒^{- 𝑛 𝐻 (𝜈)} | 𝑇_{𝑛} (𝜈) | .

To prove the first, we claim that if $Σ_{𝜈'} \subset Σ_{𝜈}$ , then

\begin{aligned} \frac{𝑃_{𝜈} (𝐿_{𝑛}^{𝐘} = 𝜈)}{𝑃_{𝜈} (𝐿_{𝑛}^{𝐘} = 𝜈')} & = \prod_{𝑎 \in Σ} \frac{| 𝑇_{𝑛} (𝜈) | {𝜈 (𝑎)}^{𝑛 𝜈 (𝑎)}}{| 𝑇_{𝑛} (𝜈') | {𝜈 (𝑎)}^{𝑛 𝜈' (𝑎)}} \\ = \prod_{𝑎 \in Σ} \frac{(𝑛 𝜈' (𝑎))!}{(𝑛 𝜈 (𝑎))!} {𝜈 (𝑎)}^{𝑛 𝜈 (𝑎) - 𝑛 𝜈' (𝑎)} \geq 1 . \end{aligned}

Indeed, the last expression consists of terms of the form $\frac{𝑚!}{ℓ!} {(\frac{ℓ}{𝑛})}^{ℓ - 𝑚}$ where the inequality is validated using the fact $\frac{𝑚!}{ℓ!} \geq ℓ^{𝑚 - ℓ}$ :

\frac{𝑃_{𝜈} (𝐿_{𝑛}^{𝐘} \in 𝑇_{𝑛} (𝜈))}{𝑃_{𝜈'} (𝐿_{𝑛}^{𝐘} \in 𝑇_{𝑛} (𝜈))} \geq 𝑛^{𝑛 [\sum_{𝑎 \in Σ} 𝜈' (𝑎) - \sum_{𝑎 \in Σ} 𝜈 (𝑎)]} = 1 .

To prove the desired inequality, observe that

1 = \sum_{𝜈' \in {ℒ︀}_{𝑛}} 𝑃_{𝜈} (𝐿_{𝑛}^{𝐘} = 𝜈') \leq | {ℒ︀}_{𝑛} | 𝑃_{𝜈} (𝐿_{𝑛}^{𝐘} = 𝜈) = | {ℒ︀}_{𝑛} | 𝑒^{- 𝑛 𝐻 (𝜈)} | 𝑇_{𝑛} (𝜈) | .

The proof is concluded by applying Lemma 1.2.

(3) Combining (1) and (2), we arrive at the estimate

𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} = 𝜈) = | 𝑇_{𝑛} (𝜈) | 𝑃_{𝜇} ((𝑌_{1}, \dots, 𝑌_{𝑛}) = 𝐲) \leq | 𝑇_{𝑛} (𝜈) | 𝑒^{- 𝑛 (𝐻 (𝜈) + 𝐻 (𝜈 | 𝜇))} \leq 𝑒^{- 𝑛 (𝐻 (𝜈 | 𝜇))},

whereas the other inequality follows from the lower bound on $| 𝑇_{𝑛} (𝜈) |$ . $□$

Theorem 1.6 (Sanov). For every set $Γ \subseteq 𝑀_{1} (Σ)$ of probability measures,

\begin{aligned} - inf_{𝜈 \in \overset{˚}{Γ}} 𝐻 (𝜈 | 𝜇) & \leq \underset{𝑛 \to \infty}{lim inf} \frac{1}{𝑛} log 𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} \in Γ) \\ \leq \underset{𝑛 \to \infty}{lim sup} \frac{1}{𝑛} log 𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} \in Γ) \leq - inf_{𝜈 \in \overset{─}{Γ}} 𝐻 (𝜈 | 𝜇) . \end{aligned}

Proof. By Lemma 1.5, we obtain the upper bound:

\begin{aligned} 𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} \in Γ) & = \sum_{𝜈 \in Γ \cap {ℒ︀}_{𝑛}} 𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} = 𝜈) \leq | Γ \cap {ℒ︀}_{𝑛} | 𝑒^{- 𝑛 {inf}_{𝜈 \in Γ \cap {ℒ︀}_{𝑛}} 𝐻 (𝜈 | 𝜇)} \\ \leq {(𝑛 + 1)}^{| Σ |} 𝑒^{- 𝑛 {inf}_{𝜈 \in Γ \cap {ℒ︀}_{𝑛}} 𝐻 (𝜈 | 𝜇)}, \end{aligned}

which yields

\underset{𝑛 \to \infty}{lim sup} \frac{1}{𝑛} log 𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} \in Γ) \leq - \underset{𝑛 \to \infty}{lim inf} inf_{𝜈 \in Γ \cap {ℒ︀}_{𝑛}} 𝐻 (𝜈 | 𝜇) \leq - inf_{𝜈 \in \overset{─}{Γ}} 𝐻 (𝜈 | 𝜇) .

To prove the lower bound, we begin with an analogous estimate

𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} \in Γ) = \sum_{𝜈 \in Γ \cap {ℒ︀}_{𝑛}} 𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} = 𝜈) \geq {(𝑛 + 1)}^{- | Σ |} 𝑒^{- 𝑛 {inf}_{𝜈 \in Γ \cap {ℒ︀}_{𝑛}} 𝐻 (𝜈 | 𝜇)} .

Since ${sup}_{𝜈 \in 𝑀_{1} (Σ)} 𝑑_{𝑉} (𝜈, {ℒ︀}_{𝑛}) \leq \frac{| Σ |}{2 𝑛}$ , for every $𝜈 \in \overset{˚}{Γ}$ with $Σ_{𝜈} \subset Σ_{𝜇}$ , one can find for every sufficiently large $𝑛$ some $𝜈_{𝑛} \in \overset{˚}{Γ} \cap {ℒ︀}_{𝑛}$ such that $𝜈_{𝑛} \to 𝜈$ . By the continuity of the relative entropy on the restricted domain,

\underset{𝑛 \to \infty}{lim inf} \frac{1}{𝑛} log 𝑃_{𝜇} (𝐿_{𝑛}^{𝐘} \in Γ) \geq - \underset{𝑛 \to \infty}{lim sup} 𝐻 (𝜈_{𝑛} | 𝜇) = - 𝐻 (𝜈 | 𝜇) .

The theorem follows since $𝜈 \in \overset{˚}{Γ}$ is arbitrary as long as $Σ_{𝜈} \subset Σ_{𝜇}$ , and $𝐻 (𝜈 | 𝜇) = \infty$ whenever $Σ_{𝜈} ⊈ Σ_{𝜇}$ . $□$

As an application of Sanov’s theorem, we prove a version of Cramér’s theorem concerning Large Deviations for the empirical mean. Let $𝑓 : Σ \to ℝ$ be a function. We identify $𝑓$ with the vector $𝐟 \in ℝ^{| Σ |}$ so that the empirical average ${\hat{𝑆}}_{𝑛} = \frac{1}{𝑛} \sum_{𝑖 = 1}^{𝑛} 𝑓 (𝑌_{𝑖})$ can be written as the inner product ${\hat{𝑆}}_{𝑛} = ⟨ 𝐿_{𝑛}^{𝐘}, 𝐟 ⟩$ . Sanov’s theorem then implies the following result.

Theorem 1.7 (Cramér). For any set $𝐴 \subseteq ℝ$ ,

\begin{aligned} - inf_{𝑥 \in \overset{˚}{𝐴}} 𝐼 (𝑥) & \leq \underset{𝑛 \to \infty}{lim inf} \frac{1}{𝑛} log 𝑃_{𝜇} ({\hat{𝑆}}_{𝑛} \in 𝐴) \\ \leq \underset{𝑛 \to \infty}{lim sup} \frac{1}{𝑛} log 𝑃_{𝜇} ({\hat{𝑆}}_{𝑛} \in 𝐴) \leq - inf_{𝑥 \in \overset{─}{𝐴}} 𝐼 (𝑥), \end{aligned}

where $𝐼 (𝑥) = {inf}_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇)$ . The rate function $𝐼$ is continuous on the interval $[{min}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎), {max}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎)]$ and satisfies

𝐼 (𝑥) = sup_{𝜆 \in ℝ} [𝜆 𝑥 - Λ (𝜆)],

where

Λ (𝜆) = log \sum_{𝑎 \in Σ} 𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)} .

Proof. We provide two proofs of the theorem.

(1) The formula

𝐼 (𝑥) = inf_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇) = inf_{𝜈 \in 𝑀_{1} (Σ)} sup_{𝜆 \in ℝ} [𝜆 𝑥 - \sum_{𝑎 \in Σ} 𝜈 (𝑎) log (\frac{𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)}}{𝜈 (𝑎)})]

follows from that ${\hat{𝑆}}_{𝑛} = ⟨ 𝐿_{𝑛}^{𝐘}, 𝐟 ⟩$ and that $𝜈 \mapsto ⟨ 𝜈, 𝐟 ⟩$ is a continuous function. Moreover, in view of the formula, $𝐼$ is clearly continuous on its effective domain $[{min}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎), {max}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎)]$ . We note that the optimization problem here is a classical problem in convex optimization where strong duality holds (see, for example, [1, Section 5]); specifically, one can swap $inf$ and $sup$ without changing the value of the expression:

𝐼 (𝑥) = sup_{𝜆 \in ℝ} inf_{𝜈 \in 𝑀_{1} (Σ)} [𝜆 𝑥 - \sum_{𝑎 \in Σ} 𝜈 (𝑎) log (\frac{𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)}}{𝜈 (𝑎)})],

The inner minimization can then be solved using Gibbs inequality (or Jensen’s inequality applied to $𝑥 \mapsto 𝑥 log 𝑥$ ), yielding

𝐼 (𝑥) = sup_{𝜆 \in ℝ} [𝜆 𝑥 - log \sum_{𝑎 \in Σ} 𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)}] .

This establishes the Fenchel–Legendre transform representation.

(2) Alternatively, this result is a special case of Cramér’s theorem for real-valued random variables, and its rate function $𝐼 (𝑥) = Λ^{*} (𝑥)$ , a fortiori, is the Fenchel–Legendre transform of the logarithmic moment generating function

Λ (𝜆) = log 𝔼 [𝑒^{𝜆 𝑓 (𝑌_{1})}] = log \sum_{𝑎 \in Σ} 𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)} .

It remains to show that $Λ^{*} (𝑥) = {inf}_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇)$ , for, once established, the continuity of $𝐼$ follows from that of $𝐻 (\cdot | 𝜇)$ immediately. To this end, it suffices to show that $Λ^{*} (𝑥) \geq {inf}_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇)$ , since by Gibbs’ inequality,

𝜆 ⟨ 𝐟, 𝜈 ⟩ - 𝐻 (𝜈 | 𝜇) = \sum_{𝑎 \in Σ} 𝜈 (𝑎) log (\frac{𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)}}{𝜈 (𝑎)}) \leq Λ (𝜆)

for all $𝜈 \in 𝑀_{1} (Σ)$ and $𝜆 \in ℝ$ , implying $Λ^{*} (𝑥) \leq {inf}_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇)$ .

Recall that $Λ$ is convex and differentiable in the interior of its effective domain. By asymptotic analysis of the derivative $Λ' (𝜆)$ , for every $𝑥 \in ({min}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎), {max}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎))$ , there exists $𝜆 \in ℝ$ such that

𝑥 = Λ' (𝜆) = \frac{\sum_{𝑎 \in Σ} 𝑓 (𝑎) 𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)}}{\sum_{𝑎 \in Σ} 𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)}} \Rightarrow Λ^{*} (𝑥) = 𝜆 𝑥 - Λ (𝜆) .

Choosing $𝜂_{𝑎} = \frac{𝜇 (𝑎) 𝑒^{𝜆 𝑓 (𝑎)}}{\sum_{𝑏} 𝜇 (𝑏) 𝑒^{𝜆 𝑓 (𝑏)}}$ , we have $⟨ 𝜂, 𝐟 ⟩ = 𝑥$ and

Λ^{*} (𝑥) = 𝜆 𝑥 - Λ (𝜆) = 𝐻 (𝜂 | 𝜇) \geq inf_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇)

as desired. For the boundary point $𝑥 = {max}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎)$ (the case for $min$ is similar), we have that

inf_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇) = - log 𝜇 ({𝑎 \in Σ : 𝑓 (𝑎) = 𝑥}) .

and, through direct evaluation, that

Λ^{*} (𝑥) = lim_{𝜆 \to \infty} [𝜆 𝑥 - Λ (𝜆)] = - log 𝜇 ({𝑎 \in Σ : 𝑓 (𝑎) = 𝑥}) .

Combining these results proves $Λ^{*} (𝑥) = {inf}_{𝜈 : ⟨ 𝜈, 𝐟 ⟩ = 𝑥} 𝐻 (𝜈 | 𝜇)$ . Finally, for $𝑥 \notin [{min}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎), {max}_{𝑎 \in Σ_{𝜇}} 𝑓 (𝑎)]$ , one can show $Λ^{*} (𝑥) = \infty$ . This concludes the proof. $□$

References

[1] Boyd, Stephen, and Vandenberghe, Lieven, Convex Optimization, Cambridge University Press, 2004.↩