From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Sun Jul 04 1993 - 01:33:35 UTC
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 (A+B)^n 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 AxA+BxB are required; this is not the same
as (A+B)x(A+B); 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 Ci=gamma+ci, the
normalized eigenvector as xi+1/n+ui (for an nxn matrix), whose Perron
eigenvalue (the largest one) is lambda. Then there is a Statistical
Gershgorin Theorem which asserts
lambda = gamma + n var(c) var(x) cos(theta)
where theta 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, gamma 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 AxA,
BxB, and their sum, we have 1/16 the square of the number of ancestors. For
AxA and BxB, the value ranges between 0 and 4 (the square of 2), while for
AxA+BxB 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 theta runs around 90 degrees. On
the other hand, when the corection 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 AxA+BxB,
we would then have (a^2+b^2)/16, 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.
ab number min max ave gamma
-----------------------------------------
08 1 4.000 4.000 4.000 4.000
17 8 2.938 3.381 3.102 3.125
26 28 2.400 2.800 2.580 2.500
35 56 2.132 2.695 2.253 2.125
44 70 2.000 2.480 2.155 2.000
In addition, the value for a=b (44) was split into two groups, according to
whether the eigenvalue was 2 or not.
ab number mean variance
-----------------------------------------
44 (lambda = 2) 30 2.000 0.000
44 (lambda > 2) 40 2.272 0.102
The number in each of these categories is a binomial coefficient.
One may judge how well the estimate of gamma 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
(sigma)^2 = ave(x^2) - (ave (x))^2.
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 1/f^2
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 documantation, especially in the
ancestor option.
More commentary will follow.
Harold V. McIntosh |Depto. de Aplicaci'on de Microcomputadoras
mcintosh@redvax1.dgsca.unam.mx |Instituto de Ciencias/UAP
mcintosh@redvax1.bitnet |Apdo. Postal 461
(+52+22)43-6330 |72000 Puebla, Pue., MEXICO
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:17 UTC