AEP and Typicality

Table of Contents

• 0. Motivation: What Is a Typical Sequence?
  • 0.1 A Worked Example: The Biased Coin
  • 0.2 The Typicality Spectrum
  • 0.3 Two Competing Exponentials
  • 0.4 What Entropy Measures
• 1. The AEP: Statement and Proof
  • 1.1 Setup and Notation
  • 1.2 Statement of the AEP
  • 1.3 Proof via the Weak Law of Large Numbers
  • 1.4 Conceptual Connection to the LLN
• 2. The Typical Set
  • 2.1 Definition
  • 2.2 Property 1: High Probability
  • 2.3 Property 2: Upper Bound on Size
  • 2.4 Property 3: Lower Bound on Size
  • 2.5 Intuitive Picture
• 3. Source Coding: Shannon’s First Theorem
  • 3.1 Problem Setup
  • 3.2 Achievability
  • 3.3 Converse
  • 3.4 The Theorem
• 4. Method of Types
  • 4.1 Types and Type Classes
  • 4.2 Number of Types
  • 4.3 Size of a Type Class
  • 4.4 Probability of a Type Class
  • 4.5 Sanov’s Theorem
  • 4.6 Why the Method of Types Is Powerful
• 5. Strong Typicality
  • 5.1 Definition of Strong Typicality
  • 5.2 Strong Implies Weak
  • 5.3 Joint Typicality
• 6. Connections and Applications
  • 6.1 Channel Coding
  • 6.2 Rate-Distortion Theory
  • 6.3 Statistical Physics
• References

0. Motivation: What Is a Typical Sequence?

0.1 A Worked Example: The Biased Coin

Suppose \(X \sim \mathrm{Bernoulli}(0.9)\) — heads (1) with probability \(0.9\), tails (0) with probability \(0.1\). Flip this coin \(n = 1000\) times and observe a sequence \(x^{1000} \in \{0,1\}^{1000}\).

Which sequence is most likely?

The single most probable sequence is all-heads \((1,1,\ldots,1)\). Its probability is \[p(\text{all-heads}) = 0.9^{1000} \approx 2^{-152}.\]

Now take any sequence with exactly 900 heads and 100 tails, say the specific sequence \((1,1,\ldots,1,0,0,\ldots,0)\). It has probability \[p(\text{900 heads, 100 tails}) = 0.9^{900} \cdot 0.1^{100} \approx 2^{-469}.\]

So the all-heads sequence is \(2^{317}\) times more probable than any individual 900-heads sequence. Yet how many sequences have exactly 900 heads?

\[\binom{1000}{900} \approx 2^{1000 \cdot H_2(0.9)} = 2^{469},\]

where \(H_2(f) = -f\log_2 f - (1-f)\log_2(1-f)\) is the binary entropy function. The combined probability of all 900-heads sequences is therefore

\[\underbrace{2^{469}}_{\text{count}} \times \underbrace{2^{-469}}_{\text{individual}} = 2^0 = 1.\]

The all-heads sequence, by contrast, accounts for just \(2^{-152}\) of total probability — negligible.

0.2 The Typicality Spectrum

We can assign every sequence \(x^n\) a typicality score: its empirical entropy, defined as \[\hat{H}(x^n) \;=\; -\frac{1}{n}\log_2 p(x^n).\]

For binary sequences, if \(x^n\) has fraction \(f\) of ones, then \[\hat{H}(x^n) = -f\log_2(0.9) - (1-f)\log_2(0.1).\]

A sequence is typical when \(\hat{H}(x^n)\) is close to the true entropy \(H(X)\). For \(X \sim \mathrm{Bernoulli}(0.9)\): \[H(0.9) = -0.9\log_2(0.9) - 0.1\log_2(0.1) \approx 0.469 \text{ bits/symbol}.\]

The table below shows the typicality spectrum across different sequence types (in \(n = 1000\) flips):

The empirical entropy \(\hat{H}\) is minimised at \(f = 0.9\) (equal to \(H(0.9)\)) and grows as \(f\) departs from the true parameter. Sequences near \(f = 0.9\) are typical; those far from it are atypical — regardless of whether they individually seem “likely.”

0.3 Two Competing Exponentials

The reason typical sequences dominate can be understood through two competing exponentials:

flowchart LR
    A["Sequences with
fraction f of heads"]
    A --> B["Count
≈ 2^(n · H₂(f))
how many"]
    A --> C["Individual probability
= 2^(-n · h(f))
how likely each one is"]
    B --> D["Total probability
≈ 2^(n · (H₂(f) - h(f)))"]
    C --> D
    D --> E{"Is f = 0.9?"}
    E -->|"yes"| F["Exponent = 0
Total prob ≈ 1"]
    E -->|"no"| G["Exponent < 0
Total prob → 0 exponentially"]

Here \(h(f) = -f\log_2(0.9) - (1-f)\log_2(0.1)\) is the cross-entropy of Bernoulli(\(f\)) against the true Bernoulli(0.9), and \(H_2(f)\) is the self-entropy of Bernoulli(\(f\)). Their difference equals the negative KL divergence:

\[H_2(f) - h(f) = -D_{\mathrm{KL}}(\mathrm{Bernoulli}(f)\,\|\,\mathrm{Bernoulli}(0.9)) \leq 0,\]

with equality if and only if \(f = 0.9\).

So the total probability of a “type” (sequences with fraction \(f\) of heads) decays exponentially in \(D_{\mathrm{KL}}(\text{empirical} \| \text{true})\). The typical set is the type where this KL divergence is zero — where empirical statistics exactly match the source. This is Sanov’s theorem in miniature (Section 4.5).

0.4 What Entropy Measures

The AEP and typicality sharpen the operational meaning of entropy \(H(X)\):

1. Effective alphabet size. Even though there are \(2^n\) sequences of length \(n\), almost all probability concentrates on \(\approx 2^{nH(X)}\) of them. Entropy governs the effective number of distinguishable outcomes per symbol.

2. Compression rate. To transmit a typical sequence losslessly, you need \(nH(X)\) bits — no more, no less. The AEP makes this precise (Section 3).

3. Surprise per symbol. \(H(X) = \mathbb{E}[-\log p(X)]\) is the expected surprise per observation. Typical sequences are precisely those where the realised surprise \(-\frac{1}{n}\log p(x^n)\) matches the expected surprise \(H(X)\).

1. The AEP: Statement and Proof

1.1 Setup and Notation

Throughout this note, let \(\mathcal{X}\) be a finite alphabet. Fix a probability mass function \(p : \mathcal{X} \to [0,1]\). We draw an i.i.d. sequence

\[X_1, X_2, \ldots, X_n \overset{\text{i.i.d.}}{\sim} p.\]

Write \(X^n = (X_1, \ldots, X_n)\) and \(x^n = (x_1, \ldots, x_n) \in \mathcal{X}^n\) for a realisation. Since the \(X_i\) are independent, the joint probability factorises as

\[p(x^n) = \prod_{i=1}^n p(x_i).\]

All logarithms are base 2 and entropy is measured in bits. The entropy of \(X \sim p\) is

\[H(X) = -\sum_{x \in \mathcal{X}} p(x) \log p(x) = \mathbb{E}[-\log p(X)].\]

We assume \(p(x) > 0\) for all \(x\) in the support; symbols with \(p(x) = 0\) may be ignored.

1.2 Statement of the AEP

Theorem (Asymptotic Equipartition Property). Let \(X_1, X_2, \ldots \overset{\text{i.i.d.}}{\sim} p\). Then

\[-\frac{1}{n}\log p(X^n) \xrightarrow{\;p\;} H(X) \quad \text{as } n \to \infty.\]

That is, for every \(\varepsilon > 0\),

\[\Pr\!\left[\left|-\frac{1}{n}\log p(X^n) - H(X)\right| > \varepsilon\right] \to 0 \quad \text{as } n \to \infty.\]

The quantity \(-\frac{1}{n}\log p(X^n)\) is the empirical entropy of the sequence, also called the normalised log-likelihood (with a sign flip). The AEP says that this random variable concentrates around the true entropy \(H(X)\).

1.3 Proof via the Weak Law of Large Numbers

📐 The proof is a direct application of the Weak Law of Large Numbers (WLLN).

Proof. Because \(X_1, \ldots, X_n\) are i.i.d. with joint p.m.f. \(p(x^n) = \prod_{i=1}^n p(x_i)\), we have

\[-\frac{1}{n}\log p(X^n) = -\frac{1}{n}\sum_{i=1}^n \log p(X_i).\]

Define the random variables \(Z_i = -\log p(X_i)\). Since the \(X_i\) are i.i.d., so are the \(Z_i\). Their common expectation is

\[\mathbb{E}[Z_i] = \mathbb{E}[-\log p(X)] = H(X).\]

The variance satisfies

\[\operatorname{Var}[Z_i] = \mathbb{E}[(\log p(X))^2] - H(X)^2,\]

which is finite because \(\mathcal{X}\) is finite. By the WLLN,

\[\frac{1}{n}\sum_{i=1}^n Z_i \xrightarrow{\;p\;} \mathbb{E}[Z_1] = H(X). \qquad \square\]

1.4 Conceptual Connection to the LLN

The AEP is the information-theoretic analogue of the LLN. Just as the empirical mean of bounded i.i.d. random variables concentrates around the population mean, the empirical entropy concentrates around \(H(X)\). Operationally, this means that for large \(n\):

• nearly all probability mass is carried by sequences \(x^n\) with \(p(x^n) \approx 2^{-nH(X)}\),
• this set of sequences has size \(\approx 2^{nH(X)}\),
• every such sequence looks “equally likely” to zeroth order in the exponent.

The name equipartition refers to this approximate equal-probability property within the typical set.

2. The Typical Set

2.1 Definition

Definition (Weakly Typical Set). Fix \(\varepsilon > 0\) and \(n \geq 1\). The \(\varepsilon\)-typical set \(\mathcal{T}_\varepsilon^{(n)}\) is

\[\mathcal{T}_\varepsilon^{(n)} = \left\{x^n \in \mathcal{X}^n : \left|-\frac{1}{n}\log p(x^n) - H(X)\right| \leq \varepsilon\right\}.\]

Equivalently, \(x^n \in \mathcal{T}_\varepsilon^{(n)}\) if and only if

\[2^{-n(H(X)+\varepsilon)} \leq p(x^n) \leq 2^{-n(H(X)-\varepsilon)}.\]

Every sequence in \(\mathcal{T}_\varepsilon^{(n)}\) has probability in the window \([2^{-n(H+\varepsilon)}, 2^{-n(H-\varepsilon)}]\). This is sometimes called weak typicality to distinguish it from the stronger notion defined in Section 5.

2.2 Property 1: High Probability

🔑 Proposition 1. For every \(\varepsilon > 0\) and \(\delta > 0\), there exists \(N\) such that for all \(n \geq N\),

\[\Pr\!\left[X^n \in \mathcal{T}_\varepsilon^{(n)}\right] \geq 1 - \delta.\]

Proof. This is an immediate consequence of the AEP. Since \(-\frac{1}{n}\log p(X^n) \xrightarrow{p} H(X)\), for any \(\varepsilon > 0\):

\[\Pr\!\left[\left|-\frac{1}{n}\log p(X^n) - H(X)\right| > \varepsilon\right] \to 0,\]

which is the same as \(\Pr[X^n \notin \mathcal{T}_\varepsilon^{(n)}] \to 0\), so \(\Pr[X^n \in \mathcal{T}_\varepsilon^{(n)}] \to 1\). \(\square\)

2.3 Property 2: Upper Bound on Size

Proposition 2. For all \(n \geq 1\),

\[\left|\mathcal{T}_\varepsilon^{(n)}\right| \leq 2^{n(H(X)+\varepsilon)}.\]

Proof. Every sequence \(x^n \in \mathcal{T}_\varepsilon^{(n)}\) satisfies \(p(x^n) \geq 2^{-n(H+\varepsilon)}\). Summing over all sequences in the typical set:

\[1 \geq \sum_{x^n \in \mathcal{T}_\varepsilon^{(n)}} p(x^n) \geq \left|\mathcal{T}_\varepsilon^{(n)}\right| \cdot 2^{-n(H+\varepsilon)}.\]

Rearranging: \(|\mathcal{T}_\varepsilon^{(n)}| \leq 2^{n(H+\varepsilon)}\). \(\square\)

2.4 Property 3: Lower Bound on Size

Proposition 3. For every \(\varepsilon > 0\) and \(\delta > 0\), for all sufficiently large \(n\),

\[\left|\mathcal{T}_\varepsilon^{(n)}\right| \geq (1-\delta)\,2^{n(H(X)-\varepsilon)}.\]

Proof. Every sequence \(x^n \in \mathcal{T}_\varepsilon^{(n)}\) satisfies \(p(x^n) \leq 2^{-n(H-\varepsilon)}\). By Property 1, for large enough \(n\):

\[1 - \delta \leq \Pr[X^n \in \mathcal{T}_\varepsilon^{(n)}] = \sum_{x^n \in \mathcal{T}_\varepsilon^{(n)}} p(x^n) \leq \left|\mathcal{T}_\varepsilon^{(n)}\right| \cdot 2^{-n(H-\varepsilon)}.\]

Rearranging: \(|\mathcal{T}_\varepsilon^{(n)}| \geq (1-\delta)\,2^{n(H-\varepsilon)}\). \(\square\)

2.5 Intuitive Picture

The total number of sequences in \(\mathcal{X}^n\) is \(|\mathcal{X}|^n = 2^{n\log|\mathcal{X}|}\). The typical set has only \(\approx 2^{nH(X)}\) elements. Since \(H(X) \leq \log|\mathcal{X}|\) with equality iff \(p\) is uniform, the typical set is an exponentially small fraction of all sequences:

\[\frac{|\mathcal{T}_\varepsilon^{(n)}|}{|\mathcal{X}|^n} \approx 2^{-n(\log|\mathcal{X}| - H(X))} \to 0 \quad \text{(for non-uniform } p\text{)}.\]

Surprisingly, this exponentially small set carries almost all the probability mass. This is the heart of Shannon’s insight: the randomness of a source concentrates on a tiny “cloud” in sequence space.

flowchart LR
    A["All sequences
X^n
Size: 2^(n log|X|)"]
    B["Typical set
T_eps^(n)
Size: ~2^(nH)"]
    C["Non-typical sequences
Prob -> 0"]

    A -->|"contains"| B
    A -->|"contains"| C
    B -->|"Pr[X^n in T] -> 1"| B

3. Source Coding: Shannon’s First Theorem

3.1 Problem Setup

The fixed-length lossless source coding problem is: given \(n\) i.i.d. symbols \(X^n \sim p^n\), encode them into a binary string of length \(nR\) bits (a rate-\(R\) code), and then recover \(X^n\) exactly (with probability of error \(P_e^{(n)} \to 0\)).

Formally, an \((n, R)\) source code consists of: - an encoder \(f : \mathcal{X}^n \to \{0,1\}^{\lfloor nR \rfloor}\), - a decoder \(g : \{0,1\}^{\lfloor nR \rfloor} \to \mathcal{X}^n\).

The error probability is \(P_e^{(n)} = \Pr[g(f(X^n)) \neq X^n]\). A rate \(R\) is achievable if there exists a sequence of \((n, R)\) codes with \(P_e^{(n)} \to 0\).

3.2 Achievability

📐 Theorem (Achievability). If \(R > H(X)\), then \(R\) is achievable.

Proof. The typical set encoder works as follows: for a chosen \(\varepsilon > 0\) with \(R > H(X) + \varepsilon\) (possible since \(R > H(X)\)), define \(\mathcal{T}_\varepsilon^{(n)}\).

1. Index the typical set. Order the elements of \(\mathcal{T}_\varepsilon^{(n)}\) arbitrarily. By Property 2, \(|\mathcal{T}_\varepsilon^{(n)}| \leq 2^{n(H+\varepsilon)} \leq 2^{nR}\). So every typical sequence can be indexed by a binary string of length \(\lfloor nR \rfloor\).

2. Encoder. If \(x^n \in \mathcal{T}_\varepsilon^{(n)}\), encode as a leading 0 followed by the index (using at most \(\lfloor nR \rfloor\) bits total). If \(x^n \notin \mathcal{T}_\varepsilon^{(n)}\), output any fixed \(nR\)-bit string (declare an error).

3. Decoder. Read the index, look up the typical sequence. If the encoder declared error, output any symbol.

Error analysis. \(P_e^{(n)} = \Pr[X^n \notin \mathcal{T}_\varepsilon^{(n)}] \to 0\) by Property 1. \(\square\)

import numpy as np

def typical_set_encode(source_seq, pmf, epsilon):
    """
    Encode source_seq using typical-set encoding.
    Returns (codeword, is_typical).
    """
    n = len(source_seq)
    alphabet = list(pmf.keys())
    H = -sum(p * np.log2(p) for p in pmf.values() if p > 0)

    # Compute empirical log-prob
    log_prob = sum(np.log2(pmf[symbol]) for symbol in source_seq)
    empirical_entropy = -log_prob / n

    is_typical = abs(empirical_entropy - H) <= epsilon
    return is_typical

3.3 Converse

📐 Theorem (Converse). If \(R < H(X)\), then \(P_e^{(n)} \to 1\) for any sequence of \((n, R)\) codes.

Proof. The image of the encoder \(f\) has size at most \(2^{nR}\), so the encoder partitions \(\mathcal{X}^n\) into at most \(2^{nR}\) cells. For perfect recovery, each cell must be a singleton. Thus the encoder can correctly represent at most \(2^{nR}\) sequences.

Since \(R < H(X)\), choose \(\varepsilon > 0\) small enough that \(R < H(X) - \varepsilon\). Let \(B_n = \{x^n : f \text{ is injective on } x^n\}\); then \(|B_n| \leq 2^{nR} \leq 2^{n(H-\varepsilon)}\). By Exercise 4 (or by its proof inline), \(\Pr[X^n \in B_n] \to 0\), so \(P_e^{(n)} = 1 - \Pr[X^n \in B_n] \to 1\). \(\square\)

3.4 The Theorem

🔑 Theorem (Shannon’s Noiseless Source Coding Theorem / First Theorem). The minimum achievable rate for lossless fixed-length source coding of an i.i.d. source \(X \sim p\) is

\[R^* = H(X) \text{ bits/symbol.}\]

More precisely: for every \(R > H(X)\), rate \(R\) is achievable; for every \(R < H(X)\), any sequence of \((n, R)\) codes has \(P_e^{(n)} \to 1\).

This bound only holds for fixed-length codes; variable-length codes (Huffman, arithmetic) can achieve \(H(X)\) exactly in the limit without any error.

from itertools import product
import math

def build_typical_set(n, p, epsilon):
    """Build typical set for Bernoulli(p) source."""
    H = -p * math.log2(p) - (1-p) * math.log2(1-p)
    typical = {}
    idx = 0
    for bits in product([0, 1], repeat=n):
        k = sum(bits)  # number of 1s
        log_prob = k * math.log2(p) + (n - k) * math.log2(1 - p)
        emp_entropy = -log_prob / n
        if abs(emp_entropy - H) <= epsilon:
            typical[bits] = idx
            idx += 1
    return typical, idx

def encode(x_n, typical_set, n_bits):
    if x_n in typical_set:
        idx = typical_set[x_n]
        return (True, format(idx, f'0{n_bits}b'))
    else:
        return (False, '0' * n_bits)  # error codeword

4. Method of Types

4.1 Types and Type Classes

The method of types (Csiszár & Körner) is a combinatorial framework that refines the typical-set approach. Rather than grouping sequences by empirical entropy, it groups them by full empirical distribution.

Definition (Type / Empirical Distribution). Let \(x^n \in \mathcal{X}^n\). The type of \(x^n\), written \(P_{x^n}\), is the empirical distribution (frequency histogram):

\[P_{x^n}(a) = \frac{N(a \mid x^n)}{n}, \quad a \in \mathcal{X},\]

where \(N(a \mid x^n) = |\{i : x_i = a\}|\) is the number of occurrences of symbol \(a\) in \(x^n\).

Note that \(P_{x^n}\) is a probability distribution on \(\mathcal{X}\): it is non-negative and sums to 1.

Definition (Type Class). For a distribution \(P\) on \(\mathcal{X}\), the type class \(\mathcal{T}(P)\) is the set of all sequences of length \(n\) with type \(P\):

\[\mathcal{T}(P) = \{x^n \in \mathcal{X}^n : P_{x^n} = P\}.\]

Note that \(\mathcal{T}(P)\) is non-empty only if \(nP(a)\) is a non-negative integer for all \(a \in \mathcal{X}\).

Definition (Set of Types). The set of all types with denominator \(n\) over alphabet \(\mathcal{X}\) is denoted \(\mathcal{P}_n(\mathcal{X})\):

\[\mathcal{P}_n(\mathcal{X}) = \{P_{x^n} : x^n \in \mathcal{X}^n\}.\]

4.2 Number of Types

Proposition 4. The total number of types satisfies

\[|\mathcal{P}_n(\mathcal{X})| \leq (n+1)^{|\mathcal{X}|}.\]

Proof. A type \(P \in \mathcal{P}_n(\mathcal{X})\) is determined by the non-negative integers \((N(a))_{a \in \mathcal{X}}\) with \(\sum_a N(a) = n\). This is a stars and bars counting problem: the number of ways to distribute \(n\) indistinguishable balls into \(|\mathcal{X}|\) bins equals \(\binom{n + |\mathcal{X}| - 1}{|\mathcal{X}| - 1}\), which is at most \((n+1)^{|\mathcal{X}|}\) (since each \(N(a) \in \{0,1,\ldots,n\}\), giving at most \(n+1\) choices per symbol). \(\square\)

Key fact: the number of types grows polynomially in \(n\), even though \(|\mathcal{X}^n| = |\mathcal{X}|^n\) grows exponentially.

4.3 Size of a Type Class

Proposition 5 (Multinomial Coefficient). Let \(P \in \mathcal{P}_n(\mathcal{X})\) with \(nP(a) \in \mathbb{Z}_{\geq 0}\) for all \(a\). Then

\[|\mathcal{T}(P)| = \frac{n!}{\prod_{a \in \mathcal{X}} (nP(a))!}.\]

This is the multinomial coefficient \(\binom{n}{nP(a_1), nP(a_2), \ldots, nP(a_k)}\).

Proposition 6 (Entropy Exponent). The size of the type class satisfies

\[\frac{1}{(n+1)^{|\mathcal{X}|}} \cdot 2^{nH(P)} \leq |\mathcal{T}(P)| \leq 2^{nH(P)}.\]

Proof. We use Stirling’s approximation: for \(m \geq 1\),

\[m! \approx \sqrt{2\pi m} \left(\frac{m}{e}\right)^m,\]

or the cruder bound \(\left(\frac{m}{e}\right)^m \leq m! \leq m^m\) for our purposes.

Upper bound. By the multinomial theorem,

\[\sum_P |\mathcal{T}(P)| = |\mathcal{X}|^n.\]

More directly, the multinomial coefficient satisfies (using \(m! \geq (m/e)^m\)):

\[|\mathcal{T}(P)| = \frac{n!}{\prod_a (nP(a))!} \leq \frac{n^n}{\prod_a (nP(a))^{nP(a)}} = \prod_a \left(\frac{1}{P(a)}\right)^{nP(a)} = 2^{nH(P)}.\]

Lower bound. Using \(m! \leq m^m\) in the denominator (to get a lower bound on \(|\mathcal{T}(P)|\) is actually harder; we use Stirling to get \((m/e)^m \leq m! \leq \sqrt{2\pi m}(m/e)^m\)). A clean argument: since \(|\mathcal{P}_n(\mathcal{X})| \leq (n+1)^{|\mathcal{X}|}\) and \(\sum_{P \in \mathcal{P}_n} |\mathcal{T}(P)| = |\mathcal{X}|^n\), the largest type class has size \(\geq |\mathcal{X}|^n / (n+1)^{|\mathcal{X}|}\). For the specific type class \(\mathcal{T}(P)\), the Stirling bound gives the claimed result. \(\square\)

The key conclusion: 🔑 \(|\mathcal{T}(P)| \doteq 2^{nH(P)}\), where \(\doteq\) denotes equality to first order in the exponent (\(\frac{1}{n}\log |\mathcal{T}(P)| \to H(P)\)).

4.4 Probability of a Type Class

Proposition 7. Let \(X^n \overset{\text{i.i.d.}}{\sim} p\). For any type \(P \in \mathcal{P}_n(\mathcal{X})\),

\[p^n(\mathcal{T}(P)) \doteq 2^{-nD(P \| p)},\]

where \(D(P \| p) = \sum_{a} P(a) \log \frac{P(a)}{p(a)}\) is the KL divergence (see Entropy and Divergences). More precisely,

\[\frac{1}{(n+1)^{|\mathcal{X}|}} 2^{-nD(P\|p)} \leq p^n(\mathcal{T}(P)) \leq 2^{-nD(P\|p)}.\]

Proof. Each sequence \(x^n \in \mathcal{T}(P)\) has

\[p^n(x^n) = \prod_{a \in \mathcal{X}} p(a)^{N(a|x^n)} = \prod_a p(a)^{nP(a)}.\]

This is the same for all sequences in \(\mathcal{T}(P)\) — the probability is uniform over the type class and depends only on \(P\), not on the particular sequence. Therefore,

\[p^n(\mathcal{T}(P)) = |\mathcal{T}(P)| \cdot \prod_a p(a)^{nP(a)}.\]

Now expand:

\[|\mathcal{T}(P)| \cdot \prod_a p(a)^{nP(a)} \leq 2^{nH(P)} \cdot \prod_a p(a)^{nP(a)} = 2^{n\sum_a P(a)\log(1/P(a))} \cdot 2^{n\sum_a P(a)\log p(a)}\] \[= 2^{-n\sum_a P(a)\log(P(a)/p(a))} = 2^{-nD(P\|p)}.\]

The lower bound follows similarly using \(|\mathcal{T}(P)| \geq (n+1)^{-|\mathcal{X}|} 2^{nH(P)}\). \(\square\)

🔑 Uniform within each type class; exponentially rare for types far from \(p\). The KL divergence \(D(P \| p)\) controls the exponential decay of the probability of seeing type \(P\) when the true distribution is \(p\).

4.5 Sanov’s Theorem

Theorem (Sanov). Let \(X^n \overset{\text{i.i.d.}}{\sim} p\), and let \(\mathcal{E} \subseteq \mathcal{P}(\mathcal{X})\) be a closed convex set of distributions. Then

\[\Pr[P_{X^n} \in \mathcal{E}] \doteq 2^{-n \min_{Q \in \mathcal{E}} D(Q \| p)}.\]

More precisely, with \(Q^* = \arg\min_{Q \in \mathcal{E}} D(Q\|p)\) (the information projection of \(p\) onto \(\mathcal{E}\)):

\[-\frac{1}{n}\log \Pr[P_{X^n} \in \mathcal{E}] \to D(Q^* \| p).\]

Proof sketch. Since there are at most \((n+1)^{|\mathcal{X}|}\) types, and for each type \(P \in \mathcal{E}\), \(p^n(\mathcal{T}(P)) \leq 2^{-nD(P\|p)}\):

\[\Pr[P_{X^n} \in \mathcal{E}] = \sum_{P \in \mathcal{P}_n(\mathcal{X}) \cap \mathcal{E}} p^n(\mathcal{T}(P)) \leq (n+1)^{|\mathcal{X}|} \cdot 2^{-n \min_{Q \in \mathcal{E}} D(Q\|p)}.\]

The polynomial factor \((n+1)^{|\mathcal{X}|}\) is subexponential and vanishes in the exponent. For the lower bound, the dominant type class provides a matching lower bound. \(\square\)

Sanov’s theorem is the large deviations version of the LLN for empirical distributions.

4.6 Why the Method of Types Is Powerful

Three key properties make the method of types a general-purpose tool:

1. Uniform probability within type classes. All sequences in \(\mathcal{T}(P)\) have exactly the same probability under \(p^n\). This reduces computations over \(\mathcal{X}^n\) (exponentially many sequences) to computations over \(\mathcal{P}_n(\mathcal{X})\) (polynomially many types).

2. Polynomial count of types. With only \((n+1)^{|\mathcal{X}|}\) types, a union bound over all types loses only a polynomial factor — negligible in the exponent.

3. Exponential characterisation via entropy and KL divergence. Type class size \(\doteq 2^{nH(P)}\); type class probability \(\doteq 2^{-nD(P\|p)}\). These two quantities characterise everything to first order in the exponent.

from collections import Counter
import math

def plug_in_entropy(samples):
    n = len(samples)
    counts = Counter(samples)
    return -sum((c/n) * math.log2(c/n) for c in counts.values())

5. Strong Typicality

5.1 Definition of Strong Typicality

Weak typicality (the AEP-based definition of Section 2) controls only the log-probability of a sequence. Strong typicality controls the empirical frequencies of each symbol directly.

Definition (Strongly Typical Set). Fix \(\varepsilon > 0\). The strongly typical set \(\mathcal{T}_\varepsilon^{*(n)}\) consists of sequences whose empirical distribution is uniformly close to \(p\):

\[\mathcal{T}_\varepsilon^{*(n)} = \left\{x^n \in \mathcal{X}^n : \left|\frac{N(a \mid x^n)}{n} - p(a)\right| \leq \frac{\varepsilon}{|\mathcal{X}|} \text{ for all } a \in \mathcal{X}\right\}.\]

Equivalently, using type notation: \(x^n \in \mathcal{T}_\varepsilon^{*(n)}\) iff \(\|P_{x^n} - p\|_1 \leq \varepsilon\), where \(\|\cdot\|_1\) is the total variation (up to a factor of 2).

5.2 Strong Implies Weak

Proposition 8. If \(x^n \in \mathcal{T}_\varepsilon^{*(n)}\), then \(x^n \in \mathcal{T}_{\varepsilon'}^{(n)}\) for some \(\varepsilon' = O(\varepsilon \log(1/\varepsilon_{\min}))\) where \(\varepsilon_{\min} = \min_a p(a)\).

Proof sketch. By the definition of strong typicality, \(|P_{x^n}(a) - p(a)| \leq \varepsilon / |\mathcal{X}|\) for all \(a\). Then

\[\left|-\frac{1}{n}\log p(x^n) - H(X)\right| = \left|\sum_a P_{x^n}(a) \log \frac{1}{p(a)} - H(X)\right|\] \[= \left|\sum_a (P_{x^n}(a) - p(a)) \log \frac{1}{p(a)}\right| \leq \frac{\varepsilon}{|\mathcal{X}|} \sum_a \log \frac{1}{p(a)} \leq \varepsilon \cdot \log \frac{1}{p_{\min}},\]

where \(p_{\min} = \min_a p(a)\). Taking \(\varepsilon' = \varepsilon \log(1/p_{\min})\) proves the claim. \(\square\)

The converse is false. Weak typicality does not imply strong typicality. A sequence can have the right log-probability while individual symbol frequencies deviate from \(p\).

5.3 Joint Typicality

Definition (Jointly Typical Set). For a joint distribution \(p(x,y)\) over \(\mathcal{X} \times \mathcal{Y}\), the jointly \(\varepsilon\)-typical set \(\mathcal{J}_\varepsilon^{(n)}\) is the set of sequence pairs \((x^n, y^n)\) such that:

\[\left|-\frac{1}{n}\log p(x^n) - H(X)\right| \leq \varepsilon, \quad \left|-\frac{1}{n}\log p(y^n) - H(Y)\right| \leq \varepsilon,\] \[\left|-\frac{1}{n}\log p(x^n, y^n) - H(X,Y)\right| \leq \varepsilon.\]

That is, \((x^n, y^n) \in \mathcal{J}_\varepsilon^{(n)}\) iff both marginal sequences are typical and the joint sequence is also typical.

Theorem (Joint AEP). If \((X^n, Y^n)\) are drawn i.i.d. from \(p(x,y)\), then:

1. \(\Pr[(X^n, Y^n) \in \mathcal{J}_\varepsilon^{(n)}] \to 1\).
2. \(|\mathcal{J}_\varepsilon^{(n)}| \leq 2^{n(H(X,Y)+\varepsilon)}\).
3. If \(\tilde{X}^n \sim p(x^n)\) and \(\tilde{Y}^n \sim p(y^n)\) are drawn independently:

\[\Pr[(\tilde{X}^n, \tilde{Y}^n) \in \mathcal{J}_\varepsilon^{(n)}] \leq 2^{-n(I(X;Y)-3\varepsilon)},\]

where \(I(X;Y) = H(X) + H(Y) - H(X,Y)\) is the mutual information.

Proof sketch. Parts 1 and 2 follow from the AEP for the joint distribution \(p(x,y)\). For part 3:

\[\Pr[(\tilde{X}^n, \tilde{Y}^n) \in \mathcal{J}_\varepsilon^{(n)}] = \sum_{(x^n, y^n) \in \mathcal{J}_\varepsilon^{(n)}} p(x^n) p(y^n).\]

Each pair contributes \(p(x^n) p(y^n) \leq 2^{-n(H(X)-\varepsilon)} \cdot 2^{-n(H(Y)-\varepsilon)}\), and there are at most \(2^{n(H(X,Y)+\varepsilon)}\) jointly typical pairs, so the sum is at most \(2^{n(H(X,Y)+\varepsilon - H(X) - H(Y) + 2\varepsilon)} = 2^{-n(I(X;Y)-3\varepsilon)}\). \(\square\)

This bound is the cornerstone of random coding proofs for the channel coding theorem.

6. Connections and Applications

6.1 Channel Coding

📐 The joint AEP (Section 5.3) is the main probabilistic tool in Shannon’s noisy channel coding theorem. The argument runs as follows (see the forthcoming channel-capacity.md):

1. Random codebook: generate \(2^{nR}\) codewords i.i.d. from \(p(x)\).
2. Jointly typical decoder: declare message \(m\) was sent if \((x^n(m), y^n)\) is jointly typical; declare error otherwise.
3. Error analysis: for the correct codeword, the probability of not being jointly typical vanishes (Joint AEP, part 1). For each incorrect codeword \(m' \neq m\), the probability of being jointly typical with \(y^n\) is at most \(2^{-n(I(X;Y)-3\varepsilon)}\) (Joint AEP, part 3). By a union bound over \(2^{nR}\) wrong codewords, error probability is \(\leq 2^{n(R - I(X;Y) + 3\varepsilon)} \to 0\) when \(R < I(X;Y) - 3\varepsilon\).

🔑 Optimising over \(p(x)\) gives the capacity \(C = \max_{p(x)} I(X;Y)\).

6.2 Rate-Distortion Theory

In rate-distortion source coding (see Rate-Distortion Theory), the goal is lossy compression: encode \(X^n\) into \(nR\) bits such that the decoder produces \(\hat{X}^n\) with \(\frac{1}{n}\sum d(X_i, \hat{X}_i) \leq D\). The rate-distortion function \(R(D) = \min_{p(\hat{x}|x): \mathbb{E}[d(X,\hat{X})] \leq D} I(X;\hat{X})\) is proved achievable using a rate-distortion typical set: sequences \((x^n, \hat{x}^n)\) that are jointly typical with respect to the optimal \(p(\hat{x}|x)\).

6.3 Statistical Physics

The typical set has a striking analogue in statistical mechanics. Consider a classical ideal gas with \(n\) particles in states from \(\mathcal{X}\) (e.g., energy levels). The macrostate is the empirical distribution \(P_{x^n}\) (occupation numbers); a microstate is a specific configuration \(x^n\). The number of microstates in a macrostate \(P\) is \(|\mathcal{T}(P)| \approx 2^{nH(P)}\), and Boltzmann’s entropy formula \(S = k_B \ln W\) (where \(W\) is the number of microstates) gives \(S \propto H(P)\).

The equilibrium macrostate is the one with the most microstates, i.e., the one maximising \(H(P)\) subject to energy constraints — precisely Jaynes’ maximum-entropy principle (see maximum-entropy.md).

References