The Asymptotic Equipartition Property

Motivation: from one keystroke to a whole tape

So far every quantity we built (entropy, relative entropy, mutual information) is an average per keystroke. But a telecom engineer never sells a single keystroke. They sell a tape: a message of $n$ symbols $X_1, X_2, \ldots, X_n$ punched out by an operator whose language habits are the pmf $p(x)$ .

This raises an engineering question that the per-symbol averages cannot answer on their own. The operator can, in principle, type any of the $\lvert \mathcal{X} \rvert^n$ possible tapes. If we must reserve a codebook slot for every one of them, the cost of the system is $n \log \lvert \mathcal{X} \rvert$ bits regardless of how skewed the language is, and all the structure we measured with $H(X)$ bought us nothing.

IntuitionThe question we actually want answered

Out of the astronomically many tapes the machine could print, how many does it realistically print? If that realistic subset is far smaller than $\lvert \mathcal{X} \rvert^n$ , an engineer only needs to build a codebook for the subset, and can dismiss everything else as an event too rare to pay for.

The Asymptotic Equipartition Property (AEP) is the answer, and it is the information-theoretic analogue of the law of large numbers.

	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)$
Physical reading	The average voltage of a long tape settles down	The average surprise of a long tape settles down

Because $-\frac{1}{n}\log p(X_1, \ldots, X_n)$ settles at $H(X)$ , the probability of whatever tape we actually observe settles at $2^{-nH}$ — the same value for essentially every tape we are ever likely to see.

IntuitionThe one-line summary

“Almost all events are almost equally surprising.” Formally, if $X_1, \ldots, X_n$ are i.i.d. $\sim p(x)$ , then

$\Pr \Big\{ (X_1, \ldots, X_n) : p(X_1, \ldots, X_n) = 2^{-n(H \pm \epsilon)} \Big\} \approx 1$

ConventionTape notation

We write $x^n$ as shorthand for a sequence $x_1, x_2, \ldots, x_n$ , and $X^n$ for the corresponding random tape. So $p(x^n)$ is the probability the operator punches out that exact tape, and $\mathcal{X}^n$ is the set of all $\lvert \mathcal{X} \rvert^n$ tapes of length $n$ .

Intuition check: are all tapes equally likely?

A naive first guess is that the AEP is trivially true because every tape 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 tape $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}$

ExampleA concrete tape

The tape $(1, 0, 1, 1, 0, 1)$ has probability $p^4 q^2$ . A tape of six zeroes has probability $q^6$ . These are wildly different numbers whenever $p \neq q$ , so it is plainly not true that all $2^n$ tapes of length $n$ are equally probable.

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$ tapes have very different probabilities, the tapes that actually get printed almost all share roughly the same probability $2^{-nH(p)}$ . In this binary example that is just the statement that the number of $1$ s on a printed tape is close to $np$ with high probability, and every tape with about $np$ ones carries about the same probability.

RemarkThe self-referential flavour

We are asking for the probability $p(X_1, \ldots, X_n)$ of the outcome $X_1, \ldots, X_n$ , where the outcome is itself drawn according to that same distribution. This is insidiously self-referential, but perfectly well defined: $p(X^n)$ is a random variable (a function of the $X_i$ ), and we are studying its distribution.

Convergence of random variables

The AEP is a statement about a random variable converging, so we need to fix which mode of convergence we mean.

DefinitionConvergence of random variables

Given a sequence of random variables $X_1, X_2, \ldots$ , we say the sequence converges to a random variable $X$ :

In probability if for every $\epsilon > 0$ , $\Pr\{ \lvert X_n - X \rvert > \epsilon \} \rightarrow 0$ .
In mean square if $\mathbb{E}(X_n - X)^2 \rightarrow 0$ .
With probability 1 (also called almost surely) if $\Pr\{ \lim_{n \rightarrow \infty} X_n = X \} = 1$ .

IntuitionWhich one the AEP uses

Convergence in probability is the weakest of the three and is all we need. Physically it says: pick any tolerance $\epsilon$ you like on the average surprise per keystroke; as the tape gets longer, the fraction of tapes whose average surprise misses $H(X)$ by more than $\epsilon$ shrinks to zero. It does not claim that a single infinitely long tape never has a bad stretch — only that a bad stretch at the moment you look becomes vanishingly unlikely.

The AEP theorem

TheoremAsymptotic Equipartition Property

If $X_1, X_2, \ldots$ are i.i.d. $\sim p(x)$ , then

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

IntuitionPhysical meaning

