Back to the on-screen lesson · Print

Entropy rate

H(X) = lim H(Xⁿ)/n = lim H(Xₙ | past) for stationary sources; Markov chains.

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 define the entropy rate of a stationary source, prove that its two natural definitions agree, explain why memory can only lower it, and compute it for i.i.d. sources and for stationary Markov chains as the stationary average of the row entropies. You will run arithmetic coding by hand on a short message, find the interval it produces and the number of bits it needs, and explain why its overhead is two bits per message rather than up to one bit per symbol, which is how practical compressors reach the entropy rate without grouping symbols into blocks.

2. Entropy rate

For a source with memory the per-symbol information is the entropy rate $$H(\mathcal{X}) = \lim_{n \to \infty} \frac{H(X_1, \ldots, X_n)}{n},$$ and for a stationary source this equals $\lim_n H(X_n \mid X_1, \ldots, X_{n-1})$: the conditional entropies decrease (conditioning on a longer past reduces entropy, and stationarity keeps the comparison fair), so they converge, and $H(X^n)/n$ is their running average by the chain rule. Memory can only lower the rate: $H(\mathcal{X}) \le H(X_1)$, with equality for i.i.d. sources. For a stationary Markov chain with transition matrix $P$ and stationary distribution $\pi$, the rate is $H(X_2 \mid X_1) = \sum_i \pi_i H(P_{i\cdot})$, the average row entropy; a symmetric binary chain that switches with probability $p$ has rate $h(p)$. The AEP and the source coding theorem hold with $H(\mathcal{X})$ in place of $H$ for stationary ergodic sources, so English text compresses to its entropy rate, about one bit per letter, not to the $4.1$ bits of its letter frequencies.

3. Two definitions, one number

For a source with memory, 'bits per symbol' needs care: the first symbol may be more surprising than the thousandth. Two limits offer themselves, $$H(\mathcal{X}) = \lim_n \frac{H(X_1, \ldots, X_n)}{n} \quad \text{and} \quad H'(\mathcal{X}) = \lim_n H(X_n \mid X_1, \ldots, X_{n-1}),$$ and for a stationary source they agree. Why: the conditional entropies decrease, because conditioning on more reduces entropy and stationarity lets us shift the window, $H(X_n \mid X^{n-1}) \le H(X_n \mid X_2^{n-1}) = H(X_{n-1} \mid X^{n-2})$. A decreasing sequence bounded below converges. By the chain rule $H(X^n)/n$ is the running average of exactly that sequence, and the average of a convergent sequence converges to the same limit (Cesàro).

The consequence to remember: memory can only lower the rate, $H(\mathcal{X}) \le H(X_1)$, with equality exactly for i.i.d. sources. English has about $4.1$ bits per letter if you ignore context and roughly $1$ bit per letter if you use it — the difference is what a compressor lives on.

4. Markov chains: the rate is a weighted average of row entropies

For a stationary Markov chain the past matters only through the current state, so $H(X_n \mid X^{n-1}) = H(X_2 \mid X_1)$ for every $n$ and the limit is reached immediately: $$H(\mathcal{X}) = H(X_2 \mid X_1) = \sum_i \pi_i H(P_{i\cdot}),$$ the entropy of each row of the transition matrix, averaged with the stationary distribution $\pi$.

Row two is the one the practice uses: a binary chain that stays with probability $q$ and switches with probability $p = 1 - q$ is symmetric, so $\pi = (\tfrac{1}{2}, \tfrac{1}{2})$, both rows have entropy $h(p)$, and the rate is simply $h(p)$ — even though each symbol on its own is a fair bit with entropy $1$. Memory has cut the rate by more than half.

5. Solving the practice problems

1. Binary chain that stays with probability $q$: the rate is $h(1 - q) = h(p)$; read it from the table of lesson 1.
2. Two states with $\pi = (\tfrac{1}{2}, \tfrac{1}{2})$ and row entropies $a/4$ and $b/4$: average them, $\tfrac{1}{2}(a/4) + \tfrac{1}{2}(b/4)$.
3. An i.i.d. source: $H(X^n) = nH(X_1)$ and the rate is $H(X_1)$ itself; the block length is a distraction.
4. Which statement is correct: the rate is at most $H(X_1)$, and the two limit definitions agree for a stationary source.

Common mistakes

• Using $h(q)$ instead of $h(p)$ — though since $h(q) = h(1 - q)$ they agree here, the habit fails for asymmetric chains.
• Reporting $H(X_1) = 1$ for a sticky chain: each symbol is a fair bit, but the rate is lower.
• Multiplying by $n$: the rate is per symbol, and $H(X^n)$ is the whole block.

6. A sticky binary chain

1. The chain repeats its symbol with probability $0.9$ and switches with probability $0.1$; by symmetry $\pi = (\tfrac{1}{2}, \tfrac{1}{2})$.

   Stationary distribution first.

2. Each row has entropy $h(0.1) = 0.469$, so the rate is $0.469$ bits per symbol, though each symbol alone is a fair bit with $H(X_1) = 1$.

   Memory halves the information.

7. Why the two limits agree

1. $H(X_n \mid X^{n-1}) \le H(X_n \mid X_2^{n-1}) = H(X_{n-1} \mid X^{n-2})$: conditioning on less, then shifting by stationarity.

   A nonincreasing sequence bounded below converges.

2. $H(X^n)/n = \tfrac{1}{n} \sum_{i=1}^n H(X_i \mid X^{i-1})$, the average of a convergent sequence, converges to the same limit.

   Chain rule plus Cesàro.

8. A chain that stays with probability $0.8$

1. Switching probability $p = 0.2$; by symmetry $\pi = (\tfrac{1}{2}, \tfrac{1}{2})$.

2. Each row of the transition matrix is $(0.8, 0.2)$, with entropy $h(0.2) = 0.722$.

3. Rate $= 0.5 \cdot 0.722 + 0.5 \cdot 0.722 = 0.722$ bits per symbol, against $H(X_1) = 1$.

   Predicting from the previous symbol saves $0.278$ bits each time.

9. Averaging unequal rows

1. $\pi = (\tfrac{1}{2}, \tfrac{1}{2})$; from state $0$ the next symbol has entropy $0.5$ bits, from state $1$ it has $1$ bit.

2. Rate $= \tfrac{1}{2} \cdot 0.5 + \tfrac{1}{2} \cdot 1 = 0.75$ bits per symbol.

   Weight by how often the chain visits each state, not by the number of states.

3. Sanity check: the rate lies between the smallest row entropy $0.5$ and the largest $1$.

10. Your turn: a chain with $\pi = (\tfrac{1}{2}, \tfrac{1}{2})$, row entropies $0.5$ and $1$

1. Rate $= \tfrac{1}{2} \cdot 0.5 + \tfrac{1}{2} \cdot 1$.

2. Your turn: work this step out. Its working is at the end of the packet.

   $0.75$ bits per symbol.

11. Guided practice

A binary Markov chain stays in its current state with probability $0.6$ and switches with probability $0.4$. What is its entropy rate in bits per symbol, to three decimal places?

Computed value: _answer

12. Guided practice

A stationary two-state Markov chain has stationary distribution $(\tfrac{1}{2}, \tfrac{1}{2})$; from state $0$ the next symbol has entropy $2/4$ bits and from state $1$ it has entropy $4/4$ bits. What is the entropy rate?

Computed value: _answer

13. Practice

An i.i.d. source has $H(X_1) = 5/2$ bits. What is $H(X_1, \ldots, X_{40})$, and hence the entropy rate? Enter the entropy rate.

Computed value: _answer

14. Practice

A binary Markov chain stays in its current state with probability $0.95$ and switches with probability $0.05$. What is its entropy rate in bits per symbol, to three decimal places?

Computed value: _answer

15. Somewhere new

For a stationary source, which statement about the entropy rate is correct?

• $\lim H(X^n)/n$ and $\lim H(X_n \mid X^{n-1})$ both exist and are equal, and are at most $H(X_1)$
• The entropy rate always equals $H(X_1)$
• $H(X_n \mid X^{n-1})$ grows with $n$ because the past grows
• The entropy rate is $H(X^n)$ for any fixed $n$

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 stationary two-state Markov chain has stationary distribution $(\tfrac{1}{2}, \tfrac{1}{2})$; from state $0$ the next symbol has entropy $4/4$ bits and from state $1$ it has entropy $2/4$ bits. What is the entropy rate?

Computed value: _answer

18. What you can do now

You can find the entropy rate of a source with memory and code a message to within two bits of its information. This closes source coding; the next unit turns to noisy channels.

Working for the steps left to you

10. Your turn: a chain with $\pi = (\tfrac{1}{2}, \tfrac{1}{2})$, row entropies $0.5$ and $1$, step 2