Asynchronous cellular automata and brownian motion.

This paper deals with some very simple interacting particle systems, elementary cellular automata, in the fully asynchronous dynamics: at each time step, a cell is randomly picked, and updated. When the initial configuration is simple, we describe the asymptotic behavior of the random walks performed by the borders of the black/white regions. Following a classification introduced by Fates et al., we show that four kinds of asymptotic behavior arise, two of them being related to Brownian motion.

Keywords: cellular automata, asynchronism, random processes, coalescent random walks

Contents

1 Introduction                                                 386

1.1 Elementary Cellular Automata                               386
1.2 Worst expected convergence time                            387
1.3 Convergence in Pp(I)                                       389
1.4 The results                                                390

2 Quadratic automata: non-random limit                         390
2.1 The automaton FG                                           390
2.2 Other quadratic automata                                   392

3 Cubic automata : interactions between Brownian motions       392
3.1 The automaton BCEFG                                        392
3.2 Automata BDEF, BEF, BCDEFG, BCEFG : Brownian motion        396
3.3 Automata BDEG, BEG: no convergence                         396

4 Exponential automaton: no convergence                        396
4.1 The automaton BDFG.                                        396

5 Divergent automata                                           398
5.1 The automata BCFG, BF and CF: reflected Brownian motions   398
5.2 The automaton BCF                                          399
5.3 The automaton BG                                           399

1 Introduction

1.1 Elementary Cellular Automata

Cellular automata are dynamical systems widely used the two last decades in order to modelize phenomena arising in game theory, economy, theoretical physics, biology, or theoretical computer science (complexity, computation). It consists of a (finite or countable) set of cells, the state of each cell at time 1 being a function of the state of its neighbours at time 1 - 1. The set of possible states is finite, and, as we see, time is discrete. Cellular automata were introduced by von Neumann [vN66] in order to emulate self-replication in biology.

This paper deals more specifically with elementary cellular automata (ECA), introduced by Wolfram [Wo184], that is two-state automata (0/1 or white/black) with a finite and cyclic set of cells. Let us recall a few definitions.

Definition 1 A (deterministic) elementary cellular automaton (ECA) is a triplet (n, x(0), b), in which n stands for the number of cells, x(0) [member of] {0, 1} denotes the initial configuration and b : {0,1}s {0,1} is the local transition function, or local rule.

The first studies focused on the synchronous dynamic of (n, x (0), b), i.e. the evolution of the configuration under iterations of the function [A.sup.[delta] on x(0):

[A.sup.[delta]: {0,1}n [right arrow] {0,1}n ([X.sub.i],...,[x.sub.n]) [right arrow] ([x'.sub.i]..., [x'.sub.n])

in which, for i [member of] {1, 2, ... , n}, [x'i = [delta]([x.sub.i-1], [x.sub.i], [x.sub.i+1]), that is, the n cells are updated simultaneously. It must be understood with the convention x,,+1 = x1, xo = x, so that the set of configuration is cyclic.

Thus, (x(k);k = 0, 1....) is a sequence of words of length n on the alphabet {0,11. Alternatively, we shall consider configurations as doubly infinite periodic sequences (xn)neZ, with period n. We will focus here only on double-quiescent ECA, i.e. ECA for which b(0, 0, 0) = 0 and b(1, 1, 1) = 1. This terminology has been introduced in [FMST05].

We are intersested here in the asynchronous dynamic: when the n cells are not updated simultaneously, but randomly picked and sequentially updated.

Definition 2 The fully asynchronous dynamic of the automaton b is the random process on 10,11n defined by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where (ik)k [less than or equal to] 1 is a sequence of i.i.d. random variables, uniform in f l, . . . , of and AS is the function defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

in which [x'.sub.j] = [delta]([x.sub.j-1], [x.sub.j], [x.sub.j+1]), while, if i [not equal to] j, [x'.sub.i] = [x.sub.i].

Influence of asynchronism in ECA's has been studied for instance in [11384, SdR99], with motivations in physics, and in biology. It turns out that asynchronism actually changes drastically the asymptotic behavior of cellular automata (see Figure 1.2 below for a simulation).

1.2 Worst expected convergence time

In the asynchronous case, for the 64 double-quiescent ECA s, the question of worst expected convergence time has been exhaustively investigated by Fates et al. [FMSTOS], with surprising results, that we recall below. A local transition function b is given by its eight transitions. A transition is said to be active if it changes the cell it is applied to. Of course b is completely determined by its active transitions. Active transitions are labelled with a letter, as follows (a notation that proves to be quite handy when classifying ECA's).

 A     B     C     D     E     F     G     H
000   001   100   101   010   011   110   111
 1     1     1     1     0     0     0     0

For instance, the only cells possibly changed by the automaton [delta] = DG are precisely the white cells surrounded by two black cells, and the black cells with a black cell on the left side and a white cell on the right side. Double-quiescent ECA are those for which neither A nor H appear. The automaton Identity is denoted 0. For an automaton [delta], [??][delta] denotes the set of fixed points of b (of course, when b is double-quiescent, {[0.sup.n], [1.sup.n],[1.sup.n]} [subset] [??] [delta]).

Definition 3 Given a fully asynchronous automaton (n, x(0), b), Tn = Tn(b, x(0)) denotes the random variable

Tn = inf {k [greater than or equal to] 0; [X.sub.k] [member of] [??] [delta]},

in which we use the convention inf {0} = + [infinity]. The Worst Expected Convergence Time WECT[delta] is the real number

WEC[T.sub.[delta] = max E[[T.sub.n](b, x(0))]. x(oM0,l}n

Fates et al. [FMST05] classify the 64 double-quiescent ECA's in five families, according to the asymptotic behavior of WEC[T.sub.[delta], when n is large. Let [THETA](9n) denote the set of sequences f = (fn) n[greater than or equal to]1 that satisfy [c.sub.1] [less than or equal to] fn/gn [less than or equal to] [c.sub.2], for suitably chosen constants [c.sub.1], [c.sub.2] [member of] (0, + [infinity]) that depend on f but not on n.

Theorem 1 (Fates, Morvan, Schabanel & Thierry [FMST05]) For [delta] [not equal to] 0, either WEC[T.sub.[delta] is infinite or it belongs to one of these four classes : [THETA](nlogn), [THETA]([n.sup.2]), [THETA]([n.sup.3]), [THETA](n [2.sup.n]). The corresponding families of automata are called respectively Divergent, Coupon Collector, Quadratic, Cubic, and Exponential.

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

This classification is remarkably similar to that introduced by Wolfram in a completely different context. For reasons of symmetry between black and white, or between left and right, the 64 cases reduce actually to 25. The main results of [FMST05] are summarized in Figure 1 (the third column gives the number of symmetries).

Without loss of generality, we assume in the sequel that n is even. Original motivation of this work was to refine the methods leading to Theorem 1. When the initial configuration contains only one black region, say x(0) = [0.sup.n/2][1.sup.n/2], the whole sequence (x([kappa])) in the asynchronous dynamic contains only one black region (see Fig. 1.2), unless it has reached the fixed point [O.sup.n]. We assume from now on that x(0) = [0.sup.n/2][1.sup.n/2]. In a longer paper, we shall discuss the asymptotic behavior of the borders of black regions for an initial state with several black regions. We set (Ro, Lo) = (0, n/2). For 1 < Tn, we define ([R.sub.[kappa], [L.sub.[kappa]) by induction as the unique element of [Z.sup.2] such that X[L.sub.[kappa] ([kappa]) = 0, X [L.sub.[kappa]+1 ([kappa]) = 1, and |[L.sub.[kappa]] - [L.sub. [kappa]-1]| [less than or equal to] 1, resp. X [R.sub.[kappa]] ([kappa]) = 1, X[L.sub.[kappa]+1] ([kappa]) = 0 and |[R.sub.[kappa] - [R.sub.[kappa]| 1 [less than or equal to] 1. This way, we can track if the black zone shifts, makes several revolutions, for instance.

Simulations suggest that there exists a continuous limit for the bi-dimensional process (Rk, Lk)k>o, after a suitable renormalization. Precisely, given some automaton, we exhibit some continuous process with values in [R.sup.2] such that the following weak convergence holds (in a sense to be defined in the next Section):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

From this convergence of stochastic processes, we hope to deduce quantitative information on statistics of automata, e.g. on the r.v. [T.sub.n]/E[[T.sub.n]].

1.3 Convergence in [D.sub.p](I)

If I is an interval [0, T], with 0 [less than or equal to] T [less than or equal to] + [infinity], let [D.sub.p](I) be the set of cadlag(i) functions: I [right arrow] [R.sup.P]. We adress the convergence of random variables in [D.sub.p] (I), endowed with the Skorohod topology. Recall that, when the limit is a continuous function, convergence in the Skorohod topology is equivalent to uniform convergence on compact sets, that is, convergence for the distance

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Definition 4 (Convergence in [D.sub.p] (I)) Let X (resp. ([X.sup.(n)]) n[greater than or equal to]0) be a random variable (resp. a sequence of random variables) with values in Dp (I). The sequence X (n) converges weakly to X, if for arty function L : [D.sub.p] (I) [right arrow] R, bounded and continuous,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We shall use the notation

[X.sup.(n)] [right arrow] X.

We use repeatedly the next two results:

Theorem 2 ([Bi168], Th. 5.1) Let h : Pp (1) [right arrow] Pp (1), and Dh be the set of discontinuity points of h. Assume that [X.sup.(n]) [right arrow] X and that P(X [member of] [D.sub.h]) = 0. Then

h(X(n)) [right arrow] h (X).

Perhaps the most important result of convergence of stochastic processes is the convergence of renormalized random walks to the linear Brownian motion (Bt)t>o [Bi168, Don51, RY99]:

Theorem 3 (Donsker [Don51]) Let X1, X2, ... be a sequence of i.i.d. random variables with E[[X.sub.i]] = 0 and IE[X2] = 1. Set Sk = Ei<k Xi. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

1.4 The results

In this paper, we study the case where the initial configuration x(0) is composed by a single black region: x(0) - [O.sup.n/2][1.sup.n/2]. The space renormalization must be 1/n, and the time renormalization has to be 0 (E[[T.sub.n]].sup.-1]), as shown in equation (1). Roughly speaking, renormalization of a discrete process can lead to four different behaviors, ordered by increasing degree of randomness:

* the sequence converges to a non null, non-random, process,

* the sequence converges to a random process (e.g. to the standard linear Brownian motion),

* the sequence is tight (relatively compact) but different subsequences converge to different limit processes,

* the sequence is not tight (unbounded).

Our results are roughly summarized below:

quadratic [right arrow] non-random limit

cubic [right arrow] reflected (and-or) coalescent Brownian motions

exponential [right arrow] no limit (untight)

divergent [right arrow] reflected Brownian motions

so that three of the four previous cases occur when renormalizing ECA s as in (1).

2 Quadratic automata : non-random limit

2.1 The automaton FG

For t [greater than or equal to] 0, set

7P (t) - (01(t), 02(t)) - (z + t, 1 -t) .

Due to Theorem 1, only the time-renormalization nz can, eventually, lead to a nontrivial limit process. Actually, a limit process exists, and this limit is non-random. Recall that (Lk, Rk) is the process of the borders of the black region,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Theorem 4 The following convergence holds in Dz (R+)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof: First, consider the Markov chain ([L.sub.[kappa] [R.sub.[kappa]) k[greater than or equal to]0 defined by ([L.sub.o], [R.sub.o]) = (n/2,0), and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

P (SUP in(t) - 1(t) > x) < P (SUP in(t) -Wn(t)] > 2) .

[FIGURE 3 OMITTED]

We need the following bound:

Lemma 4.1 (Kolmogorov's inequality, [Bi195], Th. 22.4) Let (Yk,n)k>o denote sequences of i.i.d. random variables such that IE[YI,n] = 0, IE [YI,n2] = cn < oc. One notes Sk,n = Y1,n + + Y,n. For any k and x > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Let us write

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

in which the Bi's are i.i.d. random variables with IE(Bi = 1) = 1 - P([B.sub.i] = 0) = 1/n. Applying Lemma 4.1 with [S.sub.k,n] = [L.sub.[kappa] - (n/2) - (k/n), [Y.sub.i,n] = [B.sub.i] - (1/n), [c.sub.n] = n-1/[n.sup.2] and k = [[Tn.sup.2]], one obtains

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

With x = [n.sup.-1/2+[delta], for some [delta] [member of] (0, 1/2), it leads to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

([l.sub.n], [r.sub.n] [right arrow] [psi]

The same argument holds for the right border k. It follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Now, the process (Lk, Rk) k>o is designed to have the same distribution as (Lk, Rk)k>o, as long as Lk [R.sub.k-1]. More precisely, if [tau] and G denote the operators defined on [D.sub.2] (0, + [infinity]) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Theorem 2 allows us to conclude, since, in the relation (5), the limit point [psi] is a point of continuity of L, and since ([psi] (t [LAMBDA] 1/4)),>0 = L [psi].

2.2 Other quadratic automata.

Quadratic automata are roughly divided into two sub-families. FG belongs to the first one, with automata B, EF, EFG, BDE, BE, BCDE and BCE. The proof adapts easily to all of them, and they converge to non-random limits. The second family contains BCDEF and BEFG. Their behavior is slightly different. A border (say, the left-border) essentially drifts to the right (with small random perturbations), whereas the right-border performs a symmetric random walk. However, these random perturbations are of order 0 (nl/a) and are erased by the space renormalization factor 1/n, so that the limit is also deterministic. We get the following convergence:

Theorem 5 For automata BCDEF and BEFG, the following convergence holds in [D.sub.2] ([R.sub.+])

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [psi](t) = (1/2, 1 - t).

Proof: This proof and the proof of Theorem 4 are similar. One just has to replace the sequence (Bi) in (4) by a sequence of i.i.d. r.v., with

P([B.sub.i] = 1) = P([B.sub.i] = -1) = 1/2 (1- P([B.sub.i] = 0)) = 1/n.

3 Cubic automata : interactions between Brownian motions

3.1 The automaton BCEFG

The class of cubic automata provides a variety of interesting limit processes, related with the standard linear Brownian motion [RY99]. For sake of brevity, we focus on the automaton BCEFG: its limit process can be described by reflection and coalescence of two independent standard linear Brownian motions W1 and [W.sub.2]: set [B.sup.(1).sub.t] = 0.5 + [square root of (3[W.sub.1])] (t) (resp. [B.sup.(2).sub.t]) = [square root of (2[W.sub.2](t))]. Fort [greater than or equal to] 0, set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

[FIGURE 4 OMITTED]

We have

Theorem 6 Set

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof: First, we study a simpler Markov, ([L.sup.(n).sub.[kappa], R.sup.(n).sub.[kappa])k [greater than or equal to] 0 = ([L.sub.[kappa], [R.sub.[kappa])k [greater than or equal] o, with values in [Z.sup.2], starting at (n/2 , 0). Its transition probabilities [p.sub.(x,y),(z,t)] are defined as follows:

* if y = x - 1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We take p symmetric, that is: [P.sub.(y,x),(t,z) = p(x,y),(z,t)]. The transitions of ([L.sub.k], [R.sub.k]) [k [greater than or equal to] are designed with the purpose that the Markov chain

([L.sup.+.sub.[kappa], [R.sup.-.sub.[kappa]) = ([L.sub.[kappa] V [R.sub.[kappa]], [L.sub.[kappa]] [and] [R.sub.[kappa])

has the same distribution as ([L.sub.[kappa], [R.sub.[kappa]) [kappa] [greater than or equal to]o, as long as Lk - n < Rk - 1. These processes, when suitably renormalized, converges to Brownian-like stochastic processes. More precisely, for t [greater than or equal to] 0, set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Lemma 6.1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof of the Lemma: This Lemma is a consequence of the following Proposition, which is a particular case of ([EK86], Chap.7, Th 4.1).

Proposition 1 Let [l.sub.n], [r.sub.n], [a.sub.n], [b.sub.n], [c.sub.n] be some random elements in [D.sub.1] ([R.sub.+]), and let ([F.sub.n.sub.t])t [greater than or equal]o be the filtration defined by [F.sup.n.sub.t] = [sigma] ([l.sub.n] (s), [r.sub.n] (s); s < t). Suppose that

1. For each n, [l.sub.n] and [r.sub.n] are [F.sub.n.sub.t]-martingales.

2. For each n, [l.sup.2.sub.n] - [a.sub.n], [r.sup.2.sub.n] - [b.sub.n] and [l.sub.n] [r.sub.n] - [c.sub.n] are [F.sup.n.sup.t]-martingales.

Assume furthermore that for each constant T > 0, the following convergerwes hold ire probability:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [B.sup.1.sub.t], [B.sup.2.sub.t] are two independent Brownian motions.

We apply Proposition 1 with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Simple calculations show that

1. Vn(t))t [greater than or equal to]o and (mn(t))t>o are [F.sup.t.sub.n]-martingales,

2. [l.sup.2.sub.n] - [a.sub.n] and [r.sup.2].sub.n] - [b.sub.n] are [f.sup.n.sub.t]-martingales,

3. [l.sub.n] - [r.sub.n] is a [F.sup.n.sub.t] -martingale.

The Theorem will be proved once it is etablished that for each [tau] > 0,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Only (12) is nontrivial. We will denote by L' the local time in p at time 1 of the random walk (I Lc - [R.sub.l|)[k.sub.o]; that is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

It is proved in Appendix that there exists C such that for each p,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Hence, by the Markov inequality,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

which converges to zero when [tau] is fixed.

Now, since the operator A defined on D2 (0, + [infinity]) by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is continuous, it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The stochastic process (Bt , Bt) t>o is often called a planar Brownian motion reflected at a line (here the first bisectrix). Finally, using the operators T and G defined at Section 2.1, we have again:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Again, Theorem 2 allows us to conclude, since, due to properties of sample paths of the standard Brownian motion (cf. [RY99], Chap.2, Th.2.2), the limit point (Bt , Bt)t>o is almost surely a point of continuity of L.

3.2 Automata BDEF, BEF, BCDEFG, BCEFG : Brownian motion

Up to symmetries, there are 6 different cubic automata. The same arguments show that four of them admit a continuous limit with a n3-time-renormalization: automata BDEF, BEF, BCDEFG, BCEFG. All these limits involve the standard Brownian motion: resp. reflected and stopped, reflected, coalescent, coalescent and reflected BM. The proofs differ only by the choice of the operator [LAMBDA].

3.3 Automata BDEG, BEG: no convergence

The [n.sup.3]-time-renormalization is not suitable for these two automata, that behave as quadratic automata. It is primarily due to the fact that

E[[n.sup.-1] L[[tn.sup3] - 1/2 + tn,

that does not converge.

4 Exponential automaton : no convergence

4.1 The automaton BDEG

[FIGURE 5 OMITTED]

BDFG is, up to symmetries, the only exponential automaton. Simulations suggest that its behavior is quite different from those already encountered. The right border essentially drifts to the left (with small random perturbations), while the left border, that would be a symmetric random walk, is pushed to the left by the right border. Actually, the size of the black region [Z.sup.(n).sub.[kappa] = |[R.sub.k] - [L.sub.k]| performs a biased random walk on {1, ... , n}, reflected at 1, absorbed at n. According to [FMSTOS],

E[[T.sub.n]] = 1/9 n [2.sup.n] + O ([n.sup.2]).

As opposed to the previous cases, it turns out that the process

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is not weakly convergent. Actually, the sequence ([z.sub.n]) is not tight ("). This is a consequence of the next Proposition, a slight modification of ([Ald78], Cor. 1), very powerful in this case:

Proposition 2 Assume that the sequence (zn) converges in D(R). Let ([tau].sub.n], [delta].sub.n]) be a sequence such that

(i) for all n, Tn is a stopping time wrt the process ([z.sub.n])t [greater than or equal to]o (with its natural filtration) and Tn takes its values in a finite set,

(ii) ([[delta].sub.n]) is a sequence of real numbers converging to zero.

Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Now, set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The r.v. [tau].sub.n] is a stopping time w.r.t. [z.sub.n], and it takes its values in the finite set {[n.sup.-1][2.sup.-n]k : 1 [less than or equal to] k [less than or equal to] 2n [2.sup.n]}. We show that these sequences ([tau].sub.n]) and ([[delta].sub.n]) violate the condition (14), as would do any subsequence. Incidentally, the fact that any subsequence violates (14) precludes tightness for the sequence (zn).

It is convenient to generate the sequence ([Z.sub.k]) with the help of a sequence of i.i.d. r.v. (Yo, Y,....), as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For any 0 < [epsilon] < 1/3, we see that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The two events on the right hand side are independent. More precisely,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

in which [lim.sub.n] P([Y.sub.1] + ... + [Y.sub.2n] [less than or equal to] n[epsilon]) = 1 by the Bienayme-Tchebychev inequality. It is more involved to prove that lim [inf.sub.n] P([tau], [less than or equal to] 1) > 0, so we only give a sketch of the proof. Let us consider the number N and the positions of excursions of [Z.sub.n] that reach n but not 2n, and that occur before [T.sub.n]: N has a geometric distribution with parameter [([2.sub.n] + 2).sup.-1], so that E[N] = [2.sub.n] + 1, and so that, with a probability exponentially close to 1, N [greater than or equal to] 2. Given that N [greater than or equal to] 2 and [T.sub.n] = l, the first excursion of [Z.sub.n] that reaches n takes place before all the other excursions of the same kind (since N [greater than or equal to] 2, there exists at least another one of the kind), and approximately before half the other excursions. Thus the conditional expectation of the first return of [z.sub.n] to 0 after [tau].sub.n], given N [greater than or equal to] 2 and T = f, is not larger than n-12- f/2, or than [t.sub.n]/2]. Markov inequality entails that the conditional probability that [tau.sub.n] [less than or equal to] [3.sub.t]/4 is larger than 1/3. As a consequence, IE(T,, < 1) is larger than IE(t,, < 4/3)/3 ti (1 - C-12)/3, and (14) does not hold.

5 Divergent automata

5.1 The automata BCFG, BF and CF: reflected Brownian motions

[FIGURE 6 OMITTED]

The limit processes of these three divergent automata are related to reflected Brownian motions. The main difference with Section 3 is that coalescence does not occur. In order to state our results for the automaton BCFG, we shall use the same tools and notations as in Section 3. Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is odd. One can see (L, R) as two self-reflected Brownian motions on the circle.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

with these notations one gets the following result.

Theorem 7 For the automaton BCFG,

([l.sub.n], [r.sub.n]) [greater than or equal to] (L, R).

For the automaton BF, ([l.sub.n], [r.sub.n]) [right arrow] (W,1), in which W denotes a standard linear Brownian motion starting at 0.5, reflected at 0 and 1, while for the automaton CF, only the renormalized width [z.sub.n] = [r.sub.n] - [l.sub.n] of the black region converges to W, while ([l.sub.n], [r.sub.n]) is untight: more precisely, one can see that

([l.sub.n](t)/n, [r.sub.n](t)/n) t [greater than or equal to]o [right arrow] (t, 0.5 + t)t [greater than or equal to]o.

5.2 The automaton BCF 

This automaton behaves a lot like the exponential automaton BDFG of Section 4, with the difference that its width is reflected at 0 but also at n - 1. The hitting time of the barrier n - 1 has again an expectation n [2.sup.n], but then the whole process starts again. For the same reasons as in Section 4, the sequence of processes [z.sub.n] is not tight.

5.3 The automaton BG

Starting from x(0) = [O.sup.n/2][1.sup.n/2], the automaton BG cannot reach a fixed point. However, the dynamic is similar to that of quadratic automata, and the limit is indeed deterministic, when the renormalization is that of Section 2: here

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Theorem 8 For automaton BG, the following convergence holds in D2 (R+)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Appendix

Lemma 8.1 Let ([Z.sub.l])l [greater than or equal to]o be a random walk on Z, P([Z.sub.l+1] = [Z.sub.l + 1]) = P([Z.sub.l+1] = [Z.sub.l - 1]) = 1/n, P([Z.sub.l+1] = [Z.sub.l]) = [n-2]/n, starting from [z.sub.o]. There exists a constant C such that pour each p

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proof: Let ([Z.sub.l])l > o be ar.w. on Z, P([Z.sub.l+1] = [Z.sub.l] + 1) = P([Z.sub.l+1] = [Z.sub.l] - 1) = 1/2, starting from [z.sub.o]. If l [greater than or equal to] n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [B.sub.l,2/n] is a binomial r.v., with parameters (l, 2/n).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Here we have used that P(|B.sub.r,q] - rq| > h) [less than or equal to] 2 exp (-2h2) (see for example [Bo185],Chap.1,Cor.4). Hence,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

This last inequality is the consequence of two well-known facts (see [Fel70],Chap.VI):

1. The central term in the binomial distribution Bn,q is bounded above by C/[square root rq(1-q)]

2. P([S.sub.j] = p) is bounded above by C/[square root (j)], C being independent of [z.sub.o] and p.

Now, for each k > n,

Acknowledgements

The authors thank Nazim Fates for his valuable comments on the first version of this paper.

received 23rd January 2008,

References

[Ald78] David Aldous. Stopping times and tightness. Annals of Probability, 6, 1978.

[Bi168] Patrick Billingsley. Convergence of Probability Measures. Wiley, 1968.

[Bi195] Patrick Billingsley. Probability and Measure. Wiley, 1995.

[Bo185] Belas BolloWs. Random Graphs. Academic Press, 1st edition, 1985.

[Don51] Monroe D. Donsker. An invariant principle for certain probability limit theorems. Memoirs of the American Mathematical Society, 6, 1951.

[EK86] S.N. Ethier and T.G. Kurtz. Markov Processes : Characterization and Convergence. John Wiley & Sons, 1st edition, 1986.

[Fel70] William Feller. Are Introduction to Probability Theory and its Applications, volume 1. John Wiley & Sons, 3rd edition, 1970.

[FMST05] Nazim Fates, Michel Morvan, Nicolas Schabanel, and Eric Thierry. Fully asynchronous behavior of double-quiescent elementary cellular automata. In LNCS Proceedings of the 30th Mathematical Foundations of Computer Science sympsosium, volume 6, pages 316-327, 2005.

[IB84] T.E. Ingerson and R.L. Buvel. Structure in asynchronous cellular automata. Physica D., 10, 1984.

[Pet75] Valentin V Petrov. Sums of Independent Random Variables. Springer-Verlag, ????? edition, 1975.

[RY99] Daniel Revuz and Marc Yor. Continuous Martingales and Brownian Motion. Springer-Verlag, 3rd edition, 1999.

[SdR99] B. Schontisch and A. de Roos. Synchronous and asynchronous updating in cellular automata. Biosystems, 51, 1999.

[vN66] John von Neumann. The Theory of Self-Reproducing Automata. University of Illinois Press, 1966.

[Wo184] Stephen Wolfram. Universality and complexity in cellular automata. Physica D., 10, 1984.

(ii) The terminology cadlag is usually applied to right-continuous functions that admit a left-limit at each point of (0, T]. It is an acronym for the french expression continued droite, limited gauche.

(ii) Meaning that its closure is not even compact, cf. [Bi168] for definitions.

Philippe Chassaing[1] and Lucas Gerin[1]

[1] Institut Elie Cartan Nancy. Universite Henri Poincare Nancy 1. B.P. 239, 54506 Vandoeuvre-les-Nancy Cedex. France.