The Asymptotic Equipartition Property

Motivation: from one keystroke to a whole message

The quantities we built in the notes (entropy, relative entropy, mutual information) are an average per keystroke. But a user never transmits a single keystroke in isolation. They transmit a long message: a sequence of $n$ symbols $X_1, X_2, \ldots, X_n$ generated by a source (like an English typist) with a specific probability distribution $p(x)$.

To transmit this message, the engineer must design a codebook, a dictionary that translates every possible raw typed sequence into a unique string of binary 0s and 1s.

If a typewriter has an alphabet $\mathcal{X}$, a message of length $n$ can be filled in $\lvert \mathcal{X} \rvert^n$ different ways. If the engineer blindly treats every possible jumble of letters as equally likely, they must assign a fixed-length binary code to every single one of those $\lvert \mathcal{X} \rvert^n$ messages. This requires a hardcoded length of $n \log \lvert \mathcal{X} \rvert$ bits per transmission. This is incredibly expensive, and completely ignores the fact that languages have statistical structure.

The Law of Large Numbers

To answer this, we borrow a foundational concept from statistics: the Law of Large Numbers (LLN).

The LLN states that if you perform the same random experiment many times, the empirical average of the results will strictly converge to the theoretical expected value. If you roll a fair six-sided die once, the result is completely unpredictable. But if you roll it 10,000 times, you know with near absolute certainty that the average of those rolls will be roughly 3.5.

The Asymptotic Equipartition Property (AEP) is the information-theoretic analogue of the Law of Large Numbers. But instead of averaging the raw values of the data, we average the surprise (the negative log probability) of the data.

	Law of large numbers	Asymptotic Equipartition Property
Object averaged	The values themselves, $\frac{1}{n}\sum_{i=1}^n X_i$	The surprise of the values, $-\frac{1}{n}\log p(X_1, \ldots, X_n)$
Converges to	$\mathbb{E}[X]$	$H(X)$ (Entropy)

Because $-\frac{1}{n}\log p(X_1, \ldots, X_n)$ strictly settles down to the Entropy $H(X)$, the overall probability of whatever message we actually observe settles to roughly $2^{-nH}$.

---

Intuition check: are all tapes equally likely?

A naive first guess is that the AEP is trivially true because every message is equally likely anyway. It is not, and seeing why sharpens what the theorem is actually claiming.

Let the operator have a two-key machine, $X \in \{0, 1\}$, with $p(1) = p$ and $p(0) = q$. Since keystrokes are i.i.d., the probability of a specific sequence $x_1, x_2, \ldots, x_n$ is the product of the per-key probabilities:

$$p(x_1, x_2, \ldots, x_n) = \prod_{i=1}^n p(x_i) = p^{\sum_i x_i} \; q^{\, n - \sum_i x_i}$$

So the AEP is not saying that the sample space is uniform. It is saying something weaker but far more useful: although the $2^n$ possible sequences have very different mathematical probabilities, the sequences that actually get typed in reality almost all share the exact same probability: $2^{-nH(p)}$.

In this binary example, this simply means the number of $1$s on a printed message will almost always be close to $np$. And every sequence that has exactly $np$ ones naturally carries the exact same mathematical probability.

---

Convergence of random variables

The AEP is a statement about a sequence of random variables converging.

To understand what is converging, we have to be precise: the raw characters on the wire do not converge. If an operator types binary digits $X_i \in \{0, 1\}$, individual keystrokes bounce between 0 and 1 forever.

What converges is a calculated property of the message as a whole. Specifically, we define a new random variable $Y_n$: the sample entropy (the average surprise per keystroke across a message of length $n$):

$$Y_n = -\frac{1}{n} \log p(X_1, X_2, \ldots, X_n)$$

We want to prove that as the message length $n$ grows, this empirical quantity $Y_n$ settles onto the true, theoretical entropy of the language, $H(X)$.

Because $Y_n$ is a random variable, it doesn’t converge like a standard calculus function. In probability theory, there are three distinct mathematical ways a sequence of random variables $Y_n$ can converge to a constant $c$:

---

Why the three modes differ

The three definitions test completely different engineering concerns: frequency, variance/energy, and infinite timelines.

