3
$\begingroup$

I am given a version of Conway's Game of Life where each cell can be in any of 3 states: Dead (D), Alive (A) or Dying (X).

The following transition rules exist:

  • An Alive cell next to a Dying cell will become Dying
  • A Dying cell will become Dead
  • An Alive cell with no Dying neighbors will be Dying with probability $P_X$
  • A Dead cell will be revived with probability $min(1.0, n \times P_R)$ with n being the number of Alive cells in its 3x3 neighborhood

The parameters $P_X$ and $P_R$ can be chosen.

What I am interested in is the probability of a cell being in a certain state in the next iteration given the state probabilities of it and its neighbors:

Denote the probability that cell $c$ is in state $A$ at the current iteration as $P_c^{t}(A)$. Similarly for the next iteration $P_c^{t+1}(A)$. (Other states analogous)

What I have is the following:

$P_{dying} = 1 - \prod_{n \in neighbors} (1 - P_n^t(X))$, i.e. the probability that any neighbor is dying. $P_{revive} = min(1, \sum_{n \in neighbors} (P_n^t(A) \times P_R))$, i.e. the probability that a cell is revived if it is dead.

$P_c^{t+1}(D) = P_c^{t}(X) + P_c^{t}(D) \times (1 - P_{revive})$

$P_c^{t+1}(X) = P_c^{t}(A) \times P_{dying} + P_c^{t}(A) \times (1 - P_{dying}) \times P_X$

$P_c^{t+1}(A) = 1 - P_c^{t+1}(X) - P_c^{t+1}(D)$

Is this correct?
And is it possible that these probabilities converge? (eventually subject to some conditions)

