# A note on the fast convergence of asynchronous Elementary Cellular Automata

Nazim Fatès

► To cite this version:

Nazim Fatès. A note on the fast convergence of asynchronous Elementary Cellular Automata. 19th International Workshop, AUTOMATA 2013., Sep 2013, Gießen, Germany. pp.31-45, 10.1007/978-3-642-40867-0_3. hal-00981691

HAL Id: hal-00981691

https://inria.hal.science/hal-00981691

Submitted on 22 Apr 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A note on the fast convergence of asynchronous Elementary Cellular Automata

Nazim Fatès

nazim.fates@loria.fr

Inria Nancy Grand-Est, LORIA UMR 7503
F-54 600, Villers-lès-Nancy, France

April 22, 2014

## Abstract

We tackle the problem of the classification of elementary cellular automata when the cells are updated in a fully asynchronous scheme (one cell is selected at random at each time step). We establish a proof of convergence in logarithmic time as a function of the size of the automaton. Techniques involve a direct Markov chain analysis or the construction of potential function whose convergence rate is bounded by a particular martingale.

## 1 Introduction

This note is a contribution to the study of the 256 Elementary Cellular Automata (ECA) submitted to an asynchronous updating scheme. We are interested in the fully asynchronous case, that is, when only one cell is updated at each time step, chosen uniformly at random in the set of cells. More precisely, we wish to determine which are the rules whose convergence time to a fixed point is very rapid: this time scales logarithmically with the size of the automaton.

Asynchronous cellular automata are currently receiving an increasing attention. Their study concerns various fields such as computability [7], dynamical systems [1], or modelling [5] (see Ref. [2] for a survey). The question of the classification of asynchronous cellular automata is still open. One proposition to classify the rules analytically is to study the average time needed to reach a fixed point. Indeed, the way the time of convergence varies as function of the size of the automaton is strongly related to the dynamical behaviour of the system; it can be classified into well-separated “families” [4].

The problem of estimating the convergence rate of asynchronous rules has recently been tackled with an experimental approach [6, 3]. On the analytical side, a previous analysis of a subset of the ECA with two quiescent states allowed us to identify (only) two ECA with a logarithmic convergence [4]. But what
about the other rules? Can the analysis for this specific two rules be transposed to a wider class of cellular automata ? We here propose to process in three steps and gradually generalise our approach of the fast convergence phenomenon, using Markov-chain analysis and martingale arguments.

## 2 Definitions and candidates

### 2.1 Definitions

An Elementary Cellular Automaton (ECA) is defined as a one-dimensional binary CA with nearest-neighbour interactions. We here tackle the finite case where cells are arranged in a ring and we denote by $\mathcal{L} = \mathbb{Z}/n\mathbb{Z}$ the set of cells. A configuration corresponds to an assignment of a state to each cell, the state of configurations is thus $\mathcal{E}_n = \{0, 1\}^\mathcal{L}$. The evolution of the ECA is governed by its local function $f: \{0, 1\}^3 \to \{0, 1\}$, which specifies how each cell updates its state according to its own state and the states of its two nearest neighbours.

The updating of the automaton is stochastic, we denote by $(U_t)_{t \in \mathbb{N}}$ the sequence of independent and identically distributed random variables which uniformly choose select one cell in $\mathcal{L}$. Given a sequence of updates $(U_t)$ and an initial condition $x$, we can describe the evolution of a fully asynchronous CA by the stochastic process denoted by $(x^t)_{t \in \mathbb{N}}$ and defined recursively with: $x^0 = x$ and $x^{t+1} = F(x, U_t)$, where

$$ \forall i \in \mathcal{L}, x_i^{t+1} = \begin{cases} f(x_{i-1}^t, x_i^t, x_{i+1}^t) & \text{if } i = U_t \\ x_i^t & \text{otherwise} \end{cases} \quad (1) $$

For the sake of brevity, the i.i.d. sequence of random updates $(U_t)$ is always implicit and we simply write $F(x)$ as the random variable that describes the configuration obtained by a uniform random update on $x$. A configuration $x \in \mathcal{L}$ is called a fixed point if we have $F(x) = x$ with probability 1 (all cells are in a stable state). Note that the synchronous and asynchronous updating induce the same set of fixed points, that is here denoted by $\mathcal{FP}$.

Starting from a configuration $x$, the convergence time $T(x)$ is the average time required to reach a fixed point. Formally, $T(x) = \mathbb{E}\{\min t \in \mathbb{N}, x^t \in \mathcal{FP}\}$. For a fixed ring size $n$, taking some freedom with notations, we define the worst expect convergence as $T(n) = \max_{x \in \mathcal{E}_n} T(x)$.

The 256 ECA will be identified with two different notations. The first one is the classical decimal notation introduced by Wolfram. The second one, called the *t-code*, consists in assigning to an ECA the letters that designate each active transition of the rule. (A transition is an association of a triplet $(x, y, z)$ to $f(x, y, z)$. We say that a transition is *active* if its application changes the state of a cell, that is, $f(x, y, z) \neq y$). The labels associated to each transition are presented in the following table:

<table><tr><td>(x,y,z)</td><td>000</td><td>001</td><td>100</td><td>101</td><td>010</td><td>011</td><td>110</td><td>111</td></tr><tr><td>t-code</td><td>A</td><td>B</td><td>C</td><td>D</td><td>E</td><td>F</td><td>G</td><td>H</td></tr></table>
As an illustration, take the majority rule. It has only two active transitions, $(1, 0, 1) \to 1$ and $(0, 1, 0) \to 0$. Its t-code is thus DE and we will denote by 232-DE this rule when we want to indicate both codes. For the sake of simplicity, instead of studying the 256 ECA rules, we will restrict our examination to the 88 so-called minimal representative rules. They are the rules which have the smallest decimal code when applying the symmetries of reflexion (left-right exchange) and conjugation (0-1 exchange) and when combining both operations.

## 2.2 Candidates

Among the 88 minimal rules, we previously identified a subset of rules which appear to converge rapidly to a fixed point [3]. We divide this set into two classes: the RCH and RCN class group the rules rapid convergence to a homogeneous or non-homogeneous fixed point, respectively. In the RCH class, we find the following 16 minimal rules:

<table><tr><td>0, 2, 8, 10,<br>18, 24, 26, 32,<br>34, 40, 42, 50,<br>56, 58, 74, 106.</td><td>EFGH, BEFGH, EGH, BEGH,<br>BCEFGH, CEGH, BCEGH, DEFGH,<br>BDEFGH, DEGH, BDEGH, BCDEFGH,<br>CDEGH, BCDEGH, BEH, BDEH.</td></tr></table>

and in the RCN class, we find the following 12 minimal rules:

<table><tr><td>4, 5, 12, 13,<br>36, 44, 72, 76,<br>77, 104, 200, 232,</td><td>FGH, AFGH, GH, AGH,<br>DFGH, DGH, EH, H,<br>AH, DEH, E, DE,</td></tr></table>

On the left column, we give the Wolfram code and on the right column, we give the T-code. We keep this convention in the following. The case of 74-BEH, which is now excluded for the list of candidates, is discussed at the end of this note.

Below are space-time diagrams of four rules from the RCH and RCN class:

<figure><img src="image_2.png" /><figcaption>0 - EFGH</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>26 - BCEGH</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>58 - BCDEGH</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>74 - BEH</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>4 - FGH</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>5 - AFGH</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>72 - EH</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>104 - DEH</figcaption></figure>

These diagrams should be interpreted as follows. Time goes from bottom to top; square in blue and white represent cells with states 0 and 1, respectively. The time is rescaled by a factor $1/n$: the transition from one line to the other is obtained after $n$ updates. (This explains some discontinuities in the groups of cells). The ring size is fixed to $n = 50$ and the random evolution is represented over 30 time steps. Recall that the space is a ring, which explains that some sets of coloured cells seem to “appear”. It should also be noted that the initial configuration is made of half of the cells contiguously set to 1 and 0. This choice
<table><caption>Table 1: Table of the 32 possible re-writing triplets of T-codes. The column corresponds to the 8 possible states of the central cell and the lines corresponds to the 4 possible states of the left and right cells.</caption><thead><tr><th></th><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th><th>G</th><th>H</th></tr></thead><tbody><tr><th>1</th><td>aaa<br>bec</td><td>abe<br>bfg</td><td>eca<br>fgc</td><td>ede<br>fhg</td><td>bec<br>aaa</td><td>bfg<br>abe</td><td>fgc<br>eca</td><td>fhg<br>ede</td></tr><tr><th>2</th><td>aab<br>bed</td><td>abf<br>bfh</td><td>ecb<br>fgd</td><td>edf<br>fhh</td><td>bed<br>aab</td><td>bfh<br>abf</td><td>fgd<br>ecb</td><td>fhh<br>edf</td></tr><tr><th>3</th><td>caa<br>dec</td><td>cbe<br>dfg</td><td>gca<br>hgc</td><td>gde<br>hhg</td><td>dec<br>caa</td><td>dfg<br>cbe</td><td>hgc<br>gca</td><td>hhg<br>gde</td></tr><tr><th>4</th><td>cab<br>ded</td><td>cbf<br>dfh</td><td>gcb<br>hgd</td><td>gdf<br>hhh</td><td>ded<br>cab</td><td>dfh<br>cbf</td><td>hgd<br>gcb</td><td>hhh<br>gdf</td></tr></tbody></table>

was made on purpose in order to make explicit the fragmentation process at play with these rules.

# 3 Classification

## 3.1 “Monotonous” rules

As simple starting point, we consider 76-H, the coupon collector argument still applies as: a) cells in state h are active and b) any h that is updated is turned into a d and c) no h can be created by updating a h. To which set of rules can we generalise this argument?

It is important to remark that if we consider T-configurations, updating a cell *i* can be considered as re-writing operation that will potentially change the labels of *three*: the updated cell, but also its left and right cells.

In order to find out all the transformations that can occur when a cell is updated, we thus need to consider all the possible triplets, that is the 32 possible sequences of five cells. These transitions are represented on Table 1. In the sequel we call this table the *rewriting table*. We define a transition of the table to be *active* if the column to which it belongs corresponds to an active transition. For instance, if we take the majority rule 232-DE, only the 8 transitions of columns D and E will be active.

**Definition 1.** A strictly monotonous rule is a rule for which each time an active cell is updated, the number of active cells decreases.

**Theorem 1.** The (minimal) rules that are strictly monotonous are: 0-EFGH, 4-FGH, 12-GH, 76-H, 77-AH, 200-E, 232-DE.

*Proof.* Clearly, a rule is strictly monotonous if and only if all the *active* transitions of the rewriting table lead to a negative difference in the number of active cells. (That is, for each entry of the table the number of active cells before updating is strictly higher than the number of active cells after updating.)
For a given rule, let us assign a value 1 or 0 to the eight variables $\omega_a..., \omega_h$, depending on whether the T-code of the rule considered contains or does not contain the transitions A, ..., H, respectively. For instance, for the rule FGH, we have $\omega_a = 0...\omega_e = 0$ and $\omega_f = 1, \omega_g = 1, \omega_h = 1$.

We can now discuss the possible cases where a decrease in the number of active cells occurs each time an active cell is updated. We denote by $\Delta(ij)$ the variation of the number active cells which corresponds to the column $i$ and line $j$ of the rewriting table.

* First case: we assume that H is active, that is, $\omega_h = 1$. Looking at the entry (D4) of the rewriting table, we see that transition D can not be active: $\omega_d = 0$. By looking at (B2) we have $\Delta(B2) = \omega_h - \omega_a = 1 - \omega_a$. As this quantity can not be made negative, we have that B is inactive: $\omega_b = 0$. By symmetry, looking at (C3) gives $\omega_c = 0$. We now discuss the value of $\omega_a$.

- If $\omega_a = 1$, then looking at (E1), (F2), (G3), lead to $\omega_e = 0$, $\omega_f = 0$ and $\omega_g = 0$, respectively. As the values of the eight transitions are fixed, we thus find rule $\boxed{AH}$. (We use a box to denote the minimal representative rules.)

- If $\omega_a = 0$, from (H1) we deduce $\omega_e = 1 \implies \omega_f = 1$ and $\omega_g = 1$. One solution is thus $\boxed{EFGH}$. The case $\omega_e = 0$ gives: $\boxed{FGH}, FH, GH, H}$. (It can be checked these are all valid solutions.)

* Second case: we assume that H is inactive, that is, $\omega_h = 0$. By (F2) and (G3), we obtain: $\omega_f = 0$ and $\omega_g = 0$. We now discuss on the value of $\omega_e$.

- If $\omega_e = 1$, entries (E1), (B2) and (C2) give: $\omega_a = 0, \omega_b = 0$ and $\omega_c = 0$, respectively. We thus obtain rules $\boxed{E}$ and $\boxed{DE}$.

- If $\omega_e = 0$, it can be observed that the possible candidates are all rules whose active transitions are A, B, C and D. These rules can be reduced to previously examined cases by the 0/1-exchange symmetry, as the active transitions of the symmetric rules will contain only E, F, G and H.

□

**Theorem 2.** *Strictly monotonous rule have a logarithmic convergence time.*

The convergence of rule D and DE has already been studied in a previous work [4]. To upper-bound the convergence time, we simply use the fact that the probability to decrease the number of active cells by at least one is exactly $1/n$ times the number of active cells. For the lower bound, remark that if a rule differs from identity, that is, if it has at least one active transition, we can take a sequence $p \in \{0, 1\}^k$ of $k$ cell states such that $p$ contains an active transition. The configuration $x$ obtained by repeating $i$ times $p$ has a length $n = ip$ and contains at least $i$ active transitions. The system converges
if (at least) the $i$ unstable cells are updated, the average time of convergence thus scales as $n \log i$ (see coupon collector processes), that is, as $n \log n$. (In the following we call “logarithmic” this type of convergence as we implicitly rescale the time by a factor $n$ for a fair comparison with the synchronous case).

## 3.2 Rules with a monotonous potential

The question is now to determine if the previous argument can be generalised to other rules. As an illustration, let us turn our attention to the rule EH. By examining the rewriting table, it can be seen that this rule is “almost” strictly monotonous, but if we look at the entry (H1), we see that one h can produce two e. The problem produced by this increase in the number of active cells can be solved with the convention that an h counts as much as three e. In this case, a transition of type (H1) would still continue to decrease the number of “weighted” active cells.

However, a difficulty appears at this point as, even with this “weighted” active cells, it is no longer possible to reconduct the previous argument as we have now lost the proportionality that existed between the “activity” and the probability to decrease. We are thus unable to “compare” conveniently the two processes.

Recall that the set of fixed points is denoted by $\mathbb{F}$. We can now state our specific lemma to establish a logarithmic convergence time.

**Lemma 1 (Logarithmic convergence).** For a rule $R$, if there exists an integer $k$, a potential function $W: \mathcal{E}_n \to \{0, \dots, k\}$ and a constant $\alpha > 0$ such that $\forall x \in \mathcal{E}_n$:

$$W(x) = 0 \implies x \in \mathbb{F}, \qquad (C1)$$

and

$$\forall x \in \mathcal{E}_n, F(x) \neq x \implies \Delta W(x) < 0 \qquad (C2)$$

and

$$\mathbb{E}\{\Delta W(x)\} \leq -\alpha W(x), \qquad (C3)$$

where $\Delta W(x) = W(F(x)) - W(x)$, then the worst expected convergence time of $R$ is bounded by $\log k/\alpha$.

In words, if there exists a non-negative potential function $W$ that cancels only on fixed points, and such that, each time a configuration $x$ is updated on an unstable cell, the decrease of $W$ is (at least) proportional to $W$, then the convergence time is at most logarithmic in the size of the configurations.

*Proof.* We prove the lemma by recurrence. We define $(E_i)$ as the partition of $\mathcal{E}_n$ that is induced by $W$, that is: $E_i = \{x \in \mathcal{E}_n, W(x) = i\}$. Let $x$ be an arbitrary configuration ; we denote by $k$ its potential and by $T_x$ its average convergence time. Let $T_i$ be the maximum average convergence time for a configuration that has a potential $i$: $T_i = \max_{x \in E_i} T_x$. As $E_0$ is the set of fixed points, we obviously have $T_0 = 0$.
First, let us introduce the following recurrence relation: $T_x = 1+\sum_{y \in \varepsilon_n} p_{x,y}T_y$, where $p_{x,y}$ denotes the probability to go from state $x$ to state $y$. This relation, often called the step-forward equation, is a “classical” tool from Markov chain theory.

For $i \in \{0, \dots, k-1\}$, let $\lambda_i = \sum_{y \in E_i} p_{x,y}$ be the probability to go from $x$ to a configuration of potential $i$ (recall that the potential can only decrease). Grouping all the states of equal potential, the step-forward equation gives:

$$T_x \le 1 + p_{x,x}T_x + \sum_{i=0}^{k-1} \lambda_i T_i. \quad (2)$$

We define $\delta = 1 - p_{x,x} = \sum_{i=0}^{k-1} \lambda_i$, this quantity represents the probability to “leave” state $x$ after one (random) update. The previous equation becomes:

$$T_x = \frac{1}{\delta} \left( 1 + \sum_{i=0}^{k-1} \lambda_i T_i \right). \quad (3)$$

In order to prove the theorem by recurrence, let $P_k$ be the following property:

$$T_k \le \frac{1}{\alpha} \mathcal{H}_k \text{ where } \mathcal{H}_k = \frac{1}{k} + \frac{1}{k-1} + \dots + \frac{1}{1}. \quad (4)$$

We now prove that $P_k$ holds for every $k$.

First, let us show that $P_1$ holds. Let us take $x \in E_1$. Condition C2 of the Lemma implies that: $\Pr[W(F(x)) = 0] \ge \alpha$, that is, $\Pr[F(x) \in \mathcal{F}\mathcal{P}] \ge \alpha$, from which we directly derive $T_1 \le 1/\alpha$.

Now, we assume $P_1, \dots, P_{k-1}$ and prove $P_k$. The idea is to compare the value of $T_k$ with $\frac{1}{\alpha}\mathcal{H}_k$. To this end, we study the sign of $\Delta = \delta\alpha T_k - \delta\mathcal{H}_k$: showing that $P_k$ is valid is equivalent to showing that $\Delta$ is negative. (The form of $\Delta$ is chosen in order to avoid manipulating fractions as much as possible).

We have:

$$\Delta = \alpha + \sum_{i=0}^{k-1} \lambda_i \alpha T_i - \delta \cdot \mathcal{H}_k \quad (5)$$

which, using the hypothesis $P_{k-1}$, gives:

$$\Delta \le \alpha + \sum_{i=0}^{k-1} \lambda_i \mathcal{H}_i - \delta \cdot \mathcal{H}_k \le \alpha + \sum_{i=0}^{k-1} \lambda_i (\mathcal{H}_i - \mathcal{H}_k) \quad (6)$$

given that $\delta = \lambda_0 + \dots + \lambda_k$. Finally, by noting that $\forall i \in \{1, \dots, k\}, H_i - H_k \ge \frac{i}{k}$, we obtain: $k\Delta \le k\alpha - \sum_{i=0}^{k-1} (k-i)\lambda_i$, which shows that $\Delta$ is negative by using the conditions of the decrease in potential. $\Delta$ is thus negative for all possible configurations of potential $k$, which proves $P_k$. We thus have $T_k \le H_k/\alpha \le \log k/\alpha$, which concludes the proof. $\square$

We can now apply this lemma to extend the list of monotonous rules.
**Definition 2.** We say that a potential function $W: \mathcal{E}_n \to \mathbb{N}$ is balanced if the difference of potential brought by the update of a cell $i$ is only a function of the T-label of cell $i$. $W$ is said to be p-linear if it is defined as a positive linear combination of the number of cells of a given configuration, that is, $W(x) = \omega_a a(x) + \dots + \omega_h h(x)$ with $\omega_a, \dots, \omega_h \in \mathbb{N}$. $W$ is i-linear (short of instability-linear) if the positive coefficients all correspond to active transitions.

**Claim 1.** $W$ is balanced if and only if: $\omega_a + \omega_d = \omega_b + \omega_c$ and $\omega_e + \omega_h = \omega_f + \omega_g$.

We have no intuitive explanation of this fact, which was discovered empirically. It can be checked that if the two conditions are verified, the entries of each line of the transition table are equal, which guarantees that the rule is balanced.

**Theorem 3.** *Among the RCN and RCH class, rules 5-AFGH, 8-EGH, 13-AGH, 72-EH are the only (non-strictly) monotonous rules ; their convergence time is logarithmic.*

*Proof.* To show this, we examine which are the “candidates” to be monotonous. First, it can be remarked that if the T-code of a rule contains two letters in that form one of these couples: A-E, B-F, C-G or D-H, then the rule is not strictly monotonous. Indeed if a rules has two of such “opposed” active transitions, a configuration which is updated twice on a cell with such a transition comes back to initial state, which is contradiction with the hypothesis of monotony. Second, if we also rule out from the empirically-made list of candidates (RCH + RCN) the strictly monotonous rules, the only candidates left are: EH, EGH, BEGH, AFGH, and AGH.

We can also rule out BEGH with a specific example. If we start from configuration 0110, and update the third cell, we obtain the configuration 0100. If we then the first cell, we come back to the initial state 0110, which is also a contradiction with the monotony of the rule.

We now exhibit relevant potential functions for the four rules that remain. For a particular configuration $x \in \mathcal{E}_n$, we denote by $a(x), \dots, h(x)$ the number of occurrences of the t-labels a, \dots, h in x. The potential functions $W(x)$ will be constructed as linear combinations of these functions and the argument $x$ will be omitted for brevity. Note that, for a given potential function, being balanced is equivalent to having the same values of decrease in potential for a particular column of the rewriting table: the decrease of potential of a cell having a given t-label $t$ is denoted by $\delta_t$.

**Case of EGH.** We take $W = e + 2g + h$. This potential verifies C1 as it is p-linear. It verifies C2 as it is balanced with: $\delta_E = \delta_G = \delta_H = -1$. It also directly verifies C3 because it is i-linear.

**Case of AFGH.** Similarly, we take $W = a + f + g + 2h = e + 2g + h$. This potential verifies C1 as it is i-linear. It can also be checked that the potential decreases by at least 1, when an A a For a G is updated and that the potential decreases by 4 when an H is updated. Condition C2 is thus verified and we
have:

$$n \cdot \mathbb{E}\{\Delta W\} \leq -a - f - g - 4h \quad (7)$$

$$\leq -a - f - g - 2h \qquad \leq -W \qquad (8)$$

Condition C3 is thus verified with $\epsilon = 1/n$.

(Due to lack of space, rest of the proof is put in annex, see Sec. 4.1.)

<figure><img src="image_10.png" /></figure>

### 3.3 Rules with an average decrease of potential

Our efforts to generalise the first argument allowed us to deal with “only” four more rules. The reason why this attempt had a limited success is not so difficult to guess: by requiring that the potential always decreases when an active cell was updated, we were demanding too much.

We now present a lemma that allows us to extend one step further the domain of application of the mathematical analysis: in this new step, we will only require that the decrease happens on average. However, in order to get a logarithmic convergence time, we need to impose that the decrease of the potential is proportional to the current value of the potential.

**Lemma 2.** Let $(X_t)_{t \in \mathbb{N}}$ be a stochastic process whose values are in $\{0, \dots, k\}$ and $(\mathcal{F}_t)_{t \in \mathbb{N}}$ a filtration adapted to it. If there exists a constant $0 < \epsilon < 1$ such that $\forall t \in \mathbb{N}$:

$$\mathbb{E}\{X_{t+1} - X_t | \mathcal{F}_t\} \leq -\epsilon X_t$$

then the average time for reaching 0 is upper-bounded by $-\frac{\log k+1}{\log 1-\epsilon}$.

*Proof.* First let us, introduce the stochastic process defined by: $Y_t = (X_t+1)\lambda^t$. Our goal is to show that for a proper setting of $\lambda$, $(Y_t)$ is a supermartingale and to use this to bound the time needed for $(X_t)$ to hit zero. We have:

$$\mathbb{E}\left\{\frac{Y_{t+1}}{Y_t} \mid \mathcal{F}_t\right\} = \mathbb{E}\left\{\frac{X_{t+1} + 1}{X_t + 1} \lambda \mid \mathcal{F}_t\right\} = \lambda \cdot \mathbb{E}\left\{\frac{\frac{X_{t+1}}{X_t} + \frac{1}{X_t}}{1 + \frac{1}{X_t}} \mid \mathcal{F}_t\right\} \quad (9)$$

$$\leq \lambda \cdot \mathbb{E}\left\{\frac{X_{t+1}}{X_t} \mid \mathcal{F}_t\right\} \qquad (10)$$

We rewrite the condition on the average decrease of $X_t$ as: $\mathbb{E}\{\frac{X_{t+1}}{X_t} | \mathcal{F}_t\} \leq 1-\epsilon$, from which we deduce that $\lambda = 1/(1-\epsilon)$ implies that $(Y_t)$ is a supermartingale (that is, $\mathbb{E}\{Y_{t+1} - Y_t | \mathcal{F}_t\} \leq 0$). Let $T$ be the random variable defined as $T = \min_{t \in \mathbb{N}} X_t = 0$. This defines an stopping time and, according to Doob's optional stopping time theorem, one can define the random variable $Y_T$ and write that: $\mathbb{E}\{Y_T\} \leq \mathbb{E}\{Y_0\}$, which gives $\mathbb{E}\{Y_T\} \leq k+1$. On the other hand we have: $\mathbb{E}\{Y_T\} = \mathbb{E}\{\lambda^T\}$ with $\lambda \geq 1$. Using the fact that $x \to \lambda^x$ is a concave function, we can apply Jensen's inequality and write:

$$\lambda^{\mathbb{E}\{T\}} \leq \mathbb{E}\{\lambda^T\} \leq k+1,$$
from which we deduce: $\mathbb{E}\{T\} \le \frac{\ln(k+1)}{\ln \lambda}$ and the fact that the mean value of $T$ is bounded by $\Theta(\ln k)$. $\square$

We now apply the lemma to four rules.

**Theorem 4.** *Rules BEFGH, DEFGH, BDEFGH, DEGH have a logarithmic WECT.*

Before we can go to the proof we use the following fact:

**Claim 2.** *If for a rule R, there exists a positive integer m, a p-linear function W such that for every ring size n ∈ $\mathbb{N}$: $W(x) = 0 \Rightarrow x \in \mathbb{F}^p$ and*

$$ \forall x \in \mathcal{E}_n - \mathbb{F}^p, \mathbb{E}\{W(F(x)) - W(x)\} \le -\frac{1}{m \cdot n} W(x), \quad (11) $$

then the rule has a logarithmic convergence.

This fact simply represents an application of Lemma 2 in our context. It is obtained by taking $\epsilon = 1/m \cdot n$ and $-\ln(1 - \epsilon) \sim \epsilon$ for $\epsilon \to 0$.

*Proof.* We begin with rule BEFGH. We take as a potential function: $W = 3e + 5f + 2h$. (The form of $W$ can be justified by the necessary condition: $\omega_a + \omega_h < \omega_d + \omega_e < 2\omega_h$ obtained by looking at the variation of potential of the two configurations: all-1 and 010.) $W$ is balanced and the variation of potential

associated to each transition is: $\begin{array}{c|cccccc} \text{tr.} & B & E & F & G & H \\ \delta & 2 & -3 & -2 & -2 & -1 \end{array}$

We thus have: $n\mathbb{E}\{\Delta W(x)|x\} = 2b - 3e - 2f - 2g - h$ and

$$ 3n\mathbb{E}\{\Delta W(x)|x\} = 6b - 9e - 6f - 6g - 3h \quad (12) $$

$$ \le 6e + 6f - 9e - 12f - 3h \quad \text{as: } b \le e + f \text{ and } f = g \quad (13) $$

$$ \le -3e - 6f - 3h \quad (14) $$

$$ \le -3e - 5f - 2h \le W(x) \quad (15) $$

The proofs for rules DEFGH, BDEFGH and DEGH are omitted due to lack of space. (See Annex, sec. 4.2) $\square$

## 3.4 A non-logarithmic rule

Contrarily to what was first thought, Rule 74-BEH does not have logarithmic convergence. This can be observed if we observe what happens to the fixed point (011)$^k$ (with k large enough) and change one cell state: a “cascade” propagates from right to left and makes the system progressively converge to 0. (The construction can be made for all ring sizes: repeat pattern 001 and then “complete” with something). This error of classification underlines the need to distinguish the average case and the worst case.
## References

[1] Alberto Dennunzio, Enrico Formenti, and Luca Manzoni. Computing issues of asynchronous CA. *Fundamenta Informaticae*, 120(2):165-180, 2012. doi: 10.3233/FI-2012-755.

[2] Nazim Fatès. A guided tour of asynchronous cellular automata. In Jarkko Kari, Martin Kutrib, and Andreas Malcher, editors, *Automata, volume 8155 of Lecture Notes in Computer Science*, pages 15–30. Springer, 2013. doi: 10.1007/978-3-642-40867-0_2.

[3] Nazim Fatès. A note on the classification of the most simple asynchronous cellular automata. In Jarkko Kari, Martin Kutrib, and Andreas Malcher, editors, *Proceedings of Automata'13*, volume 8155 of *Lecture Notes in Computer Science*, pages 31–45. Springer, 2013. doi:10.1007/978-3-642-40867-0_3.

[4] Nazim Fatès, Michel Morvan, Nicolas Schabanel, and Eric Thierry. Fully asynchronous behavior of double-quiescent elementary cellular automata. *Theoretical Computer Science*, 362:1–16, 2006. doi:10.1016/j.tcs.2006.05.036.

[5] Carlos Grilo and Luís Correia. Effects of asynchronism on evolutionary games. *Journal of Theoretical Biology*, 269(1):109-122, 2011. doi:10.1016/j.jtbi.2010.10.022.

[6] Biswanath Sethi, Souvik Roy, and Sukanta Das. Experimental study on convergence time of elementary cellular automata under asynchronous update. In Andreas Malcher Jarkko Kari, Martin Kutrib, editor, *Proceedings of AUTOMATA 2013 - Exploratory Papers*. Giessen University - IFIG Research Report 1302, 2013. available on http://www.informatik.uni-giessen.de/reports/Report1302.pdf.

[7] Thomas Worsch. (intrinsically?) universal asynchronous CA. In Georgios Ch. Sirakoulis and Stefania Bandini, editors, *Proceedings of ACRI 2012*, Lecture Notes in Computer Science, pages 689-698. Springer, 2012. doi:10.1007/978-3-642-33350-7_70.

# 4 Annex

## 4.1 Proof of the existence of suitable potential function for EH and AGH

The case of EH is slightly more complicated as it is easier to establish the proof with a non-blanced function. We take $W = e + 3h$. This potential verifies C1 as it is p-linear. We can check by hand that verifies C2 as $W$ decreases by 1 each time an E is updated and by *at least* 1 each time an H is updated. (The entries H1, H2, H3, H4 have a corresponding variation of potential of -1,-5,-5,-9, respectively). It respects C3 because it is i-linear.
Case of AGH. We take $W = a + 2g + 2h$. This potential verifies C1 as it is p-linear. It is not balanced, however, it can be checked by looking at each entry individually that: the potential decreases by at least 1, when an A or a G is updated (entries C4,G1 and G3), the potential decreases by 4 when an H is updated. Condition C2 is thus verified. We also we have:

$$n.E\{\Delta W\} \leq -a - g - 4h \quad (16)$$

$$\leq -\frac{1}{2}(2a + 2g + 8h) \quad (17)$$

$$\leq -\frac{1}{2}(a + 2g + 4h) \leq -\frac{1}{2}W \quad (18)$$

which shows that Condition C3 is verified with $\epsilon = 1/2n$.

## 4.2 Proof of the existence of a suitable potential function for DEFGH, BDEFGH, and DEGH

For DEFGH, we proceed by taking again $W = 3e+5f+2h$. This balanced potential rules generates the following changes in potential: $\begin{array}{c|ccccc} \text{tr.} & D & E & F & G & H \\ \delta & 1 & -3 & -2 & -2 & -1 \end{array}$. As for the previous case, we write:

$$\begin{aligned} 2nE\{\Delta W(x)|x\} &= 2d - 6e - 4f - 4g - 2h \\ &\leq 2e + 2f - 6e - 8f - 2h \quad \text{as: } d \leq e + f \text{ and } f = g \\ &\leq -4e - 6f - 2h \\ &\leq -3e - 5f - 2h \leq W(x) \end{aligned}$$

$W$ is also a suitable function for BDEFGH. We have the same decrease for each transition as before, to which we add $\delta_B = 2$. We thus write:

$$\begin{aligned} 2nE\{\Delta W(x)|x\} &= 2b + 2d - 6e - 4f - 4g - 2h \\ &= -4e - 6f - 2h \quad \text{as: } b+d=e+f \text{ and } f=g \\ &\leq -3e - 5f - 2h \leq W(x) \end{aligned}$$

Last, $W$ is also a suitable function for DEGH. Indeed, the decreases of potential are: $\begin{array}{c|cccc} \text{tr.} & D & E & G & H \\ \delta & 1 & -3 & -2 & -1 \end{array}$ and we have:

$$\begin{aligned} nE\{\Delta W(x)|x\} &= d - 3e - 2g - h \\ &\leq e + f - 3e - 2f - h \quad \text{as: } d \leq e + f \text{ and } f = g \\ &\leq -2e - f - h \end{aligned}$$

We thus have $5nE\{\Delta W(x)|x\} \leq -10e - 5f - 5h \leq -3e - 5f - 2h \leq W(x)$.