3
$\begingroup$

There are several ways to run a given elementary cellular automaton in a stochastic way:

  1. by giving for each of the eight local configurations 000,100,010 and so on a probability by which the rule is applied

  2. by applying the rule for all local configurations with the same probability

  3. by applying the rule not in parallel for all cells but sequentially, picking cells randomly one after the other, then updating them deterministically.

I tried out 2. and 3. for finite cellular automata on $\mathbb{Z}/k$ and came to surprising results. The class III rules 18, 22, 122, 126, 146 have quite similar space-time diagrams and are classified by almost all classifications into the same class. (I used this online tool to create the diagrams.)

enter image description here

Applying stochastic mode 2 with probability 0.9 yields

enter image description here

Applying stochastic mode 2 with probability 0.5 yields

enter image description here

Applying stochastic mode 3 and creating a snapshot after every $k$-th step (when $k$ cells have been updated, just like in parallel mode) yields

enter image description here

The effects are similar but different nevertheless. For example, for rule 126 in stochastic mode 3 there are (almost) never white regions wider than one pixel. What's more striking is the quite different behaviour of the five otherwise so similar rules, which becomes apparent even stronger in stochastic mode 3.

Has anyone an idea how to explain (or possibly predict) this?

For the sake of completeness here stochastic mode 2 with probabilities 0.1 and 0.0:

enter image description here

enter image description here

$\endgroup$
3
  • 3
    $\begingroup$ Comment: If you scale time by the inverse of the update probability in your "mode 2", so that each cell is on average updated once per scaled time step, then your "mode 3" is effectively the limit of "mode 2" as the update probability (per unscaled time step) tends to zero from above (and as the lattice size $k$ tends to infinity). Also, this scaled process is essentially a continuous-time Markov chain. $\endgroup$ Commented Nov 1, 2022 at 17:31
  • $\begingroup$ @IlmariKaronen: How can probability tend to zero from below? BTW: Would you mind giving me your mail adress, I'd like to send you some piece of information. Just drop a note at [email protected]. Thanks. $\endgroup$ Commented Nov 3, 2022 at 9:24
  • $\begingroup$ It can't, obviously. :) I was just trying to highlight the fact that the process you get by having a non-zero update probability tend towards zero (while scaling time so that the average number of updates per cell per scaled time unit stays constant) is obviously not the trivial process shown in your last image, where the update probability is identically zero and thus nothing ever changes. $\endgroup$ Commented Nov 3, 2022 at 9:30

2 Answers 2

5
$\begingroup$

The pictures obtained in what you call 'mode 3' are relatively easy to explain (but in some cases it may be hard to turn this into actual proofs):

Rule 18: Here, black particles die at rate $1$ and branch at rate $1$, provided that there are two free sites next to them. Their number is therefore dominated by a critical Galton-Watson process which is known to die out in finite time. (This is a very bad bound though, which is why you see them die quite a bit faster than the corresponding GW process would.)

Rule 22: Here, you want to track defects in the alternating black / white pattern (which is itself left invariant by the rule). It's easy to see from the rule that isolated defects (i.e. a single repetition of a color) perform simple random walks. When two defects collide, there is at least a positive probability that they annihilate, so you see annihilating Brownian motions at large scales and, in order $N^2$ time you'll have a perfect stripe pattern (possibly with one defect, depend on the parity of $N$).

Rule 122: There, it's not obivous to me why white doesn't eventually take over. The relevant quantity is what you see if you start all white on the left, all black on the right, and keep track of the leftmost black site. That has a unit drift to the left, but it occasionally jumps to the right when there's a white region just to the right of it. From the simulation, it looks like the sign of the overall drift is slightly negative, which is why white regions never grow too large. If it were positive (which you could enforce by biasing your selection), you would see something more like what you get from rule 18.

Rule 126: Here, the rule is such that white regions always shrink, with the exception that white sites can get seeded in the interior of a black region. However, there's no mechanism for these isolated white sites to expand and they die again at rate $1$, which explains the somewhat boring pattern of isolated white sites in a sea of black.

Rule 146: Here, both black and white regions are stable and the interfaces between them perform simple random walks. However, while white regions can merge, black regions cannot, so white will eventually take everything over (again in time of order $N^2$).

(Also, modulo a rescaling of time, 'mode 3' is the limit of 'mode 2' as the probability $p$ of applying the rule goes to $0$, which explains why those pictures seem to interpolate between the deterministic case and 'mode 3'.)

$\endgroup$
2
$\begingroup$

Concerning mode 3, exact results for a subset of elementary cellular automata are proved in this paper : Asynchronous behavior of double-quiescent elementary cellular automata.

$\endgroup$
4
  • $\begingroup$ Rule 146 is the only rule out of my five rules that is treated in the paper. For some reason the other four are not. So I can learn a lot from the paper, but not about the reasons for the difference between my five rules. But maybe after having read it very carefully;-) $\endgroup$ Commented Nov 3, 2022 at 15:44
  • $\begingroup$ Thanks for the hint. I incorporated the information into my ATLAS of cellular automata. Maybe you want to have a look at it. Just switch to [Table of properties], there you will find it. $\endgroup$ Commented Nov 3, 2022 at 16:42
  • $\begingroup$ The behaviour in question can be observed when choosing a specific rule (in the [Rule] field, e.g. 146) and switch to [Space-time diagram]. Here you can choose the option [Sequential update of randomly chosen cells] $\endgroup$ Commented Nov 3, 2022 at 16:48
  • $\begingroup$ Now you can also filter by the [Property] "double-quiescent". $\endgroup$ Commented Nov 3, 2022 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.