Next: Mean field theory Up: Probabilistic evolution matrix Previous: Probabilistic evolution matrix

Regularities and anomalies

There are both temporal and spatial correlations; we have seen how the latter can be estimated by the probabilistic version of the de Bruijn diagram. It is interesting that the most serious logical discrepancy in probabilistic estimates arises from the excluded states which can be determined from the subset construction. Exclusion amounts to assigning a probability of zero, but zero probabilities cannot arise in probabilistic calculations. which involve only sums and products of positive quantities. Thus calculations based on the probabilities of individual cells will not suffice, and strings of cells must be taken into account from the outset.

Since there are arbitrarily long strings which are excluded for the first time (which is to say that none of their shorter segments is excluded, but that they are) it would seem that no theory based on the extrapolation of probabilities from finite strings could be mathematically exact. Nevertheless it can be hoped that there is a degree of approximation which is sufficient for practical purposes, but still not so complicated as to be beyond reasonable access.

For example, 10101001 is an excluded word for Rule 22, but it would have a probability of if zeroes and ones were considered equally probable. This is not the worst distortion which Rule 22 suffers, because the distribution of frequencies for other short sequences of is by no means uniform, much less a simple function of the number of zeroes and ones they contain. For example, segments of the form are generally hard to come by, inasmuch as that is a sequence which it is its only ancestor. Most rules have their own excluded words, some of them even shorter than the eight letters which form the shortest excluded words for Rule 22.

In its probabilistic version, the de Bruijn diagram serves to predict the probabilities of the possible sequences comprising a shifting window in a long chain of states, and thus the correlations between such a sequence and a similar one occurring somewhere else in the chain. The conclusion afforded by the Frobenius-Perron theory is that there will always be an equilibrium vector of probabilities, that under certain circumstances will be unique. The particular form of the de Bruijn matrix shows that the lack of any extreme bias is sufficient to make the equilibrium unique; also that any zero biases will result in zero eigenvalues. We even know that the equilibrium probabilities are the n-block probabilities if the de Bruijn matrix is derived from -block probabilities.

Although the disequilibrium eigenvalues and eigenvectors do depend in detail upon the transition probabilities of each particular diagram, the general conclusion is that the greater the bias the slower the approach to equilibrium, the node with the least bias establishing an upper limit to the speed. Zero bias results in an immediate equilibrium which may be accompanied by degenerate eigenvectors, while extreme bias offers the only possibility of alternate equilibria.

Whatever may be the spatial correlations of the moment, it is time evolution which drives the statistics of a linear automaton, continually challenging any correlations or lack thereof which may be found in the spatial distribution of the cells. Consequently we should look for probabilities, either of single cells or correlated probabilities of sequences of cells, which are consistent with the rule of evolution of the automaton.

Next: Mean field theory Up: Probabilistic evolution matrix Previous: Probabilistic evolution matrix

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx