next up previous
Next: Automata which are Up: What has not Previous: What has not

Convergence of block probabilities

Kolmogoroff's theorem asserts that a family of consistent measures converges to a limit measure. Gutowitz et.al. [34] use this result to assure a meaningful construction of a system of equations for self consistent neighborhood probabilities, wherein extrapolation via Bayes' theorem yields probabilities for the counterimages of individual neighborhoods. They incidentally remark that the Bayesian extension yields maximum entropy; in other words, the least additional information about the extension.

However, each different length of neighborhood, or order, possesses its own set of equations defining self-consistency, making the measure deduced vary from one order to the next. It would be desirable to have an estimate of how much these measures can differ from one another, to know whether the sequence of measures deduced from successively longer neighborhoods can be demonstrated to converge to a unique limit, and at what point a desired degree of accuracy has been reached.

The approach of Gutowitz et.al. was to select rules for study, keep using longer blocks until the results stabilized, and apply statical tests for goodness of fit between the result and empirical observations. In its context, this is an entirely valid methodology. But each rule needs its own analysis; some rules seem to be much more amenable to the procedure than others.

As an idea of the hazards which are to be encountered, consider the Garden of Eden states. They can be described in terms of excluded sequences, which necessarily have probability zero. Nevertheless a zero probability cannot be obtained via Bayesian extrapolation from the probabilities of shorter blocks not from the Garden of Eden, so that explicit block probabilities at least as long as the shortest excluded sequences are required. However, there is not necessarily a ``longest shortest excluded block,'' so that there may be no finite approximation at all which is logically correct. In practice, the excluded sequences may already be assigned such small probabilities by local field theories of low order that their nonvanishing would never be detectable.

In point of fact, each periodic configuration of the automaton gives rise to a discrete measure concentrated on the orbit of that particular configuration, so that without further restrictions, the determination of a measure is not at all unique. Likewise there are rules of evolution based on the linear algebra of finite fields for which periodicities of one sort or another are so scrupulously observed that the measures also retain a thoroughly discrete structure.

No wonder that it would be nice to have a more comprehensive understanding of invariant measures and their relationships to one another. Especially with respect to establishing error bounds.



next up previous
Next: Automata which are Up: What has not Previous: What has not



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