Entropy Rates of a Stochastic Process

Motivation: the operator has grammar

The AEP established that $n H(X)$ bits suffice on average to losslessly encode $n$ random variables drawn from an independent and identically distributed (i.i.d.) source.

In real-world communication systems, the i.i.d. assumption is completely broken:

• Natural language has structure: A telegraph operator typing English never draws letters from an independent lottery. After typing Q, the probability of the next letter being U is virtually $1.0$. After TH, the vowel E appears far more frequently than pure chance.
• Keystrokes are temporally correlated: The current letter $X_i$ is heavily conditioned on the historical sequence that preceded it: $(X_{i-1}, X_{i-2}, \dots, X_1)$.

Because the physical source violates independence, our naive i.i.d. formula $H(X^n) = n H(X)$ fails to capture the true information content of the wire.

Stochastic Processes and Stationarity

To model temporal correlation rigorously, we move from isolated random variables to sequences of random variables indexed over time.

The first essential assumption we impose is that the statistical rules governing the source do not drift over time.

Markov Chains: Finite Memory

Stationarity eliminates time drift, but still allows dependence to reach arbitrarily far into the past (e.g., $X_n$ depending on every single character back to $X_1$).

The simplest tractable model of memory is that the next symbol depends only on the immediately preceding symbol.

This property embodies the classical principle: the future is independent of the past, given the present.

Factorization and Time Invariance

By applying the general multiplication rule of probability along with the Markov property, the joint distribution of any $n$-character sequence collapses into a simple telescoping product:

The Probability Transition Matrix

A time-invariant Markov chain on a finite alphabet $\mathcal{X} = \{1, 2, \ldots, m\}$ is completely characterized by two objects:

1. An initial distribution vector $\mathbf{p}^{(1)} = \big[\Pr(X_1 = 1), \dots, \Pr(X_1 = m)\big]$.
2. An $m \times m$ transition probability matrix $P = [P_{ij}]$, defined entrywise as:

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

A Primer on Markov Distributions: The Marginal vs. The Transitions

To understand how a Markov chain behaves over time, we must separate two distinct objects:

1. The transition rules ($P$): The fixed rules of how you move from one keystroke to the next (e.g., “if you are at Q, you go to U with probability $0.99$”).
2. The marginal distribution at step $n$ ($\mathbf{p}^{(n)}$): The actual probability of being at each letter on the $n$-th keystroke: $$\mathbf{p}^{(n)} = \big[\Pr(X_n = 1), \, \Pr(X_n = 2), \, \dots, \, \Pr(X_n = m)\big]$$

What It Means for “Marginals to Drift”

Even if the transition rules $P$ never change from minute to minute, your probability of being in state $i$ on keystroke $n$ typically changes as the chain runs.

By the law of total probability, the distribution at step $n+1$ is obtained by multiplying the distribution at step $n$ by the transition matrix: $$\mathbf{p}^{(n+1)} = \mathbf{p}^{(n)} P$$

• An example:
  Suppose our alphabet is just two states: $\{ \text{Awake}, \text{Asleep} \}$.
  The operator transitions between them with matrix $P$:

  • If Awake: $80\%$ chance to stay Awake, $20\%$ chance to fall Asleep.
  • If Asleep: $50\%$ chance to wake up, $50\%$ chance to stay Asleep.

  Now, look at what happens depending on how the day begins:

  • At step 1 ($n=1$): Suppose the operator starts $100\%$ Awake: $\mathbf{p}^{(1)} = [1.0, \; 0.0]$.
  • At step 2 ($n=2$): $\mathbf{p}^{(2)} = [1.0, \; 0.0] P = [0.80, \; 0.20]$.
  • At step 3 ($n=3$): $\mathbf{p}^{(3)} = [0.80, \; 0.20] P = [0.74, \; 0.26]$.
  • At step 4 ($n=4$): $\mathbf{p}^{(4)} = [0.74, \; 0.26] P = [0.722, \; 0.278]$.

Notice that $\Pr(X_1 = \text{Asleep}) = 0$, but $\Pr(X_2 = \text{Asleep}) = 0.20$, and $\Pr(X_3 = \text{Asleep}) = 0.26$.
Because $\Pr(X_1) \ne \Pr(X_2) \ne \Pr(X_3)$, the single-symbol probabilities drift over time. Thus, even though the transition rules $P$ are completely constant, the process is not stationary yet during this warm-up phase.

The Equilibrium / Stationary Distribution ($\boldsymbol{\mu}$)

If you let the system run for many steps ($n \to \infty$), the distribution eventually settles into a steady-state equilibrium where it stops changing. We call this fixed probability vector $\boldsymbol{\mu}$ (mu):

$$\boldsymbol{\mu} = [\mu_1, \mu_2, \dots, \mu_m]$$

It satisfies the balance equation: $$\boldsymbol{\mu} P = \boldsymbol{\mu}$$

In our Awake/Asleep example, solving $\boldsymbol{\mu} P = \boldsymbol{\mu}$ yields $\boldsymbol{\mu} \approx [0.714, \; 0.286]$.
Once the operator hits this exact distribution: $$\mathbf{p}^{(n)} = [0.714, \; 0.286] \implies \mathbf{p}^{(n+1)} = [0.714, \; 0.286] P = [0.714, \; 0.286]$$

The probabilities of being Awake or Asleep become completely identical for every subsequent step on the tape ($n, n+1, n+2, \dots$).

Why This Eliminates the Initial State Parameters

Now the parameter count makes intuitive sense:

• If the chain starts from an arbitrary initial state: An engineer must record two independent things to specify the system:
  1. The arbitrary starting distribution $\mathbf{p}^{(1)}$ ($\vert{}\mathcal{X}\vert{} - 1$ parameters).
  2. The transition matrix $P$ ($\vert{}\mathcal{X}\vert{}(\vert{}\mathcal{X}\vert{} - 1)$ parameters).
• If the process is stationary: The chain must already be running in its stationary distribution from step 1 ($\mathbf{p}^{(1)} = \boldsymbol{\mu}$). But $\boldsymbol{\mu}$ is not an independent choice, it is mathematically forced by the eigenvector equation $\boldsymbol{\mu} P = \boldsymbol{\mu}$. Because $\boldsymbol{\mu}$ is completely determined by $P$, you do not need to measure or store a separate initial state vector. Specifying $P$ automatically specifies the entire process, leaving strictly $\vert{}\mathcal{X}\vert{}(\vert{}\mathcal{X}\vert{} - 1)$ parameters.

Structural Conditions: Guaranteeing Long-Term Convergence

In our earlier Awake/Asleep example, the distribution relaxed smoothly toward $\boldsymbol{\mu} \approx [0.714, \; 0.286]$. But does every Markov chain settle into a single, predictable equilibrium?

Not necessarily. Two structural pathologies can prevent a system from forgetting where it started:

1. Disconnected islands (Reducibility): The state space splinters into separate traps.
2. Clockwork loops (Periodicity): The system oscillates deterministically forever.

To guarantee that a Markov chain converges to a single stationary equilibrium regardless of where it starts, we require two structural conditions:

(A) ⟲ 1.0        (B) ⟲ 1.0
     ▲          ▲
      \ 0.5    / 0.5
       \      /
          (C)

       1.0
  (0) ------> (1)
   ▲           |
   |___________|
        1.0

How Convergence to $\boldsymbol{\mu}$ Yields a Stationary Process

A key question remains: if our machine starts with an arbitrary distribution $\mathbf{p}^{(1)} \neq \boldsymbol{\mu}$, how does it become stationary?

Here is what this means for stationarity in practice:

1. The Warm-up Phase (Transient Non-Stationarity):
   If the operator turns on the machine in state $0$ ($\mathbf{p}^{(1)} = [1, 0]$), the probabilities of early symbols drift as the system runs: $$\mathbf{p}^{(1)} \to \mathbf{p}^{(2)} \to \mathbf{p}^{(3)} \to \dots \to \boldsymbol{\mu}$$ Because $\Pr(X_1) \neq \Pr(X_2) \neq \Pr(X_3)$, the process is initially non-stationary.
2. The Stationary Regime (After Warm-up):
   Because convergence is exponential, after a short burn-in period of $K$ keystrokes, the state distribution reaches $\mathbf{p}^{(K)} \approx \boldsymbol{\mu}$. From that moment onward: $$\Pr(X_{K+1}) = \boldsymbol{\mu} P = \boldsymbol{\mu}, \quad \Pr(X_{K+2}) = \boldsymbol{\mu} P = \boldsymbol{\mu}, \quad \dots$$ Not only are all subsequent single-symbol probabilities identical ($\Pr(X_t) = \boldsymbol{\mu}$), but all block probabilities become completely invariant to time shifts: $$\Pr(X_t = a, X_{t+1} = b) = \mu_a P_{ab} = \Pr(X_{t+l} = a, X_{t+l+1} = b)$$
3. The Engineering Shortcut:
   If the telecom system initializes the transmitter by drawing the very first symbol $X_1$ directly from $\boldsymbol{\mu}$ ($\mathbf{p}^{(1)} = \boldsymbol{\mu}$), the warm-up phase is eliminated entirely: the chain is strictly stationary from keystroke 1.

Analytical Tool: Solving for the Stationary Distribution $\boldsymbol{\mu}$

To find the equilibrium distribution $\boldsymbol{\mu} = [\mu_1, \mu_2, \dots, \mu_m]$, we must solve the vector equation:

$$\boldsymbol{\mu} P = \boldsymbol{\mu} \quad \iff \quad \boldsymbol{\mu}(P - I) = \mathbf{0}$$

subject to the normalization constraint $\sum_{i=1}^m \mu_i = 1$.

In standard linear algebra, you write this out as a system of $m$ simultaneous equations:

$$\begin{cases}\mu_1 P_{11} + \mu_2 P_{21} + \dots + \mu_m P_{m1} = \mu_1,\\ \mu_1 P_{12} + \mu_2 P_{22} + \dots + \mu_m P_{m2} = \mu_2,\\ \quad \vdots\\ \mu_1 + \mu_2 + \dots + \mu_m = 1\end{cases}$$

For large alphabets, performing Gaussian elimination on this full system is tedious. Fortunately, we can bypass matrix row-reduction entirely using a physical principle called conservation of probability flow.

The Intuition: Probability as Fluid Flow

Think of probability as physical water circulating through a network of pipes:

• Each state is a reservoir containing a fraction of water $\mu_i$.
• A transition $P_{ij}$ is a one-way pipe from reservoir $i$ to reservoir $j$ that drains a fraction $P_{ij}$ of reservoir $i$‘s contents at each tick of the clock.
• The total volume of water flowing from reservoir $i$ into reservoir $j$ in one step is called the probability flow: $$\text{Flow}(i \to j) = \mu_i P_{ij}$$

If the system has reached a stable equilibrium (the water levels $\mu_i$ never change), water cannot magically pool up or vanish.

Now imagine drawing an imaginary dividing line, called a cut, that splits all the reservoirs into two separate camps: group $S$ and group $S^c$. For the water levels on both sides to stay constant, the total water crossing the line from left to right must exactly equal the total water crossing from right to left:

$$\underbrace{\sum_{i \in S} \sum_{j \in S^c} \mu_i P_{ij}}_{\text{Total Flow Leaving Group } S} = \underbrace{\sum_{j \in S^c} \sum_{i \in S} \mu_j P_{ji}}_{\text{Total Flow Entering Group } S}$$

This is the cut-balance equation. Instead of solving $m$ simultaneous equations at once, we can often draw a simple boundary line around a single state and balance the flow in versus flow out in one line of algebra.

Example: The Two-State Markov Chain

Consider a binary telegraph operator whose key alternates between State 1 and State 2 with transition probabilities $\alpha$ and $\beta$:

stateDiagram-v2
  direction LR
  S1: State 1
  S2: State 2
  S1 --> S2: α
  S2 --> S1: β
  S1 --> S1: 1 - α
  S2 --> S2: 1 - β

The transition matrix is:

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

(Assuming $0 < \alpha, \beta < 1$, both states communicate and have self-loops $P_{ii} > 0$, guaranteeing the chain is irreducible and aperiodic).

Calculating $\boldsymbol{\mu}$ Using Flow Balance

Instead of setting up matrix algebra, draw an imaginary boundary between State 1 and State 2:

• State 1 holds probability mass $\mu_1$, and each step sends fraction $\alpha$ over to State 2:

  $$\text{Flow}(1 \to 2) = \mu_1 \alpha$$

• State 2 holds probability mass $\mu_2$, and each step sends fraction $\beta$ back to State 1:

  $$\text{Flow}(2 \to 1) = \mu_2 \beta$$

For equilibrium to hold, the rate of people switching from $1 \to 2$ must equal the rate of people switching from $2 \to 1$:

$$\mu_1 \alpha = \mu_2 \beta$$

Since the probabilities must sum to 1 ($\mu_1 + \mu_2 = 1 \implies \mu_2 = 1 - \mu_1$):

$$\mu_1 \alpha = (1 - \mu_1) \beta \implies \mu_1(\alpha + \beta) = \beta$$

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

If we initialize the machine with $\Pr(X_1 = 1) = \mu_1$, the process is strictly stationary from step 1 onward.

The Marginal Uncertainty $H(X_n)$

At any isolated single step $n$, the single-symbol uncertainty is simply the binary entropy of its marginal distribution:

$$H(X_n) = H_b\left(\frac{\alpha}{\alpha + \beta}\right) = -\frac{\beta}{\alpha + \beta}\log_2\left(\frac{\beta}{\alpha + \beta}\right) - \frac{\alpha}{\alpha + \beta}\log_2\left(\frac{\alpha}{\alpha + \beta}\right)$$

Entropy Rate: Quantifying the Growth of Uncertainty

The Engineering Problem:
When an operator punches out $n$ correlated keystrokes on a telegraph line, how does the total uncertainty $H(X_1, X_2, \dots, X_n)$ grow as the message lengthens?

An engineer pricing bandwidth or budgeting memory buffers faces two natural perspectives:

1. The Amortized (Accounting) View: “Send a block of length $n$, measure its total joint entropy, and divide by $n$.”
2. The Marginal (Streaming) View: “Condition on the entire accumulated history of the tape, and measure the uncertainty of just the next incoming symbol.”

These two perspectives lead to two distinct mathematical formulations:

These definitions describe fundamentally different operations: an arithmetic running average vs. an instantaneous incremental derivative. A central pillar of information theory is that for stationary processes, these two rates are mathematically identical.

Worked Examples of Entropy Rates

To see how the two entropy rates, the amortized batch rate $H(\mathcal{X})$ and the streaming marginal rate $H'(\mathcal{X})$ actually behave, we walk through three cases designed to answer three distinct architectural questions:

1. The Upper Bound: What is the maximum possible entropy rate an alphabet of size $m$ can physically produce?

1. The Backward-Compatibility Check: Does this new process framework match our previous i.i.d. formulas when there is no memory?

1. The Counterexample: Can an independent system break down and fail to have an entropy rate if it lacks stationarity?

Tape index n:  1 ------------> 100 --------------> 10,000 -----------> 1,000,000 -------> ...
Entropy H(X):  [ 1 1 1 1 1 1 ] [ 0 0 0 0 0 0 0 0 ] [ 1 1 1 1 1 1 1 1 ] [ 0 0 0 0 0 0 0 0 ]
Running Avg:   Rises to ~1.0    Plunges to ~0.0    Rises to ~1.0       Plunges to ~0.0   (Oscillates forever)

The Fundamental Theorem: Equality of the Rates for Stationary Sources

To prove this theorem rigorously, we establish two preliminary steps:

1. The conditional surprise sequence is monotonically decreasing and bounded below (so it must converge).
2. The running average of any convergent sequence converges to the same limit (the Cesàro mean theorem).

For a concrete picture, take the stationary two-state chain with $\alpha = 0.1$, $\beta = 0.3$ (so $\boldsymbol{\mu} = [0.75, \; 0.25]$, worked out below). The first symbol costs $H(X_1) = H_b(0.25) \approx 0.811$ bits, and every later one costs $H(X_n \mid X_{n-1}) \approx 0.572$ bits. The running average starts at the first value and creeps down to the second like $0.239/n$:

The Shannon-McMillan-Breiman Theorem (AEP for Dependent Sources)

In our previous discussion of the Asymptotic Equipartition Property, we required the source to be i.i.d. to invoke the Weak Law of Large Numbers. The Shannon-McMillan-Breiman theorem extends this result to processes with infinite temporal memory: