Typical sets

Size about 2^{nH}, probability near 1, and the fraction of all sequences they occupy.

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.

1. What you will learn

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

2. Typical sets and block coding

The typical set $A_\varepsilon^{(n)}$ is the set of sequences with $2^{-n(H + \varepsilon)} \le p(x^n) \le 2^{-n(H - \varepsilon)}$. The AEP gives three facts: $P(A_\varepsilon^{(n)}) > 1 - \varepsilon$ for large $n$; $|A_\varepsilon^{(n)}| \le 2^{n(H + \varepsilon)}$; and $|A_\varepsilon^{(n)}| \ge (1 - \varepsilon) 2^{n(H - \varepsilon)}$. When $H < \log_2 |\mathcal{X}|$ the typical set is an exponentially small fraction $2^{-n(\log_2 |\mathcal{X}| - H)}$ of all sequences, yet it holds nearly all the probability. This is the block source coding theorem in one picture: index the typical sequences with $n(H + \varepsilon) + 1$ bits and spend a flag bit plus a long index on the rare atypical ones; the expected length per symbol tends to $H$. For a binary source the typical set is essentially the type classes with about $np$ ones, and the count of strings with $k$ ones is $\binom{n}{k} \approx 2^{n h(k/n)}$, the estimate that makes $h$ appear in counting arguments throughout coding theory.

Another way: picture

A huge square representing all $|\mathcal{X}|^n$ sequences, with a tiny dot inside it: the typical set. Almost all the probability sits in the dot. A code names each point of the dot with $nH$ bits and does not bother about the rest.

Another way: steps

Exponent of the typical count: $nH$; exponent of all sequences: $n \log_2 |\mathcal{X}|$.
Fraction typical: $2^{-n(\log_2 |\mathcal{X}| - H)}$.
Bits to index the typical set: about $nH$; that is the block code.
For binary type classes use $\log_2 \binom{n}{k} \approx n h(k/n)$.

3. The three facts, and the picture

A large area holding all sequences of length n, with a small one inside it: the typical set of about 2^(nH) sequences, each of probability about 2^(-nH), holding almost all the probability while the many non-typical sequences outside hold almost none.

The typical set $A_\varepsilon^{(n)}$ collects the sequences whose probability lies between $2^{-n(H + \varepsilon)}$ and $2^{-n(H - \varepsilon)}$. Three facts follow from the AEP and a counting argument:

$P(A_\varepsilon^{(n)}) > 1 - \varepsilon$ for large $n$ — it holds nearly all the probability (that is the AEP).
$|A_\varepsilon^{(n)}| \le 2^{n(H + \varepsilon)}$ — each member has probability at least $2^{-n(H + \varepsilon)}$ and the total is at most $1$.
$|A_\varepsilon^{(n)}| \ge (1 - \varepsilon) 2^{n(H - \varepsilon)}$ — each member has probability at most $2^{-n(H - \varepsilon)}$ and the total is at least $1 - \varepsilon$.

So the set has about $2^{nH}$ members, and it is an exponentially thin slice of everything:

alphabet size	$\log_2 \|\mathcal{X}\|$	$H$	typical fraction $2^{-n(\log_2 \|\mathcal{X}\| - H)}$ at $n = 100$
$2$	$1$	$1$	$1$ (all sequences typical)
$2$	$1$	$0.5$	$2^{-50}$
$4$	$2$	$1.5$	$2^{-50}$
$8$	$3$	$1$	$2^{-200}$

4. Block coding, and counting by weight

The block source coding theorem falls straight out of the picture. Number the typical sequences: there are at most $2^{n(H + \varepsilon)}$ of them, so $n(H + \varepsilon) + 1$ bits suffice for an index. Spend one flag bit to say 'typical' and send the index; for the rare non-typical sequences spend the flag plus a raw $n \log_2 |\mathcal{X}|$ bits. The average is at most $$n(H + \varepsilon) + 2 + \varepsilon \, n \log_2 |\mathcal{X}|,$$ which is $H$ per symbol in the limit. And the converse holds too: a set of fewer than $2^{n(H - \varepsilon)}$ sequences carries vanishing probability, so no code beats $H$ per symbol.

There is a neat cross-check with combinatorics. The number of binary strings of length $n$ with exactly $k$ ones is $\binom{n}{k}$, and Stirling's approximation gives $$\log_2 \binom{n}{k} \approx n\, h\!\left(\frac{k}{n}\right).$$ A typical sequence of a coin with bias $p$ has $k \approx np$ ones, so the count of typical sequences is about $2^{n h(p)} = 2^{nH}$ — the AEP and the binomial coefficient agree exactly. For $n = 100$ and $k = 20$: $\log_2 \binom{100}{20} \approx 100 \cdot h(0.2) = 72.2$.

