Probabilistic estimates [of cellular automaton properties]
One way to get estimates for density and other properties of class 3 cellular automata is to make the assumption that the color of each cell at each step is completely random. And with this assumption, if the overall density of black cells at a particular step is p, then each cell at that step should independently have probability p to be black. This means that for example the probability to find a black cell followed by two white cells is p (1 - p)2. And in general, the probabilities for all 8 possible combinations of 3 cells are given by
probs = Apply[Times, Table[IntegerDigits[8 - i, 2, 3], {i, 8}] /. {1 p, 0 1 - p}, {1}]
In terms of these probabilities the density at the next step in the evolution of cellular automaton with rule number m is then given by
Simplify[probs . IntegerDigits[m, 2, 8]]
For rule 22, for example, this means that if the density at a particular step is p, then the density on the next step should be 3 p (1 - p)2, and the densities on subsequent steps should be obtained by iterating this function. (At least for the 256 elementary cellular automata this iterated map is never chaotic.) The stable density after many steps is then given by Solve[3 p (1 - p)2 p, p], so that p 1 - 1/√3 or approximately 0.42. The actual density for rule 22 is however 0.35095. The reason for the discrepancy is that the probabilities for different cells are in fact correlated. One can systematically include more such correlations by looking at more steps of evolution at once. For two steps, one must consider probabilities for all 32 combinations of 5 cells, and for rule 22 the function becomes p (1 - p)2 (2 + 3p2), yielding density 0.35012; for three steps it is p (1 - p)2 (p4 - 18 p3 + 41 p2 - 22 p + 6) yielding density 0.379. The plot below shows what happens with more steps: the results seem to converge slowly to the exact result indicated by the gray line.
(For rules 90 and 30 the functions obtained after one step are respectively 2 p (1 - p) and p (2 p2 - 5 p + 3), both of which turn out to imply correct final densities of 1/2).
Probabilistic approximation schemes like this are often used in statistical physics under the name of mean field theories. In general, such approximations tend to work better for systems in larger numbers of dimensions, where correlations tend to be less important.
Probabilistic estimates can also be used for other quantities, such as growth rates of difference patterns (see page 949). In most cases, however, buildup of correlations tends to prevent systematic improvement of such approximations.