pyCA.measures module
Information-theoretic measures for cellular automaton histories.
A cellular automaton is a compression problem in disguise: the rule is a few bits, yet the spacetime diagrams range from dead uniformity to apparently irreducible randomness. The measures here quantify where on that range a history sits. All entropies are in bits, all distributions are estimated empirically from the supplied data, and all functions accept either a single state (1d array) or a spacetime history (2d array, time along axis 0) with periodic boundaries assumed in space.
- pyCA.measures.block_entropy(data, k=1)[source]
Shannon entropy of the length-k block distribution, in bits.
Slides a circular window of length k along each row of data, histograms the resulting k-bit words over all rows and positions, and returns the Shannon entropy of that empirical distribution. For k = 1 this is the entropy of the cell-value distribution; growth with k probes spatial correlations.
- Parameters:
data (array_like of 0s and 1s) – A state (1d) or spacetime history (2d, time along axis 0).
k (int, optional) – Block length (default 1).
- Returns:
H_k, between 0 (uniform lattice) and k (iid coin flips).
- Return type:
float
- pyCA.measures.entropy_rate(data, k=2)[source]
Estimate of the spatial entropy rate, H_k - H_{k-1}, in bits per cell.
The block entropies H_k grow at most linearly in k; their increments converge (from above) to the entropy rate, the number of new bits each additional cell carries once its neighbors to one side are known. Larger k tightens the estimate but needs exponentially more data — keep 2**k well below the number of samples.
- Parameters:
data (array_like of 0s and 1s) – A state (1d) or spacetime history (2d, time along axis 0).
k (int, optional) – Block length of the finer scale (default 2). Must be >= 1; k = 1 returns H_1 itself, the rate estimate with no conditioning.
- Returns:
h_k = H_k - H_{k-1}, between 0 and 1.
- Return type:
float
- pyCA.measures.lz_complexity(data)[source]
Normalized Lempel–Ziv (LZ76) complexity, dimensionless.
Parses each row into the phrases of Lempel and Ziv’s 1976 exhaustive history — each phrase the shortest word not yet producible by copying from what came before — using the Kaspar–Schuster scanning algorithm, and normalizes the phrase count by n/log2(n), the asymptotic count for an iid fair-coin string. A random row therefore reads near 1 and a structured one falls below. The mean over rows is returned.
Two cautions. Unlike the block measures, the parse is sequential and does not wrap: rows are read left to right. And the normalized count converges to the entropy rate from above slowly — at n ~ 1000 a fair coin still reads ~1.05 — so compare rows of equal length, not values across lengths.
- Parameters:
data (array_like of 0s and 1s) – A state (1d) or spacetime history (2d, time along axis 0).
- Returns:
Mean over rows of c(n) log2(n) / n, where c(n) is the LZ76 phrase count.
- Return type:
float
References
A. Lempel and J. Ziv, “On the complexity of finite sequences,” IEEE Trans. Inf. Theory 22, 75 (1976). https://doi.org/10.1109/TIT.1976.1055501
F. Kaspar and H. G. Schuster, “Easily calculable measure for the complexity of spatiotemporal patterns,” Phys. Rev. A 36, 842 (1987). https://doi.org/10.1103/PhysRevA.36.842
- pyCA.measures.mutual_information(data, distance=1)[source]
Mutual information between cells distance apart, in bits.
Estimates I(X; Y) = H(X) + H(Y) - H(X, Y) where X and Y are the values of two cells separated by distance sites in the same row, pooled over all rows and positions (with periodic wrapping). Zero means the cells are statistically independent at that separation; the maximum, H(X), means one determines the other.
- Parameters:
data (array_like of 0s and 1s) – A state (1d) or spacetime history (2d, time along axis 0).
distance (int, optional) – Spatial separation between the cell pair (default 1).
- Returns:
I(X; Y) >= 0.
- Return type:
float