46.01.05 · information-theory / information-measures

Entropy Rates of Stationary Processes and the Entropy of Markov Chains

shipped3 tiersLean: none

Anchor (Master): Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §4.1-4.5; Shannon 1948 A Mathematical Theory of Communication §7; Kieffer 1974 On the Inverse Problem for Entropy Rates of Stationary Processes

Intuition Beginner

Imagine recording the weather every day for a year. Each day is sunny, cloudy, or rainy. If every day's weather were independent of the previous day, the total information in 365 days would just be 365 times the entropy of a single day. But weather is not independent — today's weather depends heavily on yesterday's. When outcomes depend on each other, there is less total information in a sequence than you would get by treating each observation as independent.

The entropy rate measures the average information per symbol in a long sequence of dependent observations. It answers: if you have already observed a million days of weather, how much new information does the next day bring? That new information is the entropy rate. For independent draws it equals the single-symbol entropy. For dependent draws it is strictly less, because the past already tells you something about the future.

A Markov chain is the simplest model of dependence: tomorrow's state depends only on today's state, not on any earlier history. For a Markov chain, the entropy rate has a clean formula. You average the uncertainty of the next step over the long-run proportion of time spent in each state. If a weather chain spends 60 percent of days sunny, 25 percent cloudy, and 15 percent rainy, the entropy rate is 0.6 times the entropy of "tomorrow given today is sunny" plus 0.25 times the entropy of "tomorrow given today is cloudy" plus 0.15 times the entropy of "tomorrow given today is rainy."

Why does this matter? The entropy rate tells you the compression limit for correlated data. English text has an entropy rate of about 1 to 1.5 bits per character, far below the 4.7 bits you would get from treating each character independently. The gap comes from the fact that letters strongly predict their successors. The entropy rate captures exactly how predictable a source is, and no compression scheme can beat it.

Visual Beginner

Figure: a two-state Markov chain with states A and B. State A has a self-loop with probability 0.8 and an arrow to B with probability 0.2. State B has a self-loop with probability 0.6 and an arrow to A with probability 0.4. Below the diagram: the stationary distribution is $μ_{A} = 2/3$ , $μ_{B} = 1/3$ . The entropy rate is $H \approx 0.722$ bits per symbol.

Source type	Entropy rate (bits/symbol)	Intuition
Fair coin (independent)	1.00	Each flip gives one full bit
Loaded coin 90/10 (independent)	0.47	Each flip is somewhat predictable
Two-state Markov (sticky)	0.72	Past reduces uncertainty in the next symbol
Two-state Markov (nearly independent)	0.99	Weak dependence, rate close to single-symbol entropy
English text (estimated)	1.0-1.5	Letters strongly predict successors
Deterministic chain	0.00	The next state is fully known

The pattern: dependence between symbols reduces the entropy rate below the single-symbol entropy. The stronger the dependence, the larger the gap.

Worked example Beginner

Consider a two-state Markov chain for weather. State S (sunny) and state R (rainy). The transition probabilities are: if today is sunny, tomorrow is sunny with probability 0.7 and rainy with probability 0.3. If today is rainy, tomorrow is rainy with probability 0.6 and sunny with probability 0.4.

Step 1. Find the stationary distribution. The stationary distribution $μ$ satisfies $μ P = μ$ . Let $μ_{S} = s$ and $μ_{R} = 1 - s$ .

s = 0.7 s + 0.4 (1 - s) = 0.7 s + 0.4 - 0.4 s = 0.3 s + 0.4.

Solving: $0.7 s = 0.4$ , so $s = 4/7 \approx 0.571$ and $μ_{R} = 3/7 \approx 0.429$ .

Step 2. Compute the conditional entropy for each state. Given state S, the next state has distribution $(0.7, 0.3)$ , so:

H (X_{2} ∣ X_{1} = S) = - 0.7 lo g_{2} 0.7 - 0.3 lo g_{2} 0.3 \approx 0.360 + 0.521 = 0.881 bits .

Given state R, the next state has distribution $(0.4, 0.6)$ , so:

H (X_{2} ∣ X_{1} = R) = - 0.4 lo g_{2} 0.4 - 0.6 lo g_{2} 0.6 \approx 0.529 + 0.442 = 0.971 bits .

Step 3. Average over the stationary distribution:

H = \frac{4}{7} \times 0.881 + \frac{3}{7} \times 0.971 \approx 0.503 + 0.416 = 0.919 bits per symbol .

What this tells us. Each new day's weather adds about 0.92 bits of information, given that you already know today's weather. Over 365 days, the total information is roughly $365 \times 0.919 \approx 335$ bits. Compare this to 365 independent draws from the stationary distribution $(4/7, 3/7)$ , which would give $365 \times H (4/7) = 365 \times 0.985 \approx 360$ bits. The Markov dependence saves about 25 bits over a year, because knowing yesterday's weather partially predicts today's.

Check your understanding Beginner

Formal definition Intermediate+

Let ${X_{n}}_{n = 1}^{\infty}$ be a discrete-time stochastic process taking values in a finite alphabet $X$ .

Definition (Entropy rate). The entropy rate of a stochastic process is

H (X) = n \to \infty lim \frac{1}{n} H (X_{1}, X_{2}, \dots, X_{n}),

provided the limit exists, where $H (X_{1}, \dots, X_{n})$ is the joint Shannon entropy of the first $n$ symbols.

Theorem (Existence for stationary processes). If the process is stationary, then $H (X)$ exists and equals

H (X) = n \to \infty lim H (X_{n} ∣ X_{n - 1}, X_{n - 2}, \dots, X_{1}) .

Proof sketch. Stationarity implies that the sequence of conditional entropies $a_{n} = H (X_{n} ∣ X_{n - 1}, \dots, X_{1})$ is non-increasing: conditioning on more variables reduces (or preserves) entropy, so $H (X_{n + 1} ∣ X^{n}) \leq H (X_{n} ∣ X^{n - 1})$ . Since $a_{n} \geq 0$ , the sequence converges to some limit $H$ . By the chain rule, $H (X_{1}, \dots, X_{n}) = \sum_{i = 1}^{n} H (X_{i} ∣ X^{i - 1})$ . By the Cesaro mean theorem, the average of a convergent sequence converges to the same limit: $(1/ n) \sum_{i = 1}^{n} a_{i} \to H$ . Hence both limits exist and are equal.

Definition (Entropy rate of a stationary Markov chain). For a stationary Markov chain with state space $X$ , transition matrix $P = (P_{ij})$ , and stationary distribution $μ = (μ_{i})$ , the entropy rate is

H (X) = i \in X \sum μ_{i} H (X_{2} ∣ X_{1} = i) = - i \in X \sum j \in X \sum μ_{i} P_{ij} lo g_{2} P_{ij} .

This follows because for a first-order Markov chain, $H (X_{n} ∣ X_{n - 1}, \dots, X_{1}) = H (X_{n} ∣ X_{n - 1})$ , so the conditional entropy does not decrease after the first step, and the entropy rate equals $H (X_{2} ∣ X_{1}) = \sum_{i} μ_{i} H (X_{2} ∣ X_{1} = i)$ when the chain is in its stationary regime.

Counterexamples to common slips

Entropy rate is not $H (X_{1})$ . For a process with dependence, the entropy rate is the average new information per symbol given the entire past. It is always at most $H (X_{1})$ and equals it only when symbols are independent.
The limit may not exist for non-stationary processes. A process whose statistics drift over time (e.g., a source that becomes more random) need not have a well-defined entropy rate. Stationarity is what guarantees the limit exists.
A Markov chain must be in stationarity. The formula $H = - \sum_{i, j} μ_{i} P_{ij} lo g P_{ij}$ applies when the chain is started from (or has converged to) its stationary distribution $μ$ . If you start from a different initial distribution, the per-symbol entropy converges to this rate as $n \to \infty$ , but the finite- $n$ averages may differ.

Key theorem with proof Intermediate+

Theorem (Entropy rate of a stationary Markov chain). Let ${X_{n}}$ be a stationary first-order Markov chain with transition matrix $P$ and stationary distribution $μ$ . Then

H (X) = - i, j \sum μ_{i} P_{ij} lo g_{2} P_{ij} .

Proof. For a first-order Markov chain, the conditional entropy satisfies $H (X_{n} ∣ X_{n - 1}, \dots, X_{1}) = H (X_{n} ∣ X_{n - 1})$ by the Markov property. By stationarity, $H (X_{n} ∣ X_{n - 1}) = H (X_{2} ∣ X_{1})$ for all $n \geq 2$ . Therefore

H (X) = n \to \infty lim H (X_{n} ∣ X_{n - 1}, \dots, X_{1}) = H (X_{2} ∣ X_{1}) .

Expanding the conditional entropy:

H (X_{2} ∣ X_{1}) = i \sum Pr (X_{1} = i) H (X_{2} ∣ X_{1} = i) = i \sum μ_{i} (- j \sum P_{ij} lo g_{2} P_{ij}) = - i, j \sum μ_{i} P_{ij} lo g_{2} P_{ij} . □

Bridge. The entropy rate formula $H = - \sum_{i, j} μ_{i} P_{ij} lo g P_{ij}$ is the load-bearing identity that connects the probabilistic structure of a Markov source to the information-theoretic compression limit. It builds toward the AEP for stationary ergodic sources 46.02.01 by establishing that the per-symbol entropy converges to a fixed constant, which becomes the exponent governing the typical set size. It appears again in the channel coding theorem 46.03.01 as the information rate that a channel can sustain, the foundational reason why Markov structure simplifies the capacity calculation. The formula generalises to hidden Markov models and processes with countable alphabets, and is dual to the thermodynamic entropy production rate in statistical mechanics, the central insight being that the entropy rate is the unique time-averaged information measure that is both operationally meaningful (compression limit) and mathematically well-behaved (Cesaro convergence) for any stationary source.

Exercises Intermediate+

Exercise (medium, numeric).

Let ${X_{n}}$ be a second-order stationary Markov chain on ${0, 1}$ where $X_{n}$ depends on $(X_{n - 1}, X_{n - 2})$ . The chain has four "super-states" $(0, 0), (0, 1), (1, 0), (1, 1)$ with transition probabilities given by: from $(a, b)$ , the next state is $(b, 0)$ with probability $p$ and $(b, 1)$ with probability $1 - p$ , where $p = 0.7$ . Compute the entropy rate.

Hint

This is a first-order Markov chain on the four super-states. Find the stationary distribution of the super-state chain, then compute the entropy rate from the super-state transition probabilities.

Answer

The super-state transition matrix is $4 \times 4$ . From $(0, 0)$ : to $(0, 0)$ with prob 0.7, to $(0, 1)$ with prob 0.3. From $(0, 1)$ : to $(1, 0)$ with prob 0.7, to $(1, 1)$ with prob 0.3. From $(1, 0)$ : to $(0, 0)$ with prob 0.7, to $(0, 1)$ with prob 0.3. From $(1, 1)$ : to $(1, 0)$ with prob 0.7, to $(1, 1)$ with prob 0.3.

By symmetry, the pairs $(0, 0)$ and $(1, 1)$ have equal stationary probability, as do $(0, 1)$ and $(1, 0)$ . Solving: $μ_{(0, 0)} = μ_{(1, 1)} = 7/20$ and $μ_{(0, 1)} = μ_{(1, 0)} = 3/20$ . Each super-state has the same conditional entropy: $H_{b} (0.7) = - 0.7 lo g_{2} 0.7 - 0.3 lo g_{2} 0.3 \approx 0.881$ bits. The entropy rate is $H = 0.881$ bits per symbol. (Each super-state produces exactly one new symbol, so the entropy rate equals the super-state conditional entropy.)

Exercise (hard, short answer).

Prove that for a stationary process, the sequence $a_{n} = H (X_{n} ∣ X_{n - 1}, \dots, X_{1})$ is non-increasing: $a_{n + 1} \leq a_{n}$ for all $n \geq 1$ .

Hint

Use the chain rule to expand $H (X_{n + 1} ∣ X^{n})$ and $H (X_{n} ∣ X^{n - 1})$ , then apply conditioning reduces entropy to a suitable pair of variables.

Answer

By stationarity, the joint distribution of $(X_{1}, \dots, X_{n + 1})$ is the same as that of $(X_{2}, \dots, X_{n + 2})$ shifted by one. Therefore $a_{n} = H (X_{n} ∣ X_{n - 1}, \dots, X_{1}) = H (X_{n + 1} ∣ X_{n}, \dots, X_{2})$ . Now:

a_{n + 1} = H (X_{n + 1} ∣ X_{n}, \dots, X_{1}) \leq H (X_{n + 1} ∣ X_{n}, \dots, X_{2}) = a_{n},

where the inequality follows because conditioning on strictly more variables (adding $X_{1}$ to the conditioning set) can only reduce or preserve entropy. Since $a_{n}$ is non-negative and non-increasing, it converges.

Exercise (hard, short answer).

Let ${X_{n}}$ be a stationary Markov chain with entropy rate $H (X)$ and let $Y_{n} = f (X_{n})$ for a deterministic function $f$ . Show that the entropy rate of ${Y_{n}}$ satisfies $H (Y) \leq H (X)$ .

Hint

Use the data-processing inequality for entropy: $H (Y_{1}, \dots, Y_{n}) \leq H (X_{1}, \dots, X_{n})$ because $(Y_{1}, \dots, Y_{n})$ is a function of $(X_{1}, \dots, X_{n})$ . Then divide by $n$ and take limits.

Answer

Since $Y_{i} = f (X_{i})$ , the vector $(Y_{1}, \dots, Y_{n})$ is a deterministic function of $(X_{1}, \dots, X_{n})$ . By the property that processing cannot increase entropy, $H (Y_{1}, \dots, Y_{n}) \leq H (X_{1}, \dots, X_{n})$ . Dividing by $n$ :

\frac{1}{n} H (Y_{1}, \dots, Y_{n}) \leq \frac{1}{n} H (X_{1}, \dots, X_{n}) .

Taking $n \to \infty$ , both limits exist (both processes are stationary), giving $H (Y) \leq H (X)$ . Equality holds iff $f$ is injective on the support of the stationary distribution.

Exercise (hard, short answer).

For a stationary irreducible aperiodic Markov chain with transition matrix $P$ and stationary distribution $μ$ , show that the entropy rate can be written as $H (X) = H (X_{2}) - I (X_{1}; X_{2})$ , where $I (X_{1}; X_{2})$ is the mutual information between consecutive symbols.

Hint

Use the identity $H (X_{2} ∣ X_{1}) = H (X_{2}) - I (X_{1}; X_{2})$ and the fact that the entropy rate equals $H (X_{2} ∣ X_{1})$ for a stationary Markov chain.

Answer

By definition, $I (X_{1}; X_{2}) = H (X_{2}) - H (X_{2} ∣ X_{1})$ , so $H (X_{2} ∣ X_{1}) = H (X_{2}) - I (X_{1}; X_{2})$ . For a stationary Markov chain, $H (X) = H (X_{2} ∣ X_{1})$ (the entropy rate equals the one-step conditional entropy). Substituting gives $H (X) = H (X_{2}) - I (X_{1}; X_{2})$ . This decomposition says the entropy rate is the marginal entropy minus the information that one symbol carries about the next. The stronger the dependence (larger $I$ ), the lower the rate.

Exercise (hard, short answer).

Let ${X_{n}}$ be i.i.d. Bernoulli(1/2) and define $Y_{n} = X_{n} \oplus X_{n - 1}$ (binary XOR). Show that ${Y_{n}}$ is a stationary Markov chain and compute its entropy rate. Compare with $H (Y_{n})$ for a single symbol.

Hint

$Y_{n}$ depends on $X_{n}$ and $X_{n - 1}$ . Since $X_{n}$ is independent of the past, $Y_{n}$ depends on $Y_{n - 1}$ only through $X_{n - 1}$ . Work out the transition probabilities for ${Y_{n}}$ .

Answer

Since $X_{n}$ is independent of $X_{n - 1}$ and each is Bernoulli(1/2), $Y_{n}$ is Bernoulli(1/2) marginally. Given $Y_{n - 1} = y$ , we know $X_{n - 1} \oplus X_{n - 2} = y$ , but $X_{n}$ is independent of everything past. Since $Y_{n} = X_{n} \oplus X_{n - 1}$ and $X_{n}$ is fresh Bernoulli(1/2) independent of $X_{n - 1}$ , we have $Pr (Y_{n} = 1∣ X_{n - 1} = a) = 1/2$ regardless of $a$ . So $Pr (Y_{n} = 1∣ Y_{n - 1}) = 1/2$ . The process ${Y_{n}}$ is actually i.i.d. Bernoulli(1/2) with entropy rate $H = 1$ bit. Here $H (Y) = H (Y_{n}) = 1$ bit, and the Markov structure collapses to independence because XOR with a fresh fair coin erases all dependence.

