# A Note on Endogamous Diploid Elementary Cellular Automata

Nazim Fatès

► To cite this version:

Nazim Fatès. A Note on Endogamous Diploid Elementary Cellular Automata. Automata 2025 - 31st International Workshop on Cellular Automata and Discrete Complex Systems, Sara Riva; Adrien Richard, Jun 2025, Lille, France. hal-05449168

HAL Id: hal-05449168

https://inria.hal.science/hal-05449168v1

Submitted on 8 Jan 2026

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 CC BY 4.0 - Attribution - International License
# A Note on Endogamous Diploid Elementary Cellular Automata

Nazim Fatès¹[0000-0001-6018-8656]

Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

nazim.fates@loria.fr

https://members.loria.fr/nazim.fates/

**Abstract.** Diploid cellular automata are stochastic mixtures of two local rules: at each time step each cell independently applies one rule with a given probability $\lambda$ and the other rule with probability $1 - \lambda$. Here, following a proposition by Roy et al., we investigate the subset of the 168 endogamous rules, that is, the diploid rules formed by a rule and one of its symmetric. Even with such a restriction, these diploids have a great diversity of dynamics. We study the cases where the average convergence time has a logarithmic, linear, or quadratic scaling law and show that this characterisation is useful to understand the behaviour of these endogamous rules.

**Keywords:** stochastic cellular automata · classification of the convergence · Markov chains

## 1 Introduction

In the field of cellular automata, various approaches coexist and one important question is to know how to design computing models which mimic some properties found in natural systems, for instance robustness, self-organisation, scaling, coordination without centralisation, etc. In particular, since it is rare to find deterministic behaviours in natural systems, one may ask what are the fundamental differences between stochastic and deterministic cellular automata. This question is of course too difficult to be dealt with in general and it is necessary to restrict the scope of the study to particular classes of models.

In this note, we are interested in diploid cellular automata, that is, stochastic mixtures of a couple of two local rules *f* and *g*: at each time step, each cell independently applies *g* with a given probability *λ* and *f* with a probability *1 - λ*. More specifically, following a proposition by Roy et al. [1], we investigate the subset of endogamous rules, that is, the very particular case where the two rules *f* and *g* are symmetric by the left-right inversion, by the 0-1 inversion (or conjugation), or by the combination of these two operations.

It is quite surprising that to date the behaviour of stochastic systems is still a mystery, even if one restricts to one-dimensional binary systems with nearest interactions [2]. If we limit ourselves to diploid ECAs, after simplification by the
reflection and conjugation symmetries, we are still left with 8808 such couples of rules, which is too much for an exhaustive study.

Among the recent contributions on this topic, Bolt et al. have considered diploid CA as a testing framework for the identification problem of stochastic rules [3]. Spitoni et al. studied analytically the diploids that are crossed with the null rule [4] and later used a local-structure approximation to predict the behaviour of the rules [5].

In this note, we examine the 168 endogamous non-equivalent couples. Although one may first think that stochastically mixing a rule and its symmetric may give rise to a reduced spectrum of behaviour, it has been observed on the contrary an impressive diversity of dynamics [1]. Our aim is specifically to show that, similarly to what has been observed for asynchronous cellular automata, the convergence time to a fixed point falls in well-known classes: logarithmic, linear, quadratic or exponential convergence time as a function of the number of cells.

# 2 Presentation of the model

## 2.1 Formalism

We denote by $\mathcal{L} = \mathbb{Z}/n\mathbb{Z}$ the set of $n$ cells arranged in a ring, that is, with periodic boundary conditions. We denote by $\mathbf{0} = \mathbf{0}^{\mathcal{L}}$ and $\mathbf{1} = \mathbf{1}^{\mathcal{L}}$ the two homogeneous configurations and for $n \in 2\mathbb{Z}$, we similarly define $\mathbf{01} = (\mathbf{01})^{n/2}$ and $\mathbf{10} = (\mathbf{10})^{n/2}$.

A diploid CA is a rule that evolves by mixing stochastically two Elementary Cellular Automata (ECA). Let $f$ and $g$ be two ECAs: $f, g: \{0, 1\}^3 \to \{0, 1\}$. For a given value of $\lambda \in [0, 1]$, the diploid $(f, g)[\lambda]$ is the stochastic process such that a configuration $x \in \mathcal{E}_n$ evolves according to the random sequence of configurations $(x^t)_{t \in \mathbb{N}}$ such that $x^0 = x$ and, for a time $t$:

$$ \forall i \in \mathcal{L}, x_i^{t+1} = \begin{cases} g(x_{i-1}^t, x_i^t, x_{i+1}^t) & \text{with proba. } \lambda, \\ f(x_{i-1}^t, x_i^t, x_{i+1}^t) & \text{with proba. } 1 - \lambda. \end{cases} $$

In this study, as we are interested in “purely” stochastic rules, we will exclude the case $f = g$, as well as the two extreme values $\lambda = 0$ and $\lambda = 1$. We simply write $(f, g)$ to refer to the set of rules obtained with $\lambda \in (0, 1)$.

**t-code.** To each ECA $f$, we associate its decimal code $W(f) = f(0, 0, 0) \cdot 2^0 + f(0, 0, 1) \cdot 2^1 + \dots + f(1, 1, 1) \cdot 2^7$. We also designate a rule by its t-code: this code is composed of the list of letters that identify the active transitions of the rule, that is, the triplets $x, y, z \in \{0, 1\}^3$ such that $f(x, y, z) \neq y$. These letters are given by 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>

t-codes are also used to encode the configurations, and we associate to each cell a letter from a to h according to whether transitions A to H respectively apply.
*Symmetries*. Consider an ECA *f*, we denote by *f*<sup>R</sup>, *f*<sup>C</sup> and *f*<sup>RC</sup> its respective reflected, conjugate, and reflected-conjugate rules.

Considering a diploid (f, g), the inversion symmetry, which swaps f and g, the reflection and the inversion, we obtain a class of equivalence of eight (potentially identical) rules: (f, g), (f<sup>R</sup>, g<sup>R</sup>), (f<sup>C</sup>, g<sup>C</sup>), (f<sup>RC</sup>, g<sup>RC</sup>), (g, f), (g<sup>R</sup>, f<sup>R</sup>), (g<sup>C</sup>, f<sup>C</sup>), (g<sup>RC</sup>, f<sup>RC</sup>). We call minimal representative the diploid the first element of this list when we sort the eight rules lexicographically with the decimal codes. It can be seen that in order to enumerate all the minimal endogamous rules, one can take the usual minimal 88 ECA rules and compose them with their reflected and conjugate rules when these symmetrical rules are not identical to them.

**Proposition 1.** *There are 168 minimal endogamous rules.*

*Proof*. Indeed, a given rule can be composed with one or three symmetrical rules. If *f* is invariant both by reflection and conjugation, then it cannot be composed with another rule to form a diploid. If it is invariant one symmetry only, then it can be composed with one other rule. Otherwise, *f* can be composed with the three other symmetric rules.

Out of the 256 ECAs, there are: (a) 4 rules invariant by both reflection and conjugation, (b) 12 rules invariants by conjugation only, (c) 12 rules invariants by the composition of reflection and conjugation only, (d) 60 rules invariants by conjugation only, (e) 256-(4+12+12+60)= 168 rules with no symmetry. These groups form respectively 4/1, 12/2, 12/2, 60/2 and 168/4 minimal rules, which can each be associated with respectively 0, 1, 1, and 3 other non-equivalent rules to form a minimal diploid. The total number of minimal diploids is thus:
$$4 \times 0 + (6 + 6 + 30) \times 1 + 42 \times 3 = 42 \times 4 = 168.$$

**3 Simple analytical results**

For each rule, given a ring size *n*, we define the worst expected convergence time *T*(*n*), or *convergence time* for short, as the maximum for all the configurations of size *n* of the expected value of the number of steps needed to attain a fixed point. Our aim is to show that *T*(*n*) is not arbitrary and falls into well-known classes. For each class of convergence, we present some selected rules in order to illustrate how we can bound the convergence time and how this bound is related to the very dynamics of the rule. For reasons of brevity, various proofs are omitted.

**3.1 Logarithmic convergence**

**Theorem 1.** For every $\lambda \in (0, 1)$, the diploid (8, 64) = (EGH, EFH) has a logarithmic convergence, that is, $T(n) \sim \Theta(\log n)$ for $n \to \infty$.

*Proof. (a) Upper bound.* First, let us note that 0 is the only fixed point of the rule. Also note that the 0's are always stable, and that every h-cell turns into a 0 deterministically; only f- and g-cells evolve randomly.
Consider a configuration $x$ with $k$ f's and g's: $k = |x|_f + |x|_g$. The probability that an f (resp. a g) turns into a 0 is $\lambda$ (resp. $\bar{\lambda}$). The lifetime of each of these f's or g's thus follows a geometric law. It is well known that the expectation of the maximum of $k$ geometric laws of parameter $p$ is equivalent to $\frac{\log k}{\log p}$ (see e.g. Ref. [6]), which here implies, as $k < n$, that we have as an upper bound $T(n) = \Omega(\log n)$.

(b) **Lower bound.** Without loss of generality, let us consider $n \in 3\mathbb{Z}$ and $0 < \lambda \le 1/2$. Let us examine the average convergence time of $x = 011^{n/3}$. Obviously, this convergence time can be lower-bounded by the average time needed to remove all the f's, that is, by the expectation of the maximum of $n/3$ i.i.d. geometric random variables, which, as said above, has a logarithmic scaling. This means that the survival time of each f-cell (resp. g-cell) follows a geometric law of parameter $\lambda$ (resp. $\bar{\lambda}$) and that the survival time of the 1's can be upper-bounded by the maximum of $k$ geometric laws with parameter $p = \min\{\lambda, \bar{\lambda}\}$.

If $n$ is not a multiple of 3, we can simply complete $x$ with one or two 0's, and for $\lambda > 1/2$, we simply consider the erasure of the g's. These modifications do not change the scaling laws. $\square$

*Claim.* The diploids (2,16), (6,20), (8,64), (10,80), (24,66), (38,52), (40,96), (74,88), (130,144), and (134,148) have a logarithmic convergence to the fixed point 0.

*Claim.* The diploids (12,68), (13,69), (44,100), (76,205), (200,236) have a logarithmic convergence to a fixed point (possibly non-homogenous).

With the convention that white and blue cells are respectively 0's and 1's and that time goes from bottom to top, the space-time diagrams below illustrate this behaviour:

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

(2, 16)[$\frac{1}{2}$]

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

(6, 20)[$\frac{1}{2}$]

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

(38, 52)[$\frac{1}{2}$]

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

(134, 148)[$\frac{1}{2}$]

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

(12, 68)[$\frac{1}{2}$]

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

(44, 100)[$\frac{1}{2}$]

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

(76, 205)[$\frac{1}{2}$]

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

(200, 236)[$\frac{1}{2}$]
## 3.2 Linear convergence

<figure><img src="image_10.png" /><figcaption>**Fig. 1.** Markov chain of the evolution of the initial condition $01^{n-1}$ where the state represents the number of 1's in the current state of the system. On states $n-1$ to 2, self-loops of value $1 - \alpha - \beta$ are omitted for clarity.</figcaption></figure>

**Theorem 2.** For every $\lambda \in (0, 1)$, the diploid (136, 192) = (EG, EF) has a linear convergence, that is, $T(n) \sim \Theta(n)$ for $n \to \infty$.

One may remark that the only difference with the diploid of Thm. 1 is that transition H is now passive.

**Proof. Upper bound.** The rule has only two fixed points, **0** and **1**. The rule is also monotonous in the sense that 0's are stable and a 1 with an adjacent 0 turns into a 0 with probability 1, $\lambda$ or $\bar{\lambda}$, depending on whether it is an **e**, an **f** or a **g**, respectively. Let us take $W_t = (\mathbf{e} + \mathbf{f} + \mathbf{g})(x^t)$ as a potential for obtaining a linear upper bound. For an arbitrary configuration $x^t \notin \{0, 1\}$, we have:

$$ \mathbb{E}\{W^{t+1} - W^t|x^t\} = -(e + \lambda f + \bar{\lambda}g) \leq -p \cdot (e + f + g) \\ \leq p, $$

since $x \notin \{0, 1\}$ implies that $e + f + g > 0$. By applying Lemma 3 of Ref. [7], we obtain an upper bounded that has a linear scaling in $n$.

**Lower bound.** Let us consider the length-$n$ configuration $x^0 = 01^{n-1}$. Let $X^t$ denote the number of 1's in $x^t$. Clearly, the random process $(X^t)$ is a Markov chain whose evolution can be described by the following probabilities: for $X^t \geq 2$ the probability that $X^t$ decreases by 1 or 2 is respectively $\alpha = \lambda^2 + \bar{\lambda}^2$ and $\beta = \lambda\bar{\lambda}$; the probability that it keeps its value is $1 - \alpha - \beta$. If $x^t$ equals $01^{n-2}$ up to shifts, $x^{t+1} = 0$ as the transition E applies deterministically. The evolution of this Markov chain is described in Fig. 1. Let $T_k$ be the average convergence time needed to attain 0. We have: $T_0, T_1 = 1$ and $\forall k \in \{2, \dots, n-2\}, T_k = 1 + \beta T_{k-2} + \alpha T_{k-1} + (1 - \alpha - \beta)T_k$ (see e.g. Ref. [7]).

Instead of solving the system, we can simply remark that a lower bound for $T_k$ is obtained by setting $\beta = 0$, in which case we obtain directly $T_k = 1 + 1/\alpha(k-1)$. Since $k$ is bounded by $n$ and since $p = \lambda^2 + \bar{\lambda}^2$ is independent of $n$, we obtain a lower bound for the convergence of $x$ that scales linearly with $n$. □

*Claim.* The rules (78,92), (136,192), (138,208), (140,196), (152,194), (168,224), (172,228) have linear convergence to a fixed point.
The space-time diagrams below illustrate this behaviour:

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

### 3.3 Quadratic convergence

As an easy case, we take the stochastic mixture between the left shift (ECA 170) and the right shift (ECA 240).

**Theorem 3.** For every $\lambda \in (0,1)$, the diploid (170, 240) has a worst expected convergence time that scales quadratically with $n$: $T(n) = \Theta(n^2)$.

The proof of the theorem relies on the following lemma.

**Lemma 1.** Let $(x^t)$ be the Markov chain that describes the evolution of a probabilistic cellular automaton $f$ on the configuration space $E$, and let $\mathcal{F}P$ be the set of fixed points of this rule. Let $W: E \to \mathbb{N}$ be a potential such that: $\forall x \in E, W(x) \in \{0, \dots, n\}$ and let us define the random process $(X_t)$ with $X_t = W(x^t)$ for all $t \in \mathbb{N}$.

- If the Markov chain $(x^t)$ is absorbing,

- if $(X_t)$ is a martingale, that is, if $\forall x \in E, \mathbb{E}\{X_{t+1} - X_t|\mathcal{F}_t\} = 0$, where $\mathcal{F}_t$ is a filtration that represents the history of the process at time $t$, and

- if there exists $\epsilon > 0$ such that:

$$x \notin \mathcal{FP} \implies \Pr[X^{t+1} \neq X^t] \geq \epsilon,$$

then the absorption time $T$ verifies $T \leq \frac{1}{\epsilon}n^2$.

Three different formulations of this very idea have already been proposed: two for fully asynchronous CA [8, 7] and one for probabilistic CA for the density classification problem [9]. This fourth version is a simple variation in order to accommodate the new possibility of having “chequerboards” as a new situation where $W$ would not vary (and which are thus equivalent to fixed points). Indeed, when $n$ is even, we have $F(01) = 10$ and $F(10) = 01$ in a deterministic way.

*Claim.* The diploids (34,48), (42,112), (56,98), (162,176), and (162,186) have a quadratic convergence to **0** or to the chequerboard cycle.
The space-time diagrams below illustrate this behaviour:

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

*Claim.* For $n \in 2\mathbb{Z}$, the rules (3,17), (3,63), (3,119), (7,21), (7,31), (7,87), (27,83), (27,39), (27,53), (35,49) convergence quadratically to the **0-1-alternation** cycle or to the **01** and **10** fixed points.

*Claim.* For $n \in 2\mathbb{Z}$, the rules (12,207), (13,79), and (78,141) converge quadratically to the **01** and **10** fixed points.

The rules (5,95) and (15,85) converge quadratically to the **0-1-alternation** cycle or to the **01** and **10** fixed points.

For $n \in 2\mathbb{Z}$, the rules (34,187), (34,243), (35,115), (58,163), (58,177), (162,242) converge quadratically to the chequerboard cycle (**01-10-alternation**).

## 3.4 Linear-quadratic mixed convergence

**Theorem 4.** *The diploid (172, 202) = (DG, BE) has a linear convergence for $\lambda \in (0, 1/2) \cup (1/2, 1)$ and a quadratic convergence for $\lambda = 1/2$.*

The discontinuity at $\lambda = 1/2$ can be explained by noting that for $\lambda \in (0, 1/2)$, the density is biased towards **0**, while it is biased towards **1** for $\lambda \in (1/2, 1)$. However, for $\lambda = 1/2$, the density follows non-biased random walk, which typically produces a quadratic convergence time (see e.g. Sec. 4 of Ref. [7]).

## 3.5 Other dynamics

Many other phenomena deserve a specific attention. For example, there are diploid rules, such as (46,116), which show second-order phase transitions, with the presence of *two critical rates* which separate the active phase, with a stationary state that has a positive density, and an extinct phase, where the **1**'s tend to disappear until the fixed point **0** is attained.

We also noticed that (56,185) has a quite peculiar behaviour: although it starts with a stochastic behaviour, its evolution quickly becomes deterministic. This can be understood by observing that only the transitions **A** and **H** are random and by noting that the number **a**- and **h**-cells decreases with time.

There are also many rules which cannot converge to a fixed point and whose density profile can be easily computed with a mean-field approximation. This is for example the case of the *positive-rate rules*, that is, the diploids for which for
each transition, the probability to update to 0 and to 1 are both positive. We also leave for future work the analysis of the endogamous rules with an exponential convergence time.

## References

[1] Souvik Roy, Harsh Modi, Rohil Patel, and Sumit Adak. "Are Some Family Members Harmful? - A Study on Diploid Cellular Automata". In: *Proceedings of ACRI 2024 - 16th International Conference on Cellular Automata for Research and Industry*. Ed. by Franco Bagnoli, Jan M. and Stefania Bandini Baetens, and Tommaso Matteuzzi. Vol. 14978. Lecture Notes in Computer Science. Springer, 2024, pp. 10-21. DOI: 10.1007/978-3-031-71552-5_2.

[2] Jean Mairesse and Irène Marcovici. "Around probabilistic cellular automata". In: *Theoretical Computer Science* 559.0 (2014). Non-uniform Cellular Automata, pp. 42-72. DOI: 10.1016/j.tcs.2014.09.009.

[3] Witold Bołt, Aleksander Bołt, Barbara Wolnik, Jan M Baetens, and Bernard de Baets. "A statistical approach to the identification of diploid cellular automata based on incomplete observations". In: *Biosystems* 186 (2019), p. 103976. DOI: 10.1016/j.biosystems.2019.103976.

[4] Emilio N.M. Cirillo, Francesca R Nardi, and Cristian Spitoni. "Phase transitions in random mixtures of elementary cellular automata". In: *Physica A: Statistical Mechanics and its Applications* 573 (2021), p. 125942. DOI: 10.1016/j.physa.2021.125942.

[5] Emilio N.M. Cirillo, Giacomo Lancia, and Cristian Spitoni. "Block approximations for probabilistic mixtures of elementary cellular automata". In: *Physica A: Statistical Mechanics and its Applications* 654 (2024), p. 130150. ISSN: 0378-4371. DOI: 10.1016/j.physa.2024.130150.

[6] Nazim Fatès, Damien Regnault, Nicolas Schabanel, and Eric Thierry. "Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata". In: *Proceedings of LATIN 2006*. Ed. by José R. Correa, Alejandro Hevia, and Marcos A. Kiwi. Vol. 3887. Lecture Notes in Computer Science. Springer, 2006, pp. 455-466. DOI: 10.1007/11682462_43.

[7] Nazim Fatès. "A tutorial on elementary cellular automata with fully asynchronous updating". In: *Natural Computing* 19 (2020), pp. 179-197. DOI: 10.1007/s11047-020-09782-7.

[8] Nazim Fatès, Michel Morvan, Nicolas Schabanel, and Eric Thierry. "Fully asynchronous behavior of double-quiescent elementary cellular automata". In: *Theoretical Computer Science* 362 (2006), pp. 1-16. DOI: 10.1016/j.tcs.2006.05.036.

[9] Nazim Fatès. "Stochastic Cellular Automata Solutions to the Density Classification Problem - When Randomness Helps Computing". In: *Theory of Computing Systems* 53.2 (2013), pp. 223-242. DOI: 10.1007/s00224-012-9386-3.