Entropy Rates of a Stochastic Process

Motivation: the operator has grammar

The AEP established that $nH(X)$ bits suffice on average to describe $n$ independent and identically distributed random variables. That i.i.d. assumption is the single most unrealistic thing in the whole telegraph model.

A real operator does not roll a fresh die for each keystroke. After punching Q they punch U with probability near 1; after TH they punch E far more often than chance; English spelling and grammar make $X_{i}$ heavily dependent on $X_{i-1}, X_{i-2}, \ldots$ . So the tape is not a sequence of i.i.d. draws, and every count we made in Chapter 3 — “about $2^{nH}$ realistic tapes” — was computed under an assumption the wire violates.

IntuitionThe engineering question

If the keystrokes are dependent, does the joint entropy $H(X_1, X_2, \ldots, X_n)$ still grow linearly in $n$ ? If it does, there is still a well-defined “bits per keystroke” price for this operator and the telecom can still quote a rate. If it grows some other way, there is no such thing as a per-symbol cost and the whole business model of charging per word loses its information-theoretic footing.

The answer is that for a stationary process the growth is asymptotically linear at a rate $H(\mathcal{X})$ , which we call the entropy rate of the process. Dependence does not destroy the per-symbol price; it lowers it, because grammar is predictability and predictability is cheap.

ConventionNotation for the rate

We write $H(\mathcal{X})$ (calligraphic argument, a process) for the entropy rate, to distinguish it from $H(X)$ (a single random variable). The interpretation of $H(\mathcal{X})$ as the best achievable data compression for a dependent source is not proved here — that needs the full source coding analysis. This chapter only establishes that the rate exists and computes it.

Stochastic processes and stationarity

DefinitionStochastic process

A stochastic process $\{X_i\}$ is an indexed sequence of random variables. In general there can be arbitrary dependence among them. The process is characterized by its joint probability mass functions

$\Pr\{(X_1, X_2, \ldots, X_n) = (x_1, x_2, \ldots, x_n)\} = p(x_1, x_2, \ldots, x_n)$

for $(x_1, \ldots, x_n) \in \mathcal{X}^n$ , $n = 1, 2, \ldots$

Component	Detail
Physical anchor	The operator’s entire typing career: $X_i$ is the $i$ -th keystroke.
What replaces $p(x)$	Not one pmf but an infinite family of joint pmfs, one for each length $n$ , which must be consistent with each other.
Why this is harder	For an i.i.d. source the whole process is specified by $\lvert \mathcal{X} \rvert$ numbers. Here it takes $\lvert \mathcal{X} \rvert^n$ numbers per $n$ — unmanageable without extra structure.

The first structural assumption we impose is that the operator’s habits do not change over time.

DefinitionStationarity

A stochastic process is stationary if the joint distribution of any subset of the sequence is invariant with respect to shifts in the time index:

$\Pr\{X_1 = x_1, \ldots, X_n = x_n\} = \Pr\{X_{1+l} = x_1, \ldots, X_{n+l} = x_n\}$

for every $n$ , every shift $l$ , and all $x_1, \ldots, x_n \in \mathcal{X}$ .

IntuitionWhat stationarity physically rules out

It says the operator’s language statistics are the same in the afternoon as in the morning. It does not say the keystrokes are independent — the operator may still have grammar. It only says the grammar itself is not drifting. Note the definition is about blocks, not just single symbols: the probability of the digram TH must be the same at positions $(5,6)$ as at $(500, 501)$ , not merely the frequency of T.

WarningStationarity is an assumption about the source, and it can fail

An operator who starts the shift alert and ends it exhausted, or a wire whose noise profile worsens as the line heats up, is not stationary. Everything in this note that relies on shifting the time index silently fails for such a source, and, as example 3 below shows, the entropy rate may then not even exist.

Markov chains

Stationarity alone still leaves arbitrarily long-range dependence. The simplest useful restriction is that dependence reaches back exactly one step.

DefinitionMarkov chain

A discrete stochastic process $X_1, X_2, \ldots$ is a Markov chain (or Markov process) if for $n = 1, 2, \ldots$

$\Pr(X_{n+1} = x_{n+1} \mid X_n = x_n, X_{n-1} = x_{n-1}, \ldots, X_1 = x_1) = \Pr(X_{n+1} = x_{n+1} \mid X_n = x_n)$

for all $x_1, \ldots, x_{n+1} \in \mathcal{X}$ .

IntuitionThe telegraph reading

Each keystroke depends only on the one immediately preceding it and is conditionally independent of everything before that. This is the same “the future depends on the past only through the present” condition we used for the [[information-inequalities#Markov chains ( $X \rightarrow Y \rightarrow Z$ )|data processing inequality]], now applied along a time axis instead of along a processing pipeline.

Because each conditional collapses to depend on one symbol, the general chain rule of probability collapses with it:

FormulaFactorization of a Markov chain

$p(x_1, x_2, \ldots, x_n) = p(x_1)\, p(x_2 \mid x_1)\, p(x_3 \mid x_2) \cdots p(x_n \mid x_{n-1})$

DefinitionTime invariance

The Markov chain is time invariant if the conditional probability $p(x_{n+1} \mid x_n)$ does not depend on $n$ ; that is,

$\Pr\{X_{n+1} = b \mid X_n = a\} = \Pr\{X_2 = b \mid X_1 = a\} \qquad \text{for all } a, b \in \mathcal{X}$

(We assume the Markov chain is time invariant unless otherwise stated.)

If $\{X_i\}$ is a Markov chain, $X_n$ is called the state at time $n$ . A time-invariant Markov chain is fully characterized by two things: its initial state, and a probability transition matrix $P = [P_{ij}]$ , $i, j \in \{1, 2, \ldots, m\}$ , where

$P_{ij} = \Pr\{X_{n+1} = j \mid X_n = i\}$

Component	Detail
Domain	$P$ is an $m \times m$ matrix indexed by (current state, next state).
Row constraint	Each row is a pmf: $\sum_j P_{ij} = 1$ . Row $i$ is “the operator’s habits given they just typed $i$ ”.
What it is not	$P$ is not symmetric in general, and its columns need not sum to 1 (that extra condition has its own name — see ).

Structural conditions

DefinitionIrreducible and aperiodic

Irreducible: it is possible to go with positive probability from any state to any other state in a finite number of steps.
Aperiodic: the largest common factor of the lengths of different paths from a state back to itself is 1.

IntuitionWhy these two conditions keep appearing

Irreducibility rules out a machine with a stuck key that traps the operator in a sub-alphabet they can never leave. Aperiodicity rules out a machine that can only return to a state on even-numbered steps, which would make the distribution oscillate forever instead of settling. Together they are exactly what is needed for the chain to forget where it started.

Stationary distributions

If the pmf of the state at time $n$ is $p(x_n)$ , then the pmf at time $n+1$ is obtained by pushing it through the transition matrix:

$p(x_{n+1}) = \sum_{x_n} p(x_n) P_{x_n x_{n+1}}$

DefinitionStationary distribution

A distribution on the states such that the distribution at time $n+1$ is the same as the distribution at time $n$ is called a stationary distribution. In matrix form, $\mu$ is stationary iff $\mu P = \mu$ , i.e.

$\mu_j = \sum_i \mu_i P_{ij} \qquad \text{for all } j$

ImportantWhy it is called stationary

The name is not a coincidence with the earlier definition: if the initial state of a Markov chain is drawn according to a stationary distribution, the Markov chain forms a stationary process. The distribution being a fixed point of $P$ is precisely what makes the joint law shift-invariant.

TheoremUniqueness and convergence

If the finite-state Markov chain is irreducible and aperiodic, the stationary distribution is unique, and from any starting distribution, the distribution of $X_n$ tends to the stationary distribution as $n \rightarrow \infty$ .

Example: the two-state chain

stateDiagram-v2
  direction LR
  S1: State 1
  S2: State 2
  S1 --> S2: alpha
  S2 --> S1: beta
  S1 --> S1: 1 - alpha
  S2 --> S2: 1 - beta

ExampleTwo-state Markov chain

Consider a two-state chain with transition matrix

$P = \begin{bmatrix} 1 - \alpha & \alpha \\ \beta & 1 - \beta \end{bmatrix}$

Let the stationary distribution be the vector $\mu = (\mu_1, \mu_2)$ . Solve $\mu P = \mu$ , or more simply balance probabilities: for a stationary distribution, the net probability flow across any cut set in the state transition graph is zero. Here there is one cut, between the two states:

$\mu_1 \alpha = \mu_2 \beta$

Combined with $\mu_1 + \mu_2 = 1$ :

$\mu_1 = \frac{\beta}{\alpha + \beta}, \qquad \mu_2 = \frac{\alpha}{\alpha + \beta}$

If the chain is started from $\mu$ , the process is stationary, and the entropy of the state $X_n$ at time $n$ is

$H(X_n) = H\!\left( \frac{\beta}{\alpha + \beta}, \frac{\alpha}{\alpha + \beta} \right)$

Warning $H(X_n)$ is not the entropy rate

$H(X_n)$ is a constant, the same for every $n$ by stationarity, so you might guess $H(X_1, \ldots, X_n) = n H(X_n)$ . That is exactly the i.i.d. answer and it is wrong here. The dependence among the $X_i$ will take a steady toll: each keystroke after the first is partly predicted by its predecessor, so it contributes strictly less than $H(X_n)$ fresh bits. Quantifying that toll is what the next section is for.

Entropy rate

The problem. We have a sequence of $n$ dependent keystrokes. The natural question for a telecom quoting a per-word price: how does the entropy of the sequence grow with $n$ ? There are two different reasonable ways to define a “per-symbol” answer, and they are not obviously the same number.

DefinitionEntropy rate (per-symbol definition)

The entropy of a stochastic process $\{X_i\}$ is

$H(\mathcal{X}) = \lim_{n \rightarrow \infty} \frac{1}{n} H(X_1, X_2, \ldots, X_n)$

when the limit exists.

DefinitionEntropy rate (conditional definition)

A related quantity:

$H'(\mathcal{X}) = \lim_{n \rightarrow \infty} H(X_n \mid X_{n-1}, X_{n-2}, \ldots, X_1)$

when the limit exists.

	$H(\mathcal{X})$	$H'(\mathcal{X})$
Measures	The per-symbol entropy of the $n$ random variables, averaged over the whole tape	The conditional entropy of the last random variable given the entire past
Engineering reading	”What did this whole tape cost me, divided by its length?” — an accounting figure	”What does the next keystroke cost me, given everything I have already seen?” — a marginal figure
Natural for	Pricing a message already sent	Deciding how many bits to budget for the next symbol in a streaming encoder

These are genuinely different notions — an average versus a marginal — and the central theorem of this section is that for stationary processes they coincide.

Worked examples of entropy rates

Example1. Typewriter with $m$ equally likely letters

The typewriter can produce $m^n$ sequences of length $n$ , all equally likely. Hence $H(X_1, \ldots, X_n) = \log m^n = n \log m$ , and

$H(\mathcal{X}) = \log m \text{ bits per symbol}$

This is the no-structure baseline: the rate saturates the maximum entropy bound at every $n$ .

Example2. $X_1, X_2, \ldots$ i.i.d.

$H(\mathcal{X}) = \lim \frac{H(X_1, X_2, \ldots, X_n)}{n} = \lim \frac{n H(X_1)}{n} = H(X_1)$

The entropy rate of an i.i.d. source is just the per-symbol entropy, which is what one would expect and is the case Chapter 3 handled. This is the sanity check that the new definition generalizes the old one rather than replacing it.

Example3. Independent but not identically distributed — the rate can fail to exist

If the $X_i$ are independent then $H(X_1, \ldots, X_n) = \sum_{i=1}^n H(X_i)$ , but the $H(X_i)$ are not all equal, and we can choose a sequence of distributions such that $\frac{1}{n}\sum H(X_i)$ has no limit.

Take a random binary sequence where $p_i = \Pr(X_i = 1)$ is a function of $i$ :

$p_i = \begin{cases} 0.5 & \text{if } 2k < \log \log i \le 2k+1 \\ 0 & \text{if } 2k+1 < \log \log i \le 2k+2 \end{cases} \qquad k = 0, 1, 2, \ldots$

Then there are arbitrarily long stretches where $H(X_i) = 1$ , followed by exponentially longer segments where $H(X_i) = 0$ . The running average of the $H(X_i)$ oscillates between $0$ and $1$ and never settles. Thus $H(\mathcal{X})$ is not defined for this process.

Why the doubly-exponential construction is needed: to break the limit you must keep dragging the running average back and forth. Once the average is near $1$ , you need a $0$ -stretch longer than everything so far to drag it to $0$ , and then a $1$ -stretch longer than that. Nesting inside $\log \log i$ produces exactly this escalation.

IntuitionWhat example 3 is really telling us

Independence is not what makes the entropy rate exist — this process is independent and has no rate. What fails here is stationarity: the source’s statistics keep changing. This is why the theorems below assume stationarity and say nothing about independence.

The two definitions agree for stationary processes

TheoremEquality of the two entropy rates

For a stationary stochastic process, the limits defining $H(\mathcal{X})$ and $H'(\mathcal{X})$ both exist and are equal:

$H(\mathcal{X}) = H'(\mathcal{X})$

We prove it in three pieces: first that the marginal quantity converges at all, then a purely analytic fact about averages, then the combination.

TheoremConditional entropy is nonincreasing

For a stationary stochastic process, $H(X_n \mid X_{n-1}, \ldots, X_1)$ is nonincreasing in $n$ and has a limit $H'(\mathcal{X})$ .

ProofConditioning reduces entropy, then shift the index

Step 1: Drop a conditioning variable to get an upper bound. By conditioning reduces entropy, removing $X_1$ from the conditioning set can only increase the entropy — so keeping the shorter past on the right gives an upper bound:

$H(X_{n+1} \mid X_1, X_2, \ldots, X_n) \le H(X_{n+1} \mid X_n, \ldots, X_2)$

Step 2: Shift the time index. The right-hand side conditions symbol $n+1$ on the $n-1$ symbols immediately before it. By stationarity, shifting every index down by one changes nothing:

$H(X_{n+1} \mid X_n, \ldots, X_2) = H(X_n \mid X_{n-1}, \ldots, X_1)$

Step 3: Conclude. Chaining Steps 1 and 2 gives $H(X_{n+1} \mid X_n, \ldots, X_1) \le H(X_n \mid X_{n-1}, \ldots, X_1)$ , so the sequence is nonincreasing. It is also a sequence of nonnegative numbers (entropies are $\ge 0$ ). A decreasing sequence bounded below converges, so it has a limit $H'(\mathcal{X})$ .

∎

IntuitionPhysical meaning of monotonicity

The more of the operator’s past you have on the tape in front of you, the less surprised you are by their next keystroke. Extra context never hurts your prediction — the same “information can’t hurt” principle, applied along time.

TheoremCesàro mean

If $a_n \rightarrow a$ and $b_n = \frac{1}{n}\sum_{i=1}^n a_i$ , then $b_n \rightarrow a$ .

IntuitionInformal outline

Since most of the terms in the sequence $\{a_k\}$ are eventually close to $a$ , the running average $b_n$ of the first $n$ terms is also eventually close to $a$ . The finitely many early terms, however wild, get divided by a growing $n$ .

ProofSplit the average into the early terms and the late terms

Step 1: Fix a tolerance and find where the sequence settles. Let $\epsilon > 0$ . Since $a_n \rightarrow a$ , there exists $N(\epsilon)$ such that $\lvert a_n - a \rvert \le \epsilon$ for all $n \ge N(\epsilon)$ .

Step 2: Write the deviation of the average.

$\lvert b_n - a \rvert = \left\lvert \frac{1}{n} \sum_{i=1}^n (a_i - a) \right\rvert \le \frac{1}{n} \sum_{i=1}^n \lvert a_i - a \rvert$

(triangle inequality, moved inside the sum).

Step 3: Split the sum at $N(\epsilon)$ . The first $N(\epsilon)$ terms are whatever they are; each of the remaining $n - N(\epsilon)$ terms is at most $\epsilon$ by Step 1:

$\le \frac{1}{n} \sum_{i=1}^{N(\epsilon)} \lvert a_i - a \rvert + \frac{n - N(\epsilon)}{n}\, \epsilon \;\le\; \frac{1}{n} \sum_{i=1}^{N(\epsilon)} \lvert a_i - a \rvert + \epsilon$

for all $n \ge N(\epsilon)$ .

Step 4: Kill the first term. $\sum_{i=1}^{N(\epsilon)} \lvert a_i - a \rvert$ is a fixed finite number once $\epsilon$ is chosen — it does not grow with $n$ — so dividing it by $n$ sends it to $0$ . Hence we can make $\lvert b_n - a \rvert \le 2\epsilon$ by taking $n$ large enough, so $b_n \rightarrow a$ .

∎

ProofEquality of the two entropy rates

Step 1: The chain rule turns the joint entropy into a sum of conditionals. By the [[entropy-mutual-information#Chain rule for entropy ( $n$ variables)|chain rule for entropy]]:

$\frac{1}{n} H(X_1, X_2, \ldots, X_n) = \frac{1}{n} \sum_{i=1}^n H(X_i \mid X_{i-1}, \ldots, X_1)$

Read this carefully: the entropy rate is the time average of the conditional entropies. The left side is the per-symbol accounting figure; the right side averages the marginal figures. The whole theorem is now a statement about averages versus limits.

Step 2: The terms being averaged converge. By the monotonicity theorem above, $a_i := H(X_i \mid X_{i-1}, \ldots, X_1)$ tends to a limit $H'(\mathcal{X})$ .

Step 3: Apply Cesàro. The running average of a convergent sequence converges to the same limit. Hence

$H(\mathcal{X}) = \lim \frac{H(X_1, X_2, \ldots, X_n)}{n} = \lim H(X_n \mid X_{n-1}, \ldots, X_1) = H'(\mathcal{X})$

∎

IntuitionWhy this is the result that saves the business model

The accounting price per symbol and the marginal price of the next symbol are the same number. A streaming encoder budgeting $H'$ bits for each new keystroke and a billing department dividing the total by $n$ agree in the long run, so “bits per symbol” is unambiguous for a stationary source.

The AEP for stationary ergodic processes

TheoremGeneral AEP (proved elsewhere)

For any stationary ergodic process,

$-\frac{1}{n} \log p(X_1, X_2, \ldots, X_n) \longrightarrow H(\mathcal{X}) \qquad \text{with probability 1}$

ImportantEverything from Chapter 3 survives, with $H$ replaced by $H(\mathcal{X})$

Using this, the theorems of the AEP chapter extend directly. Define the typical set exactly as in the i.i.d. case; by the same arguments, the typical set has probability close to 1, there are about $2^{nH(\mathcal{X})}$ typical sequences of length $n$ , each with probability about $2^{-nH(\mathcal{X})}$ , and we can therefore represent them using about $nH(\mathcal{X})$ bits. This is what makes the entropy rate the average description length for a stationary ergodic process — and it is the answer to the open question left at the end of the AEP note.

NoteTwo caveats on scope

First, the general AEP is stated here and proved only much later (Cover & Thomas §16.8) — we are borrowing it. Second, it needs ergodicity on top of stationarity, a strictly stronger condition; the entropy rate itself is well defined for all stationary processes, but the typical-set machinery needs the process to actually explore its statistics rather than getting stuck in one of several possible regimes.

Entropy rate of a Markov chain

The entropy rate is particularly easy to calculate for Markov chains, because the conditional definition collapses immediately.

FormulaMarkov entropy rate

For a stationary Markov chain,

$H(\mathcal{X}) = H'(\mathcal{X}) = \lim_n H(X_n \mid X_{n-1}, \ldots, X_1) = \lim_n H(X_n \mid X_{n-1}) = H(X_2 \mid X_1)$

where the conditional entropy is calculated using the given stationary distribution $\mu$ , the solution of $\mu_j = \sum_i \mu_i P_{ij}$ for all $j$ .

IntuitionWhy the limit disappears

Each equality does one job: the first is the theorem above; the second is the Markov property (conditioning on the whole past is the same as conditioning on the last symbol); the third is time invariance plus stationarity (the conditional is the same at every $n$ , so the limit of a constant sequence is that constant). No limit actually needs computing — the rate is a one-step quantity.

TheoremEntropy rate of a stationary Markov chain

Let $\{X_i\}$ be a stationary Markov chain with stationary distribution $\mu$ and transition matrix $P$ . Let $X_1 \sim \mu$ . Then

$H(\mathcal{X}) = - \sum_{ij} \mu_i P_{ij} \log P_{ij}$

ProofExpand the one-step conditional entropy

$H(\mathcal{X}) = H(X_2 \mid X_1) = \sum_i \mu_i \left( \sum_j -P_{ij} \log P_{ij} \right)$ — the outer weight $\mu_i$ is how often the chain sits in state $i$ , and the inner bracket is the entropy of row $i$ of the transition matrix.

∎

IntuitionReading the formula as a machine

Row $i$ of $P$ is the operator’s habits given they just typed $i$ , and $-\sum_j P_{ij} \log P_{ij}$ is the surprise of their next keystroke from that state. The entropy rate is just those per-state surprises averaged by how much time the operator spends in each state.

ExampleTwo-state Markov chain

For the chain of the earlier example, with $\mu_1 = \beta/(\alpha+\beta)$ and $\mu_2 = \alpha/(\alpha+\beta)$ , row 1 has entropy $H(\alpha)$ and row 2 has entropy $H(\beta)$ , so

$H(\mathcal{X}) = H(X_2 \mid X_1) = \frac{\beta}{\alpha + \beta} H(\alpha) + \frac{\alpha}{\alpha + \beta} H(\beta)$

Compare this against $H(X_n) = H\!\big(\beta/(\alpha+\beta)\big)$ from before: the two are different numbers, and the gap is exactly the “steady toll” the dependence takes.

RemarkNon-stationary starts don’t matter

If the Markov chain is irreducible and aperiodic it has a unique stationary distribution, and any initial distribution tends to it as $n \rightarrow \infty$ . So even when the chain is started off-distribution, the entropy rate — being defined purely in terms of long-term behaviour — is still the $H(\mathcal{X})$ computed from $\mu$ .

Example: entropy rate of a random walk on a weighted graph

The problem. A particle (or a message-routing token, or a king on a chessboard) walks randomly from node to node on a connected graph. This is a Markov chain with a lot of structure, and we would like a closed form for its entropy rate rather than a numerical eigenvector computation.

Setup. Consider a graph with $m$ nodes labelled $\{1, 2, \ldots, m\}$ , with weight $W_{ij} \ge 0$ on the edge joining node $i$ to node $j$ . The graph is undirected, so $W_{ij} = W_{ji}$ , and we set $W_{ij} = 0$ if there is no edge. Given $X_n = i$ , the next vertex $j$ is chosen among the nodes connected to $i$ with probability proportional to the connecting edge’s weight:

$P_{ij} = \frac{W_{ij}}{\sum_k W_{ik}}$

Define the local and global weight totals:

$W_i = \sum_j W_{ij} \quad (\text{weight emanating from node } i), \qquad W = \sum_{i,j \,:\, j > i} W_{ij} \quad (\text{all edges})$

Because each undirected edge is counted once in $W$ but contributes to two nodes’ local totals, $\sum_i W_i = 2W$ .

The stationary distribution

TheoremStationary distribution of a weighted random walk

$\mu_i = \frac{W_i}{2W}$

The stationary probability of a node is proportional to the total weight of the edges emanating from it.

ProofGuess and verify

\mu P = \mu

We guess the form above and check it directly:

$\sum_i \mu_i P_{ij} = \sum_i \frac{W_i}{2W} \cdot \frac{W_{ij}}{W_i}$

Step 1: The $W_i$ cancel. This is the crucial cancellation, and it is what makes the guess work: the factor that makes a node likely to be occupied is exactly the factor that divides its outgoing probabilities.

$= \sum_i \frac{1}{2W} W_{ij} = \frac{1}{2W} \sum_i W_{ij}$

Step 2: Use undirectedness. Since $W_{ij} = W_{ji}$ , the sum $\sum_i W_{ij}$ is the total weight at node $j$ , namely $W_j$ :

$= \frac{W_j}{2W} = \mu_j \qquad \checkmark$

∎

IntuitionThe locality property

This stationary distribution depends only on the total weight $W$ and on the weight of edges connected to that one node. Rewiring some distant part of the graph, as long as the total weight $W$ is held constant, does not change $\mu_i$ at all. For a network engineer this is a strong statement: a node’s long-run traffic share is a purely local quantity.

The entropy rate

DerivationFrom

H(X_2 \mid X_1)

to a difference of two entropies

Step 1: Start from the Markov entropy rate.

$H(\mathcal{X}) = H(X_2 \mid X_1) = - \sum_i \mu_i \sum_j P_{ij} \log P_{ij}$

Step 2: Substitute $\mu_i = W_i / 2W$ and $P_{ij} = W_{ij}/W_i$ . The $W_i$ cancel again:

$= - \sum_i \frac{W_i}{2W} \sum_j \frac{W_{ij}}{W_i} \log \frac{W_{ij}}{W_i} = - \sum_i \sum_j \frac{W_{ij}}{2W} \log \frac{W_{ij}}{W_i}$

Step 3: Renormalize the inside of the logarithm. We want both entropies to be over probability distributions with denominator $2W$ , so write $\log \frac{W_{ij}}{W_i} = \log \frac{W_{ij}/2W}{W_i/2W}$ and split the log:

$= - \sum_i \sum_j \frac{W_{ij}}{2W} \log \frac{W_{ij}}{2W} \;+\; \sum_i \sum_j \frac{W_{ij}}{2W} \log \frac{W_i}{2W}$

Step 4: Collapse the second term by marginalizing. The log in the second term does not depend on $j$ , and $\sum_j W_{ij} = W_i$ :

$\sum_i \sum_j \frac{W_{ij}}{2W} \log \frac{W_i}{2W} = \sum_i \frac{W_i}{2W} \log \frac{W_i}{2W} = -H\!\left(\ldots, \frac{W_i}{2W}, \ldots\right)$

Step 5: Recognize both pieces as entropies. The quantities $\{W_{ij}/2W\}$ (over ordered pairs) and $\{W_i/2W\}$ (over nodes) are both valid distributions, so:

$H(\mathcal{X}) = H\!\left(\ldots, \frac{W_{ij}}{2W}, \ldots\right) - H\!\left(\ldots, \frac{W_i}{2W}, \ldots\right)$

FormulaEntropy rate of a weighted random walk

$H(\mathcal{X}) = H\!\left(\ldots, \frac{W_{ij}}{2W}, \ldots\right) - H\!\left(\ldots, \frac{W_i}{2W}, \ldots\right)$

(the entropy of the edge distribution minus the entropy of the node distribution).

CorollaryUnweighted graphs

If all edges have equal weight, the stationary distribution puts weight $E_i / 2E$ on node $i$ , where $E_i$ is the number of edges at node $i$ and $E$ is the total number of edges. The edge distribution is then uniform over $2E$ ordered pairs, so its entropy is $\log(2E)$ , and

$H(\mathcal{X}) = \log(2E) - H\!\left( \frac{E_1}{2E}, \frac{E_2}{2E}, \ldots, \frac{E_m}{2E} \right)$

WarningThis answer is so simple it is almost misleading

Apparently the entropy rate — an average transition entropy, which sounds like it should depend on the fine structure of the graph — depends only on the entropy of the stationary distribution and the total number of edges. Two very differently shaped graphs with the same degree sequence have the same entropy rate.

ExampleRandom walk of a king on a chessboard

Let a king move at random on an $8 \times 8$ board. The king has 8 moves in the interior, 5 at the edges, and 3 at the corners. Counting all moves gives $2E = 420$ , so the stationary probabilities are $\frac{8}{420}$ , $\frac{5}{420}$ and $\frac{3}{420}$ respectively, and the entropy rate works out to $0.92 \log 8$ .

The factor $0.92$ is due purely to edge effects — on an infinite chessboard every square would have 8 moves, the degree distribution would be uniform, and the rate would be exactly $\log 8$ . Similarly one can find the entropy rate of rooks ( $\log 14$ bits, since a rook always has 14 possible moves regardless of position, so there are no edge effects at all), bishops, and queens.

(Open question worth thinking about: the queen combines the moves of a rook and a bishop. Does the queen have more or less freedom than the pair?)

RemarkTime reversibility

A stationary random walk on a graph is time-reversible: the probability of any sequence of states is the same forward or backward,

$\Pr(X_1 = x_1, \ldots, X_n = x_n) = \Pr(X_n = x_1, \ldots, X_1 = x_n)$

Rather surprisingly, the converse is also true: any time-reversible Markov chain can be represented as a random walk on an undirected weighted graph. So the closed form above is not a special case — it covers the entire reversible class.

The second law of thermodynamics

The problem. The second law of physics says the entropy of an isolated system is nondecreasing. In statistical thermodynamics, entropy is defined as the log of the number of microstates — which corresponds exactly to our notion of entropy if all states are equally likely. Does our $H$ reproduce the second law?

Model the isolated system as a Markov chain whose transitions obey the physical laws governing it. (Implicit in this: there is an overall state, and knowing the present state, the future is independent of the past.) Within this model there are four or five different readings of “the second law.”

WarningThe headline result is not what you expect

It may come as a shock, but the entropy does not always increase. What always decreases is the relative entropy. Entropy increase is a special case that needs an extra condition.

1. Relative entropy between two distributions decreases

Theorem $D(\mu_n \Vert \mu'_n)$ decreases with $n$

Let $\mu_n$ and $\mu'_n$ be two distributions on the state space of a Markov chain at time $n$ , evolving to $\mu_{n+1}$ and $\mu'_{n+1}$ . Then

$D(\mu_n \Vert \mu'_n) \ge D(\mu_{n+1} \Vert \mu'_{n+1})$

ProofExpand the joint relative entropy two ways

Step 1: Set up the two joint distributions. Let $p$ and $q$ be the joint mass functions of $(X_n, X_{n+1})$ under the two starting distributions. Both are driven by the same physics, i.e. the same transition function $r(\cdot \mid \cdot)$ :

$p(x_n, x_{n+1}) = p(x_n)\, r(x_{n+1} \mid x_n), \qquad q(x_n, x_{n+1}) = q(x_n)\, r(x_{n+1} \mid x_n)$

Step 2: Apply the chain rule for relative entropy in both orders.

$D\big(p(x_n, x_{n+1}) \Vert q(x_n, x_{n+1})\big) = D\big(p(x_n) \Vert q(x_n)\big) + D\big(p(x_{n+1} \mid x_n) \Vert q(x_{n+1} \mid x_n)\big)$

$= D\big(p(x_{n+1}) \Vert q(x_{n+1})\big) + D\big(p(x_n \mid x_{n+1}) \Vert q(x_n \mid x_{n+1})\big)$

Step 3: Kill the forward conditional term. Since both $p$ and $q$ are derived from the same Markov chain, $p(x_{n+1} \mid x_n)$ and $q(x_{n+1} \mid x_n)$ are both equal to $r(x_{n+1} \mid x_n)$ . A relative entropy between a distribution and itself is zero, so $D(p(x_{n+1} \mid x_n) \Vert q(x_{n+1} \mid x_n)) = 0$ .

Step 4: Discard the backward conditional term by non-negativity. By the information inequality, $D(p(x_n \mid x_{n+1}) \Vert q(x_n \mid x_{n+1})) \ge 0$ . Equating the two expansions and dropping this non-negative term:

$D\big(p(x_n) \Vert q(x_n)\big) \ge D\big(p(x_{n+1}) \Vert q(x_{n+1})\big)$

that is, $D(\mu_n \Vert \mu'_n) \ge D(\mu_{n+1} \Vert \mu'_{n+1})$ .

∎

IntuitionThe asymmetry that drives the whole proof

The forward conditional is shared (same physics) and contributes nothing; the backward conditional is not shared and contributes something non-negative. Running the chain forward therefore blurs the two distributions together. Any two ensembles evolving under the same dynamics become more alike.

ExampleWealth distributions

Suppose the tax system for redistributing wealth is the same in Canada and in England. If $\mu_n$ and $\mu'_n$ represent the distributions of wealth among people in the two countries, the inequality says the relative entropy distance between them decreases with time: the two wealth distributions become more similar.

2. Distance to a stationary distribution decreases

Corollary $D(\mu_n \Vert \mu)$ decreases with $n$

Let $\mu'_n$ in the previous theorem be any stationary distribution $\mu$ . Then $\mu'_{n+1} = \mu$ as well, so

$D(\mu_n \Vert \mu) \ge D(\mu_{n+1} \Vert \mu)$

Any state distribution gets closer and closer to every stationary distribution as time passes.

RemarkConvergence of the sequence, and the harder claim

$D(\mu_n \Vert \mu)$ is a monotonically nonincreasing nonnegative sequence, so it must have a limit. That the limit is zero when the stationary distribution is unique is true but more difficult to prove — monotone convergence alone does not give it.

3. Entropy increases only if the stationary distribution is uniform

WarningDecreasing relative entropy does not imply increasing entropy

Counterexample: take any Markov chain with a nonuniform stationary distribution and start it from the uniform distribution. The uniform is already the maximum entropy distribution, and the chain will drift towards the stationary distribution, which has lower entropy. Here entropy decreases with time, while relative entropy still obediently decreases.

TheoremEntropy increase under a uniform stationary distribution

If the stationary distribution is the uniform distribution $\mu = 1/\lvert \mathcal{X} \rvert$ , then

$D(\mu_n \Vert \mu) = \log \lvert \mathcal{X} \rvert - H(\mu_n) = \log \lvert \mathcal{X} \rvert - H(X_n)$

and the monotonic decrease in relative entropy implies a monotonic increase in entropy.

IntuitionWhy this is the case that matches physics

This is the interpretation that ties in most closely with statistical thermodynamics, where all microstates are equally likely, i.e. the stationary distribution genuinely is uniform. The famous “entropy always increases” is not a theorem about Markov chains in general — it is a theorem about Markov chains whose equilibrium is uniform.

Doubly stochastic transitions

DefinitionDoubly stochastic matrix

A probability transition matrix $[P_{ij}]$ is doubly stochastic if

$\sum_i P_{ij} = 1 \quad \text{for all } j \qquad \text{and} \qquad \sum_j P_{ij} = 1 \quad \text{for all } i$

(columns sum to 1 as well as rows).

RemarkThe exact characterization

The uniform distribution is a stationary distribution of $P$ if and only if $P$ is doubly stochastic. So “doubly stochastic dynamics” is precisely the physical condition under which entropy is guaranteed to increase.

4. Conditional uncertainty about the future increases

Theorem $H(X_n \mid X_1)$ increases with $n$

For a stationary Markov process, $H(X_n)$ is constant (so entropy is certainly not increasing), but the conditional entropy $H(X_n \mid X_1)$ increases with $n$ .

IntuitionThe right reading of “entropy increases”

A single observation of the system at time 1 tells you less and less about the system as time goes on. This is the version of the second law that survives for a general stationary Markov chain: not that the system’s entropy grows, but that your conditional uncertainty about its future, given a fixed past observation, grows.

ProofProof 1 — via entropy properties

Step 1: Add a conditioning variable. Conditioning reduces entropy, so adding $X_2$ to the conditioning set can only lower it:

$H(X_n \mid X_1) \ge H(X_n \mid X_1, X_2)$

Step 2: Drop $X_1$ by Markovity. Given $X_2$ , the variable $X_n$ (for $n \ge 2$ ) is independent of $X_1$ :

$H(X_n \mid X_1, X_2) = H(X_n \mid X_2)$

Step 3: Shift indices by stationarity. Conditioning symbol $n$ on symbol 2 is the same as conditioning symbol $n-1$ on symbol 1:

$H(X_n \mid X_2) = H(X_{n-1} \mid X_1)$

Chaining: $H(X_n \mid X_1) \ge H(X_{n-1} \mid X_1)$ , which is the claim.

∎

ProofProof 2 — via the data processing inequality

Step 1: Identify the Markov chain. The states satisfy $X_1 \rightarrow X_{n-1} \rightarrow X_n$ . Applying the data processing inequality:

$I(X_1 ; X_{n-1}) \ge I(X_1 ; X_n)$

Step 2: Expand both mutual informations into entropies.

$H(X_{n-1}) - H(X_{n-1} \mid X_1) \ge H(X_n) - H(X_n \mid X_1)$

Step 3: Cancel the marginals by stationarity. $H(X_{n-1}) = H(X_n)$ , so they cancel, leaving

$H(X_{n-1} \mid X_1) \le H(X_n \mid X_1)$

(The same techniques show that $H(X_0 \mid X_n)$ is increasing in $n$ for any Markov chain — the system also becomes harder to reconstruct backwards.)

∎

5. Shuffles increase entropy

TheoremShuffles increase entropy

If $T$ is a shuffle (permutation) of a deck of cards, $X$ is the initial (random) position of the cards, and the choice of $T$ is independent of $X$ , then

$H(TX) \ge H(X)$

where $TX$ is the permutation of the deck induced by applying $T$ to $X$ .

IntuitionWhere the independence assumption does the work

The shuffler must not be looking at the deck. A shuffle chosen because of the current arrangement could undo it and lower the entropy; a shuffle chosen blind can only mix. This is the card-table version of the doubly-stochastic condition above — a random relabelling by an independent permutation acts uniformly.

Functions of Markov chains

The problem. Let $X_1, X_2, \ldots$ be a stationary Markov chain, and let $Y_i = \phi(X_i)$ be a process each of whose terms is a function of the corresponding state. What is the entropy rate $H(\mathcal{Y})$ ?

This is the realistic observation model. In many situations one has only partial information about the state of the system: the wiretap sees whether the voltage is high or low, not which of 32 keys was pressed; the receiver’s tape shows a letter class, not the operator’s full internal state.

Warning $Y$ is generally not a Markov chain

It would simplify matters greatly if $Y_1, Y_2, \ldots$ were itself Markov, but in many cases it is not — collapsing states can create dependence on the arbitrarily distant past, because the current $Y$ does not pin down which underlying state you are in. So we cannot just apply $H(\mathcal{Y}) = H(Y_2 \mid Y_1)$ .

Since the Markov chain is stationary, so is $\{Y_i\}$ , and the entropy rate is well defined. The obvious approach is to compute $H(Y_n \mid Y_{n-1}, \ldots, Y_1)$ for each $n$ and take the limit.

WarningWhy the obvious approach is unusable in practice

The convergence can be arbitrarily slow, so we will never know how close we are to the limit. And we cannot use the change between consecutive values as a stopping criterion: the difference between step $n$ and $n+1$ may be tiny even when we are still far from the limit — consider $\sum \frac{1}{n}$ , whose terms shrink to zero while the sum diverges.

The fix is to bracket the limit: get a sequence converging from above and another from below, and stop when they meet.

IntuitionWhere the lower bound comes from

We already know $H(Y_n \mid Y_{n-1}, \ldots, Y_1)$ converges monotonically to $H(\mathcal{Y})$ from above (the monotonicity theorem). For a lower bound we use $H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1)$ — a neat trick based on the idea that $X_1$ contains as much information about $Y_n$ as the entire unobserved prehistory $Y_1, Y_0, Y_{-1}, \ldots$ does. Handing the estimator the hidden initial state is at least as generous as handing it the infinite past, so it over-conditions and under-estimates.

LemmaLower bound

$H(Y_n \mid Y_{n-1}, \ldots, Y_2, X_1) \le H(\mathcal{Y})$

ProofInflate the conditioning set with the hidden past, then trade it for observed past

For $k = 1, 2, \ldots$ :

$H(Y_n \mid Y_{n-1}, \ldots, Y_2, X_1) \overset{(a)}{=} H(Y_n \mid Y_{n-1}, \ldots, Y_2, Y_1, X_1)$

$\overset{(b)}{=} H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1, X_0, X_{-1}, \ldots, X_{-k})$

$\overset{(c)}{=} H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1, X_0, \ldots, X_{-k}, Y_0, \ldots, Y_{-k})$

$\overset{(d)}{\le} H(Y_n \mid Y_{n-1}, \ldots, Y_1, Y_0, \ldots, Y_{-k}) \overset{(e)}{=} H(Y_{n+k+1} \mid Y_{n+k}, \ldots, Y_1)$

Justifications:

(a) $Y_1$ is a function of $X_1$ , so adding it to a conditioning set that already contains $X_1$ adds nothing.
(b) By the Markovity of $X$ : given $X_1$ , the earlier states $X_0, X_{-1}, \ldots, X_{-k}$ are irrelevant to anything after time 1, so they can be added freely.
(c) Each $Y_i$ is a function of $X_i$ , so the $Y_0, \ldots, Y_{-k}$ are already determined by the conditioning set and add nothing.
(d) Conditioning reduces entropy, applied in reverse: dropping the $X$ ‘s can only increase the entropy. This is the one inequality in the chain, and it is where we trade the hidden states for observed symbols.
(e) Stationarity: shift every index up by $k+1$ .

Since the inequality holds for all $k$ , it holds in the limit:

$H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1) \le \lim_k H(Y_{n+k+1} \mid Y_{n+k}, \ldots, Y_1) = H(\mathcal{Y})$

∎

LemmaThe bracket closes

$H(Y_n \mid Y_{n-1}, \ldots, Y_1) - H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1) \longrightarrow 0$

ProofThe gap is a mutual information, and it is a term of a convergent series

Step 1: Recognize the gap. By the definition of conditional mutual information, the interval length is exactly

$H(Y_n \mid Y_{n-1}, \ldots, Y_1) - H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1) = I(X_1 ; Y_n \mid Y_{n-1}, \ldots, Y_1)$

So proving the bracket closes means proving these conditional mutual informations vanish.

Step 2: Bound the total information $X_1$ can ever supply. Mutual information with $X_1$ cannot exceed $X_1$ ‘s own entropy:

$I(X_1 ; Y_1, Y_2, \ldots, Y_n) \le H(X_1)$

and $I(X_1 ; Y_1, \ldots, Y_n)$ increases with $n$ (more observations can only reveal more about $X_1$ ). An increasing sequence bounded above converges, so $\lim_n I(X_1; Y_1, \ldots, Y_n)$ exists and is $\le H(X_1)$ .

Step 3: Decompose that limit with the chain rule. By the chain rule for mutual information:

$H(X_1) \ge \lim_{n \rightarrow \infty} I(X_1 ; Y_1, \ldots, Y_n) = \lim_{n \rightarrow \infty} \sum_{i=1}^n I(X_1 ; Y_i \mid Y_{i-1}, \ldots, Y_1) = \sum_{i=1}^\infty I(X_1 ; Y_i \mid Y_{i-1}, \ldots, Y_1)$

Step 4: A convergent series of non-negative terms has vanishing terms. The infinite sum is finite (bounded by $H(X_1)$ ) and every term is non-negative (mutual informations are $\ge 0$ ), so the terms must tend to $0$ :

$\lim_{n \rightarrow \infty} I(X_1 ; Y_n \mid Y_{n-1}, \ldots, Y_1) = 0$

∎

IntuitionWhy the gap must close

The hidden initial state $X_1$ holds only $H(X_1)$ bits — a finite budget. Each new observation $Y_n$ can extract some of that budget, but the extractions must sum to no more than $H(X_1)$ , so they have to die out. Eventually the observed sequence has told you everything about $X_1$ that it ever will, and knowing $X_1$ outright stops helping.

TheoremBracketing the entropy rate of a function of a Markov chain

If $X_1, X_2, \ldots, X_n$ form a stationary Markov chain and $Y_i = \phi(X_i)$ , then

$H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1) \;\le\; H(\mathcal{Y}) \;\le\; H(Y_n \mid Y_{n-1}, \ldots, Y_1)$

and

$\lim_n H(Y_n \mid Y_{n-1}, \ldots, Y_1, X_1) = H(\mathcal{Y}) = \lim_n H(Y_n \mid Y_{n-1}, \ldots, Y_1)$

IntuitionThe computational payoff

This is what makes $H(\mathcal{Y})$ actually computable. Evaluate both bounds at increasing $n$ ; they squeeze the answer from both sides, and you halt when their difference is below your tolerance — with a certified error bar, unlike the naive single-sequence approach that could stall arbitrarily far from the limit without telling you.

Hidden Markov models

DefinitionHidden Markov model

Instead of a deterministic $Y_i = \phi(X_i)$ , let each $Y_i$ be a stochastic function of $X_i$ : drawn according to $p(y_i \mid x_i)$ , conditionally independent of all other $X_j$ , $j \ne i$ . The joint law is

$p(x^n, y^n) = p(x_1) \prod_{i=1}^{n-1} p(x_{i+1} \mid x_i) \prod_{i=1}^n p(y_i \mid x_i)$

flowchart LR
  X1[X1] --> X2[X2] --> X3[X3]
  X1 --> Y1[Y1]
  X2 --> Y2[Y2]
  X3 --> Y3[Y3]

RemarkSame machinery applies

HMMs are used extensively in speech recognition, handwriting recognition and similar settings — and in our telegraph picture, an HMM is just the Markov operator seen through the noisy wire rather than through a clean deterministic collapse. The same argument used above for functions of a Markov chain carries over, and we can lower bound the entropy rate of an HMM by conditioning on the underlying Markov state. (Details left to the reader.)

