Contents / Information Theory / Entropy Rates and the AEP

Chapter 3

Entropy Rates and the AEP

Information per symbol for a process with memory, and the asymptotic equipartition property that makes long sequences predictable in bulk.

Introduction

Information per symbol for a process with memory, and the asymptotic equipartition property that makes long sequences predictable in bulk.

3.1Entropy Rate of a Stationary Process

For a single random variable, entropy is the uncertainty per draw. A process $X_1, X_2, X_3,\dots$ is different: its symbols are usually dependent, so the useful question is not how uncertain one symbol is but how much new uncertainty each additional symbol contributes. That long-run average per symbol is the entropy rate, and it, not the single-symbol entropy, is the number that governs the compressibility of real files — whose symbols are anything but independent.

Definition 3.1 (Entropy rate). For a discrete-time stochastic process $\{X_i\}$ define, when the limits exist,

H(\mathcal X) = \lim_{n\to\infty}\frac1n H(X_1,\dots,X_n), \qquad H'(\mathcal X) = \lim_{n\to\infty} H\bigl(X_n \mid X_1,\dots,X_{n-1}\bigr).

The first is the per-symbol block rate, the second the conditional rate.

Definition 3.2 (Stationary process). A process is stationary if its finite-dimensional distributions are shift-invariant: for every $n$ and every $k \ge 1$ ,

P(X_1 = x_1,\dots,X_n = x_n) = P(X_{1+k}=x_1,\dots,X_{n+k}=x_n).

The two rates look different — one averages a whole block, the other looks one symbol ahead — but for a stationary process they exist and coincide. The proof is a good illustration of how the chain rule and "conditioning reduces entropy" combine.

Lemma 3.3 (The conditional entropies decrease). For a stationary process, $H(X_n\mid X_1,\dots,X_{n-1})$ is non-increasing in $n$ and therefore converges (it is bounded below by $0$ ).

Proof. Conditioning on more reduces entropy, so

H(X_n \mid X_1,\dots,X_{n-1}) \le H(X_n\mid X_2,\dots,X_{n-1}),

since the left side conditions on one extra variable. Stationarity says the right side equals $H(X_{n-1}\mid X_1,\dots,X_{n-2})$ , because the block $(X_2,\dots,X_n)$ has the same joint law as $(X_1,\dots,X_{n-1})$ . Hence the sequence is non-increasing, and being non-negative it converges.∎

Lemma 3.4 (Cesàro mean). If $a_n \to a$ then $\frac1n\sum_{i=1}^n a_i \to a$ .

Proof. Given $\varepsilon>0$ choose $N$ with $|a_i - a| < \varepsilon/2$ for $i > N$ . For $n > N$ ,

\Bigl|\frac1n\sum_{i=1}^n a_i - a\Bigr| \le \frac1n\sum_{i=1}^{N}|a_i-a| + \frac1n\sum_{i=N+1}^{n}|a_i-a| < \frac{C_N}{n} + \frac{\varepsilon}{2},

where $C_N = \sum_{i\le N}|a_i - a|$ is a fixed number. Taking $n > 2C_N/\varepsilon$ makes the whole expression less than $\varepsilon$ .∎

Theorem 3.5 (The two rates agree). For a stationary process both limits in Definition Entropy rate exist and

H(\mathcal X) = H'(\mathcal X).

Proof. The conditional rate $H'$ exists by Lemma The conditional entropies decrease. The chain rule writes the block entropy as a sum of exactly those conditional entropies:

\frac1n H(X_1,\dots,X_n) = \frac1n\sum_{i=1}^n H\bigl(X_i \mid X_1,\dots,X_{i-1}\bigr).

The right side is the Cesàro mean of a convergent sequence, so by Lemma Cesàro mean it converges to the same limit $H'(\mathcal X)$ . Hence $H(\mathcal X)$ exists and equals $H'(\mathcal X)$ .∎

Figure 3.6. For a stationary process the one-step conditional entropies

H(X_n\mid X_1,\dots,X_{n-1})

fall monotonically to the entropy rate, while the block averages

\tfrac1n H(X_1,\dots,X_n)

— their Cesàro means — approach the same limit from above and more slowly. Here the limit is

0.8

bits per symbol.

Corollary 3.7 (The rate is below the marginal entropy). For a stationary process, $H(\mathcal X) \le H(X_1)$ , with equality if and only if the process is i.i.d.

Proof. Each term $H(X_i\mid X_{<i}) \le H(X_i) = H(X_1)$ by conditioning-reduces-entropy and stationarity; averaging preserves the bound. Equality for every $i$ requires $X_i$ independent of its past for every $i$ , which with stationarity is exactly independence with a common marginal.∎

Intuition. Memory is redundancy, and redundancy is compressibility. Written English has a per-letter marginal entropy of about $4.1$ bits, but its entropy rate — measured by how well people predict the next letter given the text so far — is closer to $1.3$ bits. The three-bit gap is grammar, spelling and meaning, and it is exactly what a good compressor harvests.