Read the left side as a measurement taken off the printed tape: take the whole tape, compute its surprise $-\log p(\text{tape})$ , and divide by the number of keystrokes to get the sample entropy — the average bits of surprise per key actually delivered by this particular tape. Read $H(X)$ as the blueprint property of the operator’s language, computed from the pmf alone with no tape in hand. The theorem says the measurement converges to the blueprint. Equivalently, since $-\frac{1}{n}\log p(\text{tape}) \approx H$ rearranges to $p(\text{tape}) \approx 2^{-nH}$ , the tape you are holding is overwhelmingly likely to be one with probability about $2^{-nH}$ .

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 [[entropy-mutual-information#The three conditions we need on $h$ |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}$

∎

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"]

DefinitionThe typical set $A_\epsilon^{(n)}$

The typical set $A_\epsilon^{(n)}$ with respect to $p(x)$ is the set of sequences $(x_1, x_2, \ldots, x_n) \in \mathcal{X}^n$ with the property

$2^{-n(H(X) + \epsilon)} \le p(x_1, x_2, \ldots, x_n) \le 2^{-n(H(X) - \epsilon)}$

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$ .

IntuitionWhat membership physically means

A tape is typical if it “sounds like the language.” Its letter frequencies came out close enough to the operator’s blueprint $p(x)$ that its total surprise per key lands within $\epsilon$ of $H(X)$ . It is not a statement about the content of the message — only about whether its statistics look ordinary for this source.

WarningThe most probable tape is usually not typical

Take a binary operator with $p(1) = 0.9$ . The single most likely tape of length $n$ is the all-ones tape, with probability $0.9^n$ — larger than any other individual tape. But its sample entropy is $-\frac{1}{n}\log(0.9^n) = \log(1/0.9) \approx 0.152$ bits, while $H(X) = H(0.9) \approx 0.469$ bits. It misses the band entirely and is atypical. “Typical” means representative of the source’s statistics, not most likely as an individual outcome: the typical tapes here are the ones whose proportion of $1$ s is close to $0.9$ , and the typical set wins on total probability not because its members are individually special, but because there are so enormously many of them. We return to this exact example in .

Properties of the typical set

TheoremProperties of $A_\epsilon^{(n)}$

If $(x_1, x_2, \ldots, x_n) \in A_\epsilon^{(n)}$ , then $H(X) - \epsilon \le -\frac{1}{n} \log p(x_1, x_2, \ldots, x_n) \le H(X) + \epsilon$
$\Pr\big\{ A_\epsilon^{(n)} \big\} > 1 - \epsilon$ for $n$ sufficiently large.
$\big\lvert A_\epsilon^{(n)} \big\rvert \le 2^{n(H(X) + \epsilon)}$ , where $\lvert A \rvert$ denotes the number of elements in the set $A$ .
$\big\lvert A_\epsilon^{(n)} \big\rvert \ge (1 - \epsilon) 2^{n(H(X) - \epsilon)}$ for $n$ sufficiently large.

IntuitionThe three physical facts, in order

Taken together, these say that the typical set has probability nearly 1 (property 2 — so an engineer who only handles typical tapes is almost never caught out), all its elements are nearly equiprobable (property 1 — so a fixed-length index wastes nothing, since no member deserves a shorter codeword than another), and it contains about $2^{nH}$ elements (properties 3 and 4 — so indexing it takes about $nH$ bits rather than $n \log \lvert \mathcal{X} \rvert$ ).

ProofProperty 1 — immediate from the definition

Start from the membership condition:

$2^{-n(H + \epsilon)} \le p(x_1, \ldots, x_n) \le 2^{-n(H - \epsilon)}$

Take $\log$ of all three parts (monotone, so inequalities are preserved):

$-n(H + \epsilon) \le \log p(x_1, \ldots, x_n) \le -n(H - \epsilon)$

Multiply through by $-\frac{1}{n}$ , which is negative and therefore flips both inequalities:

$H - \epsilon \le -\frac{1}{n} \log p(x_1, \ldots, x_n) \le H + \epsilon$

So the “probability band” definition and the “sample entropy within $\epsilon$ ” description are literally the same condition, just written on different scales.

∎

ProofProperty 2 — the typical set captures nearly all the probability

This is exactly the AEP restated as a probability.

Step 1: Write the AEP in its $\epsilon$ - $\delta$ form. Theorem (AEP) says $-\frac{1}{n}\log p(X_1, \ldots, X_n) \to H(X)$ in probability. By the definition of convergence in probability, for any $\delta > 0$ there exists an $n_0$ such that for all $n \ge n_0$ :

$\Pr \left\{ \left\lvert -\frac{1}{n} \log p(X_1, X_2, \ldots, X_n) - H(X) \right\rvert < \epsilon \right\} > 1 - \delta$

Step 2: Recognize the event. By Property 1, the event inside that probability — sample entropy within $\epsilon$ of $H(X)$ — is the event $(X_1, \ldots, X_n) \in A_\epsilon^{(n)}$ . So the displayed line already reads $\Pr\{A_\epsilon^{(n)}\} > 1 - \delta$ .

Step 3: Set $\delta = \epsilon$ . The AEP holds for every $\delta > 0$ , so we are free to choose $\delta = \epsilon$ , giving $\Pr\{A_\epsilon^{(n)}\} > 1 - \epsilon$ for $n$ sufficiently large. This identification is purely a notational convenience that keeps one symbol instead of two in everything that follows.

∎

ProofProperty 3 — upper bound on the size, from total probability

The argument is: each typical tape carries at least a known minimum probability, and all of them together cannot carry more than the total probability 1, so there cannot be too many of them.

Step 1: Start from the total probability of the whole tape space.

$1 = \sum_{x^n \in \mathcal{X}^n} p(x^n)$

Step 2: Discard the atypical tapes. Restricting a sum of non-negative terms to a subset can only shrink it:

$1 \ge \sum_{x^n \in A_\epsilon^{(n)}} p(x^n)$

Step 3: Replace each term by its floor. By the membership definition, every typical tape has $p(x^n) \ge 2^{-n(H + \epsilon)}$ :

$1 \ge \sum_{x^n \in A_\epsilon^{(n)}} 2^{-n(H(X) + \epsilon)}$

Step 4: Collapse the sum into a count. Every summand is now the same constant, so the sum is just that constant times the number of terms:

$1 \ge 2^{-n(H(X) + \epsilon)} \big\lvert A_\epsilon^{(n)} \big\rvert$

Step 5: Rearrange.

$\big\lvert A_\epsilon^{(n)} \big\rvert \le 2^{n(H(X) + \epsilon)}$

∎

ProofProperty 4 — lower bound on the size, from Property 2

Symmetric argument: the typical set carries nearly all the probability, but each of its members carries at most a known maximum, so there must be many of them.

Step 1: Start from Property 2. For $n$ sufficiently large,

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

Step 2: Replace each term by its ceiling. By the membership definition, every typical tape has $p(x^n) \le 2^{-n(H - \epsilon)}$ :

$1 - \epsilon < \sum_{x^n \in A_\epsilon^{(n)}} 2^{-n(H(X) - \epsilon)}$

Step 3: Collapse the sum into a count.

$1 - \epsilon < 2^{-n(H(X) - \epsilon)} \big\lvert A_\epsilon^{(n)} \big\rvert$

Step 4: Rearrange.

$\big\lvert A_\epsilon^{(n)} \big\rvert \ge (1 - \epsilon) 2^{n(H(X) - \epsilon)}$

∎

RemarkWhy the two size bounds are proved in opposite directions

Property 3 needs a floor on each member’s probability (to stop the count running away), and property 4 needs a ceiling (to force the count up). The typical set’s defining band supplies exactly one of each, which is the whole reason the definition is a two-sided band rather than a single threshold.

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

NoteWhere the two extra bits come from

One bit is the flag. The other is a ceiling: indexing $2^{n(H+\epsilon)}$ items needs $\lceil n(H + \epsilon) \rceil$ bits, and $n(H + \epsilon)$ need not be an integer, so $n(H + \epsilon) + 1$ safely covers it. Same for the atypical pile.

IntuitionWhat the flag bit is physically doing

The initial bit is a length flag: it tells the receiver, before they have decoded anything, which of the two codeword lengths to read off the wire. That is what makes the scheme one-to-one and easily decodable despite the two piles having different codeword lengths.

RemarkWe are being deliberately wasteful, and it doesn’t matter

Notice that we indexed the atypical set by brute-force enumeration over all of $\mathcal{X}^n$ , ignoring the fact that $\lvert {A_\epsilon^{(n)}}^c \rvert$ is strictly smaller than $\lvert \mathcal{X}^n \rvert$ . We are paying full price for a pile we could have indexed more cleverly. Surprisingly, this crude treatment is still good enough to yield an efficient description — because the pile it wastes bits on has probability under $\epsilon$ , so the waste is multiplied by almost nothing.

Expected codeword length

Let $l(x^n)$ be the length of the codeword assigned to tape $x^n$ . Take $n$ large enough that $\Pr\{A_\epsilon^{(n)}\} \ge 1 - \epsilon$ .

TheoremSource coding via the typical set

Let $X^n$ be i.i.d. $\sim p(x)$ and let $\epsilon > 0$ . Then there exists a code mapping sequences $x^n$ of length $n$ into binary strings such that the mapping is one-to-one (and therefore invertible) and

$\mathbb{E}\left[ \frac{1}{n} l(X^n) \right] \le H(X) + \epsilon'$

for $n$ sufficiently large. That is: we can represent tapes $X^n$ using about $nH(X)$ bits on average.

ProofSplit the expectation by pile, bound each pile’s length, then bound each pile’s probability

Step 1: Write the expectation. By definition of expected value over all tapes:

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

Step 2: Split the sum along the partition. Every tape is in exactly one pile, so the sum splits cleanly with no double counting:

$= \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: Replace each length by its worst case. Within a pile, every codeword obeys the length bound from the construction table, so substituting the maximum can only increase the sum:

$\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 \lvert \mathcal{X} \rvert + 2\big)$

Step 4: Collapse each sum into a probability. The length factors are now constants within each pile and pull out, leaving bare sums of $p(x^n)$ over each pile — which are by definition the piles’ probabilities:

$= \Pr\big\{A_\epsilon^{(n)}\big\}\big(n(H + \epsilon) + 2\big) \;+\; \Pr\big\{{A_\epsilon^{(n)}}^c\big\}\big(n \log \lvert \mathcal{X} \rvert + 2\big)$

Step 5: Bound the two probabilities — this is the step that does the work. For the typical term use the trivial bound $\Pr\{A_\epsilon^{(n)}\} \le 1$ (we are happy to pay full price on the cheap pile). For the atypical term use Property 2, $\Pr\{{A_\epsilon^{(n)}}^c\} \le \epsilon$ (the expensive pile is charged at a rate of $\epsilon$ ):

$\le n(H + \epsilon) + \epsilon\, n \log \lvert \mathcal{X} \rvert + 2$

Step 6: Collect into a single $\epsilon'$ . Factor out $n$ :

$= n\left(H + \underbrace{\epsilon + \epsilon \log \lvert \mathcal{X} \rvert + \frac{2}{n}}_{\epsilon'}\right) = n(H + \epsilon')$

Step 7: Check $\epsilon'$ can be made arbitrarily small. The order matters. First choose $\epsilon$ small enough to crush $\epsilon + \epsilon \log \lvert \mathcal{X} \rvert$ — note this is possible because $\log \lvert \mathcal{X} \rvert$ is a fixed constant of the alphabet, not something growing with $n$ . Then, with $\epsilon$ fixed, choose $n$ large enough to crush the $2/n$ term. Dividing through by $n$ gives the theorem.

∎

IntuitionWhat this buys the telecom company

A naive engineer reserves a codeword slot for all $\lvert \mathcal{X} \rvert^n$ tapes and pays $n \log \lvert \mathcal{X} \rvert$ bits per message no matter what. This scheme pays about $nH(X)$ bits per message instead, and the gap $n\big(\log \lvert \mathcal{X} \rvert - H(X)\big)$ is precisely the structure in the operator’s language — the same gap measured per-symbol by the maximum entropy bound. Nothing was thrown away to get it: the code is still one-to-one on every tape the machine can print.

High-probability sets and the typical set

The problem. From its definition, $A_\epsilon^{(n)}$ is clearly a fairly small set that contains most of the probability. But nothing in the definition says it is the smallest such set. Perhaps a cleverer engineer, picking tapes by hand rather than by the sample-entropy band, could find a much smaller set that still captures nearly all the probability — and then index it with far fewer than $nH$ bits, beating the code we just built.

We settle this by defining the best possible competitor and showing it is no better, to first order in the exponent.

DefinitionSmallest high-probability set $B_\delta^{(n)}$

For each $n = 1, 2, \ldots$ , let $B_\delta^{(n)} \subset \mathcal{X}^n$ be the smallest set with

$\Pr\big\{B_\delta^{(n)}\big\} \ge 1 - \delta$

IntuitionHow $B_\delta^{(n)}$ is built, and why it differs from $A_\epsilon^{(n)}$

To make a high-probability set as small as possible you take the most probable tapes first and keep going until you have accumulated $1 - \delta$ of the probability. So $B_\delta^{(n)}$ is a greedy top-of-the-list set, whereas $A_\epsilon^{(n)}$ is a band set. They are built by genuinely different rules, and they are not the same set — $B_\delta^{(n)}$ contains the single most probable tapes, which as we saw can be atypical.

TheoremSize of the smallest high-probability set

Let $X_1, X_2, \ldots, X_n$ be i.i.d. $\sim p(x)$ . For $\delta < \frac{1}{2}$ and any $\delta' > 0$ , if $\Pr\{B_\delta^{(n)}\} > 1 - \delta$ , then

$\frac{1}{n} \log \big\lvert B_\delta^{(n)} \big\rvert > H - \delta'$

for $n$ sufficiently large.

NoteProof status

Cover & Thomas outline this proof in Problem 3.3.11 rather than giving it in the text. The argument sketch is: any set with probability above $1 - \delta$ must have a significant intersection with $A_\epsilon^{(n)}$ (since $A_\epsilon^{(n)}$ itself carries nearly all the probability, and $\delta < \frac{1}{2}$ prevents $B_\delta^{(n)}$ from dodging it), and every tape in that intersection carries probability at most $2^{-n(H - \epsilon)}$ — so covering that much probability with such small pieces forces at least about $2^{nH}$ pieces.

So $B_\delta^{(n)}$ must have at least $2^{nH}$ elements, to first order in the exponent — while $A_\epsilon^{(n)}$ has $2^{n(H \pm \epsilon)}$ elements by properties 3 and 4. The typical set is therefore about the same size as the smallest high-probability set, and no clever hand-picking beats it.

Equality to first order in the exponent

The phrase “to first order in the exponent” is doing real work above, so it gets its own notation.

DefinitionFirst-order exponential equality

The notation $a_n \doteq b_n$ means

$\lim_{n \rightarrow \infty} \frac{1}{n} \log \frac{a_n}{b_n} = 0$

IntuitionWhat $\doteq$ deliberately ignores

This says $a_n$ and $b_n$ agree in the exponent, not in the number. Two sets of sizes $2^{nH}$ and $n^{100} \cdot 2^{nH}$ satisfy $a_n \doteq b_n$ , because dividing the log by $n$ kills any polynomial factor. For an engineer this is exactly the right resolution: what they pay is $\log(\text{set size})$ bits, so a polynomial factor costs a vanishing number of bits per symbol.

With this notation, the results of the whole note collapse to one line. If $\delta_n \rightarrow 0$ and $\epsilon_n \rightarrow 0$ , then

$\big\lvert B_{\delta_n}^{(n)} \big\rvert \doteq \big\lvert A_{\epsilon_n}^{(n)} \big\rvert \doteq 2^{nH}$

Illustration: where the two sets actually differ

Take a Bernoulli sequence $X_1, X_2, \ldots, X_n$ with parameter $p = 0.9$ , i.e. a binary operator who types $1$ with probability $0.9$ .

	$A_\epsilon^{(n)}$	$B_\delta^{(n)}$
Rule	Tapes whose proportion of $1$ s is close to $0.9$	The most probable tapes, taken greedily until probability $1 - \delta$ is covered
Contains all-ones tape?	No — its sample entropy is $\approx 0.152$ bits, far from $H(0.9) \approx 0.469$	Yes — it is the single most likely tape of all
Contains the $\approx 90\%$ -ones tapes?	Yes, by construction	Yes — forced by the theorem
Size	$\doteq 2^{nH}$	$\doteq 2^{nH}$

IntuitionThe reconciliation

The two sets are not equal — $B_\delta^{(n)}$ contains the all-ones tape and $A_\epsilon^{(n)}$ does not. But both are forced to contain the bulk of the tapes with about $90\%$ ones, and that bulk is what determines the size. The disagreement is over a handful of exceptional tapes that carry negligible total probability and negligible count, so the two sets are almost equal in size even though neither contains the other.

RemarkWhat is still open after all this

We have shown the typical set yields a code costing about $H(X)$ bits per symbol, and that no smaller high-probability set exists to beat it. We have not proved a converse for arbitrary codes (that no one-to-one scheme whatsoever can average below $H$ ), and everything here assumed the source is i.i.d. — real operators have grammar, so their keystrokes are dependent, and extending the AEP to such sources needs the entropy rate of a stochastic process.

Quick reference

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

[[lit/cover2006-elements|Cover & Thomas, Elements of Information Theory]] — Chapter 3

Related