For and a finite measurable partition , . The backward conditional entropy chain rule expresses the left side as . Each term equals by measure preservation and the infinite-future formula for partition entropy rate. No invertibility is needed.
If an invertible probability measure-preserving system has a finite one-sided generator , then its future sigma-algebra equals modulo null sets. Hence , and the infinite-future formula for partition entropy rate and Kolmogorov-Sinai generator theorem give . Invertibility matters: a fair binary one-sided Bernoulli shift has entropy and a finite one-sided generator.
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 108 3 Solution Created 2026-10-03 Updated 2026-10-05
On a probability measure-preserving system, for a finite measurable partition , the entropy of a finite measurable partition isUse natural logarithms, so information entropy is measured in nats; another fixed logarithm base rescales all answers. The join of measurable partitions is their common refinement, and write , with an empty join the trivial partition. The entropy rate of a measurable partition and Kolmogorov-Sinai entropy are respectivelyThe block entropies form a subadditive sequence, so the first limit exists by the Fekete lemma. For finite partitions the conditional entropy of finite measurable partitions is .
Put and for . The chain rule for information entropy, applied from the last coordinate backwards, and measure preservation giveThe second equality uses invariance of the joint partition atom probabilities under the common pullback ; invertibility is unnecessary. Since conditioning reduces entropy, decreases to a nonnegative limit . The Cesaro convergence of a sequence of this convergent sequence has the same limit. ThereforeEquivalently , where . Here conditional entropy of a countable measurable partition conditioned on a sigma-algebra is computed using conditional partition atom probabilities; the Martingale convergence theorem gives continuity under increasing conditioning sigma-algebras. This is the infinite-future formula for partition entropy rate.
The Kolmogorov-Sinai generator theorem states that if a finite or countable measurable partition has finite entropy of a countable measurable partition and its iterates generate the whole completed sigma-algebra modulo null sets, then . For an invertible system, generating means modulo null sets. For a noninvertible system a one-sided generator, using , suffices. The two-sided and one-sided versions must not be confused.
For a Bernoulli shift with discrete symbol probabilities , the coordinate-zero measurable partition has independent coordinate iterates. ThusFor a finite alphabet the coordinate partition is a generator of finite entropy of a finite measurable partition; on the two-sided sequence space use all integer coordinate iterates, and on the one-sided space use the nonnegative ones. The Kolmogorov-Sinai generator theorem proves the displayed answer in both cases. The same calculation applies to countably many symbols when their Shannon entropy is finite, using the countable finite-entropy version of the theorem. If the Shannon entropy is infinite, merge all but the first symbols into one cell. These finite coordinate partitions have entropy rate , so the system entropy is infinite. Zero-probability symbols contribute zero. In particular a fair -symbol shift has entropy .
For the final assertion, let and complete it modulo null sets. The approximation property forces modulo null sets. Indeed for each , choose approximating sets from finite blocks with error tending to zero. Their indicators approach in , and is a closed vector subspace, so is -measurable modulo a null set.
Invertibility now gives modulo null sets. In particular the present partition is measurable with respect to its entire future, so . The infinite-future formula gives . Since the given one-sided generator is also a two-sided generator, the Kolmogorov-Sinai generator theorem finishes the proof:This is finite one-sided generator of an invertible system forces zero entropy. Invertibility is essential: a fair binary one-sided Bernoulli shift has a finite one-sided generator and Kolmogorov-Sinai entropy .