5. Solving the practice problems

Typical fraction, as $-\log_2$: $n(\log_2 |\mathcal{X}| - H)$; with an alphabet of $2^m$ symbols that is $n(m - H)$.
How many heads in a typical sequence: $np$, the expected count.
$\log_2$ of the number of strings with $k$ ones: $n\, h(k/n)$, to one decimal.
Which statement about $A_\varepsilon^{(n)}$ is correct: it is a vanishing fraction of all sequences yet holds almost all the probability.

Common mistakes

Using $H$ where $\log_2 |\mathcal{X}| - H$ is wanted: the fraction depends on the gap, not on the entropy alone.
Computing $h(k)$ instead of $h(k/n)$ in the binomial estimate.
Thinking a small typical set means little probability; it is the opposite.

6. Block coding through the typical set

Source with $H = 0.5$ over a binary alphabet, $n = 100$: typical set of about $2^{50}$ sequences out of $2^{100}$.
A fraction $2^{-50}$.
Code: flag bit $0$ plus a $51$-bit index for typical sequences, flag $1$ plus the raw $100$ bits otherwise. Expected length $\approx 52$ bits per $100$ symbols: about $0.52$ per symbol, near $H$.
The atypical case is too rare to matter.

7. Counting strings by weight

Strings of length $100$ with $20$ ones: $\log_2 \binom{100}{20} \approx 100 \cdot h(0.2) = 72.2$.
Exact value $\log_2 \binom{100}{20} = 68.8$; the estimate is right to first order in $n$.
So the typical set of a coin with $p = 0.2$ has about $2^{72}$ members: exactly $2^{nH}$.

8. How thin is the typical set?

A source over $4$ symbols with $H = 1.5$ bits, sequences of length $60$.
All sequences: $4^{60} = 2^{120}$. Typical: about $2^{60 \cdot 1.5} = 2^{90}$.
Fraction $2^{90 - 120} = 2^{-30}$, about one in a billion — and yet that billionth holds essentially all the probability.

9. Counting strings with $40$ ones out of $80$

$k/n = 0.5$, so $h(k/n) = 1$.
$\log_2 \binom{80}{40} \approx 80 \cdot 1 = 80.0$.
The true value is $76.6$: the estimate ignores a $\sqrt{n}$ correction, which the practice's one-decimal tolerance accounts for.
For a fair coin every one of the $2^{80}$ sequences is typical, and the balanced ones are the overwhelming majority.

10. Your turn: fraction of $4$-ary sequences of length $60$ that are typical when $H = 1.5$

Exponents: typical $60 \cdot 1.5 = 90$; all $60 \cdot 2 = 120$.
Your turn: work this step out. Its working is at the end of the packet.
Fraction $2^{-30}$, about one in a billion, yet nearly all the probability.

11. Guided practice

A source over an alphabet of $32$ symbols has entropy $3$ bits. Of the $32^{28}$ sequences of length $28$, roughly what fraction is typical? Give $-\log_2$ of the fraction.

Computed value: _answer

12. Guided practice

A coin with $P(\text{heads}) = 0.4$ is flipped $n = 20$ times. About how many heads does a typical sequence contain?

Computed value: _answer

13. Practice

How many binary strings of length $n = 20$ have exactly $5$ ones? Use the estimate $\binom{n}{k} \approx 2^{n h(k/n)}$ and give $\log_2$ of the count, to one decimal place.

Computed value: _answer

14. Practice

A source over an alphabet of $32$ symbols has entropy $2$ bits. Of the $32^{42}$ sequences of length $42$, roughly what fraction is typical? Give $-\log_2$ of the fraction.

Computed value: _answer

15. Somewhere new

Which statement about the typical set $A_\varepsilon^{(n)}$ of an i.i.d. source with $H < \log_2 |\mathcal{X}|$ is correct for large $n$?

It has probability near $1$, about $2^{nH}$ members, and is a vanishing fraction of all $|\mathcal{X}|^n$ sequences
It contains the most probable sequences
It contains more than half of all sequences
Its members each have probability exactly $2^{-nH}$

16. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

17. Test question

A coin with $P(\text{heads}) = 0.15$ is flipped $n = 20$ times. About how many heads does a typical sequence contain?

Computed value: _answer

18. What you can do now

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.

Working for the steps left to you

10. Your turn: fraction of $4$-ary sequences of length $60$ that are typical when $H = 1.5$, step 2