Nazim Fatès
email: nazim.fates@loria.fr

Stochastic Cellular Automata Solutions to the Density Classification Problem -When randomness helps computing *

In the density classification problem, a binary cellular automaton (CA) should decide whether an initial configuration contains more 0s or more 1s. The answer is given when all cells of the CA agree on a given state. This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA.

We investigate how randomness in CA may help us solve the problem. We analyse the behaviour of stochastic CA rules that perform the density classification task. We show that describing stochastic rules as a "blend" of deterministic rules allows us to derive quantitative results on the classification time and the classification time of previously studied rules.

We introduce a new rule whose effect is to spread defects and to wash them out. This stochastic rule solves the problem with an arbitrary precision, that is, its quality of classification can be made arbitrarily high, though at the price of an increase of the convergence time. We experimentally demonstrate that this rule exhibits good scaling properties and that it attains qualities of classification never reached so far.

Introduction

The density classification problem has a surprisingly simple formulation: how does a dynamical system decide what is the majority state in its initial configuration? The problem is trivial in most "classical" computing frameworks (e.g., Turing machines) but the challenge here is to perform the task with the following constraints:

1. autonomy: There is no external "head" or operator to perform the computation. Instead the system should perform the calculus autonomously, allowing only changes in the state of its components, the cells.

consensus:

The end of the computation is attained when the system reaches a stable consensus in which all the cells agree on a given state.

3. locality: Each cell has only a partial view of the system. Typically, a cell can see only the other cells that are located within a given range of perception.

4. spatial and temporal uniformity: All cells obey the same law, which remains fixed over time.

5. simplicity: The state of the cells is binary.

This problem, also known as the majority problem, has been mostly studied in the context of one-dimensional binary cellular automata (CA): the cells are arranged in a ring and cells change their state synchronously, depending on their own state and the states of the cells at a fixed distance, called the radius of the neighbourhood. It is of course possible to generalise the problem to other similar systems such as higher-dimension CA [START_REF] Alonso | A very effective density classifier two-dimensional cellular automaton with memory[END_REF] or networks [START_REF] Darabos | Scalefree automata networks are not robust in a collective computational task[END_REF]B 09].

This inverse problem has attracted a considerable amount of research since its formulation by Packard [START_REF] Norman | Dynamic Patterns in Complex Systems, chapter Adaptation toward the edge of chaos[END_REF]. Note that originally, the goal was to search for non-ergodic rules rules that would be robust to noise in the sense that they would suppress errors and return to equilibrium if their evolution was perturbed [START_REF] Gács | Onedimensional homogeneous media dissolving finite islands[END_REF]. The difficulty of finding a solution comes from the impossibility to centralise the information or to use any classical counting technique. Instead, the convergence to a uniform state should be obtained by using only local decisions, which might in some cases contradict the global trend of the system. Moreover, as the structure of CA is homogeneous in space and time, there can be no specialisation of the cells for a partial computation. Solving the problem efficiently requires to find the right balance between deciding locally with a short-range view and following other cells' decision to attain a global consensus.

The quest for efficient rules has been conducted on two main directions: man-designed rules and rules obtained with large space exploration techniques such as genetic algorithms (e.g., [START_REF] Mitchell | Evolving cellular automata to perform computations: Mechanisms and impediments[END_REF]). The Gacs-Kurdymov-Levin (GKL) rule, which was originally designed in the purpose of resisting small amounts of noise [START_REF] Gács | Onedimensional homogeneous media dissolving finite islands[END_REF][START_REF] Gonzaga | The Gacs-Kurdyumov-Levin automaton revisited[END_REF], proved to be a good candidate (∼80% of the initial conditions well-classified on rings of 149 cells) and remained unsurpassed for a long time. In 1995, after observing that outperforming this rule was difficult, Land and Belew issued a key result: no perfect (deterministic) density classifier that uses only two states exist [START_REF] Land | No perfect two-state cellular automata for density classification exists[END_REF]. However, this did not stop the search for efficient CA as nothing was known about how well a rule could perform. The search for rules with an increasing quality has been carried on until now, with genetic algorithms as the main investigation tool (see e.g. [START_REF] Pedro | The best currently known class of dynamically equivalent cellular automata rules for density classification[END_REF][START_REF] Gina | Some investigations about synchronization and density classification tasks in one-dimensional and two-dimensional cellular automata rule spaces[END_REF] and references therein).

On the other hand, various modifications to the classical problem were proposed, allowing one to solve the problem exactly. For instance, Capcarrere et al. proposed to modify the output specification of the problem to find a solution that classifies the density perfectly [START_REF] Mathieu | Twostate, r = 1 cellular automaton that classifies density[END_REF]. Fukś showed that running two CA rules, namely the "traffic" and "majority" rules, successively would also provide an acceptable solution [START_REF] Fukś | Solution of the density classification problem with two cellular automata rules[END_REF]. Note that the new stochastic rule that we propose also combines these two elementary rules, although in a different way. Later, Martins and Oliveira discovered various couples and triples of rules that solve the problem when applied sequentially and for a fixed number of steps [START_REF] Claudio | Evolving sequential combinations of elementary cellular automata rules[END_REF] that depends on lattice size. Some authors also proposed to embed a memory in the cells to enhance the abilities of the rules [START_REF] Alonso | A very effective density classifier two-dimensional cellular automaton with memory[END_REF][START_REF] Stone | Evolution of cellular automata with memory: The density classification task[END_REF].

However, all of these solutions break at least one of the constraints mentioned above. The use of stochastic (or probabilistic)1 CA is an interesting alternative that complies with these constraints. Indeed, in stochastic CA, the only modification to the CA structure is that the outcome of the local transitions of the cells is no longer deterministic: it is specified by a probability to update to a given state. The use of randomness to solve the problem was first proposed by Fukś who exhibited a rule which acts as a "stochastic copy" of the state of the neighbouring cells [START_REF] Fukś | Nondeterministic density classification with diffusive probabilistic cellular automata[END_REF]. However, this mechanism generates no force that drives the system towards its goal; the convergence is mainly attained with a random drift of the density (see Sec. 2). Recently, Schüle et al. proposed a stochastic rule that implements a local majority calculus [START_REF] Schüle | Computing with probabilistic cellular automata[END_REF]. This allows the system to converge to its goal more efficiently, but the convergence still remains bounded by some intrinsic limitations (see Sec. 3).

We propose to follow this path and present a new stochastic rule that solves the density classification problem with an arbitrary precision, that is, for any ring size, the probability of success of the classification can be set arbitrarily close to 1 (Sec. 4). This answers negatively to whether there exists an upper bound on the success rate one can reach without extending the radius of the neighbourhood of the rules.

The idea is to use randomness to solve the dilemma between the local majority decisions and the propagation of a consensus state. A trade-off is obtained by tuning a single parameter that weights two well-known deterministic rules, namely the majority rule and the "traffic" rule. We show that the probability of making a good classification approaches 1 as the probability to apply the ma-jority rule gets close to 0. This increase of quality however comes at the expense of a longer convergence time. We perform numerical simulations and show that good classification rates can be attained within a "reasonable" computational time.

Formalisation of the Problem

In this section, we define the deterministic Elementary Cellular Automata and their stochastic counterpart. We introduce the main notations for studying our problem.

Elementary Cellular Automata

Let L = Z/nZ represent a set of n cells arranged in a ring. Each cell can hold a state in {0, 1} and we call a configuration the state of the system at a given time ; the configuration space is E n = {0, 1} L , it is finite and we have |E n | = 2 n . We denote by |x| P the number of occurrences of a pattern P in x. The density ρ(x) of a configuration x ∈ E n is the ratio of 1s in this configuration: ρ(x) = |x| 1 /n. We denote by 0 = 0 L and 1 = 1 L the two special uniform configurations. For q ∈ {0, 1}, a configuration x is a q-archipelago if all the cells in state q are isolated, that is, if x does not contain two adjacent cells in state q.

In all the following, we assume that n is odd. This will prevent us from dealing with configurations that have an equal number of 0s and 1s.

An Elementary Cellular Automaton (ECA) is a one-dimensional binary CA with nearest neighbour topology, defined by its local transition rule, a function φ : {0, 1} 3 → {0, 1} that specifies how to update a cell using only nearestneighbour information. For a given ring size n, the global transition rule Φ : E n → E n associated to φ is the function that maps a configuration x t to a configuration x t+1 such that:

∀c ∈ L, x t+1 c = φ(x t c-1 , x t c , x t c+1 ) .
A stochastic Elementary Cellular Automaton (sECA) is also defined by a local transition rule, but the next state of a cell is known only with a given probability. In the binary case, we define f : {0, 1} 3 → [0, 1] where f (x, y, z) is probability that the cell updates to state 1 given that its neighbourhood has the state (x, y, z). The global transition rule F associated to the local function f is the function that assigns to a random configuration x t the random configuration x t+1 characterised2 by:

∀c ∈ L, x t+1 c = B t c f (x t c-1 , x t c , x t c+1 ) (1)
where x t c denotes the random variable that is given by observing the state of cell c at time t and where (B t c ) c∈L,t∈N is a sequence of independent Bernoulli random variables, that is, B t c (p) is a random variable that equals to 1 with probability p and 0 with probability 1 -p.

Density Classifiers

We say that a configuration x is a fixed point for the global function F if we have F (x) = x with probability 1 and we say that F is a (density) classifier if 0 and 1 are its two only fixed points.

For a classifier C, let T (x) be the random variable that takes its values in N ∪ ∞ defined as:

T (x) = min t : x t ∈ {0, 1} .

We say that C correctly classifies a configuration x if T (x) is almost surely finite and if x T (x) = 1 for ρ(x) > 1/2 and x T (x) = 0 for ρ(x) < 1/2. The probability of good classification G(x) of a configuration x is the probability that C correctly classifies x.

To evaluate quantitatively the quality of a classifier, we need to choose a distribution of the initial configurations. Various such distributions are found in literature, often without an explicit mention, and this is why one may read different quality evaluations for the same rule (for instance compare the results given for the GKL rule: 82% in Ref. [START_REF] Mathieu | Twostate, r = 1 cellular automaton that classifies density[END_REF] and 97.8% in Ref. [START_REF] Land | No perfect two-state cellular automata for density classification exists[END_REF]). In order to avoid ambiguities, we re-define here the three main distributions of initial configurations that have been used by authors:

(a) The binomial distribution µ b is obtained by choosing a configuration uniformly in E n .

(b) The d-uniform distribution µ d is obtained by choosing an initial probability p uniformly in [0, 1] and then building a configuration by assigning to each cell a probability p to be in state 1 and a probability 1 -p to be state 0.

(c) The 1-uniform distribution µ 1 is obtained by choosing a number k uniformly in {0, . . . , n} and then by choosing uniformly a configuration in the set of configurations of E n that contain exactly k ones.

Formally,

∀x ∈ E n , µ b (x) = 1 2 n ; µ d (x) = 1 0 p k (1 -p) n-k dp ; µ 1 (x) = 1 n + 1 • 1 n k
where k = |x| 1 is the number of 1s in x.

Proposition 1. The d-uniform distribution µ d and the 1-uniform distribution µ 1 are equal.

Let us show the equality:

∀x ∈ E n , µ d (x) = 1 0 ρ k (1 -ρ) n-k dρ = 1 n + 1 • 1 n k = µ 1 (x) .
Proof. A first technique to prove the result is to remark that µ d (x) corresponds to the calculus of the Beta function B(k + 1, n -k + 1). This function is defined on real numbers and it was studied by Euler and Legendre. Its analytical form is generally obtained by applying a change of variable and using trigonometric relations.

We now propose a different proof, which relies on more combinatorial arguments. For i ∈ {0, . . . , n}, let us introduce

M i = 1 0 n i p i (1 -p) n-i dp.
By noting that:

1 n = (p + (1 -p)) n = n i=0 n i p i (1 -p) n-i
we find that

n i=0 M i = 1 0 1 • dp = 1.
On the other hand, using the integration by parts of M i gives:

M i = n i • 1 0 p i (1 -p) n-i dp = n i . 1 i+1 p i+1 (1 -p) n-i 1 0 + 1 0 n-i i+1 p i+1 (1 -p) n-(i+1) dp
As the first term of the sum equals 0 and

n i • n-i i+1 = n i+1 , we obtain M i = M i+1 , which gives M i = 1 n+1 and confirms µ d = µ 1 .
We can now define the quality Q of a classifier C for a given a ring size n and an initial distribution µ on E n :

Q(n) = x∈En G(x) • µ(x) .
We denote by Q b the quality, obtained with the distribution µ b , and Q d the d-uniform quality obtained with the distribution µ d . In most cases, we will have Q b < Q d as for a large n, most initial configurations of E n have a density close to 1/2 and are generally more difficult to classify. The d-uniform distribution avoids putting too much weight on the "difficult" configurations by assigning an equal chance to appear to all the initial densities.

Similarly, we define the average classification time with regard to distribution µ as

T µ = x∈En E T (x) µ(x) .
We denote by T b and T d the average classification time obtained with the µ b and µ d distributions, respectively. As for most classifiers we have T d < T b , we are only interested in estimating T b .

Table 1: Table of the 8 active transitions and their associated letters. The transition code of an ECA is the sequence of letters of its active transitions. The space of sECA can be described as an eight-dimensional hypercube with the 256 ECA in its corners. This can be perceived intuitively if we see sECA rules as vectors, to which we apply the operations of addition and multiplication. More formally, taking k sECA f 1 , . . . , f k and w 1 , . . . , w k real numbers in [0, 1] such that k i=1 w i = 1, the barycenter of the sECA (f i ) with weights w i is the sECA g defined with:

∀x, y, z ∈ {0, 1}, g(x, y, z) = k i=0 w i f i (x, y, z) .
A potential advantage of using a barycenter is to re-interpret the dynamics of the sECA g: it is equivalent to the the dynamics of a process where, for each cell independently, the rule f i would be applied with probability w i .

Another way to define an sECA is to use a simple combination of other sECA. In this case, the functions (f i ) and the weights w i should be such as, for all triples (x, yz), the sum

k i=1 w i f (x, yz) is in [0, 1].
The most intuitive basis of the sECA space is formed by the 8 (deterministic) ECA that have only one transition that leads to 1: the coordinates correspond to the values f (x, y, z). Alternatively, one may express any sECA as a combination of the 8 ECA that have only one active transition, that is, only one change of state in their transition table. Such ECA are labelled A, B, ..., H according to the notation introduced in Ref. [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF] and summed up in Tab. 1. Formally, for every sECA f , there exists a 8-tuple (p A , p B , . . . , p H ) ∈ [0, 1] 8 such that:

f = p A •A+p B •B+• • •+p H •H. We denote this relationship by f = [p A , p B , . . . , p H ] T ,
where the subscript T stands for (active) transitions.

This basis presents many advantages for studying the random evolution of configurations (see Ref. [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF]), as the eight weights code for how much "change" is assigned to each transition. The group of symmetries of a rule can easily be obtained: the left-right symmetry permutes p B and p C , and p F and p G , whereas the 0-1 symmetry permutes p A and p H , p B and p G , etc.

The main advantage of this transition code is to allows us to easily write the conservation laws of a stochastic CA and thus to estimate some aspects of its global behaviour. To do this analysis, we will write a(x) = |x| 000 , b(x) = |x| 001 , . . . , h(x) = |x| 111 (see Tab. 1) and drop the argument x when there is no ambiguity. The following equalities hold [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF]:

b + d = e + f = c + d = e + g ; b = c ; f = g .
(2) Starting from a simple example, we now detail how to use these tools to analyse the behaviour of an sECA.

Fukś Density Classifier

To start examining how stochastic CA solve the density classification problem, let us first consider the probabilistic density classifier proposed by Fukś [START_REF] Fukś | Nondeterministic density classification with diffusive probabilistic cellular automata[END_REF].

For p ∈ (0, 1/2], the local rule C F is defined with the following transition table :   (x, y, z) 000 001 010 011 100 101 110 111

C F (x, y, z) 0 p 1 -2p 1 -p p 2p 1 -p 1 .
For any ring size n, this rule is a density classifier as 0 and 1 are its only fixed points. With the transition code of Sec. 1.3, we write:

C F = [0, p, p, 2p, 2p, p, p, 0] T = p • BDEG + p • CDEF
where the rules 3 BDEG(170) and CDEF(240) are the left and right shift respectively. This means that Fukś' rule can be interpreted as applying, for each cell independently: (a) a left shift with probability p, (b) a right shift with probability p, and (c) staying in the same state with probability 1 -2p (see Fig. 1).

We also note that this rule is invariant under both the left-right and the 0-1 permutations (as

p B = p C = p F = p G , p A = p H and p D = p E ).
Theorem 1. For the classifier C F set with p ∈ (0, 1/2],

∀x ∈ E n , G(x) = max {ρ(x), 1 -ρ(x)} and E T (x) ≤ |x| 1 (n -|x| 1 ) p .
The relationship on G(x) was observed experimentally with simulations and partially explained by combinatorial arguments [START_REF] Fukś | Nondeterministic density classification with diffusive probabilistic cellular automata[END_REF]. As for the classification time of the system, no predictive law was given. We now propose a proof that uses the analytical tools developed for asynchronous ECAs [START_REF] Fatès | Fully asynchronous behavior of double-quiescent elementary cellular automata[END_REF] and completes the results established by Fukś. The proof stands on the following lemma:

Lemma 1. Let (X t ) be a sequence of random variables that represents the evolution of a Markov process on {0, . . . , m} where m is any integer. Let T (x) = min{t : X t = 0 or X t = m} be the absorbing time of the process.

If X t and ∆X t+1 = X t+1 -X t verify that:

• the stochastic process (X t ) is a martingale, that is, for the filtration F t = σ(X 0 , . . . , X t ), E ∆X t+1 |F t = 0,

• for t < T , E ∆X 2 t+1 |F t > v, then:
Pr{X T = m} = q m and T is almost surely finite and obeys:

E{T (x)} ≤ q(m -q) v ≤ m 2 4v
where q = E{X 0 }.

Proof. First, let us show that T is almost surely finite. We remark that, as long as the process has not converged, ∆X t+1 has a null expectation and a non zero variance. There exists a constant p such that t < T =⇒ Pr{∆X t+1 ≤ 1} > p, that is, the probability that X t decreases by at least one is non zero. For a given t < T , if we look m steps ahead, the probability that X t makes m successive decreases or attains the fixed point 0 before is then non-zero, say α. As (X t ) is a Markov process, this statement can be repeated for any t; the time of convergence to a fixed point is thus upper-bounded by the geometric law of parameter α.

As T is almost surely finite and (X t ) is bounded, T is a stopping time and we can apply Doob's optional stopping theorem on the martingale (X t ):

E X T = E X 0 = q .
On the other hand we have:

E X T = 0 • Pr{X T = 0} + m • Pr{X T = m} ,
which, by combining the two equations gives us: Pr{X T = m} = q/m.

To calculate an upper bound on T , let us consider the following process:

Y t = X 2 t -v • t.
For t < T , we have:

E Y t+1 -Y t |F t = E X 2 t+1 -X 2 t |F t -v = E (∆X t+1 + X t ) 2 -X 2 t |F t -v = E ∆X 2 t+1 |F t + 2 • E ∆X t+1 • X t |F t -v .
By definition of the conditional expectation, we have:

E ∆X t+1 • X t |F t = E ∆X t+1 |F t • X t = 0 .
By using the hypothesis of the Lemma:

t < T =⇒ E ∆X 2 t+1 |F t ≥ v, we obtain: E Y t+1 -Y t |F t ≥ 0, that is, (Y t ) is a submartingale 4 . Again,
noting that E T < ∞ and that (Y t ) is a process with finite increments, we apply the Optional Stopping Theorem: E Y T ≥ E Y 0 , which reads:

E X 2 T -v • T ≥ q 2 or E T ≤ E X 2 T -q 2 v . To calculate E X 2
T , we write:

E X 2 T = 0 2 • Pr{X T = 0} + m 2 • Pr{X T = m} = m • q
which gives us the expected result on E T .

We can now prove Theorem 1.

Proof. We simply show that Lemma 1 applies to X t = |x t | 1 . Denoting by Ã, B, the cells where transitions A, B, ... apply, and given that transitions B, C, D (resp. E, F, G) increase (resp. decrease) ∆X t+1 by 1, we write:

∆X t+1 = c∈ B, C B t c (p) + c∈ D B t c (2p) - c∈ Ẽ B t c (2p) - c∈ F , G B t c (p) (3)
where (B t c ) is the sequence of the Bernoulli random variables of Eq. (1). This gives:

E ∆X t+1 |F t = p • b + p • c + 2p • d -2p • e -p • f -p • g = p • (b + d -e -f ) + p • (c + d -e -g)
Using Eq. (2), we obtain E ∆X t+1 |F t = 0.

Let us now assume that t < T , that is, x t is not a fixed point. Using the independence of the random variables of Eq. (3) and var B(p) = p(1 -p), we obtain:

E ∆X 2 t+1 |F t = (b + c + f + g) • p(1 -p) + (d + e) • 2p(1 -2p) = p • [(s 1 + 2s 2 ) -(s 1 + 4s 2 ) • p]
where s 1 = b + c + f + g and s 2 = d + e. Using Eq. ( 2) and noting that the value of n is odd, we remark that there exists at least one 00 or 11 pattern in the configuration and that s 1 = b + c + f + g ≥ 2. From p ≤ 1/2, we obtain (s 1 + 2s 2 ) -(s 1 + 4s 2 ) • p ≥ 1 and E ∆X 2 t+1 |F t ≥ p. Lemma 1 thus applies by taking v = p and m = n. The probability that the process stops on X T = n, that is, on the fixed point 1, is equal to the initial density ρ(x) = |x| 1 /n. From this result, we derive that for any configuration x the probability of good classification is G(x) = max{ρ(x), 1 -ρ(x)} and obtain the upper-bound on E T (x) .

Theorem 2. The d-uniform quality of C F is Q d (n) = 3/4 + 1/4n. The quality of C F is Q b (n) = 1 2 + 1 2 n • n -1 n-1 2 .
The average classification time verifies

T b ∈ O(n 2 ).
Proof. The result on Q d is obtained with an integration or a sum (use µ d or µ 1 ); the result on T b is obtained with a simple upper-bound. Let us now calculate the quality Q b :

Q b (n) = 1 2 n x∈L max{ρ(x), 1 -ρ(x)} .
We group the configurations with equal number of 1s:

Q b (n) = 1 2 n n i=0 n i max{ i n , 1 - i n } .
For n = 2k + 1, we decompose the sum into:

Q b (n) = 1 2 n k i=0 n i n -i n + n i=k+1 n i i n .
Using the symmetry n i = n n-i , we obtain:

Q b (n) = 1 2 n • 2 • n i=k+1 n i i n = 1 2 n-1 k i=0 n -1 i .
To calculate the sum, we write n -1 = 2k and:

k i=0 2k i = k i=0 2k 2k -i = 2k i=k 2k i .
This gives: We then obtain:

2. k i=0 2k i = k i=0 2k i + 2k k + 2k i=k+1 2k i = 2 2k + 2k k .
Q b (n) = 1 2 2k 2 2k + 2k k 2 = 1 2 + n-1 (n-1)/2 2 n .
This formula explains why the quality of classification of C F quickly decreases as the ring size n increases. For instance for n = 49, we have: Q b (n) = 0.557, that is, the gain of using C F compared to a random guess is less than 6%. For the reference value n = 149, the gain drops down to 3.3% (see Fig. 4

p. 19).

It is interesting to note that the setting of p does not have any influence on the quality, but there exists a value p which minimises the classification time.

Schüle Density Classifier

We now consider the probabilistic density classifier proposed by Schüle et al. [START_REF] Schüle | Computing with probabilistic cellular automata[END_REF]. It was designed to improve the convergence of the system towards a fixed point. The idea of the authors is to "blend" the majority rule, which has good properties for the classification problem, with the XOR rule, which introduces some noise to make the boundaries between regions of 0s and 1s unstable. Formally, for ε ∈ (0, 1), the local rule C S is defined with the following transitions: (x, y, z) 000 001 010 011 100 101 110 111

C S (x, y, z) 0 1 -ε 1 -ε ε 1 -ε ε ε 1 .
This rule is a density classifier as 0 and 1 are its only fixed points. With the transition code of Sec. 1.3, we write:

C S = [0, 1 -ε, 1 -ε, ε, ε, 1 -ε, 1 -ε, 0] T = (1 -ε) • BCFG + ε • DE
where rule BCFG(150) is the rule that implements a XOR function with three neighbours and DE(232) is the majority rule. This means that Schüle's rule can be interpreted as applying for each cell independently: (a) a XOR with probability 1 -ε (b) a majority with probability ε (see Fig. 2). This rule is invariant under both the left-right and the 0-1 symmetries (as we have:

p B = p C = p F = p G , p A = p H and p D = p E ).

Exact results on Schüle's rule

Theorem 3. For the classifier C S set with ε = 2/3,

∀x ∈ E n , G(x) = max {ρ(x), 1 -ρ(x)} and E T (x) ≤ |x| 1 (n -|x| 1 ) (1 -) .
As a consequence, it has the same quality as Fukś rule and its classification time T b has the same scaling order:

T b ∈ O(n 2 ).
The relationship on G(x) was proved under the mean-field approximation [START_REF] Schüle | Computing with probabilistic cellular automata[END_REF]. We now propose to re-derive this result without approximation.

Proof. Let us take again X t = |x t | 1 and show that Lemma 1 applies to (X t ). Recall that we denote by Ã, B,... the cells where transitions A, B ,... apply. We have:

∆X t+1 = c∈ B, C B t c (1 -ε) + c∈ D B t c (ε) - c∈ Ẽ B t c (ε) - c∈ F , G B t c (1 -ε) ,
where (B t c ) is the sequence of Bernoulli random variables of Eq. ( 1). This gives:

E ∆X t+1 |F t = (1 -ε)(b + c -f -g) + ε(d -e) = (1 -ε) • (b + c -d + e -f -g) + d -e .
Using Eq. ( 2), we obtain:

E ∆X t+1 |F t = (3ε -2)(d -e) , (4)
which leads to E ∆X t+1 = 0 for ε = 2/3. On the other hand, let us assume that t < T , that is, x t is not a fixed point. This implies that b

+ c + d + e + f + g ≥ 1. As var B(ε) = var B(1 -ε) = ε.(1 -ε), we obtain: E ∆X 2 t+1 |F t = (b + c + d + e + f + g) • ε(1 -ε) ≥ ε(1 -ε) .
Lemma 1 thus applies by taking v = ε(1 -ε) and m = n. Consequently, we find that the probability that the process stops on the fixed point 1 (given by X T = n) is equal to X 0 /n = ρ(x), which gives the value of G(x) and the upper-bound on E T (x) .

General behaviour of Schüle's rule

Equation (4) also allows us to understand the general behaviour of the classifier C S for ε = 2 3 . Informally, let us consider a configuration x with a density close to 1. For such a configuration, we most likely have more isolated 0s than isolated 1s, that is, d -e > 0 and the sign of ∆X t+1 is the same as 3 -2. As for such configurations, we want the density to increase, we see that setting > 2/3 drives the system more rapidly towards its goal. This also explains why for < 2/3, it was no longer possible to observe the system convergence within "reasonable" simulation times. In fact, as observed by Schüle et al. [START_REF] Schüle | Computing with probabilistic cellular automata[END_REF], the system is then in a metastable state: although the classification time is almost surely finite, the system is always attracted towards a density 1/2. Last, but not least, we think that for > 2/3, only isolated 0s or 1s of the initial configuration contribute to driving the system to its goal. This leads us to formulate the following statement:

Proposition 2. For the classifier C S set with ε > 2/3, the quality of classifi- cation Q b (n) is bounded. More precisely: ∀x ∈ E n : |x| 010 = |x| 101 = 0, G(x) = max{ρ(x), 1 -ρ(x)} and ∀x ∈ E n , G(x) ≤ max{ρ * (x), 1 -ρ * (x)}
where ρ * (x) is the density attained by an asymptotic evolution of x under the majority rule.

Intuitively, let us consider a configuration x t that has no isolated 0 or 1. Equation (4) then reads E ∆X t+1 |F t = 0. At time t + 1, isolated 0s or 1s may appear (if transitions B and F, or C and G, are applied simultaneously) but there is an equal chance to make an isolated 0 than an isolated 1. As this analysis can be repeated recursively, this shows that once the first isolated 0s or 1s have disappeared (with the effect of the majority rule), the boundary of the homogeneous regions randomly drift until they merge. As a consequence, the probability of good classification of a configuration with no isolated 0 or 1 is the same as for Fukś classifier. This behaviour implies that the average convergence times scales as n 2 , which is confirmed experimentally (see Fig. 4).

We now present a rule that does not suffer from such limitations.

14 inria-00608485, version 3 15 Feb 2012

A New Rule for Density Classification

For η ∈ (0, 1], let us consider the stochastic rule C TM defined with:

(x, y, z) 000 001 010 011 100 101 110 111

C TM (x, y, z) 0 0 0 1 1 -η 1 η 1
With the transition code, we write:

C TM = [0, 0, 1 -η, 1, 1, 0, 1 -η, 0] T = η • DE + (1 -η) • CDEG .
For η ∈ (0, 1), the effect of the rule is the same as applying, for each cell and at each time step, the so-called "traffic" rule (see below) CDEG(184) with probability 1 -η and the majority rule DE(232) with probability η. We thus call this rule the traffic-majority rule.

General behaviour of the rule

The traffic rule is a well-known elementary rule that has the property to be number conserving, that is, the number of 1s is conserved as the system evolves (see e.g., [START_REF] Boccara | Number-conserving cellular automaton rules[END_REF]). Observing the evolution of this rule, we see that a 1 with a 0 at its right moves to right while a 0 with a 1 at its left is moved to the left. So everything happens as if the 1s were cars that tried to go to the right, possibly meeting traffic jams. These jams resorb by going in the inverse directions of the cars (when possible).

Combining this rule with applications of the majority creates a positive effect: a 1 followed by two 0 might simply disappear (see Fig. 3). So, if we start from a configuration with less 1s than 0s, all happens as if the 1s, which can be considered as defects, will spread on the lattice, and then progressively disappear by the effect of the majority rule. Moreover, even though the system is stochastic, there exists an infinity of configurations that can be classified with no error.

Lemma 2. An archipelago is well-classified with probability 1. A configuration x that is q-archipelago with k cells in state q has an average convergence time

E T (x) ≤ k/η.
Proof. The proof is simple and relies on two observations. First, let us note that the successor of a q-archipelago is a q-archipelago. To see why this holds, without loss of generality, let us assume that x is a 1-archipelago. By the application of the rule, all 1s are isolated and will be transformed into 0s. As for the 0s that will be transformed into 1s, they are necessarily preceded by a 1, which implies that no such two 0s can be found next to another in x.

Second, we remark that the number of 1s in x t is a non-increasing function of t. Indeed, at each time step, each isolated 1 can "disappear" if transition C is not applied, which happens with probability η > 0. As a result, all the 1s will eventually disappear and the system will attain the fixed point 0, which corresponds to a good classification as we have ρ(x) < 1/2. As long as the system has not reached a fixed point, there exists a probability greater than η to decrease the number of "islands" of the archipelago by 1; so if the archipelago is made of k islands, its disappearing average time is upper-bounded by k/η. Interestingly, we experimentally observed that the traffic-majority rule seems to have a bifurcation point at η = 1/2 : for η > 1/2, the qualitative behaviour of the rule is the same as Fukś or Schüle's rule: isolated 0s and 1s quickly disappear, then boundaries between homogeneous regions follow a random walk until they meet and annihilate. On the contrary, for η < 1/2, the system behaves "correctly": if for instance we start from a density lower than 1/2, we observe that regions of consecutive 1s are progressively transformed into regions of 01 patterns, and then, that these patterns dissolve from right to left due to the mechanism explained above.

Fig. 4 shows the values of Q b and T b estimated by numerical simulations. We can observe that the quality rapidly increases to high values, even when keeping the average convergence time to a few thousand steps. In particular for η < 1%, the quality goes above the symbolic rate of 90%, which, to our knowledge, had not been reached for one-dimensional systems (see e.g. [START_REF] Pedro | The best currently known class of dynamically equivalent cellular automata rules for density classification[END_REF][START_REF] Gina | Some investigations about synchronization and density classification tasks in one-dimensional and two-dimensional cellular automata rule spaces[END_REF]). Another major point regards the classification time of C TM : for n ≤ 300 and η ≤ 0.1, it is experimentally determined as varying linearly (or quasi-linearly) with the ring size n (see Fig. 5).

The general analytical estimation of the quality of C TM and its time of convergence is more complex than for Fukś and Schüle classifiers. However, some analytical can be obtained when the rate of application of the majority rule η, which represents the "randomness" of the system, becomes small.

Behaviour of the rule for a small amount of randomness

For a configuration x, we say that an archipelago a is appropriate if it has the same majority state as x, that is, if ρ(x) < 1/2 and ρ(a) < 1/2 or if ρ(x) > 1/2 and ρ(a) > 1/2. The second important property of the rule is that any configuration is transformed into an "appropriate" archipelago with a probability that approaches 1 as η → 0.

Lemma 3. For every p ∈ [0, 1), there exists a setting η of the classifier C TM such that every configuration x ∈ E n will evolve to an appropriate archipelago with a probability greater than p.

Proof. The idea of the proof is to compare the evolution of the traffic-majority rule C TM and the Traffic rule. First, we claim that, starting from any configuration x if these two rules evolve identically during the T = n/2 steps, the system reaches the appropriate archipelago (for x). This relies on the fact that (a) the Traffic rule is number conserving and (b) it always evolves to an archipelago in at most T steps (see e.g., Ref.

[CST96] Lemma 4). It is then sufficient to take η such that the probability that a difference between the two rules occurs is lower than p to prove the lemma. Looking at the transition tables the traffic rule and C TM , we see that such differences only occur if a transition 100 → 0 or 110 → 1 occur, which happens with probability η. Moreover, the number of occurrence of such transitions can be grossly upperbounded by nT , which gives η < p 1/nT to ensure that the probability that a difference occurs is lower than p.

However, it should be noted that the upper-bound established in the proof above does not give the correct order of the probability that a non-appropriate archipelago is reached (which implies fatally an error of classification). Indeed, if for instance the initial condition x has a density ρ(x) < 1/2, the transitions 100 → 0 are "beneficial" to the evolution and only the transitions 100 → 1 can lead to a "bad" state the density of which is higher than 1/2. Moreover, we can remark that (a) such "bad" transitions have to be more numerous than the difference between 0s and 1s in x and (b) a transition 100 → 1 can only concern a 0 that is always preceded by a 11 pattern before its "transformation". We leave as an open question the quantitative estimation of these effects and now to state our main result.

Theorem 4. For a quality q ∈ [0, 1), there exists a setting η of the classifier C TM such that ∀x ∈ E n , G(x) ≥ q. As a consequence, for η → 0 the quality verifies Q b (n) → 1.

Proof. We simply combine the two previous lemmas: for η small enough, the system evolves to an "appropriate" archipelago (Lemma 3); it will then progressively "drift" towards the appropriate fixed point (Lemma 2).

The drawback of setting η small is the increase of the time taken to classify a configuration. We experimentally verified that the system possesses an optimal convergence time. For n = 149, it is obtained for η ∼ 0.30 for which value the classification time is as low as T b ∼ 250 steps (see Fig. 4 p. 19). We leave the question open as to how to calculate this optimal value analytically.

Conclusion

This paper presented an analysis of three stochastic cellular automata that solve the density classification problem. We studied two known rules and presented a new rule which, for a given ring size, solves the problem with an arbitrary precision. This illustrates how, in some cases, randomness is not an obstacle to overcome but a useful means to achieve a computation that would otherwise be impossible in a strict deterministic computing framework. One may see an analogy with biological organisms, which need a certain degree of randomness to maintain their state and functions.

The use of analytical techniques originally developed for asynchronous cellular automata allowed us to gain a better understanding of the behaviour of the stochastic rules. Numerical simulations showed that for the standard reference value n = 149, the traffic-majority rule obtains a quality of classification over 90%, a result never attained so far. This shows that the construction is not only "theoretical" but also leads to an effective classification method. However, some questions remain unsolved, among which: Question 1. The results also suggest that the quality of classification cannot be taken as the unique criterion for evaluating the classifiers. As there exists some trade-off between quality and time to classify, we ask how to estimate numerically the best compromise between these two constraints. Schüle proposed to use the parameter Q/T [START_REF] Schüle | Computing with probabilistic cellular automata[END_REF]; one may also consider the quantity (Q -1/2)/T by noting that a purely random rule is useless. There are also other possibilities as to consider an average quantity of information gained at each time step, etc. Question 2. Are there are other couples (or t-uples) of rules that can be "blended" to obtain similar or even better results? Note that the "blending" technique could also be used with rules that have a larger radius, and on lattices with two or more dimensions. Question 3. It was shown that for a small neighbourhood (radius 1), one may construct a rule that performs arbitrarily well for any ring size. However, what can we say if the rule is fixed and if we evaluate its quality over any ring size? In particular, does there exist a rule whose quality for a large ring size does not approach 1/2 (pure randomness)? We conjecture that such a rule does not exist for the Binomial distribution (but we saw that there are solutions for other initial distributions such as the d-uniform distribution).

acknowledgements

The author expresses his sincere gratitude to the two anonymous referees and to his collaborators for interesting remarks and suggestions which resulted from a careful reading of the manuscript.

  Structure of the sECA space

Figure 1 :

 1 Figure 1: Space-time diagrams showing the evolution of Fuks' classifier C F with n = 25, p = 0.48 and the same initial condition of density 8/25 = 0.32. Time goes from bottom to top; white cells are 0-cells and blue cells are 1-cells. (left) good classification; (middle) uncertain evolution of the system; (right) bad classification.

Figure 2 :

 2 Figure 2: Space-time diagrams showing the evolution of Schuele classifier C S with n = 25, ε = 0.75 and the same initial condition of density 8/25 = 0.32. (left) good classification; (middle) uncertain evolution of the system; (right) bad classification.

Figure 3 :

 3 Figure 3: Space-time diagrams showing the evolution of traffic-majority classifier C TM with n = 25, η = 0.30 and the same initial condition of density 8/25 = 0.32. (left) good classification; (middle) good classification will happen with proba 1; (right) bad classification will happen with proba 1.

Figure 4 :

 4 Figure 4: Quality of classification Q b and convergence time T b for a ring size n = 149; averages obtained with 10 000 samples. (top) Fukś rule; (middle) Schüle's rule ; (bottom) traffic-majority rule.

Question 4 .

 4 Last, we ask how to generalise the problem to infinite lattices. In a recent work, Marcovici et al. obtained various results for CA where the cells are initialised by independent Bernoulli random variables of parameter p [BFMM11]. However, the question as to whether the traffic-majority rule solves the problem for Z remains an open problem.

Both terms 'stochastic' and 'probabilistic' CA are found in literature. We prefer to employ the former as etymologically the Greek word 'stochos' implies the idea of goal, aim, target or expectation.

Note that defining rigorously the sequence of random variables x t obtained from F would require to introduce advanced tools from the probability theory.

We give the "classical" rule code into parenthesis; it is obtained by converting the sequence of 8 bits of the transition table (000 to 111) to the corresponding decimal number.

Rigorously, one needs to use the "stopped" process Yt = X 2 t∧T -v • (t ∧ T ).