next up previous
Next: ancestors (9) Up: Ancestors: Commentaries on The Previous: ancestors (7)

ancestors (8)

Commentary related to Andrew Wuensche and Mike Lesser's book, ``The Global Dynamics of Cellular Automata.'' Addison-Wesley, 1992 (ISBN 0-201-55740-1) continues. Having described the line of reasoning leading to the Uniform Multiplicity Theorem, we turn to an analysis of variance, or equivalently, of the second moment of the ancestor distribution. The reason for the interest lies in the relation between zero variance and zero Garden of Eden.

Every (2,1) automaton has a pair of 4x4 matrices which can be used to count ancestors and whose tensor squares count squares of numbers of ancestors; these are the A and B matrices of previous commentaries. Individual terms in the expansion of yield the number of ancestors associated with the monomials in the expansion; A+B itself is the de Bruijn matrix D, whose powers can be calculated explicitly. Each one is double its predecessor, and in the end there is an AVERAGE of four ancestors per configuration, whatever its length. How well individual terms of the sum conform to this average is an object of study.

For the second moment, powers of are required; this is not the same as ; and therein lies a tale. What we need are eigenvalues, not forgetting the discrepancy between spectral norm and spectral radius for certain matrices. A widely used, and one of the best, estimates of the eigenvalues of a matrix is Gerschgorin's theorem, which has some alternative forms. One says that the eigenvalue is contained in a disk in the complex plane whose radius is the sum of the absolute values of the elements of some row. Not knowing which row leads to superposing the disks for each row and saying that the eigenvalue is lurking somewhere within. All of them.

Obvious variants use columns instead of rows, others center the disk on the (complex) diagonal elements, calculating the radius from the remainder of the row. It is also possible to average the rows, and it is possible to apply statistical concepts to the rows and eigenvectors themselves. Here it is useful to work with non-negative matrices, because all the numbers in the matrices can be used directly without absolute values. Furthermore, the eigenvector whose eigenvalue dominates the growth rate is non-negative, or can be normalized to be so.

Elementary statistics teaches that the average is an ideal origin for a set of data, within which the variance provides an ideal scale. Following this precept, the elements of a vector might be decomposed into an an average plus a residual. Write the column sums in a matrix as , the normalized eigenvector as (for an nxn matrix), whose Perron eigenvalue (the largest one) is . Then there is a Statistical Gershgorin Theorem which asserts

where is an angle involved in the derivation (correlation between c and x), but whose cosine is bounded between -1 and 1. For the matrices of our interest, is 1/n th the sum of their elements. For A and B, this is 1/4 the number of ancestors, and so a number ranging between 0 and 2. For , , and their sum, we have 1/16 the square of the number of ancestors. For and , the value ranges between 0 and 4 (the square of 2), while for it ranges between 2 and 4.

Of the correction terms in this formula, n can be large, the variance in column sums can be modest; and the variance in x is small, the elements themselves never surpassing 1 and averaging 1/n. The formula itself is not something that anyone would think remarkable, and one mostly hopes that either the variances are small or that runs around 90 degrees. On the other hand, when the correction IS minor, it says that an 'average' number of ancestors is the eigenvalue which determines the growth rate.

Suppose that a is the sum of the elements in A, and b is the sum of the elements in B. We have a+b=8 always. To estimate the eigenvalue of , we would then have , subject to the same constraint. The value is smallest when a=b, greatest when a=0 or b=0, symmetric between a and b.

The following table summarizes the results of a survey in which the maximum eigenvalue of each matrix was estimated by comparing the ratio of its third and fourth powers. The data was classified according to the value of a, with averages and variances for the estimated eigenvalue calculated individually for each value of a.

In addition, the value for a=b (44) was split into two groups, according to whether the eigenvalue was 2 or not.

The number in each of these categories is a binomial coefficient.

One may judge how well the estimate of matches the experimental data. It seems mostly better than 5%, and often better than 1%.

To turn the second moment into a variance, we need the relationship

Since the average is 2, and the second moment lies in the range 2-4, the standard deviation lies in the range 0-sqrt(2), with the assurance that some data are actually as far away from the mean as the standard deviation. Tchebycheff's Theorem is also pertinent, that less than of the data lies more than f standard deviations away from the mean.

The members of the group of 30 in the last table are candidates for reversible rules, and are the only (2,1) Rules for which there is no Garden of Eden. The other 40 Rules in the 44 class are balanced, in the sense that a=b and 0 has as many ancestral neighborhood as 1, namely 4 out of 8. That requirement is necessary but not sufficient.

The data which has been tabulated and discussed can also be presented as a histogram, but the limitations of a typescript prevent showing it on a printed page (although we could no doubt create an acceptable image if we really tried).

These results have been taken from two preprints which can be had upon request (with full mailing address), and were obtained by the use of the program LCAU21, for PC's, which is also available on request. Using it is non-trivial, however, due to its meagre documentation, especially in the ancestor option.

More commentary will follow.

next up previous
Next: ancestors (9) Up: Ancestors: Commentaries on The Previous: ancestors (7)

Harold V. McIntosh