Example 3.8 (A memoryless source). An i.i.d. source has per-symbol entropy $2$ bits. Find its entropy rate.

Solution. Independence makes the chain rule collapse: $H(X_i\mid X_{<i}) = H(X_i) = 2$ for every $i$ , so $H(X_1,\dots,X_n) = 2n$ and

\frac1n H(X_1,\dots,X_n) = 2 \quad\text{for every } n,

giving $H(\mathcal X)=2$ bits/symbol. Note that the rate is attained at every block length, not merely in the limit — for an i.i.d. source there is nothing to be gained by coding long blocks other than amortising the $+1$ of the source coding theorem. □□

Exercises for §3.1 →

3.2Entropy Rate of a Markov Chain

The most important computable case is a Markov chain, where the entire past is summarised by the current state.

Definition 3.9 (Stationary Markov chain). A process is a Markov chain if $p(x_{n+1}\mid x_1,\dots,x_n) = p(x_{n+1}\mid x_n)$ for all $n$ . It is time-invariant if that transition law $P_{ij} = P(X_{n+1}=j \mid X_n = i)$ does not depend on $n$ , and stationary if in addition the marginal law $\mu$ satisfies $\mu_j = \sum_i \mu_i P_{ij}$ for all $j$ .

Theorem 3.10 (Entropy rate of a Markov chain). For a stationary Markov chain with stationary distribution $\mu$ and transition matrix $P$ ,

H(\mathcal X) = H(X_2 \mid X_1) = -\sum_{i,j} \mu_i P_{ij}\log_2 P_{ij}.

For a stationary Markov chain of order $k$ , $H(\mathcal X) = H(X_{k+1}\mid X_1,\dots,X_k)$ .

Proof. By Theorem The two rates agree, $H(\mathcal X) = \lim_n H(X_n\mid X_1,\dots,X_{n-1})$ . The Markov property makes the conditioning collapse: given $X_{n-1}$ , the variable $X_n$ is independent of $X_1,\dots,X_{n-2}$ , so $H(X_n\mid X_1,\dots,X_{n-1}) = H(X_n\mid X_{n-1})$ , and stationarity makes this the same number for every $n$ , namely $H(X_2|X_1)$ . The sequence is constant, so its limit is that constant. Expanding the definition of conditional entropy with $p(i,j) = \mu_i P_{ij}$ gives the displayed formula. The order- $k$ case is identical with the state taken to be the last $k$ symbols.∎

Example 3.11 (A sticky binary chain). A binary chain stays in its current state with probability $0.9$ and flips with probability $0.1$ . Find the stationary distribution, the marginal entropy, and the entropy rate.

Solution. Symmetry gives $\mu = (\tfrac12,\tfrac12)$ , which we check: $\tfrac12(0.9)+\tfrac12(0.1)=\tfrac12$ . ✓ So the marginal entropy is $H(X_1)=1$ bit.

From either state the next symbol is a Bernoulli $(0.1)$ decision to flip, so $H(X_2\mid X_1 = i) = h_2(0.1) \approx 0.469$ for each $i$ , and

H(\mathcal X) = \tfrac12(0.469)+\tfrac12(0.469) = 0.469 \text{ bits/symbol}.

Sanity check: $0.469 < 1 = H(X_1)$ , as Corollary The rate is below the marginal entropy requires, and the gap of $0.531$ bits per symbol is precisely $I(X_1;X_2)$ — the predictability that memory supplies. A file of a million such symbols compresses to about $469$ kbit, not $1$ Mbit. □□

Example 3.12 (An asymmetric two-state chain). A chain has $P_{01}=0.2$ , $P_{10}=0.4$ . Find $\mu$ and the entropy rate.

Solution. Stationarity requires $\mu_0 P_{01} = \mu_1 P_{10}$ (balance of flow across the cut), so $0.2\mu_0 = 0.4\mu_1$ , giving $\mu_0 = 2\mu_1$ and hence $\mu = (\tfrac23,\tfrac13)$ .

From state $0$ the next symbol is Bernoulli $(0.2)$ , contributing $h_2(0.2) \approx 0.7219$ ; from state $1$ it is Bernoulli $(0.4)$ , contributing $h_2(0.4)\approx 0.9710$ . Weighting,

H(\mathcal X) = \tfrac23(0.7219)+\tfrac13(0.9710) \approx 0.4813+0.3237 = 0.805 \text{ bits/symbol}.

Sanity check: the marginal entropy is $h_2(1/3)\approx 0.918$ bits, and indeed $0.805 < 0.918$ . □□

Pitfall. The entropy rate is not the entropy of the stationary distribution. $H(\mu)$ ignores the transition structure entirely and is only an upper bound. In the sticky chain above, $H(\mu)=1$ while the rate is $0.469$ — a factor of two.

Remark. A hidden Markov process — a function of a Markov chain, observed through noise — need not be Markov of any finite order, and its entropy rate has no closed form. It can be sandwiched: $H(X_n \mid X_{1:n-1}, S_1) \le H(\mathcal X) \le H(X_n\mid X_{1:n-1})$ , where $S_1$ is the initial hidden state, and both bounds converge to the rate. Establishing that sandwich is beyond this chapter.

Exercises for §3.2 →

3.3The AEP, Compression, and the Continuous Analogue

The entropy rate is not only an average; for well-behaved processes it is the value that essentially every long realisation exhibits. That is the content of the asymptotic equipartition property.

Write $A_\varepsilon^{(n)} \subseteq \mathcal X^n$ for the set of sequences whose per-symbol code length $-\tfrac1n\log_2 p(x_1,\dots,x_n)$ lies within $\varepsilon$ of $H$ — the typical set. It is defined carefully, and its size pinned down, in Definition Typical set below; here we need only the name.

Theorem 3.13 (Asymptotic equipartition property, i.i.d. case). Let $X_1,X_2,\dots$ be i.i.d. with entropy $H = H(X)$ on a finite alphabet. Then

-\frac1n\log_2 p(X_1,\dots,X_n) \longrightarrow H \quad\text{in probability},

and consequently $P\bigl(A_\varepsilon^{(n)}\bigr) \to 1$ for every $\varepsilon>0$ : the typical set eventually carries essentially all of the probability.

Proof. Independence factors the joint mass function, so

-\frac1n\log_2 p(X_1,\dots,X_n) = \frac1n\sum_{i=1}^n \bigl(-\log_2 p(X_i)\bigr),

an average of i.i.d. random variables with common mean $\mathbb{E}[-\log_2 p(X)] = H(X)$ and finite variance (the alphabet is finite). The weak law of large numbers gives convergence in probability to $H$ , which is the first claim, and membership of $A_\varepsilon^{(n)}$ is precisely the event $\bigl|-\tfrac1n\log_2 p(X^n) - H\bigr| \le \varepsilon$ , so its probability tends to $1$ . The weak law itself is proved in the next section, and the counting consequences — that $|A_\varepsilon^{(n)}|$ is about $2^{nH}$ — in the section after that.∎

Intuition. Of the $|\mathcal X|^n$ possible sequences, only about $2^{nH}$ are ever seen, and they are all roughly equally likely. Compression is therefore just indexing: number the typical sequences and send the index, which needs $nH$ bits. Everything else is handled by an escape code whose cost vanishes because its probability does.

Indexing the typical set is how the entropy rate becomes an achievable compression rate, and the last section of this chapter carries that construction out and measures its length. The matching claim that no scheme beats the rate — Shannon's source coding theorem, in both directions, with its Fano converse — is the subject of the next chapter, Source Coding and the Entropy Bound. Here we use only the achievability side, and only as arithmetic for sizing files.

Example 3.14 (Sizing a file from its rate). A source with entropy rate $1.2$ bits/symbol emits $1{,}000{,}000$ symbols. How large is the compressed file, and what would using the marginal entropy of $1.8$ bits/symbol have predicted?

Solution. The block entropy is about $nH(\mathcal X) = 1.2\times10^{6}$ bits $=150{,}000$ bytes $=150$ kB, and no scheme does sustainably better — that is the converse half of the source coding theorem, proved in the next chapter.

Using the marginal entropy instead would predict $1.8\times 10^6$ bits $=225$ kB. That estimate is an upper bound, not the truth: it ignores the memory, and the $75$ kB difference is exactly the redundancy a model of the dependence recovers. □□

Everything in this chapter has assumed a discrete alphabet. The continuous analogue is genuinely different, and the differences are worth stating because they are a standard source of error.

Definition 3.15 (Differential entropy). For a random variable $X$ with density $f$ on $\mathbb{R}$ ,

h(X) = -\int_{S} f(x)\log_2 f(x)\,dx,

where $S$ is the support of $f$ , whenever the integral exists. (The lower-case $h$ here is the traditional notation and unfortunately collides with the binary entropy function $h_2(p)$ ; the argument tells them apart — a random variable means differential entropy, a number in $[0,1]$ means the binary entropy.)

Theorem 3.16 (Differential entropy of a uniform and a Gaussian). If $X$ is uniform on $[0,a]$ then $h(X) = \log_2 a$ . If $X$ is Gaussian with variance $\sigma^{2}$ then $h(X) = \tfrac12\log_2\bigl(2\pi e\sigma^{2}\bigr)$ .

Proof. Uniform: $f = 1/a$ on $[0,a]$ , so $h = -\int_0^a \tfrac1a\log_2\tfrac1a\,dx = \log_2 a$ .

Gaussian: with $f(x) = (2\pi\sigma^{2})^{-1/2}e^{-x^{2}/2\sigma^{2}}$ ,

-\ln f(X) = \tfrac12\ln(2\pi\sigma^2) + \frac{X^2}{2\sigma^2},

