Information Measures

Describe a spacetime diagram cell by cell and you have described it completely. Though complete, that description is mostly data with very little information. The measures in pyCA.measures compress the data into the few numbers that matter: how unpredictable is a cell, how far do correlations reach, how many new bits does each cell carry once its neighbors are known. All entropies are in bits, and every function accepts either a single state or a full spacetime history (time along axis 0).

Block entropy

Slide a window of length \(k\) along each row, histogram the \(2^k\) possible words, and take the Shannon entropy[1] of the result: that is \(H_k\), the block entropy. For a frozen lattice it vanishes; for fair coin flips it equals \(k\); everything interesting lies between, and the gap below \(k\) measures the structure the automaton has built.

from pyCA import ECA, measures

ca = ECA(30, N=512)
ca.run(500)
st = ca.spacetime()

for k in (1, 2, 3, 4, 5):
    print(k, measures.block_entropy(st, k))

\(H_k\) never decreases with \(k\); prove this to yourself from the definition before trusting the code, which is tested for it.

Entropy rate

The increments \(h_k = H_k - H_{k-1}\) converge from above to the entropy rate: the number of genuinely new bits per cell once a cell’s context is known. It is the honest measure of randomness: rule 90’s diagram looks busy, but knowing two cells pins the third, and the rate exposes the redundancy.

print(measures.entropy_rate(st, k=5))

Estimating \(H_k\) needs enough samples to populate \(2^k\) bins; keep \(2^k\) comfortably below the number of cells in your history or the estimate biases low.

Mutual information

pyCA.measures.mutual_information() asks how much knowing one cell tells you about a cell distance sites away, \(I(X;Y) = H(X) + H(Y) - H(X,Y)\), pooled over every pair at that separation. Zero means independence; the maximum, \(H(X)\), means determination. Plotted against distance it is a correlation function with information-theoretic units:

import matplotlib.pyplot as plt

ds = range(1, 30)
plt.plot(ds, [measures.mutual_information(st, d) for d in ds])
plt.xlabel('distance')
plt.ylabel('I (bits)')
plt.show()

Lempel–Ziv complexity

The block measures see nothing longer than \(k\) cells. pyCA.measures.lz_complexity() has no such horizon: it parses each row into the phrases of Lempel and Ziv’s 1976 exhaustive history[2] - each phrase the shortest word that cannot be produced by copying from what came before - and counts them with the scanning algorithm of Kaspar and Schuster[3]. A row with structure at any length reuses its past and parses into few phrases; only genuine novelty forces new ones. The count is normalized by \(n/\log_2 n\), its asymptotic value for fair coin flips, so a random row reads near 1 and a frozen one near 0:

import numpy as np
from pyCA import ECA, measures

for rule in (0, 90, 30, 110):
    ca = ECA(rule, N=1024, rng=np.random.default_rng(1))
    ca.run(200)
    print(rule, measures.lz_complexity(ca.state))

Two cautions. The parse is sequential, not circular, so rows are read left to right. And the normalized count converges to the entropy rate from above slowly - at \(n \sim 1000\) a fair coin still reads about 1.05 - so compare rows of equal length rather than values across lengths.

A classification experiment

Wolfram’s four classes were assigned by eye. Assign them by number instead: for each rule in a sample, run a random initial condition, discard the transient, and place the rule on the (entropy rate, mutual information) plane. Class I collapses to the origin, Class III crowds the high-rate edge, and Class IV - the computing class - lives where the entropy rate is moderate but the mutual information refuses to die. There is a lot of unexplored territory in that plane; keep a journal of what you find in it.