Can two feeds have the same symbol frequencies but different rates?

Yes. The fictional Markov and independent feeds illustrate this.

Is the rate always measured per second?

No. Here it is per observation.

Does knowing one previous state always suffice?

Only for models with the relevant first-order Markov property, not arbitrary processes.

AI Glossary / Mathematics and optimization / Advanced

Entropy rate

Definition

Entropy rate is the limiting average uncertainty per observation in a stochastic process. For discrete variables X1, X2, and so on, it is defined as lim_n H(X1,...,Xn)/n when that limit exists. With base-two logarithms, its unit is bits per observation. It accounts for dependence across observations, so it can differ substantially from the entropy of a single observation considered alone.

What it means

A sequence can use many possible symbols while remaining highly predictable once its past is known. Entropy rate distinguishes that situation from a sequence that keeps introducing fresh uncertainty. It asks how much uncertainty accumulates per observation over long blocks, rather than how diverse the overall symbol counts appear.

This entry concerns discrete processes with a finite alphabet. For stationary processes in this setting, the limit exists. Stationarity means that shifting the time origin does not change the joint distributions. It does not mean that successive observations are independent or that every individual sequence looks constant.

How it works

The entropy chain rule expresses block entropy as the entropy of the first observation plus successive conditional entropies given the past. For a stationary finite-alphabet process, the limiting conditional entropy equals the entropy rate.

For independent, identically distributed observations, the rate equals their single-observation entropy. For a stationary first-order Markov chain, only the previous state is needed for the next-state distribution. Its entropy rate is the stationary-probability-weighted average of the transition-row entropies.

These formulas describe a specified probability model. Estimating the rate from a recorded sequence requires additional statistical choices. A short record, an incorrect Markov assumption, or changing transition behavior can undermine a numerical estimate even when the formula is applied correctly.

Three practical examples

1. Equipment status: A machine reports either idle or active. Its overall status proportions do not reveal how frequently it switches. Two machines with the same proportions can have different entropy rates because one stays in long runs while the other changes less predictably.

2. Text streams: Letter frequencies describe individual-symbol uncertainty. Predictability from preceding letters or words introduces sequence structure. A model that ignores that context answers a different question from one intended to capture uncertainty per symbol after accounting for the past.

3. Synthetic test data: One generator emits independent fair bits. Another chooses a fair initial bit and then alternates deterministically. Both have a fair marginal distribution at each position. The first has entropy rate one bit per symbol; the second has rate zero because its entire sequence is determined by the initial choice.

Think of it this way

Think of a story that begins with a coin toss and then follows a fixed script. The opening contains uncertainty, but adding more scripted pages does not keep adding new uncertainty. Compare that with a story decided by a fresh independent coin toss on every page. Entropy rate distinguishes their long-run uncertainty per page.

Worked example

Consider an original two-state Markov model with states 0 and 1. From state 0, the next state is 0 with probability 0.9 and 1 with probability 0.1. From state 1, it is 0 with probability 0.3 and 1 with probability 0.7.

Start the chain in its stationary distribution: P(0) = 0.75 and P(1) = 0.25. Check the next probability of state 0: 0.75(0.9) + 0.25(0.3) = 0.75, as required.

The transition-row entropies are approximately 0.4690 bits for state 0 and 0.8813 bits for state 1. The entropy rate is therefore 0.75(0.4690) + 0.25(0.8813) = 0.5721 bits per observation, using unrounded values in the calculation.

The single-observation entropy is instead -0.75 log2(0.75) - 0.25 log2(0.25) = 0.8113 bits. For a block of n observations, the chain rule gives H(X1,...,Xn) = 0.811278 + (n - 1)(0.572069).

For four observations, block entropy is approximately 2.5275 bits, or 0.6319 bits per observation. For ten, it is approximately 5.9599 bits, or 0.5960 per observation. These averages approach 0.5721 as the initial-state contribution is spread across longer blocks. Direct enumeration of the model's possible blocks confirms the calculations.

Illustrative case study

In a fictional monitoring service, an analyst compares two binary status feeds. Both show state 0 about three quarters of the time. Feed A follows the Markov model above. Feed B consists of independent observations with probabilities 0.75 and 0.25.

A dashboard based only on overall frequencies assigns both the same marginal entropy, approximately 0.8113 bits. The analyst explains that the modeled entropy rates differ: about 0.5721 for A and 0.8113 for B. A's previous state helps predict its next observation.

The team retains both measures and their definitions. It also checks whether the observed transition patterns remain stable across operating shifts. The exercise does not prove that one feed is more valuable or that a particular compressor will attain the theoretical rate in production.

Common misconceptions and mistakes

A high single-symbol entropy does not imply a high entropy rate. A zero entropy rate does not require every symbol to be constant: the randomized alternating sequence is a counterexample. Stationarity does not imply independence.

Do not call a four-observation average the limiting rate without justification. Avoid mixing bits per observation with bits per second; converting between them requires a defined observation frequency. A fitted transition matrix also needs validation before its calculated rate is treated as a faithful description of a changing process.

Business use

Entropy rate can help technical teams study temporal predictability in telemetry, communication streams, and modeled workloads. Useful reports distinguish marginal diversity from sequential uncertainty and state the sampling interval, alphabet, model, and estimation method. The result can inform further compression or forecasting analysis, but it does not directly measure business value, forecast error, or achieved storage savings.

Check your understanding

What is the worked model's entropy rate?

Answer: Approximately 0.5721 bits per observation.

Why is the four-observation average higher?

Answer: It still includes the initial-state uncertainty divided across a short block.

Why does deterministic alternation with a random initial bit have zero rate?

Answer: Block uncertainty stays at one bit while block length grows.

Related terms

Learn next

Recalculate the worked example with different switching probabilities. Solve for the corresponding stationary distribution before averaging transition-row entropies. Then compare short-block averages with their limiting value and examine what changes when observations cease to be stationary.

Stationary distribution

Sources

Yury Polyanskiy and Yihong Wu, MIT 6.441 Information Theory course notes, Section 5.5, entropy-rate definition and stationary-process examples: https://ocw.mit.edu/courses/6-441-information-theory-spring-2016/5d8f16adc3385c9ff2975b121bd620e4_MIT6_441S16_course_notes.pdf

The numerical Markov model and fictional monitoring case are original illustrations.

Previous: Entropy power inequality Next: Entropy search