1. Convergence in probability (Snapshot frequency)

Look at the condition: $\Pr\{ \lvert Y_n - c \rvert > \epsilon \} \to 0$.

• What $\lvert Y_n - c \rvert > \epsilon$ means: You set a tight tolerance, say, $\epsilon = 0.01$ bits. An error occurs if your measured sample entropy $Y_n$ misses the true entropy $H(X)$ by more than that tiny margin.
• What the probability measures: It asks: “If I inspect a randomly generated message of length $n$, what is the chance its average surprise is outside that narrow band?”
• What convergence means: As $n$ grows, the percentage of messages that miss the target band shrinks to zero. It guarantees that for large $n$, almost every individual message you inspect is well-behaved.

2. Why “in mean square” is different (Extreme outlier sensitivity)

Mean square convergence demands that the average squared error $\mathbb{E}[(Y_n - c)^2]$ goes to zero.

• The difference: While convergence in probability only counts how often an error occurs, mean square multiplies the probability of an error by the magnitude squared of that error.
• Why this matters: Imagine an extremely rare message (like an operator accidentally typing a million identical symbols in a row). The probability of this happening might be $2^{-1,000,000}$ (effectively zero), but its surprise value could be mathematically enormous. Mean square convergence is overly sensitive to the numerical size of rare tails, whereas convergence in probability simply notes that such catastrophic tails carry near-zero probability mass.

3. Why “almost surely” is different (The infinite timeline)

Almost sure convergence $\Pr\{ \lim_{n \to \infty} Y_n = c \} = 1$ is about what happens if you never cut the tape.

• The difference: Convergence in probability checks a single fixed length $n$: if you choose a message of length $n = 10,000$, is it likely inside the band? Yes. But if you keep letting the tape run forever ($n \to \infty$ on a single physical machine), will the sample entropy eventually wiggle outside the tolerance band $\pm \epsilon$ at least once in the distant future?
• Why this matters: Almost sure convergence requires that on a single unbroken timeline, there is a point after which the measurement never leaves the band again, ever. That is a much stronger mathematical condition than just requiring a message of fixed size $n$ to be well-behaved when received.

---

---

The AEP theorem

ProofReduce the joint surprise to a sample mean, then apply the weak law

Step 1: Independence survives the logarithm. Functions of independent random variables are themselves independent random variables. The $X_i$ are i.i.d., and $\log p(\cdot)$ is a fixed function applied to each one separately, so the random variables $\log p(X_1), \log p(X_2), \ldots$ are also i.i.d. This is the step that licenses everything after it.

Step 2: The joint surprise is a sum, because the keystrokes are independent. Independence gives $p(x_1, \ldots, x_n) = \prod_{i=1}^n p(x_i)$, and the logarithm turns that product into a sum, the same additivity that forced $h$ to be a logarithm in the first place (see the three conditions on $h$):

$$-\frac{1}{n} \log p(X_1, X_2, \ldots, X_n) = -\frac{1}{n} \sum_{i=1}^n \log p(X_i)$$

The left side is the surprise of one enormous composite event; the right side is an ordinary sample mean of $n$ i.i.d. terms. The whole theorem is this rewriting.

Step 3: Apply the weak law of large numbers. A sample mean of i.i.d. terms converges in probability to the expectation of a single term:

$$-\frac{1}{n} \sum_{i=1}^n \log p(X_i) \longrightarrow -\mathbb{E}\big[\log p(X)\big] \quad \text{in probability}$$

Step 4: Recognize the expectation. By definition $-\mathbb{E}[\log p(X)] = -\sum_x p(x) \log p(x) = H(X)$. Chaining Steps 2–4:

$$-\frac{1}{n} \log p(X_1, \ldots, X_n) \longrightarrow H(X) \quad \text{in probability}$$

∎

For an independent and identically distributed (i.i.d.) source, the joint probability of the tape is $p(X^n) = \prod_{i=1}^n p(X_i)$. We define the sample entropy (empirical surprise rate) as:

$$\bar{H}_n = -\frac{1}{n} \log_2 p(X^n) = \frac{1}{n} \sum_{i=1}^n \left(-\log_2 p(X_i)\right)$$

Notice the mathematical structure: $\bar{H}_n$ is simply the sample average of $n$ independent random variables, where each step draws an individual surprise value $S_i = -\log_2 p(X_i)$.

Consider an unbalanced binary source that types 1 with probability $p = 0.9$ and 0 with probability $p = 0.1$:

• True Entropy: $H(X) = -0.9 \log_2(0.9) - 0.1 \log_2(0.1) \approx 0.469\text{ bits/symbol}$
• Per-symbol variance of surprise: $\sigma^2 = \text{Var}(-\log_2 p(X_i)) \approx 0.9043$

By the Central Limit Theorem, the distribution of observed sample entropy across many generated tapes follows a normal distribution centered at $H$, with variance shrinking as $\sigma^2 / n$:

$$\bar{H}_n \sim \mathcal{N}\left(0.469, \; \frac{0.9043}{n}\right)$$

As the tape length grows from $n = 25$ to $n = 1000$, the sample entropy distribution concentrates ever more violently into a sharp spike at $H \approx 0.469$:

• n = 25
• n = 100
• n = 1000

---

The typical set

The AEP says the sample entropy of a printed tape concentrates on $H(X)$. That lets us physically partition the space of all possible tapes $\mathcal{X}^n$ into two piles: the tapes whose sample entropy came out close to $H$, and everything else.

flowchart LR
  S["All tapes: alphabet^n, count = |X|^n"] --> T["Typical set: sample entropy within epsilon of H"]
  S --> N["Nontypical set: everything else"]
  T --> TP["Probability nearly 1, count about 2^(nH)"]
  N --> NP["Probability nearly 0, count can be huge"]

Component	Detail
Signature	$A_\epsilon^{(n)} \subseteq \mathcal{X}^n$, a set of tapes, not a number.
Parameters	$n$, the tape length; $\epsilon$, the tolerance we allow on the per-keystroke surprise.
Membership test	Compute the tape’s probability and check it lands in the band $[2^{-n(H+\epsilon)},\, 2^{-n(H-\epsilon)}]$. Taking $-\frac{1}{n}\log$ of all three parts turns this into the equivalent test $H - \epsilon \le -\frac{1}{n}\log p(x^n) \le H + \epsilon$.

---

Properties of the typical set

Put the size next to the coverage: the typical set holds almost all the probability, yet as a fraction of all $2^n$ binary tapes it is only about $2^{nH}/2^n = 2^{-n(1-H)}$. Unless the source is a fair coin ($H = 1$ as we showed in the binary entropy plot), this ratio drops exponentially to zero as $n$ grows:

• p = 0.9 (H ≈ 0.469)
• p = 0.7 (H ≈ 0.881)
• p = 0.5 (H = 1: every tape is typical)

For a source with $p = 0.9$ ($H \approx 0.469\text{ bits}$) and a modest tape length of $n = 60$:

• The Vanishing Slice: The typical set accounts for only: $$\frac{|A_\epsilon^{(60)}|}{2^{60}} \approx 2^{-60(1 - 0.469)} = 2^{-31.86} \approx \frac{1}{3,800,000,000}$$ It comprises barely one out of every four billion possible binary sequences.

• The Overwhelming Mass: Despite being an infinitesimal sliver of all possible sequences, this tiny subset carries over $99\%$ of the entire probability mass.

• Why Compression Works: Compression does not work by inventing complicated tricks for every single one of the $2^n$ theoretical sequences. Instead, it simply ignores the vast, empty wasteland of atypical sequences and assigns short, fixed-length binary index labels solely to the typical set. This cuts the required transmission length from $n$ bits down to just $n H(X)$ bits with negligible probability of error.

ProofComplete proof of all four properties