Quick reference

Object	Statement	Reads as
Stationary	$\Pr\{X_1 = x_1, \ldots\} = \Pr\{X_{1+l} = x_1, \ldots\}$	The source’s statistics don’t drift.
Markov	$p(x_{n+1} \mid x_n, \ldots, x_1) = p(x_{n+1} \mid x_n)$	Dependence reaches back one step.
Stationary distribution	$\mu_j = \sum_i \mu_i P_{ij}$	The occupancy that reproduces itself.
Entropy rate (average)	$H(\mathcal{X}) = \lim \frac{1}{n} H(X_1, \ldots, X_n)$	Accounting price per symbol.
Entropy rate (marginal)	$H'(\mathcal{X}) = \lim H(X_n \mid X_{n-1}, \ldots, X_1)$	Price of the next symbol given the past.
Equality	$H(\mathcal{X}) = H'(\mathcal{X})$ for stationary processes	The two prices agree.
Markov rate	$H(\mathcal{X}) = H(X_2 \mid X_1) = -\sum_{ij} \mu_i P_{ij} \log P_{ij}$	Row entropies weighted by occupancy.
Two-state chain	$\frac{\beta}{\alpha+\beta}H(\alpha) + \frac{\alpha}{\alpha+\beta}H(\beta)$	—
Weighted walk	$H(\{W_{ij}/2W\}) - H(\{W_i/2W\})$	Edge entropy minus node entropy.
Unweighted walk	$\log(2E) - H(E_1/2E, \ldots, E_m/2E)$	—
Second law	$D(\mu_n \Vert \mu'_n) \ge D(\mu_{n+1} \Vert \mu'_{n+1})$	Relative entropy always drops; plain entropy need not rise.
Function of a chain	$H(Y_n \mid Y^{n-1}, X_1) \le H(\mathcal{Y}) \le H(Y_n \mid Y^{n-1})$	Two-sided computable bracket.

Identities and conditions to keep to hand:

Stationarity gives index shifting; Markovity gives conditioning-set truncation; conditioning reduces entropy gives every inequality in this note. Almost every proof here is some combination of those three.
Irreducible $+$ aperiodic $\Rightarrow$ unique stationary distribution, reached from any start.
Uniform stationary distribution $\iff$ doubly stochastic $P$ $\iff$ entropy genuinely increases.
$\sum_i W_i = 2W$ for an undirected graph (each edge counted at both endpoints).
Entropy rate is well defined for all stationary processes; the typical-set/AEP extension additionally needs ergodicity.

References

[[lit/cover2006-elements|Cover & Thomas, Elements of Information Theory]] — Chapter 4

Related