For various reasons, the statistical properties of the evolution of cellular automata have attracted attention. That there are statistical properties to be investigated is immediately apparent whenever there are graphical means available to display the evolution, such as can be done readily with most computers nowadays. Typically, if an initial configuration is randomly chosen, it quickly develops a characteristic texture which persists until the inevitable cycles make their appearance and dominate the evolution; thus there are usually two inherent time scales and three textures associated with the evolution of any given automaton.
The first phase can be orderly or random, in either event reflecting the details of the initial pattern or random number generator used to produce it. Its duration gives some idea of the incompatibility between the evolutionary rule and the initial arrangement; for random patterns the time is typically quite short, but for quiescent automata with a recognizable ``velocity of light,'' a reasonable propagation time must be allowed for quiescent regions to feel the influence of their neighbors.
One would like to think that there might be a ``self consistent probability'' associated with any particular evolutionary rule, but calculations based on the simple rules applicable to independent probabilities produce indifferent results, traditionally disclaimed by invoking unaccounted correlations. Evidently an appeal must be made to more elaborate statistical concepts if better results are required; the crude theory usually produces results which match observations at the level of 10% to 20% error, which is often considered adequate.
Otherwise it is necessary to investigate measures which commute with the evolution or are otherwise related to it. Related concepts such as entropy are also relevant, and can also be studied. One of the first studies to be made was that of Schulman and Seiden[62], who tried to explain their measurements of Conway's Life . Later Dresden and Wong[24] made corrections for correlations, but the most comprehensive studies have been made by Wilbur, Lippman and Shamma[69], and then by Gutowitz, Victor and Knight[34].
There are actually three or four levels at which self consistent probabilities can be approached. All of them involve comparing the probability that a cell lies in a certain state with the probability that the cells in the neighborhood are in just the states in which they are found. Self consistency requires that the two probabilities agree, but the methods differ in the way that the probabilities are estimated.
The simplest comparison is to ask how many of the possible neighborhoods can evolve into the state in question; the answer may range from `none' through `an equal share' to `all of them'. The uniform fields resulting from the extremes produce no surprise, a state with scarcely any ancestors would not be expected to be very common, while a democratic assortment of rules would lead one to expect a representative mix of states. In general terms these expectations are seem to be confirmed by experience and are thus well founded.
It is a general statistical principle that the variance in averages decreases inversely as the square root of the sample size; as applied to the evolution of automata it is possible to obtain very stable frequencies for the occurrence of the different states by collecting them from an automaton with a very large number of states -- say a thousand or more. When this is done, discrepancies of tens of percent are found with respect to estimates by rule of thumb, such as counting transition rules.
The next level of self consistency consists in estimating the probability of a neighborhood by combining the probabilities of its cells according to the traditional rules, while assuming the validity of the traditional assumptions of independence. Called mean field theory, it provides polynomial equations to be solved for the self consistent probabilities. Indeed, the simpler estimate is just the probability that would be assigned the standard distribution -- the one in which all states have the same probability -- and thus could be the starting point for an iterative solution of the mean field equations.
Empirically mean field theory provides better frequencies, but not all automata perform equally well and discrepancies still range on the order of 10% or so, a useful but hardly a precision result. So the next level concentrates on taking correlations and other factors into account. The block structure theory of Gutowitz et.al. is based on Bayesian extension; empirical studies have shown that by taking into account probabilities of blocks of six, eight, ten or more cells, frequencies can be matched to two or more figures. The self consistency equations involve rational fractions rather than polynomials, and can also be solved by iteration.
The final level would be to obtain the invariant measure of the automaton, but having to describe it numerically leaves one on the level of local structure theory with very long blocks. Whatever the level of detail at which they are attempted, it would seem that the probabilistic approach is a significant alternative, and a complement to, the point of view of formal language theory.