Part 1: The Equiprobability Band By definition, a sequence belongs to $A_\epsilon^{(n)}$ if its probability satisfies: $$2^{-n(H + \epsilon)} \le p(x_1, \ldots, x_n) \le 2^{-n(H - \epsilon)}$$ Since the base-2 logarithm is strictly increasing, taking $\log_2$ across the inequality preserves the order: $$-n(H + \epsilon) \le \log p(x_1, \ldots, x_n) \le -n(H - \epsilon)$$ Multiplying through by $-\frac{1}{n}$ is multiplying by a negative number, which reverses both inequality signs: $$H + \epsilon \ge -\frac{1}{n} \log p(x_1, \ldots, x_n) \ge H - \epsilon$$ Rewriting in standard ascending order yields Property 1: $$H(X) - \epsilon \le -\frac{1}{n} \log p(x_1, \ldots, x_n) \le H(X) + \epsilon$$

Part 2: High Probability Mass The AEP theorem proves that $-\frac{1}{n}\log p(X^n) \to H(X)$ in probability. By definition of convergence in probability, for any tolerance $\epsilon > 0$ and any allowed failure probability $\delta > 0$, there exists an integer $n_0$ such that for all $n \ge n_0$: $$\Pr\left( \left\lvert -\frac{1}{n}\log p(X^n) - H(X) \right\rvert < \epsilon \right) > 1 - \delta$$ By Part 1, the condition $\lvert -\frac{1}{n}\log p(X^n) - H(X) \rvert \le \epsilon$ is precisely the condition that $X^n \in A_\epsilon^{(n)}$. Thus: $$\Pr\big\{ A_\epsilon^{(n)} \big\} > 1 - \delta$$ Since this statement holds for any arbitrarily small $\delta > 0$, we can choose $\delta = \epsilon$ for convenience, yielding $\Pr\{A_\epsilon^{(n)}\} > 1 - \epsilon$ for all sufficiently large $n$.

Part 3: Upper Bound on Size The total probability of all possible sequences in the entire universe $\mathcal{X}^n$ must sum to 1: $$1 = \sum_{x^n \in \mathcal{X}^n} p(x^n)$$ Restricting this sum strictly to the typical subset can only decrease the sum: $$1 \ge \sum_{x^n \in A_\epsilon^{(n)}} p(x^n)$$ By the membership condition, every typical sequence has an individual probability bounded below by $p(x^n) \ge 2^{-n(H + \epsilon)}$. Replacing each term with this minimum floor: $$1 \ge \sum_{x^n \in A_\epsilon^{(n)}} 2^{-n(H + \epsilon)}$$ Because the term $2^{-n(H + \epsilon)}$ is a constant that does not depend on $x^n$, summing it over all elements in $A_\epsilon^{(n)}$ simply multiplies it by the total count $\lvert A_\epsilon^{(n)} \rvert$: $$1 \ge \lvert A_\epsilon^{(n)} \rvert \cdot 2^{-n(H(X) + \epsilon)}$$ Multiplying both sides by $2^{n(H(X) + \epsilon)}$ proves the upper bound: $$\big\lvert A_\epsilon^{(n)} \big\rvert \le 2^{n(H(X) + \epsilon)}$$

Part 4: Lower Bound on Size From Part 2, for sufficiently large $n$, the total probability mass contained inside the typical set exceeds $1 - \epsilon$: $$1 - \epsilon < \Pr\big\{ A_\epsilon^{(n)} \big\} = \sum_{x^n \in A_\epsilon^{(n)}} p(x^n)$$ By the membership condition, every typical sequence has an individual probability bounded above by $p(x^n) \le 2^{-n(H - \epsilon)}$. Replacing each term with this maximum ceiling: $$1 - \epsilon < \sum_{x^n \in A_\epsilon^{(n)}} 2^{-n(H - \epsilon)}$$ Factoring out the constant ceiling collapses the sum into a direct count: $$1 - \epsilon < \lvert A_\epsilon^{(n)} \rvert \cdot 2^{-n(H(X) - \epsilon)}$$ Multiplying both sides by $2^{n(H(X) - \epsilon)}$ completes the lower bound: $$\big\lvert A_\epsilon^{(n)} \big\rvert \ge (1 - \epsilon) 2^{n(H(X) - \epsilon)}$$

∎

---

Consequence: data compression

The problem: We now have a set of about $2^{nH}$ tapes that soaks up nearly all the probability. But a set is not yet a product. The telecom engineer needs an actual code: a concrete mapping from every tape $x^n$ the machine might print to a binary string they can push down the wire. Two hard constraints:

• It must be one-to-one, so the receiver can invert it. We cannot simply refuse to encode the atypical tapes, rare is not impossible, and a code that silently fails on them is not a code.
• It must be cheap on average, since the telecom is charged per pulse actually sent, not per codeword slot reserved.

The tension is that these pull in opposite directions: covering every tape is what forces the $n \log \lvert \mathcal{X} \rvert$ cost in the first place. The resolution is to cover everything but charge differently for the two piles.

The two-part code

Order the elements within each pile by some fixed convention (lexicographic, say), and represent a tape by its index within its own pile, prefixed by a flag bit saying which pile it came from.

Pile	Size	Index cost	Flag	Total length
Typical $A_\epsilon^{(n)}$	$\le 2^{n(H + \epsilon)}$	$\le n(H + \epsilon) + 1$ bits	0	$\le n(H + \epsilon) + 2$ bits
Atypical ${A_\epsilon^{(n)}}^c$	$\le \lvert \mathcal{X} \rvert^n$	$\le n \log \lvert \mathcal{X} \rvert + 1$ bits	1	$\le n \log \lvert \mathcal{X} \rvert + 2$ bits

To see the actual bits, take the $p = 0.9$ operator with $\epsilon = 0.05$ and a short tape, $n = 10$. Only tapes with exactly one 0 have sample entropy within $\epsilon$ of $H \approx 0.469$, so the typical pile holds just $10$ tapes and $\lceil \log_2 10 \rceil = 4$ index bits suffice (inside the $n(H + \epsilon) + 1 \approx 6.2$ bound). In lexicographic order, 1111011111 is tape number $4$ of that pile, counting from $0$:

Typical tape 1111011111 → 5 bits

0flag0100index in typical pile

Atypical tape 1110111011 → 11 bits

1flag1110111011the tape itself

Fixed-length code, any tape → 10 bits

1111011111the tape itself

The receiver reads the flag first, which tells it whether $4$ or $10$ more bits follow. At $n = 10$ the typical pile only carries $10 \cdot 0.9^9 \cdot 0.1 \approx 39\%$ of the probability, so this length shows the layout, not the savings; those need the large $n$ of the theorem.

Expected Codeword Length: Why the Math Works

The two-part code assigns two completely different lengths:

• If a tape is typical, it costs a short length: $\le n(H + \epsilon) + 2$ bits.
• If a tape is atypical, it costs a long, uncompressed length: $\le n \log_2 \vert{}\mathcal{X}\vert{} + 2$ bits.

An engineer might worry: Won’t the massive length of the atypical pile ruin our average bitrate whenever an atypical tape occurs?

Because atypical tapes occur with probability less than $\epsilon$, their massive bit cost is multiplied by a vanishingly small probability, making their total impact on average bandwidth negligible.

---

---

Visualizing the Amortization of Overhead

For our operator with $p = 0.9$ ($H \approx 0.469$ bits/symbol) and $\epsilon = 0.05$:

• An uncompressed fixed-length code costs $\log_2(2) = 1.0\text{ bit/symbol}$ regardless of $n$.
• The two-part code adds an overhead of $2$ extra bits (1 flag bit + 1 rounding bit) spread across the entire block of $n$ characters.
• As $n$ grows, this overhead $\frac{2}{n}$ quickly shrinks to zero, and the average bits per symbol plunge toward the true entropy floor $H = 0.469$:

• two-part code: H + ε + 2/n
• fixed-length code: log₂ |X| = 1
• entropy H

---

ProofStep-by-Step Proof of the Expected Codeword Length Bound

Step 1: Write down the definition of expected length. The average number of bits transmitted per block across all possible sequences $x^n \in \mathcal{X}^n$ is:

$$\mathbb{E}\big[l(X^n)\big] = \sum_{x^n \in \mathcal{X}^n} p(x^n)\, l(x^n)$$

Step 2: Partition the world into the two piles. Every sequence falls into either the typical set $A_\epsilon^{(n)}$ or the atypical set ${A_\epsilon^{(n)}}^c$. The sum splits cleanly:

$$\mathbb{E}\big[l(X^n)\big] = \sum_{x^n \in A_\epsilon^{(n)}} p(x^n)\, l(x^n) \;+\; \sum_{x^n \in {A_\epsilon^{(n)}}^c} p(x^n)\, l(x^n)$$

Step 3: Plug in the maximum codeword length for each pile. From our table, typical codewords never exceed $n(H + \epsilon) + 2$ bits, and atypical codewords never exceed $n \log_2 \vert{}\mathcal{X}\vert{} + 2$ bits. Replacing each length with its worst-case bound:

$$\le \sum_{x^n \in A_\epsilon^{(n)}} p(x^n)\big(n(H + \epsilon) + 2\big) \;+\; \sum_{x^n \in {A_\epsilon^{(n)}}^c} p(x^n)\big(n \log_2 \vert{}\mathcal{X}\vert{} + 2\big)$$

Step 4: Factor out the length constants. Since the bracketed lengths are identical constants across all items in their respective piles, pull them outside the summations:

$$= \left(n(H + \epsilon) + 2\right) \underbrace{\sum_{x^n \in A_\epsilon^{(n)}} p(x^n)}_{\Pr(A_\epsilon^{(n)})} \;+\; \left(n \log_2 \vert{}\mathcal{X}\vert{} + 2\right) \underbrace{\sum_{x^n \in {A_\epsilon^{(n)}}^c} p(x^n)}_{\Pr({A_\epsilon^{(n)}}^c)}$$

Step 5: Apply probability bounds (where the miracle happens).

• For the typical pile, use the trivial ceiling: $\Pr(A_\epsilon^{(n)}) \le 1$.
• For the atypical pile, Property 2 of the typical set guarantees: $\Pr({A_\epsilon^{(n)}}^c) \le \epsilon$.

Substituting these values:

$$\mathbb{E}\big[l(X^n)\big] \le 1 \cdot \big(n(H + \epsilon) + 2\big) \;+\; \epsilon \cdot \big(n \log_2 \vert{}\mathcal{X}\vert{} + 2\big)$$

Distributing and combining the constant terms ($2 + 2\epsilon \le 2 + 2(1) = 4$, or simply factoring $+2$ since probabilities sum to 1):

$$\mathbb{E}\big[l(X^n)\big] \le n(H + \epsilon) + \epsilon\, n \log_2 \vert{}\mathcal{X}\vert{} + 2$$

Step 6: Compute the per-symbol average bit rate. Divide the total expected length by the block length $n$:

$$\mathbb{E}\left[\frac{1}{n} l(X^n)\right] \le H(X) + \underbrace{\epsilon + \epsilon \log_2 \vert{}\mathcal{X}\vert{} + \frac{2}{n}}_{\epsilon'}$$

Step 7: Vanish the excess overhead $\epsilon'$. Notice what makes up $\epsilon' = \epsilon(1 + \log_2 \vert{}\mathcal{X}\vert{}) + \frac{2}{n}$:

1. $\vert{}\mathcal{X}\vert{}$ is a fixed constant of the alphabet (e.g., $\vert{}\mathcal{X}\vert{} = 2$ for binary). We can pick $\epsilon$ arbitrarily small upfront so that $\epsilon(1 + \log_2 \vert{}\mathcal{X}\vert{})$ is as close to $0$ as we desire.
2. With $\epsilon$ fixed, we choose $n$ large enough so that the overhead term $\frac{2}{n} \to 0$.

Thus, $\epsilon'$ can be made as small as desired, completing the proof.

∎

---

---

High-probability sets and the typical set

The Problem:
The typical set $A_\epsilon^{(n)}$ contains roughly $2^{n H(X)}$ sequences and captures almost all probability ($> 1 - \epsilon$). But nowhere did we prove it is the smallest set with this property.

Could a clever engineer beat Shannon’s bound? What if, instead of filtering sequences by their sample-entropy band, they greedily picked the absolute most probable sequences one by one until they accumulated $99\%$ of the probability mass? Could that hand-picked set be dramatically smaller, say, requiring only $0.3 n$ bits instead of $n H(X)$ bits?

To settle this, we analyze the absolute best competitor that could ever exist.

The Competitor: The Smallest High-Probability Set $B_\delta^{(n)}$

How the Two Sets Are Built (And Why They Differ)

• $A_\epsilon^{(n)}$ is a middle-band set: It collects sequences whose sample entropy lands inside a narrow band around $H(X)$. It does not care whether an individual sequence is the single most likely tape in the universe.
• $B_\delta^{(n)}$ is a greedy top-of-the-list set: It sorts all $\vert{}\mathcal{X}\vert{}^n$ possible sequences from highest probability to lowest probability and grabs from the top until the cumulative probability hits $1 - \delta$.

Because their selection rules are completely different, the two sets do not contain the same elements.

The Theorem: You Cannot Beat $2^{nH}$

Even though $B_\delta^{(n)}$ greedily grabs the most probable sequences first, it cannot be significantly smaller than the typical set.

---

ProofFormal Proof via the Intersection Argument

We prove that $B_\delta^{(n)}$ must contain at least $(1 - \delta - \epsilon) 2^{n(H - \epsilon)}$ sequences by looking at where it overlaps with the typical set $A_\epsilon^{(n)}$.

Step 1: The two sets must heavily overlap.
Recall that for large $n$, the typical set carries nearly all mass: $$\Pr\big\{ A_\epsilon^{(n)} \big\} > 1 - \epsilon$$ By definition, the greedy competitor also carries nearly all mass: $$\Pr\big\{ B_\delta^{(n)} \big\} \ge 1 - \delta$$

Using the probability rule $\Pr(A \cap B) = \Pr(A) + \Pr(B) - \Pr(A \cup B)$ and the fact that $\Pr(A \cup B) \le 1$:

$$\Pr\big\{ A_\epsilon^{(n)} \cap B_\delta^{(n)} \big\} \ge \Pr\big\{ A_\epsilon^{(n)} \big\} + \Pr\big\{ B_\delta^{(n)} \big\} - 1$$ $$\Pr\big\{ A_\epsilon^{(n)} \cap B_\delta^{(n)} \big\} > (1 - \epsilon) + (1 - \delta) - 1 = 1 - \delta - \epsilon$$

Since $\delta < \frac{1}{2}$ and $\epsilon$ can be chosen arbitrarily small, the overlapping region carries a substantial, positive fraction of the total probability mass (strictly bounded away from zero).

Step 2: Every sequence in that overlap is lightweight.
Every element $x^n$ inside the overlap $A_\epsilon^{(n)} \cap B_\delta^{(n)}$ is by definition an element of $A_\epsilon^{(n)}$. From Property 1 of the typical set, no typical sequence can have probability larger than:

$$p(x^n) \le 2^{-n(H - \epsilon)}$$

Step 3: Sum the weights to bound the size.
Write out the probability of the overlap:

$$1 - \delta - \epsilon < \Pr\big\{ A_\epsilon^{(n)} \cap B_\delta^{(n)} \big\} = \sum_{x^n \in A_\epsilon^{(n)} \cap B_\delta^{(n)}} p(x^n)$$

Replace each term with its maximum possible weight $2^{-n(H - \epsilon)}$:

$$1 - \delta - \epsilon < \sum_{x^n \in A_\epsilon^{(n)} \cap B_\delta^{(n)}} 2^{-n(H - \epsilon)} = \big\lvert A_\epsilon^{(n)} \cap B_\delta^{(n)} \big\rvert \cdot 2^{-n(H - \epsilon)}$$

Rearranging:

$$\big\lvert A_\epsilon^{(n)} \cap B_\delta^{(n)} \big\rvert > (1 - \delta - \epsilon) \cdot 2^{n(H - \epsilon)}$$

Step 4: Conclude for the full set $B_\delta^{(n)}$.
Because the intersection is a subset of $B_\delta^{(n)}$ (so $\lvert B_\delta^{(n)} \rvert \ge \lvert A_\epsilon^{(n)} \cap B_\delta^{(n)} \rvert$):

$$\big\lvert B_\delta^{(n)} \big\rvert > (1 - \delta - \epsilon) \cdot 2^{n(H - \epsilon)}$$

Taking $\frac{1}{n}\log_2$ on both sides:

$$\frac{1}{n} \log_2 \big\lvert B_\delta^{(n)} \big\rvert > \frac{\log_2(1 - \delta - \epsilon)}{n} + H(X) - \epsilon$$

As $n \to \infty$, the term $\frac{\log_2(1 - \delta - \epsilon)}{n} \to 0$. By picking $\epsilon < \delta'$, we establish that $\frac{1}{n} \log_2 \vert{}B_\delta^{(n)}\vert{} > H(X) - \delta'$, completing the proof.

∎

---

First-Order Exponential Equality ($\doteq$)

Because both $\vert{}A_\epsilon^{(n)}\vert{}$ and $\vert{}B_\delta^{(n)}\vert{}$ have counts governed by the exponent $n H(X)$, information theory uses a special asymptotic notation.

Using this notation, the conclusion is:

$$\big\lvert B_\delta^{(n)} \big\rvert \;\doteq\; \big\lvert A_\epsilon^{(n)} \big\rvert \;\doteq\; 2^{n H(X)}$$

The smallest high-probability set and the typical set are of the exact same size to first order in the exponent. The typical set is already asymptotically optimal.

Comparison: Where Do the Two Sets Actually Differ?

Consider our binary source typing 1 with probability $p = 0.9$ and 0 with probability $p = 0.1$, where $H(X) \approx 0.469\text{ bits}$.

Feature	The Typical Set $A_\epsilon^{(n)}$	The Smallest Set $B_\delta^{(n)}$
Membership Rule	Tapes with roughly $90\%$ ones (sample entropy near $0.469$).	The most probable individual tapes, picked greedily from highest to lowest.
Contains all-ones tape 11...11?	NO. Its sample entropy is $-\log_2(0.9) \approx 0.152\text{ bits}$, which fails the band condition $\vert{}0.152 - 0.469\vert{} \le \epsilon$.	YES. It is the single most probable tape in the entire sample space ($p = 0.9^n$).
Contains the $90\%$-ones tapes?	YES. This is the core band.	YES. Because all-ones and near-all-ones tapes are not enough to reach $99\%$ mass, it is forced to include the $90\%$-ones tapes.
Asymptotic Size	$\doteq 2^{n(0.469)}$	$\doteq 2^{n(0.469)}$

---

---

Summary

Object	Statement	Reads as
AEP	$-\frac{1}{n}\log p(X^n) \to H(X)$ in probability	Sample entropy of a long tape converges to the source’s blueprint entropy.
Typical set	$2^{-n(H+\epsilon)} \le p(x^n) \le 2^{-n(H-\epsilon)}$	Tapes whose statistics look ordinary for this source.
Probability	$\Pr\{A_\epsilon^{(n)}\} > 1 - \epsilon$	The typical pile is almost everything that happens.
Size (upper)	$\lvert A_\epsilon^{(n)} \rvert \le 2^{n(H+\epsilon)}$	There are not many realistic tapes.
Size (lower)	$\lvert A_\epsilon^{(n)} \rvert \ge (1-\epsilon)2^{n(H-\epsilon)}$	But there are not too few either, the count really is $\approx 2^{nH}$.
Source code	$\mathbb{E}\big[\tfrac{1}{n} l(X^n)\big] \le H(X) + \epsilon'$	A one-to-one code averaging about $nH$ bits per tape exists.
Optimality	$\lvert B_\delta^{(n)} \rvert \doteq \lvert A_\epsilon^{(n)} \rvert \doteq 2^{nH}$	No smaller high-probability set beats the typical set in the exponent.

Constants to keep to hand:

• Typical codeword length: $\le n(H + \epsilon) + 2$ bits (index $+$ flag $+$ ceiling).
• Atypical codeword length: $\le n \log \lvert \mathcal{X} \rvert + 2$ bits.
• Slack in the source coding theorem: $\epsilon' = \epsilon + \epsilon \log \lvert \mathcal{X} \rvert + \frac{2}{n}$, shrink $\epsilon$ first, then grow $n$.

References

• Cover & Thomas, Elements of Information Theory: Chapter 3