Probability-based entropies

This section has concentrated on characterizing what sequences can possibly occur in 1D cellular automata, with no regard to their probability. It turns out to be difficult to extend the discussion of networks to include probabilities in a rigorous way. But it is straightforward to define versions of entropy that take account of probabilities—and indeed the closest analog to the usual entropy in physics or information theory is obtained by taking the probabilities p[i] for the kⁿ blocks of length n (assuming k colors), then constructing

-Limit[Sum[p[i] Log[k, p[i]], {i, kⁿ}]/n, n  ∞]

I have tended to call this quantity measure entropy, though in other contexts, it is often just called entropy or information, and is sometimes called information dimension. The quantity

Limit[Sum[UnitStep[p[i]], {i, kⁿ}]/n, n  ∞]

is the entropy discussed in the notes above, and is variously called set entropy, topological entropy, capacity and fractal dimension. An example of a generalization is the quantity given for blocks of size n by

h[q_, n_]:= Log[k, Sum[p[i]^q, {i, kⁿ}]]/(n(q - 1)

where q = 0 yields set entropy, the limit q1 measure entropy, and q = 2 so-called correlation entropy. For any q the maximum h[q, n]  1 occurs when all p[i]  k^-n. It is always the case that h[q+1, n] ≤ h[q, n]. The h[q] have been introduced in almost identical form several times, notably by Alfréd Rényi in the 1950s as information measures for probability distributions, in the 1970s as part of the thermodynamic formalism for dynamical systems, and in the 1980s as generalized dimensions for multifractals. (Related objects have also arisen in connection with Hölder exponents for discontinuous functions.)