From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Tue Jul 06 1993 - 04:18:43 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. We have described a 'statistical Gershgorin theorem' which
implies a maximum eigenvalue for a matrix related to an average row (or
column) sum with an error term which may or may not be easy to estimate.
Applied to (2,1) automata, it implies that the A and B matrices which
have been introduced will have an eigenvalue between 1 and 2, namely n/4,
where n is the least amongst number of ancestors of 0 (called a) or of 1
(called b), respectively. The result is not too surprising, but also refers
to the growth in the number of ancestors of a string of pure 0's or pure 1's.
We want the rate of growth of mixtures, without knowing too much about
the mix except maybe its percentage composition.
Eigenvalue 1 means the number of ancestors remains constant as the length
of the configuration grows; eigenvalue 2 means it doubles with each new
cell. As we said, no surprise here.
Turning to the pair matrix AxA+BxB, which is also the second moment matrix,
the same reasoning gives us eigenvalues in the range 2 to 4, namely
(a^2+b^2)/16. Whereas the average (first moment, computed from A+B), just
doubles as the number of cells increments, the second moment AT LEAST
doubles (when the ancestors are balanced) reaching a factor of 4, or
quadrupling, in the cases of extreme unbalance in rules 0 or 255.
In addition, numerical experiments show that (a^2+b^2)/16 is a good estimate
of the rate of increase; for a given a the rate has an average close to the
value in this formula with a small variance of its own (a variance in the
variance, if you wish).
Turning the second moment into variance and thence into standard deviation,
there are still some approximations to be made.
sigma = sqrt (g^2(a^2+b^2)/32)^n - 4)
the denominator 32 results from having to divide by 2^n, the number of
configurations. The coefficient g is a correction due to the smaller
eigenvalues of AxA+BxB, which interfere with the principal eigenvalue
at first. Unless a=4, making us raise 1 to a power, subtracting 4 makes
little difference.
So, except for a factor, sigma is a number between 1 and 2, raised to the
n/2 power (or, between 1 and 1.41 raised to the nth power).
Is this result credible? Is it useful? Rule 0 in a ten-cell automaton
shows 1023 configurations with 0 ancestors, 1 with 4096 ancestors. This
works out to a standard deviation of about 128. At the other extreme,
Rule 150 has 4 ancestors per configuration, and zero standard deviation.
For Rule 22, we have (1.06)^(n/2), or about 3% increase for each additional
cell. Six percent interest doubles your money in ten or twelve years, so we
expect the standard deviation to double for each additional 20 to 25 cells
in the configuration. The same would be expected for all the 112 (2,1) rules
with unit imbalance, that is, ab=35.
eigenvalue = distance
ab growth of needed to
sigma^2 double sigma
-----------------------------------------------
08 2.0 2
17 1.62 3
26 1.25 6
35 1.06 25
44 1.00 infinite
Here we have seen that the statistics of ancestors depends on the
neighborhood count by states in two ways. First, the dominant eigenvalue
of the de Bruijn fragments is a direct function of this count - a multiple,
in fact. Consequently the rate of growth for the number of ancestors of
a string of like cells depends on the fraction of neighborhoods leading to
that state. The biggest fraction always wins, in accordance with the
principle that 'them as has, gets.' Moreover, mixed strings predominate
pretty much according to their mix of the dominant state.
Such general statements are always subject to refinement and correction,
but the overall principle is pretty well justified.
The second aspect of the statistics of ancestors that has been discussed is
their variance, which depends on the sum of squares of percentages - again,
on Langton's parameter. Variance grows as the length of a string of cells
grows, although never as fast as the number of configurations, the same which
is true for the number of ancestors itself. Longer strings can have more
(and less) ancestors than the average. The average is small, so much less
is hard to come by; neverless the concept is interesting for reversible
and 'almost reversible' automata.
In applying this analysis to the Atlas, it should be borne in mind that,
as a matter of statistics, there are only one quarter as many configurations
satisfying periodic boundary conditions as there are without boundary
conditions (and in turn one sixteenth as many which are 'quiescent at
infinity'). Thus the average numbner of ancestors for periodic configurations
would be 1, not 4. Also, quantities may fluctuate more drastically for short
configurations as the boundary conditions become more stringent.
In spite of this, growth factors apply equally for all kinds of boundary
conditions. Moreover, once the powers of an irreducible matrix have come
into equilibrium, fluctuations in the sizes of the matrix elements will
also be immune to the boundary conditions, and they commence to dominate
at the same stage as well.
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