Lean formalization Intermediate+

Mathlib does not define the entropy rate for stochastic processes. The components exist in isolation — ProbabilityTheory.Stationary for stationary distributions, PMF for probability mass functions, and basic entropy is absent entirely — but there is no functional $H (X) = lim_{n \to \infty} (1/ n) H (X_{1}, \dots, X_{n})$ defined on the space of stationary processes. The proof that $a_{n} = H (X_{n} ∣ X^{n - 1})$ is non-increasing relies on the conditioning-reduces-entropy inequality, which itself is unformalised. The specialization to Markov chains, where $H (X) = - \sum_{i, j} μ_{i} P_{ij} lo g P_{ij}$ , requires the Markov property $H (X_{n} ∣ X^{n - 1}) = H (X_{n} ∣ X_{n - 1})$ and the Cesaro mean convergence argument, neither of which exist in Mathlib. A Codex.InformationTheory.EntropyRate module defining the entropy rate on stationary processes and proving the Markov chain formula from the Cesaro convergence theorem would be the load-bearing first step; this unit ships without it.

Advanced results Master

The second law of thermodynamics for Markov chains

The entropy rate has a thermodynamic interpretation. For a Markov chain with transition matrix $P$ , define the conditional entropy of the transition from state $i$ as $h_{i} = - \sum_{j} P_{ij} lo g P_{ij}$ . The entropy rate is the stationary average $H = \sum_{i} μ_{i} h_{i}$ .

If the chain is not started from the stationary distribution but from some initial distribution $ν$ , the per-symbol entropy at time $n$ is

H_{n} = H (X_{n + 1} ∣ X_{n}) = i \sum ν_{n} (i) h_{i},

where $ν_{n} = ν P^{n}$ is the distribution at time $n$ . The second-law interpretation says that for an irreducible aperiodic chain, $ν_{n} \to μ$ and therefore $H_{n} \to H$ . The entropy production rate converges to the stationary entropy rate.

More precisely, the conditional entropy $H (X_{n + 1} ∣ X_{n})$ increases monotonically if the chain is doubly stochastic (because the uniform distribution is stationary and the entropy under a doubly stochastic map increases), but this monotonicity does not hold in general. What does hold is the Cesaro convergence: the time-averaged entropy $(1/ N) \sum_{n = 1}^{N} H_{n} \to H$ .

Functions of Markov chains and hidden Markov models

If ${X_{n}}$ is a Markov chain and $Y_{n} = f (X_{n})$ for a function $f$ that is not injective, then ${Y_{n}}$ is generally not a Markov chain. The process ${Y_{n}}$ is a hidden Markov model (or function of a Markov chain). Its entropy rate satisfies $H (Y) \leq H (X)$ by the data-processing argument in Exercise 7.

Computing $H (Y)$ exactly is substantially harder than for the underlying Markov chain. The conditional entropy $H (Y_{n} ∣ Y_{n - 1}, \dots, Y_{1})$ does not stabilize at a fixed finite memory length, because ${Y_{n}}$ has infinite-order dependence in general. Blackwell showed in 1957 that the entropy rate can be computed via a recursive update on the space of posterior distributions over the hidden state, but this space is continuous and the computation is generally intractable except for small state spaces.

Entropy rate and the Shannon-McMillan-Breiman theorem

For a stationary ergodic process, the Shannon-McMillan-Breiman theorem (the ergodic theorem for entropy) strengthens the AEP. It states that the normalized log-probability converges almost surely:

- \frac{1}{n} lo g_{2} p (X_{1}, \dots, X_{n}) \to H (X) a.s.

This is stronger than the convergence in probability given by the AEP. The proof uses the martingale convergence theorem applied to the conditional probabilities $p (X_{n} ∣ X_{n - 1}, \dots, X_{1})$ . For a stationary ergodic Markov chain, the result follows from the ergodic theorem applied to the function $f (i) = h_{i} = - \sum_{j} P_{ij} lo g P_{ij}$ , giving

\frac{1}{n} k = 1 \sum n h_{X_{k}} \to i \sum μ_{i} h_{i} = H (X) a.s.

