Back to the on-screen lesson ·
−(1/n) log p(Xⁿ) → H; typical sequences have probability about 2^{−nH}.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive the asymptotic equipartition property from the law of large numbers applied to per-symbol surprises, state it precisely, and use it to say that a typical sequence of length $n$ has probability about $2^{-nH}$ and that there are about $2^{nH}$ such sequences. You will define the typical set, prove its three properties, compute what fraction of all sequences it occupies, explain why it carries almost all the probability while the most probable sequence need not belong to it, and turn these facts into the block source coding theorem and the counting estimate $\binom{n}{k} \approx 2^{n h(k/n)}$.
For an i.i.d. source $X_1, X_2, \ldots$ with entropy $H$, the surprise of a block factorises: $-\log_2 p(X^n) = \sum_{i=1}^n -\log_2 p(X_i)$, a sum of i.i.d. terms with mean $H$. The weak law of large numbers then gives the asymptotic equipartition property (AEP): $$-\frac{1}{n} \log_2 p(X_1, \ldots, X_n) \to H \quad \text{in probability.}$$ In words, almost every sequence the source actually produces has probability close to $2^{-nH}$: the probability mass is spread almost evenly over a set of about $2^{nH}$ typical sequences, and everything else is negligible. A typical sequence of a biased coin has about $np$ heads; the single most probable sequence, all tails, is not typical and is irrelevant for large $n$. The AEP is the engine behind block source coding, and its joint version, applied to channel inputs and outputs together, is the engine behind the channel coding theorem.
Another way: picture
A histogram of $-\tfrac{1}{n} \log_2 p(x^n)$ over random sequences: for $n = 10$ it is broad, for $n = 1000$ it is a narrow spike at $H$. The sequences under the spike are the typical set.
Another way: steps
The trick is one line of algebra. For an i.i.d. source, $p(x_1, \ldots, x_n) = \prod_i p(x_i)$, so taking $-\log_2$ turns the product into a sum: $$-\log_2 p(X^n) = \sum_{i=1}^n \bigl(-\log_2 p(X_i)\bigr).$$ The terms are i.i.d. random variables, and their common mean is $E[-\log_2 p(X)] = H$ — the entropy is literally the average surprise per symbol. The weak law of large numbers says the average of $n$ i.i.d. terms converges in probability to their mean, so $-\tfrac{1}{n} \log_2 p(X^n) \to H$. Turned around: with probability approaching $1$, the sequence you actually observe has $p(x^n) \approx 2^{-nH}$.
| $n$ flips of a coin with $p = 0.1$ | typical heads $\approx np$ | $p(x^n) \approx 2^{-nH}$ | $2^{nH}$ typical sequences |
|---|---|---|---|
| $10$ | $1$ | $2^{-4.7}$ | $2^{4.7}$ |
| $100$ | $10$ | $2^{-46.9}$ | $2^{46.9}$ |
| $1000$ | $100$ | $2^{-469}$ | $2^{469}$ |
The equipartition in the name is the surprising part: the probability is spread almost evenly. Not every sequence has probability $2^{-nH}$ — but the ones that do not, taken together, have almost no probability at all.
| sequence of $1000$ flips, $p = 0.1$ | its probability | how many like it | total probability |
|---|---|---|---|
| all tails | $0.9^{1000} = 2^{-152}$ | $1$ | $2^{-152}$ |
| about $100$ heads (typical) | $\approx 2^{-469}$ | $\approx 2^{469}$ | $\approx 1$ |
| about $500$ heads | $\approx 2^{-737}$ | $\approx 2^{1000}$ | $\approx 0$ |
All-tails is by far the single most probable sequence — $2^{-152}$ against $2^{-469}$ for a typical one, a factor of $2^{317}$ — and yet it is not typical and you will never see it, because there is only one of it while there are $2^{469}$ typical sequences. Probability per sequence and probability of the set are different questions, and the AEP is about the set. This is exactly why compression works: a code needs to name the members of a set of size $2^{nH}$, which takes $nH$ bits, not to favour the single most likely message.
Common mistakes
$P(\text{heads}) = 0.1$, $n = 1000$: $H = h(0.1) = 0.469$, so typical sequences have probability about $2^{-469}$.
$nH$ bits of surprise.
They have about $100$ heads. All-tails has probability $0.9^{1000} = 2^{-152}$, far larger than any typical sequence, yet there is only one of it: it is not typical.
Typical is about frequencies, not about being likely.
Total probability near $1$, each about $2^{-nH}$, so about $2^{nH}$ of them: for the coin above, $2^{469}$.
Out of $2^{1000}$ sequences that is a fraction $2^{-531}$: almost nothing by count, almost everything by probability.
$H = \log_2 8 = 3$ bits per roll.
A typical sequence has $-\log_2 p(x^{50}) = 50 \cdot 3 = 150$ bits, that is probability $2^{-150}$.
Here every sequence has exactly that probability: a uniform source makes all sequences typical.
The count of typical sequences is $2^{150} = 8^{50}$, all of them.
Each typical sequence has probability about $2^{-nH} = 2^{-70}$.
They carry almost all the probability, so their number is about $1 / 2^{-70} = 2^{70}$.
$\log_2$ of the count is $70$: the answer the practice asks for.
$H = 3$ bits, so $nH = 150$.
About $2^{-150}$; here every sequence is typical, since the source is uniform.
A memoryless source has entropy $3$ bits per symbol. For a typical sequence $x^n$ of length $n = 155$, what is $-\log_2 p(x^n)$, approximately?
Answer:
A source has entropy $1/4$ bits per symbol. Roughly how many typical sequences of length $n = 8$ are there? Give $\log_2$ of the number.
Answer:
$X_1, X_2, \ldots$ are i.i.d. with entropy $H$. Which statement is the asymptotic equipartition property?
A memoryless source has entropy $2$ bits per symbol. For a typical sequence $x^n$ of length $n = 28$, what is $-\log_2 p(x^n)$, approximately?
Answer:
A coin with $P(\text{heads}) = 0.3$ is flipped $n$ times, $n$ large. Is the all-tails sequence typical?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A source has entropy $1/4$ bits per symbol. Roughly how many typical sequences of length $n = 12$ are there? Give $\log_2$ of the number.
Answer:
You can reason about long sequences through their typical set and count them with the binary entropy function. Next: sources with memory, the entropy rate, and arithmetic coding.
10. Your turn: a fair $8$-sided die rolled $n = 50$ times; probability of a typical sequence?, step 2