Cellular automata in mean-field approximation

[mmcirvin]

Update to the following: Most of the following is probably invalid; I think I should actually be using a binomial distribution, not a Poisson distribution. See comments. I'll try this using the correct math some other time.

So, sparked by doctroid's experiments and mine, I started thinking about cellular automata in stochastic mean-field approximation, and wondering if I could use it to predict whether a given model would just remain chaotic from a random starting soup, or eventually settle down (at least in the medium term). I'm sure this has been done before because it's probably the most obvious thing for a physicist to think of.

The idea is that at every step, you represent the cell grid as a uniformly random distribution with a given density, then use the resulting probability distribution of neighbor numbers to calculate the density at the next step. Obviously this approximation isn't going to be true in detail; after the first step the distribution isn't uniform; there will be important correlations between cell values. But maybe it'll say something about the short-term behavior starting from chaos.

Now, if you remember your Thomas Pynchon, you know that when a uniform random distribution is divided into bins of some sort, the probability of a given number of data points being in a given bin is given by the Poisson distribution. In Gravity's Rainbow, the people at the Abreaction Research Facility were plotting Tyrone Slothrop's sexual encounters on a map of London divided into cells. If the distribution were uniform (and I guess it was close, aside from that strange external correlation), the probability of N of those falling within a given cell would be the Poisson distribution at (N, r), where r is the average number per cell.

In this case, since we're interested in the the probability of a live or dead cell having a given number of live neighbors. If the density of live cells--the probability that any given cell will be lit--at time t is P_t, then the average number of lit neighbors of a given cell is 8P_t (since the cell has eight neighbors, any of which could be lit), and the probability that k neighbors will be lit is the Poisson distribution at (k, 8P_t), which is (8P_t)^ke^-8P_t/(k!).

Now in Life, a live cell with 2 or 3 live neighbors survives, and a dead cell with exactly 3 live neighbors becomes live. So if we can model the distribution as uniform, then at time t+1, the new density is the old density of live cells times the probability of 2 or 3 live neighbors, plus the old density of dead cells times the probability of exactly 3 live neighbors:

P_t+1 = P_t (Poisson(2, 8P_t) + Poisson(3, 8P_t)) + (1-P_t) Poisson(3, 8P_t)

P_t+1 = e^-8P_t ( P_t (8P_t²/2! + 8P_t³/3! ) + (1 - P_t)( 8P_t³/3! ))

You can see how you would do a similar calculation for any other set of "outer totalistic" CA rules, that is, rules that just depend on the cell's current state and the number of live or dead neighbors.

Now this is a recursion relation, that is, it takes the density at time t and gives you (an approximate calculation of) the density at time t+1. What happens when you turn the crank over and over? Well, it depends on the initial value, and on how this function compares to the identity function P_t+1 = P_t. In general, places where the graph of the recursion relation crosses the identity line will be fixed points, where the density won't change. Whether the value gets attracted to or repelled from the fixed point depends on just how the lines cross. If the lines touch or nearly touch at a tangent, then the value in that region will tend to change very slowly. There can be oscillating or chaotic behavior in other situations.

So, anyway, I went over to Wolfram Alpha and looked at the graphs of these functions for the Life-like cellular automata I've been talking about. It looks as if this kind of analysis really isn't subtle enough to distinguish between them: they all have just about the same behavior, in which the graph just about kisses the identity line at a near-tangent somewhere between P = 0.2 and 0.3. Sometimes (as with High Life) it crosses the line just a little, sometimes (as with Conway Life and most of the ones I've been messing with) it doesn't quite cross the line, and there doesn't seem to be much correlation between that and the rule's long-term behavior, which says to me that the higher correlation functions are important.

But I think (well, conjecture) that the fact of the near-tangent, which makes the effect of overall density act slowly enough that subtler correlations can do interesting things, is probably a contributor to all these models having interesting behavior over significant spans of time when you start with some kind of haphazard input. Other rules don't do that. For instance, 3-4 Life (birth or survival at 3 or 4 neighbors) pokes further over the line with a strongly attractive fixed point near 0.4, and if you plug that rule into Golly, sure enough, you get a rapidly exploding blob of chaos with a density of about 40%.

Comments

[mmcirvin.livejournal.com]

...The fixed-point analysis works very well for the Serviettes/Persian Rugs (B234) rule as well, and Day and Night (B3678/S34678) has the "kissing curves" characteristic that suggests that it's a rule that neither explodes nor dies very quickly, but has more interesting behavior.

(But it's curious that Day and Night's symmetry between black and white pixels, which gives it its name, seems somewhat hidden in the mean-field analysis. I'd expect there to be something special going on at 50% and I don't see it; the near-tangent is at a slightly lower density. I find it mildly paradoxical; either the symmetry is somehow broken by this approximate analysis or I'm doing something wrong.)

[mmcirvin.livejournal.com]

...Anyway, someone with more experience than I have in probability or statistics is undoubtedly going to point out all the mistakes in the above.

[mmcirvin.livejournal.com]

Well, I see one mistake: I don't think I should be using a Poisson distribution, since it has nonzero values for more than 8 lit neighbors! It should be something that takes into account that a pixel is either on or off, and can't be lit twice.

Given that, it's remarkable that my results seem as relevant as they are.

[mmcirvin.livejournal.com]

...it should just be binomial, right? Which explains why the Poisson did as well as it did, it's not that far off--unless P is too close to 1. Which is probably why Day and Night is looking asymmetric.

[oonh.livejournal.com]

I have to admit, that when I hear "Poisson distribution", /Gravity's Rainbow/ is the *first* thing I think of...