whose expectation is $\tfrac12\ln(2\pi\sigma^{2}) + \tfrac12 = \tfrac12\ln(2\pi e\sigma^{2})$ . Dividing by $\ln 2$ converts nats to bits.∎

Pitfall. Differential entropy is not a limit of discrete entropies and it does not inherit their properties.

It can be negative: the uniform on $[0,\tfrac12]$ has $h = \log_2\tfrac12 = -1$ bit.
It is not invariant under relabelling: $h(aX) = h(X)+\log_2|a|$ , whereas discrete entropy is unchanged by any injective map. Differential entropy therefore depends on the units in which $X$ is measured.
It is not the number of bits needed to describe $X$ ; describing a real number exactly takes infinitely many bits. The correct statement is that an $n$ -bit uniform quantisation of $X$ has discrete entropy approximately $h(X)+n$ .

Remark. What survives the passage to densities is precisely the relative quantities. Relative entropy $D(f\|g) = \int f\log_2(f/g)$ is still non-negative, still infinite on support mismatch, and still invariant under a change of variables, because the Jacobian cancels between numerator and denominator. Mutual information $I(X;Y) = D\bigl(f_{XY}\|f_Xf_Y\bigr)$ inherits all of this: it is non-negative, invariant under smooth invertible relabelling of either variable, and satisfies the data processing inequality unchanged. This is the deeper reason to regard $D$ , rather than $H$ , as the fundamental object: $H$ is the special case $\log_2|\mathcal X| - D(p\|u)$ that only exists when a canonical uniform reference measure does.

Summary. So far: for a stationary process the entropy rate exists, equals the limiting one-step conditional entropy, is at most the marginal entropy with equality only in the i.i.d. case, and equals $-\sum_{i,j}\mu_iP_{ij}\log_2 P_{ij}$ for a stationary Markov chain. The AEP says that a long realisation exhibits that rate, and differential entropy is the continuous analogue that keeps the formula but loses the interpretation. The rest of the chapter makes the AEP quantitative: where it comes from, how large the typical set is, and what compressor it hands us.

Exercises for §3.3 →

3.4The Law of Large Numbers for Information

Entropy was introduced as the expected surprise of a single draw. To say anything about files we need a per-symbol quantity that survives dependence between symbols.

Recall the entropy rate $H(\mathcal X) = \lim_{n\to\infty} \tfrac1n H(X_1,\dots,X_n)$ of Definition Entropy rate, which for a stationary process also equals $\lim_{n\to\infty} H(X_n\mid X_1,\dots,X_{n-1})$ , the conditional entropy of the next symbol given the entire past. That is an average over the whole ensemble; what a compressor actually meets is one string, so we need a per-string quantity beside it.

For an i.i.d. source the chain rule gives $H(X_1,\dots,X_n) = nH(X)$ immediately, so $H(\mathcal X) = H(X)$ : the entropy rate is the ordinary single-symbol entropy. For a source with memory the two differ, and the difference is exactly the redundancy that a model of the memory can harvest.

Definition 3.17 (Sample information rate). For a string $x^n$ of positive probability, the sample information rate is

-\frac{1}{n}\log p(x^n),

the number of bits per symbol an ideal code would spend on this particular string. The random variable $-\frac1n \log p(X^n)$ is the empirical rate of the string actually produced.

The entropy rate is an expectation, $H(\mathcal X) = \lim_{n\to\infty} \frac1n E[-\log p(X^n)]$ ; the sample information rate is the random quantity being averaged. The AEP says that the random quantity concentrates on its mean — that essentially every long string costs the same number of bits per symbol.

Theorem 3.18 (Weak law of large numbers). If $Y_1, Y_2,\dots$ are i.i.d. with finite mean $\mu$ , then $\frac1n\sum_{i=1}^n Y_i \to \mu$ in probability: for every $\varepsilon > 0$ ,

\Pr\!\left( \left| \frac1n\sum_{i=1}^n Y_i - \mu \right| \ge \varepsilon \right) \longrightarrow 0 \qquad (n\to\infty).

Proof. We prove the case of finite variance $\sigma^{2}$ , which is all we need here: a finite alphabet makes $-\log p(X)$ a bounded random variable. The sample mean $\bar Y_n$ has mean $\mu$ and, by independence, variance $\sigma^{2}/n$ , so Chebyshev's inequality gives

\Pr\!\left( |\bar Y_n - \mu| \ge \varepsilon \right) \le \frac{\sigma^2}{n\varepsilon^2} \longrightarrow 0 .

(The general finite-mean case is Khinchin's theorem and requires a truncation argument, which we do not need.)∎

Theorem 3.19 (AEP, quantitative form). Let $X_1,X_2,\dots$ be i.i.d. $\sim p$ on a finite alphabet, write $H = H(X)$ , and let

V = \operatorname{Var}\bigl(-\log p(X)\bigr) = \sum_x p(x)\log^2 p(x) \;-\; H^2

be the varentropy of the source. Then for every $\varepsilon>0$ and every $n$ ,

\Pr\!\left( \Bigl| -\frac1n\log p(X^n) - H \Bigr| \ge \varepsilon \right) \;\le\; \frac{V}{n\varepsilon^{2}} .

Letting $n\to\infty$ recovers Theorem Asymptotic equipartition property, i.i.d. case, now with an explicit rate.

Proof. Independence factorises the joint mass function, $p(X^n) = \prod_{i=1}^n p(X_i)$ , and the logarithm turns the product into a sum:

-\frac1n \log p(X^n) = \frac1n \sum_{i=1}^n \bigl(-\log p(X_i)\bigr).

The summands $Y_i = -\log p(X_i)$ are i.i.d. functions of i.i.d. variables, and are bounded because the alphabet is finite and every symbol that can actually be observed has $p(x)>0$ . Their common mean is

E[Y_1] = \sum_{x} p(x)\bigl(-\log p(x)\bigr) = H(X),

and their common variance is $V$ , by the definition above. So $-\frac1n\log p(X^n)$ is exactly the sample mean $\bar Y_n$ of Theorem Weak law of large numbers with $\mu = H$ and $\sigma^{2} = V$ , and the Chebyshev step of that proof gives the displayed bound — at every $n$ , not merely in the limit.∎

That is the whole trick, and it is worth saying twice: the AEP is the weak law of large numbers applied to the random variable "surprise". The varentropy is the constant that says how long a block must be before the law bites. A nearly uniform source has small $V$ and concentrates almost at once; a source with one rare, very surprising symbol has large $V$ and needs long blocks before its typical set is worth anything. That is why the asymptotic statements of this chapter are careful to be asymptotic.

Remark (Beyond independence). For a general stationary ergodic process the same conclusion holds, in the stronger almost-sure form

-\frac1n\log p(X^n) \longrightarrow H(\mathcal X) \quad \text{almost surely.}

This is the Shannon–McMillan–Breiman theorem. Its proof is genuinely harder — it rests on the Birkhoff ergodic theorem together with a martingale-convergence argument for the conditional densities — and is beyond the scope of this chapter. We use it only to state results in their natural generality; every proof given here is carried out in the i.i.d. case, where the weak law suffices.

Intuition. Toss a biased coin a million times. You cannot predict the sequence, but you can predict its cost: almost every outcome you will ever see takes about the same number of bits to write down, namely $H(\mathcal X)$ per toss.

Strings that are much cheaper (all heads) or much more expensive exist, but their total probability is negligible. Compression is the art of budgeting for the ordinary strings and merely coping with the rest.

Example 3.20 (Sample rate of a specific string). A memoryless binary source has $p(1) = 0.8$ and $p(0) = 0.2$ . Compute $H(X)$ and the sample information rate of the particular string $x^{10} = 1111011110$ .

Solution. The entropy is

H = -0.8\log 0.8 - 0.2\log 0.2 = 0.8(0.3219) + 0.2(2.3219) = 0.7219 \text{ bits/symbol.}

The string has eight 1s and two 0s, so

p(x^{10}) = 0.8^{8}\,0.2^{2} = (0.16777)(0.04) = 6.711\times10^{-3},

and its sample information rate is

-\frac{1}{10}\log_2\bigl(6.711\times10^{-3}\bigr) = \frac{7.219}{10} = 0.7219 \text{ bits/symbol.}

Sanity check: the string has exactly the expected composition (80% ones), so its rate lands exactly on $H$ . A string with five 1s and five 0s would give $-\frac1{10}\log(0.8^5 0.2^5) = 1.1610$ bits/symbol, far above $H$ — atypical, and correspondingly improbable.□

Pitfall (The AEP is not "all sequences are equally likely"). The AEP says that the logarithm of the probability, divided by $n$ , concentrates. It does not say probabilities are equal: two typical strings of length $1000$ may have probabilities differing by a factor of $2^{20}$ and still both be typical, because $20/1000$ is small. "Equipartition" is a statement about bits per symbol, not about total probability.

Exercises for §3.4 →

3.5The Typical Set and How Big It Is

The AEP is a statement about a limit in probability. To use it we convert it into a statement about a set — the strings whose rate is close to $H(\mathcal X)$ .

Definition 3.21 (Typical set). For $\varepsilon > 0$ and $n \ge 1$ , the typical set $A_\varepsilon^{(n)} \subseteq \mathcal{X}^n$ consists of the strings whose sample information rate is within $\varepsilon$ of the entropy:

A_\varepsilon^{(n)} = \Bigl\{ x^n \in \mathcal{X}^n : \bigl| -\tfrac1n \log p(x^n) - H \bigr| \le \varepsilon \Bigr\},

equivalently the strings with

2^{-n(H+\varepsilon)} \;\le\; p(x^n) \;\le\; 2^{-n(H-\varepsilon)} .

The two displays say the same thing; the second is the form used in every proof, so it is worth memorising. Typicality is defined relative to a source: a string is not typical or atypical in itself, only with respect to a distribution.

Theorem 3.22 (Properties of the typical set). Let $X_1,\dots,X_n$ be i.i.d. $\sim p$ with entropy $H$ . For every $\varepsilon>0$ :

Probability. $\Pr\bigl(X^n \in A_\varepsilon^{(n)}\bigr) > 1-\varepsilon$ for all sufficiently large $n$ .
Upper bound on size. $\bigl|A_\varepsilon^{(n)}\bigr| \le 2^{n(H+\varepsilon)}$ for every $n$ .
Lower bound on size. $\bigl|A_\varepsilon^{(n)}\bigr| \ge (1-\varepsilon)\,2^{n(H-\varepsilon)}$ for all sufficiently large $n$ .

Proof. (1) is a restatement of the AEP: convergence in probability of $-\frac1n\log p(X^n)$ to $H$ means precisely that the probability of the event $\bigl|-\frac1n\log p(X^n) - H\bigr| \le \varepsilon$ exceeds $1-\varepsilon$ once $n$ is large enough.

(2) Every typical string has probability at least $2^{-n(H+\varepsilon)}$ , and probabilities of disjoint outcomes cannot sum past one:

1 \;\ge\; \sum_{x^n \in A_\varepsilon^{(n)}} p(x^n) \;\ge\; \sum_{x^n \in A_\varepsilon^{(n)}} 2^{-n(H+\varepsilon)} \;=\; \bigl|A_\varepsilon^{(n)}\bigr|\,2^{-n(H+\varepsilon)} .

Rearranging gives the bound, and note that it holds for every $n$ , not only for large $n$ .

(3) Run the same computation from the other side. For $n$ large enough that (1) holds,

1-\varepsilon \;<\; \Pr\bigl(A_\varepsilon^{(n)}\bigr) \;=\; \sum_{x^n \in A_\varepsilon^{(n)}} p(x^n) \;\le\; \bigl|A_\varepsilon^{(n)}\bigr|\, 2^{-n(H-\varepsilon)},

using the upper bound $p(x^n) \le 2^{-n(H-\varepsilon)}$ valid on the typical set. Rearranging gives (3).∎

Clauses (2) and (3) pin the size of the typical set between $(1-\varepsilon)2^{n(H-\varepsilon)}$ and $2^{n(H+\varepsilon)}$ : to first order in the exponent, $|A_\varepsilon^{(n)}| \approx 2^{nH}$ . The whole space has $|\mathcal{X}|^n = 2^{n\log|\mathcal{X}|}$ strings, and $H \le \log|\mathcal{X}|$ with equality only for the uniform distribution. So unless the source is uniform, the typical set is an exponentially vanishing fraction of the space that nevertheless captures all but $\varepsilon$ of the probability.

Intuition. Picture the space of all length- $n$ strings as a vast warehouse. The typical set is one small room inside it. Almost every string the source ever emits is found in that room, and the room holds about $2^{nH}$ objects, so a shelf label of $nH$ bits is enough to name any of them.

The rest of the warehouse is enormous but effectively empty: you may ignore it at the cost of an error probability $\varepsilon$ you choose in advance.

Example 3.23 (The typical set of a biased coin). For the source $p(1)=0.9$ , $p(0)=0.1$ with $n=100$ and $\varepsilon=0.05$ , estimate the size of the typical set and its share of the $2^{100}$ binary strings.

Solution. The entropy is

H = -0.9\log 0.9 - 0.1\log 0.1 = 0.9(0.152) + 0.1(3.322) = 0.469 \text{ bits/symbol.}

By clauses (2) and (3), the size lies between roughly $2^{100(0.469-0.05)} = 2^{41.9}$ and $2^{100(0.469+0.05)} = 2^{51.9}$ ; the natural estimate is $2^{nH} = 2^{46.9} \approx 1.3\times10^{14}$ .

The fraction of the space is therefore about

\frac{2^{46.9}}{2^{100}} = 2^{-53.1} \approx 1.1\times 10^{-16}.

Sanity check by direct counting. Typical strings are those with about $90$ ones; the number with exactly $90$ ones is $\binom{100}{90} \approx 1.73\times10^{13} = 2^{44.0}$ , the same order as $2^{46.9}$ once the neighbouring compositions (roughly $86$ to $94$ ones) admitted by the $\varepsilon$ -window are added. The two computations agree, as they must: the AEP for a binary source is the law of large numbers for the number of ones.□

Figure 3.24. Where a biased source actually lands: the composition of a length-100 block from

p(1)=0.9

, concentrated on the strings the typical set collects.

Theorem 3.25 (No smaller high-probability set exists). Fix $\delta < \tfrac12$ and let $B_n \subseteq \mathcal{X}^n$ be any sequence of sets with $\Pr(X^n \in B_n) \ge 1-\delta$ . Then for every $\varepsilon > 0$ and all sufficiently large $n$ ,

\frac1n \log |B_n| \;>\; H - \varepsilon .

No high-probability set can be essentially smaller than the typical set: about $2^{nH}$ strings are needed, whatever shape the set is given.

Proof. Write $A = A_{\varepsilon/2}^{(n)}$ . Since $\Pr(B_n) \ge 1-\delta$ and $\Pr(A) \ge 1-\varepsilon'$ for any prescribed $\varepsilon'$ once $n$ is large, the union bound gives

\Pr(B_n \cap A) \;\ge\; 1 - \delta - \varepsilon' .

Every string in $A$ has $p(x^n) \le 2^{-n(H-\varepsilon/2)}$ , so

1-\delta-\varepsilon' \;\le\; \Pr(B_n \cap A) \;=\!\!\sum_{x^n \in B_n\cap A}\!\! p(x^n) \;\le\; |B_n \cap A|\,2^{-n(H-\varepsilon/2)} \;\le\; |B_n|\,2^{-n(H-\varepsilon/2)} .

Hence $|B_n| \ge (1-\delta-\varepsilon')\,2^{n(H-\varepsilon/2)}$ and

\frac1n\log|B_n| \;\ge\; H - \frac{\varepsilon}{2} + \frac{\log(1-\delta-\varepsilon')}{n} \;>\; H - \varepsilon

for $n$ large, because $\delta < \frac12$ lets us choose $\varepsilon'$ with $1-\delta-\varepsilon' > 0$ , making the last term vanish.∎

This theorem is the reason the typical set is the right object and not merely a convenient one. One might hope to beat it by taking the $2^{nR}$ most probable strings instead, with $R<H$ ; the theorem says any such set has probability tending to zero.

Pitfall (The most probable string is usually atypical). For $p(1)=0.9$ the single most probable string of length $n$ is $111\cdots1$ , with probability $0.9^n = 2^{-0.152n}$ . Its sample information rate is $0.152$ , nowhere near $H = 0.469$ , so it is not typical for small $\varepsilon$ . The typical set is not the set of likely strings; it is the set of strings of likely composition. High-probability sets are assembled from many mid-probability strings, not from the few champions.

Exercises for §3.5 →

3.6Compressing with the Typical Set

We can now build a compressor. It is crude — a lookup table of astronomical size — but it proves that the entropy rate is achievable, and every later algorithm is an attempt to obtain the same rate with feasible resources.

Method 3.26 (Typical-set block code). Fix $\varepsilon>0$ and a block length $n$ . Split $\mathcal{X}^n$ into the typical set $A_\varepsilon^{(n)}$ and its complement, and encode a block $x^n$ as follows.

If $x^n \in A_\varepsilon^{(n)}$ : emit the flag bit $0$ , followed by the index of $x^n$ in a fixed enumeration of $A_\varepsilon^{(n)}$ , written in $\lceil n(H+\varepsilon)\rceil$ bits.
Otherwise: emit the flag bit $1$ , followed by the index of $x^n$ in $\mathcal{X}^n$ , written in $\lceil n\log|\mathcal{X}|\rceil$ bits.

The decoder reads the flag bit and looks the index up in the corresponding table, so the code is lossless — every string is recovered exactly.

The flag bit is what makes the two branches decodable, and it is the price of admitting that atypical strings exist. Note that this scheme never errs: $\varepsilon$ appears in the length, not in a failure probability.

Theorem 3.27 (Expected length of the typical-set code). Let $\ell(X^n)$ be the length in bits produced by the typical-set block code. For every $\varepsilon'>0$ there is an $n_0$ such that for all $n > n_0$ ,

E\!\left[\frac{1}{n}\,\ell(X^n)\right] \;\le\; H + \varepsilon' .

Proof. Split the expectation over the two branches. On the typical set the length is at most $n(H+\varepsilon)+2$ (one flag bit and at most one bit lost to the ceiling); on the complement it is at most $n\log|\mathcal{X}| + 2$ . Therefore

E[\ell(X^n)] \;\le\; \Pr\!\bigl(A_\varepsilon^{(n)}\bigr)\bigl(n(H+\varepsilon)+2\bigr) + \Pr\!\bigl(\overline{A_\varepsilon^{(n)}}\bigr)\bigl(n\log|\mathcal{X}|+2\bigr).

Bounding the first probability by $1$ and, for large $n$ , the second by $\varepsilon$ ,

E\!\left[\frac1n \ell(X^n)\right] \;\le\; H + \varepsilon + \varepsilon\log|\mathcal{X}| + \frac2n \;=\; H + \varepsilon\bigl(1+\log|\mathcal{X}|\bigr) + \frac2n .

Given $\varepsilon'>0$ , choose $\varepsilon = \varepsilon'/\bigl(2(1+\log|\mathcal{X}|)\bigr)$ and then $n_0 > 4/\varepsilon'$ ; for $n>n_0$ the right-hand side is at most $H+\varepsilon'$ .∎

Corollary 3.28 (Entropy is an achievable description length). For any source satisfying the AEP with entropy rate $H(\mathcal X)$ , and any $\varepsilon>0$ , there exist lossless codes with expected description length at most $H(\mathcal X)+\varepsilon$ bits per symbol for all sufficiently large block lengths.

The corollary is the achievability half of the source coding theorem, obtained before the theorem is even stated. What the next part adds is precision about what kind of code is allowed, and a matching converse.

Intuition. The compressor is a phone book. All the ordinary strings are listed in it, and to send one you send its page-and-line number. The occasional bizarre string is not in the book, so you prefix it with "not in the book" and spell it out in full.

Spelling out is expensive, but you do it so rarely that on average it costs nothing.

Example 3.29 (Rate of a typical-set code for a video frame). A residual video frame of $1920\times1080$ pixels is modelled as an i.i.d. source over a $256$ -level alphabet with $H = 0.8$ bits per pixel. Compare the raw size, the typical branch, and the average overhead of the atypical branch if $\Pr(\text{atypical}) = 10^{-3}$ .

Solution. There are $n = 1920 \times 1080 = 2{,}073{,}600$ pixels.

Raw. At $\log 256 = 8$ bits per pixel: $8n = 16{,}588{,}800$ bits $\approx 2.07$ MB.

Typical branch. $n(H+\varepsilon)$ with $\varepsilon$ negligible at this $n$ : $0.8n = 1{,}658{,}880$ bits $\approx 207$ kB — a ratio of $8/0.8 = 10{:}1$ .

Atypical branch. It costs $8n$ bits but occurs with probability $10^{-3}$ , contributing $10^{-3}\times 8 = 0.008$ bits per pixel to the average — one percent of the $0.8$ -bit budget.

Average rate: $0.999(0.8) + 0.001(8) = 0.8072$ bits per pixel.

Sanity check: the average exceeds $H$ by $0.0072$ bits per pixel, consistent with the $\varepsilon(1+\log|\mathcal{X}|)$ overhead term in the proof above with $\varepsilon = 10^{-3}$ , namely $10^{-3}(1+8) = 0.009$ — the right order. The typical-set bound is not a fiction; it is what the arithmetic actually gives.□

Remark (Why this code is never built). The table $A_\varepsilon^{(n)}$ has about $2^{nH}$ entries. For the frame above that is $2^{1658880}$ entries — more than the number of atoms in any number of universes. The typical-set code is an existence argument. The rest of this chapter is about obtaining the same rate with an algorithm that runs in linear time and constant memory; remarkably, this turns out to be possible.

Exercises for §3.6 →

Common Mistakes

Using the single-symbol entropy for a source with memory. It overestimates the true cost; the entropy rate is the correct number and is strictly smaller unless the source is i.i.d.
Assuming the rate always exists. Stationarity is what guarantees it. A non-stationary process can have $\tfrac1nH(X_{1:n})$ oscillating forever.
Confusing the entropy rate with the entropy of the stationary distribution. $H(\mu)$ ignores the transitions and is only an upper bound.
**Believing $H(X_n\mid X_{1:n-1})$ can increase.** For a stationary process it is non-increasing in $n$ — that is Lemma *The conditional entropies decrease*, and it is what makes the limit exist. (Both $H(X_n|X_{1:n-1})$ and $\tfrac1nH(X_{1:n})$ are non-increasing, and the first is below the second.)
Reading the AEP as "all long sequences are equally likely". It says the *log-probabilities per symbol* concentrate. Two typical sequences can still differ in probability by a factor of $2^{n\varepsilon}$ .
Carrying discrete intuitions into differential entropy. $h$ can be negative, changes under scaling, and is not a description length.
**Thinking every sequence has probability exactly $2^{-nh}$ . ** Only typical ones have probability close to that *on the exponential scale*, and even they vary by subexponential factors. Atypical strings can be far more or far less likely.
Confusing the size of the typical set with the size of the support. The support is usually all of $\mathcal{X}^n$ ; the typical set is the exponentially smaller subset of size about $2^{nH}$ .
Dropping the ergodicity or stationarity hypothesis. Without it the entropy rate may not exist, and the concentration in the AEP can fail outright.
**Treating the AEP as exact at finite $n$ . ** It is asymptotic. For short blocks the atypical branch is not negligible and one needs explicit finite- $n$ bounds (Chebyshev, or a Chernoff bound).
Confusing the AEP with the central limit theorem. Both concern $\frac1n\sum_i(-\log p(X_i))$ , but the AEP is a law of large numbers (the mean converges); the CLT describes the $\sqrt n$ -scale fluctuations around it, which govern finite-blocklength corrections.
Assuming typicality is a property of a string. It is a property of a string *and* a distribution. The all-ones string is typical for $p(1)=1-1/n$ and wildly atypical for a fair coin.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← Mutual Information and Relative Entropy Source Coding and the Entropy Bound →

Helpful?