$\endgroup$
5
  • $\begingroup$ For convergence, are we to assume that the neighboring cells stay fixed, or that they (and their neighbors, and their neighbors' neighbors, etc.) also evolve according to the same rule? And in the latter case, is the lattice infinite or finite (and if finite, what are the boundary conditions)? $\endgroup$ Commented Jun 13, 2019 at 23:34
  • $\begingroup$ The whole grid evolves, by convergence I mean convergence of the whole grid. I suspect having only small areas which converge is also very interesting. The boundary conditions are basicly "dummy" cells which are Dead but do not get revived. $\endgroup$
    – milck
    Commented Jun 14, 2019 at 8:41
  • $\begingroup$ OK. Well, on a finite grid with permanently dead edges, if $P_X > 0$ then your system will eventually go extinct with probability 1 simply because "all dead" is an absorbing state (and reachable with a non-zero probability from any initial state). Does that answer your question, or are you interested e.g. in the convergence to a quasi-stationary probability distribution under the condition of extinction not happening? $\endgroup$ Commented Jun 14, 2019 at 8:51
  • $\begingroup$ I do not see this extinction behaviour right a away. If the border would be only Dying cells it would be absorbing, but Dead is rather "neutral". When simulating I also observe little groups of dying/reviving cells, obviously depending on $P_X$ and $P_R$. Indeed I am rather interested in quasi-stationary distributions if no extinction occurs $\endgroup$
    – milck
    Commented Jun 14, 2019 at 9:45
  • $\begingroup$ I was actually somewhat mistaken above: for sufficiently large $P_R$, it's possible for the system to enter a state that can never go extinct, because it contains a cluster of cells that oscillate deterministically (see my answer below for an example). In any case, as long as $P_R$ is above a critical threshold of approximate $0.18$ or so, the mean time to extinction will scale exponentially with the lattice size. $\endgroup$ Commented Jun 14, 2019 at 18:28

1 Answer 1

1
$\begingroup$

Let me start with an semi-empirical observation: for most initial conditions, the value of $P_X$ doesn't matter at all in the long run!

This is because the system quickly ends up in a state where every live cell has at least one dying neighbor, which causes every live cell to always die one timestep after being born regardless of the value of $P_X$. And once the system enters such a state, it will stay in that class of states forever. To see why this happens, note that every new live cell must have had at least one live neighbor on the previous time step. And since that neighbor will now be dying (since it, in turn, had a dying neighbor on the previous time step), this means that the new live cell now also has a dying neighbor. Thus, the class of states where this property holds is closed under the transition rule.


The empirical part of this is the observation that, from almost all initial states, the system will rapidly enter the class of states describe above. The one major exception to this is when $P_X = 0$ and there are few or no dying cells in the initial state, in which case it's possible for the dying state to disappear entirely while there are still some live cells in disconnected clusters that can then grow freely to cover the entire lattice. However, as long as $P_X$ is non-zero, even if it's very small, every cluster of live cells will sooner or later be "infected" with a dying cell, and this infection will then rapidly spread across the whole cluster. Thus, for all non-zero $P_X$, the convergence to the "all live cells have a dying neighbor" class of states is guaranteed, even if it may take a while.

(For an illustrative example, try e.g. $P_R = 0.01$, $P_X = 0.0001$ and an initial state consisting of 20% live, 20% dying and 60% dead cells, mixed randomly. On a sufficiently large lattice — say, 100 × 100 cells — you should be able to clearly see several distinct stages of behavior: first an initial rapid drop in the live cell population down to just a few percent, immediately followed by the extinction of the dying cells; then the re-growth of the surviving clusters of live cells, and finally the disappearance of the clusters one by one as they each get spontaneously infected by a dying cell. I may add an animation here later...)


Anyway, once every live cell has a dying neighbor, the value of $P_X$ no longer matters and the dynamics are entirely determined by $P_R$. In particular, depending on the value of $P_R$, we can distinguish various regimes of behavior:

  • For $P_R \ge 1$, the dynamics of the system are entirely deterministic (once the invariant class where $P_X$ becomes irrelevant has been reached) and correspond to the Generations CA rule "/12345678/3" (i.e. three states, no survival, birth on 1-8 live neighbors).

    This dynamics of this rule are empirically dominated by the fact that any local configuration of three adjacent cells all in distinct states will oscillate forever, regardless of what happens to its neighbors(!), and will also emit periodic wavefronts that drive all its surrounding cells to oscillate with the same (minimal) period if they don't already. Thus, almost all random initial conditions evolve into states that oscillate with a period of three time steps.

  • Similar qualitative behavior can also be observed for $0.5 \le P_R < 1$, even though the dynamics now have a stochastic component. In particular, for these values of $P_R$, every dead cell with at least two live neighbors always becomes live in the next time step, and this is still sufficient to support persistent local configurations that exhibit deterministic period-3 oscillation.

    One example of such a pattern is the following 3 × 3 cell configuration, where the digits 0, 1 and 2 denote dead, live and dying cells respectively, and which deterministically evolves as show by the arrows, regardless of the cells surrounding it, as long as $P_R \ge 0.5$:

    0 2 0     1 0 1     2 1 2     0 2 0
    1 1 1  →  2 2 2  →  0 0 0  →  1 1 1  →  …
    0 2 0     1 0 1     2 1 2     0 2 0
    

    In particular, the appearance of any such persistent oscillator on the lattice guarantees that the live cells will never go extinct. In practice, it also seems to lead quickly to almost all cells on the lattice oscillating with a period of three time steps, and often (always?) eventually to the oscillations becoming entirely deterministic.

  • For $P_R < 0.5$, down to about $P_R ≈ 0.18$, the (quasi-)equilibrium dynamics are much more stochastic. In particular, I suspect (but have not been able to prove) that no persistent deterministic oscillators like the one shown above can exist for $P_R < 0.5$, and that there's a non-zero probability of reaching the all-dead state from any initial state. If true, this implies that in the long run any finite lattice will enter the all-dead state with probability 1, since that's the only absorbing state of the system.

    However, for these values of $P_R$ the system is still supercritical, in the sense that the expected number of live cells $n_E(\tau)$ arising after $\tau$ time steps from a single live ancestor (and its single dying neighbor) on an infinite lattice of initially dead cells is greater than 1 for all $\tau$. This implies that, on a sufficiently large lattice, the live cells will persist at a positive quasi-equilibrium density for a very long time; in fact, the expected time until extinction should grow exponentially with the quasi-equilibrium live cell count, which in turn is directly proportional to the lattice size (albeit with a constant of proportionality that drops very rapidly as $P_R$ gets close to the critical threshold value).

    The appearance of the system in this supercritical regime seems to vary smoothly as a function of $P_R$. At large values of the parameter, the equilibrium density of live cells is close to 1/3, and the dynamics are dominated by period-3 waves (which, however, are really only quasi-periodic in this regime, and will eventually break down). As $P_R$ gets lower, the quasi-equilibrium density of live cells approaches zero, and the dynamics start to look more like those of a branching random walk (as is typical of lattice population models near the critical threshold) with little if any periodicity.

  • Finally, for values of $P_R$ lower than some critical threshold $P_{\rm crit}$, which my numerical experiments suggest lies somewhere between $0.17$ and $0.18$, the system is subcritical and the live cells always go extinct in time proportional to the logarithm of the lattice size. Basically, this happens whenever $n_E(\tau)$, as defined above, is less than one for any $\tau$; since $n_E(k\tau) \le n_E(\tau)^k$, this implies that the expected population of live cells decays exponentially towards zero.

    In particular, from the observation that $n_E(1) = 7P_R$ (since an isolated live cell with one dying neighbor has seven dead neighbors, each of which can become live with probability $P_R$ on the next time step) it follows that $P_{\rm crit} \ge 1/7 ≈ 0.143$. However, it's very clear from a numerical simulation that this lower bound is not tight, and that even $P_R = 0.16$ still leads to rapid extinction. This is basically because on a regular lattice $n_E(\tau)$ is always strictly less than $n_E(1)^\tau$; if the single initial live cell spawns multiple descendants, the "lineages" of live cells arising from those descendants will be located close to each other, and will therefore compete for space to grow into.

If you're interested in studying the behavior of your system in the $P_R < 0.5$ regimes, and e.g. determining the exact value of $P_{\rm crit}$ and/or the quasi-equilibrium density of live cells conditioned on non-extinction, you should look into the theory of lattice models of epidemiology and population dynamics. (That Wikipedia article seems like a bit of a mess, to be honest, but at least it has lots of references.) In particular, your model (with $P_X = 1$, or restricted to each live cell having at least one dying neighbor) is basically equivalent to a discrete-time SIRS epidemic model on a lattice (with stochastic infections but deterministic I → R → S transitions).

In general, you'll find that, while the exact dynamics can only be simulated numerically, there are various analytical approximations that may (or may not) be useful. For example, we can derive a quick approximation of the quasi-equilibrium density $\tilde d_{\rm live}$ of live cells as a function of $P_R$ by observing that $$\tilde d_{\rm live} = 8 P_R \, \tilde q_{\rm dead \mid live} \, \tilde d_{\rm live},$$ where $\tilde q_{\rm dead \mid live}$ is the probability of a randomly chosen neighbor of a live cell in the quasi-equilibrium state being dead. Since at least one neighbor of every live cell must be dying, it's clear that $\tilde q_{\rm dead \mid live} \le 7/8$. Now, by assuming that the remaining seven neighbors are essentially picked at random from the entire lattice, we can obtain the mean field approximation $$\tilde q_{\rm dead \mid live} ≈ 7/8 \, \tilde p_{\rm dead} = 7/8 \, (1 - \tilde d_{\rm live} - \tilde d_{\rm dying}) = 7/8 \, (1 - 2\tilde d_{\rm live}),$$ from which it follows that $\tilde d_{\rm live} ≈ 7 P_R \, (1 - 2\tilde d_{\rm live}) \, \tilde d_{\rm live}$, and thus (taking the non-negative root) that $$\tilde d_{\rm live} ≈ \max \left( 0, \, \frac12 - \frac1{14 P_R} \right).$$

While this is obviously a crude approximation, it's not terrible: it predicts the same approximate critical extinction threshold of $P_R = 1/7$ that we already obtained above and found to be a slight underestimate, and it's also not too far off in predicting a quasi-equilibrium density of $1/2 - 1/7 ≈ 0.357$ for $P_R = 0.5$ (the true value, of course, being close to $1/3 ≈ 0.333$).

In fact, I believe it should be possible to show that, for your process, $\tilde q_{\rm dead \mid live} \le 7/8 \, \tilde p_{\rm dead}$, and thus that this mean field approximation always yields an upper bound for the true quasi-equilibrium density of live cells. Basically, the idea would be to show that the presence of a nearby live cell can never make it more likely for a given cell to be dead. Unfortunately, while the argument seems intuitively obvious, proving it rigorously might require tricky tools like coupled stochastic processes.

For more accuracy, you could try using a pair approximation that takes the pairwise correlations between adjacent lattice sites (partially) into account by tracking the densities of adjacent pairs of sites. In fact, we already did that to some extent, in an ad hoc manner, by inserting the scaling factor $7/8$ into the mean field approximation to account for the known presence of at least one dying neighbor around every live cell. I won't carry out the process here, but if you'd like to try it, that's the term to Google for. Or I could always suggest my own MSc thesis as background reading. :-)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .