The ergodic hierarchy
Ergodic
Weak mixing
Strong mixing
K-system
Bernoulli
After n steps, C₀ is a particle’s starting grid cell and Cₙ is its current cell. Probabilities refer to a particle chosen uniformly from the sample.
Cell-return correlation
This measures how much more or less often particles return to their starting cell than independent sampling would predict.
q is the total number of cells in the selected grid. P(Cₙ = C₀) is the fraction of particles in their starting cell after n steps. R = 1 means all particles return. R = 0 means the return fraction matches independent sampling, which is 1/q. Negative values mean fewer returns.
Coarse memory
This measures how much a particle’s current cell reveals about its starting cell.
H(C₀) measures the diversity of starting cells across all particles. H(C₀ | Cₙ) measures that diversity among particles sharing a current cell, averaged across current cells in proportion to their particle counts.
Here, diversity is measured by Shannon entropy: it is zero when all particles share one starting cell, and largest when they are evenly distributed among all starting cells.
M = 1: each current cell contains particles from just one starting cell. M = 0: each current cell contains the same proportions from each starting cell as the whole sample.
Time-average error
This measures how far each particle’s time spent in each cell departs from an equal share, averaged over all particles.
q is the total number of grid cells. vc(n) is the fraction of a particle’s recorded positions that lie in cell c, counting steps 0 through n. The equal share is 1/q.
The formula adds the absolute differences from that equal share and divides by two. ⟨…⟩ averages the result over particles.
D = 0 means every particle has spent an equal fraction of time in every cell. Larger values mean more uneven visits.
Bernoulli ⇒ K ⇒ strong mixing ⇒ weak mixing ⇒ ergodic
T is the evolution map: T(x) is the position of a point x after one step, and Tⁿ(x) is its position after n steps.
μ is the probability measure on the state space: μ(A) is the probability that a point sampled from this distribution lies in the measurable region A. Here, μ is uniform area measure, so μ(A) equals the area of A divided by the area of the whole square.
Each map preserves μ: a point initially sampled from μ still has distribution μ after any number of steps.
x is the starting point and N is the number of recorded positions. The recorded positions are x, T(x), …, Tᴺ⁻¹(x).
Non-ergodic
The space splits into parts that trajectories never cross between.
There is a measurable region A with 0 < μ(A) < 1 that is invariant: points inside stay inside, and points outside stay outside, apart from exceptions of measure zero.
The equality is understood up to a set of measure zero.
Ergodic
Almost every trajectory visits each fixed region in proportion to its measure.
For every measurable region A, and for almost every starting point x, the fraction of recorded positions lying in A converges to μ(A).
Here, # counts how many of the first N recorded positions lie in A.
Weak mixing
For any two fixed regions, the average departure from independence tends to zero, although substantial dependence may still recur at arbitrarily long time gaps.
For measurable regions A and B, the measure of points that start in A and reach B after n steps is μ(A ∩ T⁻ⁿ(B)). Independence would give μ(A)μ(B). Weak mixing requires the average absolute difference between these quantities to tend to zero.
T⁻ⁿ(B) is the set of starting points that reach B after n steps.
Strong mixing
For any two fixed regions, dependence becomes arbitrarily small and remains that small at every sufficiently long time gap.
For measurable regions A and B, the measure of points that start in A and reach B after n steps approaches the independent value μ(A)μ(B). Once the difference falls below any chosen positive bound, it stays below that bound at every sufficiently late step.
T⁻ⁿ(B) is the set of starting points that reach B after n steps.
K-system
However you divide the space into finitely many regions of positive measure, with at least two regions, the complete record of previous visits cannot always determine which region comes next.
Choose any such division into disjoint measurable regions covering the space. Record the region occupied at each step. Even given the entire past record, the next region has positive conditional entropy: its label is not determined with certainty for all histories except a set of measure zero.
S₀ is the current region label; S₋₁, S₋₂, … are the previous labels. The conditional entropy measures the information still needed to specify the current label after the previous labels are known, averaged over histories. K stands for Kolmogorov.
Bernoulli
The system has a complete description in which successive observations are independent repetitions of the same random experiment.
There is a finite or countable division of the state space into disjoint measurable regions such that recording the region occupied at each step produces independent outcomes. Knowing any previous outcomes leaves the probabilities of the next outcome unchanged. This division must also give a complete description: the record of regions visited at all past and future steps determines the starting point, apart from exceptions of measure zero.
Sₙ is the region occupied at step n, and pₐ is the measure of region a. For every length k and every choice of region labels, the probability of the whole sequence equals the product of the individual probabilities.
Bernoulli systems therefore admit a description whose observations form an independent, identically distributed Markov process.
About the experiment and references
The six views share 1,400 points sampled by seeded stratification. Changing the grid assigns each point a new starting-cell colour and uses that same partition to measure its current cell. In Cells mode, each cell is divided into bars proportional to its colour counts, ordered by starting cell from left to right and bottom to top.
Each map preserves uniform area. Independent starting and current cells therefore match with probability 1/q. Cell-return correlation measures excess agreement above this rate; its range is −1/(q − 1) to 1. Coarse memory measures any dependence between the cells. A permutation that moves every cell elsewhere gives R = −1/(q − 1) but M = 1. Zero return correlation need not mean independence. The reference rate uses uniform area, rather than fitted sample frequencies.
Time-average error uses each particle’s n + 1 observed positions, from step 0 through step n. It is the total variation distance between that particle’s cell-visit frequencies and the uniform distribution, averaged over particles. Absolute deviations are calculated before averaging, so particles confined to different regions cannot cancel each other’s errors. Ergodicity implies D(n) → 0 for every fixed grid in the infinite-time limit; a finite trace does not establish ergodicity.
Maps used above
Non-ergodic. Horizontal shear: x increases by 0.071 + 0.11y at each step; y stays fixed.
Ergodic. Add (√2 − 1, √3 − 1) modulo 1. This irrational translation is ergodic, but its rigid pattern keeps returning: it is not weakly mixing.
Weak mixing. Chacon repeats one rule: cut into three, add one level above the middle part, then stack. Repetition creates the fine structure. Applied independently to x and y, it is weakly mixing but not strongly mixing.
Strong mixing. The staircase construction uses 2, then 3, then 4, … cuts, adding 0, 1, 2, … levels above successive pieces. Applied to both coordinates, it is strongly mixing. Its entropy is zero, so it is not K.
K-system. Kalikow’s walk moves left or right through a fixed sequence of binary labels. Revisiting a site reveals the same label. Here x encodes the steps and y the labels viewed from the walker. This system is K but not Bernoulli.
Bernoulli. The baker map stretches the square horizontally, cuts it in half, then stacks the halves. Binary digits pass from x to y. Under uniform area measure, these digits are independent fair bits.
The first five examples fail the next stronger condition. The Chacon and staircase towers are extended until every displayed path avoids the top; no periodic closure is used.
The K example is Kalikow’s T,T⁻¹ system. Each coordinate encodes a two-sided binary sequence in the order 0, +1, −1, +2, −2, … . One step shifts the x-sequence forward and shifts the y-sequence left or right according to the current x-bit. The sequences are sampled once; no new randomness enters during motion. All digits needed for the 64-step display are retained.
Kalikow and baker use 192-bit initial coordinates. Curves use integer steps; animation illustrates the transitions. Chacon and staircase motion is shown horizontally, then vertically, to separate the two coordinate operations. The panels share samples and observation grids, but their coordinate representations differ: visual complexity and the speed of a finite correlation trace do not order the hierarchy.
The hierarchy concerns invertible, measure-preserving maps on standard probability spaces. Regions and codings are measurable; statements ignore sets of probability zero. Its definitions concern all regions and arbitrarily long times. Sample estimates have finite-size error; memory estimates have upward bias, which grows with finer partitions.
For an outcome Z with probabilities pz, Shannon entropy is
To compute H(C₀ | Cₙ), calculate the entropy of the starting-cell labels within each current cell, then average over current cells in proportion to their particle counts. The K definition uses the same conditional entropy with the entire past label sequence given; equivalently, it requires positive entropy rate for every finite partition with at least two regions of positive measure.
References
The Ergodic Hierarchy, Stanford Encyclopedia of Philosophy: the hierarchy, its mathematical definitions and its interpretation in physics.
Darren Creutz, Ergodic Theory of Group Actions, §§3, 5.2 and 6: ergodicity, cutting and stacking, weak mixing and Chacon’s transformation.
Boris Hasselblatt and Anatole Katok, Principal structures, in Handbook of Dynamical Systems: entropy, K and Bernoulli systems.
Darren Creutz and Cesar Silva, Mixing on Rank-One Transformations: the staircase construction and its mixing property.
Steven Kalikow, T, T⁻¹ transformation is not loosely Bernoulli, Annals of Mathematics 115 (1982), 393–409: the K but non-Bernoulli example. Christopher Hoffman’s scenery-factor paper gives the explicit transformation.
Cosma Shalizi, Information Theory I: entropy, conditional entropy and mutual information.