The time average of the per-state conditional entropies converges to the stationary average almost surely.

Entropy rate as a variational quantity

The entropy rate can be expressed as the solution to an optimization problem. For a stationary process on alphabet $X$ , the entropy rate is the infimum of $(1/ n) H (X_{1}, \dots, X_{n})$ over all $n$ , because the sequence $(1/ n) H (X_{1}, \dots, X_{n})$ converges to $H (X)$ from above (the Cesaro mean of a non-increasing sequence converges from above). Equivalently, for any $n$ :

H (X) \leq \frac{1}{n} H (X_{1}, \dots, X_{n}),

and the bound tightens as $n$ grows. This means that block-coding at block length $n$ achieves a compression rate at most $(1/ n) H (X_{1}, \dots, X_{n})$ , which approaches the entropy rate in the limit. The rate of convergence is governed by the information covariance $\sum_{k = 1}^{n} I (X_{1}; X_{k + 1})$ , which measures the total long-range dependence.

Synthesis. The entropy rate is the unique time-averaged information measure that is both operationally meaningful (the compression limit for stationary sources) and mathematically well-behaved (Cesaro convergence of conditional entropies); for Markov chains it reduces to the stationary average $H = - \sum_{i, j} μ_{i} P_{ij} lo g P_{ij}$ , a weighted sum of per-state conditional entropies; the second-law interpretation says that a non-stationary start converges to the stationary entropy rate as the chain mixes, the central insight being that the entropy rate captures the irreducible uncertainty per symbol that no amount of knowledge of the past can eliminate; this generalises to hidden Markov models and general stationary ergodic processes via the Shannon-McMillan-Breiman theorem, putting these together the entropy rate becomes the fundamental limit for source coding, channel capacity, and rate-distortion in the correlated-source setting.

Full proof set Master

Proposition (Conditional entropy decreases to the entropy rate). Let ${X_{n}}$ be a stationary process. Then $a_{n} = H (X_{n} ∣ X_{n - 1}, \dots, X_{1})$ is non-increasing, $a_{n} \geq H (X)$ for all $n$ , and $a_{n} \to H (X)$ as $n \to \infty$ .

Proof. We show $a_{n + 1} \leq a_{n}$ . By stationarity, the joint distribution of $(X_{1}, \dots, X_{n})$ equals that of $(X_{2}, \dots, X_{n + 1})$ . Therefore

a_{n} = H (X_{n} ∣ X_{n - 1}, \dots, X_{1}) = H (X_{n + 1} ∣ X_{n}, \dots, X_{2}) .

Now compare:

a_{n + 1} = H (X_{n + 1} ∣ X_{n}, \dots, X_{1}) \leq H (X_{n + 1} ∣ X_{n}, \dots, X_{2}) = a_{n},

where the inequality holds because conditioning reduces entropy: adding $X_{1}$ to the conditioning set $(X_{n}, \dots, X_{2})$ can only decrease the conditional entropy. Since $a_{n} \geq 0$ and is non-increasing, $a_{n}$ converges to some limit $L \geq 0$ .

To show $L = H (X)$ : by the chain rule, $H (X_{1}, \dots, X_{n}) = \sum_{k = 1}^{n} a_{k}$ (where $a_{1} = H (X_{1})$ ). Dividing by $n$ :

\frac{1}{n} H (X_{1}, \dots, X_{n}) = \frac{1}{n} k = 1 \sum n a_{k} .

Since $a_{k} \to L$ , the Cesaro mean also converges: $(1/ n) \sum_{k = 1}^{n} a_{k} \to L$ . By definition, $H (X) = lim_{n \to \infty} (1/ n) H (X_{1}, \dots, X_{n}) = L$ . $□$

Proposition (Markov chain entropy rate: direct derivation). Let ${X_{n}}$ be a stationary first-order Markov chain on a finite state space with transition matrix $P$ and stationary distribution $μ$ . Then

H (X) = - i \in X \sum μ_{i} j \in X \sum P_{ij} lo g_{2} P_{ij} .

Proof. For a first-order Markov chain, the Markov property gives $H (X_{n} ∣ X_{n - 1}, \dots, X_{1}) = H (X_{n} ∣ X_{n - 1})$ for all $n \geq 2$ . Stationarity gives $H (X_{n} ∣ X_{n - 1}) = H (X_{2} ∣ X_{1})$ for all $n$ . Therefore the sequence $a_{n}$ is constant for $n \geq 2$ : $a_{n} = H (X_{2} ∣ X_{1})$ , and the entropy rate equals this constant.

Expanding the conditional entropy:

H (X_{2} ∣ X_{1}) = i \sum p_{X_{1}} (i) H (X_{2} ∣ X_{1} = i) .

Under stationarity, $p_{X_{1}} (i) = μ_{i}$ , and $H (X_{2} ∣ X_{1} = i) = - \sum_{j} P_{ij} lo g_{2} P_{ij}$ . Substituting:

H (X) = i \sum μ_{i} (- j \sum P_{ij} lo g_{2} P_{ij}) = - i, j \sum μ_{i} P_{ij} lo g_{2} P_{ij} . □

Proposition (Upper bound via marginal entropy). For any stationary process, $H (X) \leq H (X_{1})$ , with equality iff the process consists of independent symbols.

Proof. By the previous proposition, $a_{1} = H (X_{1})$ and $a_{n}$ is non-increasing, so $H (X) = lim a_{n} \leq a_{1} = H (X_{1})$ . Equality holds iff $a_{n} = a_{1}$ for all $n$ , meaning $H (X_{n} ∣ X^{n - 1}) = H (X_{n})$ for all $n$ , which is equivalent to $X_{n}$ being independent of $(X_{1}, \dots, X_{n - 1})$ for all $n$ , i.e., the symbols are mutually independent. $□$

Connections Master

46.01.01 — The chain rule $H (X_{1}, \dots, X_{n}) = \sum H (X_{i} ∣ X^{i - 1})$ is the algebraic engine that decomposes joint entropy into a telescoping sum; the entropy rate is the Cesaro limit of those conditional entropies.
37.05.01 — The Markov property and transition matrix $P$ are the probabilistic substrate on which the entropy rate formula $H = - \sum_{i, j} μ_{i} P_{ij} lo g P_{ij}$ is built.
37.05.06 — Convergence to equilibrium ensures that $ν P^{n} \to μ$ , guaranteeing that the per-symbol entropy converges to the stationary entropy rate regardless of initial distribution.
46.02.01 — The AEP for stationary ergodic sources uses the entropy rate as the exponent governing the typical set size; the convergence $H (X_{n} ∣ X^{n - 1}) \to H (X)$ proved here is the foundation.
46.02.02 — Shannon's source coding theorem for stationary sources proves that the minimum achievable compression rate equals the entropy rate $H (X)$ ; this unit defines the quantity that theorem operationalizes.
46.01.02 — The mutual information decomposition $H (X) = H (X_{2}) - I (X_{1}; X_{2})$ expresses the entropy rate in terms of mutual information, connecting the rate to the divergence calculus developed in that unit.

Historical & philosophical context Master

Claude Shannon introduced the entropy rate in Section 7 of his 1948 paper "A Mathematical Theory of Communication." His motivation was modeling natural language as a stochastic process. Shannon needed a single number that captured the per-symbol information content of English text, where the dependence between letters extends over many characters. The entropy rate was that number: by estimating the conditional entropy of the next character given increasing lengths of context, Shannon bounded the entropy rate of English between 0.6 and 1.3 bits per character. His experiments involved human subjects guessing the next letter of text; the guess accuracy provided a direct estimate of the conditional entropy.

The Markov chain entropy formula appeared in the same section. Shannon modeled English as a sequence of increasingly sophisticated Markov approximations: zero-order (independent letters), first-order (single-letter frequencies), second-order (digram frequencies), and so on. Each approximation's entropy rate provides an upper bound on the true entropy rate of English, and the sequence of bounds converges downward toward the actual rate. This methodology — approximating a complex source by Markov models of increasing order — became a standard tool in language modeling and data compression.

The connection to thermodynamics is not merely analogical. The entropy rate of a physical process governed by a Markov dynamics (e.g., a particle hopping between energy states in thermal contact with a heat bath) equals the thermodynamic entropy production rate divided by Boltzmann's constant, up to a change of logarithm base from base-2 to natural logarithm. The second law of thermodynamics — that the entropy of an isolated system does not decrease — corresponds to the information-theoretic fact that the conditional entropy $H (X_{n} ∣ X^{n - 1})$ is non-increasing for stationary processes. This connection was made rigorous by T. S. Han and K. Kobayashi in their work on the information-spectrum approach to entropy rates in the 1990s, and by M. Esposito and C. Van den Broeck in their 2010 analysis of entropy production as a conditional entropy in Markov jump processes.

The Shannon-McMillan theorem (1953, extended by Breiman 1957 to almost-sure convergence) generalized the entropy rate from Markov chains to arbitrary stationary ergodic processes, establishing that the normalized log-probability converges almost surely to the entropy rate. This result is the ergodic theorem of information theory and underpins the general theory of data compression for correlated sources.

Bibliography Master

@article{shannon1948,
  author  = {Shannon, C. E.},
  title   = {A Mathematical Theory of Communication},
  journal = {Bell System Technical Journal},
  volume  = {27},
  pages   = {379--423 and 623--656},
  year    = {1948},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}
@article{mcmillan1953,
  author  = {McMillan, B.},
  title   = {The Basic Theorems of Information Theory},
  journal = {Annals of Mathematical Statistics},
  volume  = {25},
  pages   = {239--274},
  year    = {1953},
}
@article{breiman1957,
  author  = {Breiman, L.},
  title   = {The Individual Ergodic Theorem of Information Theory},
  journal = {Annals of Mathematical Statistics},
  volume  = {28},
  pages   = {809--811},
  year    = {1957},
}
@article{blackwell1957,
  author  = {Blackwell, D.},
  title   = {The Entropy of Functions of Finite-State Markov Chains},
  journal = {Transactions of the First Prague Conference on Information Theory},
  pages   = {13--20},
  year    = {1957},
}
@article{kieffer1993,
  author  = {Kieffer, J. C.},
  title   = {A General Framework for the Study of Information Rates},
  journal = {IEEE Transactions on Information Theory},
  volume  = {39},
  pages   = {1253--1269},
  year    = {1993},
}
@article{esposito-vandenbroeck2010,
  author  = {Esposito, M. and Van den Broeck, C.},
  title   = {Entropy Production as Correlation Between System and Reservoir},
  journal = {Physical Review E},
  volume  = {82},
  pages   = {011143},
  year    = {2010},
}

Prerequisites

46.01.01
37.05.01
37.05.02

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §4.1-4.2 (the weather example, entropy rate as average uncertainty per symbol)
intermediate: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §4.1-4.3 (formal definitions of entropy rate, the Cesaro-mean and conditional-entropy forms, entropy rate of Markov chains)
master: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §4.1-4.5; Shannon 1948 A Mathematical Theory of Communication §7; Kieffer 1974 On the Inverse Problem for Entropy Rates of Stationary Processes

References

Shannon, C. E. — A Mathematical Theory of Communication · Bell System Technical Journal 27 (1948) 379-423 and 623-656. Section 7 defines the entropy of an information source as $H = - \sum_{i, j} μ_{i} P_{ij} lo g P_{ij}$ for a stationary Markov source with stationary distribution $μ$ and transition probabilities $P_{ij}$ ; Shannon derives the entropy rate from the series approximation for English and connects it to the compression limit of the source.
Cover, T. M. & Thomas, J. A. — Elements of Information Theory (2nd ed.) · Wiley (2006). Section 4.1: entropy rate $H (X) = lim_{n \to \infty} \frac{1}{n} H (X_{1}, \dots, X_{n})$ for stationary processes; existence by Cesaro mean theorem. Section 4.2: alternative form $H (X) = lim H (X_{n} ∣ X_{n - 1}, \dots, X_{1})$ for stationary ergodic processes by the Cesaro convergence theorem applied to the conditional entropies. Section 4.3: entropy rate of a stationary Markov chain $H = - \sum_{i, j} μ_{i} P_{ij} lo g P_{ij}$ with worked examples. Section 4.4-4.5: functions of Markov chains and the second-law interpretation.
Kieffer, J. C. — A General Framework for the Study of Information Rates · IEEE Transactions on Information Theory 39 (1993) 1253-1269. Establishes the variational characterisation of entropy rates for general stationary processes and the continuity properties of the entropy-rate functional on the space of stationary measures.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m