![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
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 Pt, then the average number of lit neighbors of a given cell is 8Pt (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, 8Pt), which is (8Pt)ke-8Pt/(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:
Pt+1 = Pt (Poisson(2, 8Pt) + Poisson(3, 8Pt)) + (1-Pt) Poisson(3, 8Pt)
Pt+1 = e-8Pt ( Pt (8Pt2/2! + 8Pt3/3! ) + (1 - Pt)( 8Pt3/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 Pt+1 = Pt. 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%.
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 Pt, then the average number of lit neighbors of a given cell is 8Pt (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, 8Pt), which is (8Pt)ke-8Pt/(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:
Pt+1 = Pt (Poisson(2, 8Pt) + Poisson(3, 8Pt)) + (1-Pt) Poisson(3, 8Pt)
Pt+1 = e-8Pt ( Pt (8Pt2/2! + 8Pt3/3! ) + (1 - Pt)( 8Pt3/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 Pt+1 = Pt. 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%.