# Probabilistic initial value problem for cellular automaton rule 172.

1 Introduction

While working on a certain problem in complexity engineering, that is, trying to construct a cellular automaton rule performing some useful computational task, the author encountered the following question. Let f : [{0,1}.sup.3] [right arrow] {0,1} be defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

This function may be called selective copier, since it returns (copies) one of its inputs [x.sub.2] or [x.sub.3] depending on the state of the first input variable [x.sub.1]. Suppose now that s be a bi-infinite sequence of binary symbols, i.e., s = ... [s.sub.-2][s.sub.-1][s.sub.0][s.sub.1][s.sub.2] ..., i [member of] Z. We will transform this string using the selective copier, that is, for each i, we keep [s.sub.i] if it is preceded by 0, or replace it by [s.sub.i+1] otherwise, so that each [s.sub.i] is simultaneously replaced by f ([s.sub.i-1], [s.sub.i], [s.sub.i+1]). Consider now the question: Assuming that the initial sequence is randomly generated, what is the proportion of 1's in the sequence after n iterations of the aforementioned procedure?

Function defined by eq. (1) is a local function of cellular automaton rule 172, using Wolfram numbering, and the aforementioned question is an example of a broader class of problems, which could be called probabilistic initial value problems for cellular automata: given initial distribution of infinite configurations, what is the probability of occurrence of a given finite string in a configuration obtained from the initial one by n iterations of the cellular automaton rule? In what follows, we will demonstrate how one can approach probabilistic initial value problem using cellular automaton rule 172 as an example.

2 Basic definitions

Let G = {0,1, ... N - 1} be called a symbol set, and let S (G) be the set of all bisequences over G, whereby a bisequence we mean a function on Z to G. Set S(G) will be called the configuration space. Throughout the remainder of this text we shall assume that G = {0,1}, and the configuration space S(G) = [{0,1}.sup.Z] will be simply denoted by S.

A block of length n is an ordered set [b.sub.o][b.sub.1] ... [b.sub.n-1], where n [member of] N, [b.sub.i] [member of] G. Let n [member of] N and let [B.sub.n] denote the set of all blocks of length n over G and B be the set of all finite blocks over G.

For r [member of] N, a mapping f : [{0,1}.sup.2r+1] [right arrow] {0,1} will be called a cellular automaton rule of radius r. Alternatively, the function f can be considered as a mapping of [B.sub.2r+1] into [B.sub.0] = G = {0,1}.

Corresponding to f (also called a local mapping) we define a global mapping F : S [right arrow] S such that [(F(s)).sub.i] = f ([s.sub.i-r],..., [s.sub.i],..., [s.sub.i+r]) for any s [member of] S.

A block evolution operator corresponding to f is a mapping f : B [right arrow] B defined as follows. Let r [member of] N be the radius of f, and let a = [a.sub.0][a.sub.1] ... [a.sub.n-1] [member of] [B.sub.n] where n [greater than or equal to] 2r + 1 > 0. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

Note that if b [member of] [B.sub.2r+1] then f (b) = f (b).

We will consider the case of G = {0,1} and r =1 rules, i.e., elementary cellular automata. In this case, when b [member of] [B.sub.3], then f (b) = f (b). The set [B.sub.3] = {000,001,010,011,100,101,101,110, 111} will be called the set of basic blocks.

The number of n-step preimages of the block b under the rule f is defined as the number of elements of the set [f.sup.-n](b). Given an elementary rule f, we will be especially interested in the number of n-step preimages of basic blocks under the rule f.

3 Probabilistic initial value problem

The appropriate mathematical description of an initial distribution of configurations is a probability measure [mu] on S. Such a measure can be formally constructed as follows. If b is a block of length k, i.e., b = [b.sub.0][b.sub.1] ... [b.sub.k-1], then for i [member of] Z we define a cylinder set. The cylinder set is a set of all possible configurations with fixed values at a finite number of sites. Intuitively, measure of the cylinder set given by the block b = [b.sub.0] ... [b.sub.k-1], denoted by [mu][[C.sub.i](b)], is simply a probability of occurrence of the block b in a place starting at i. If the measure [mu] is shift-invariant, than [mu]([C.sub.i](b)) is independent of i, and we will therefore drop the index i and simply write [mu](C(b)).

The Kolmogorov consistency theorem states that every probability measure [mu] satisfying the consistency condition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (3)

extends to a shift invariant measure on S (Dynkin, 1969). For p [member of] [0,1], the Bernoulli measure defined as [[mu].sub.p][C(b)] = [p.sup.j][(1 - p).sup.k-j], where j is a number of ones in b and k - j is a number of zeros in b, is an example of such a shift-invariant (or spatially homogeneous) measure. It describes a set of random configurations with the probability p that a given site is in state 1.

Since a cellular automaton rule with global function F maps a configuration in S to another configuration in S, we can define the action of F on measures on S. For all measurable subsets E of S we define (F[mu])(E) = [mu]([F.sup.-1](E)), where [F.sup.-1](E) is an inverse image of E under F.

If the initial configuration was specified by [[mu].sub.p], what can be said about [F.sup.n][[mu].sub.p] (i.e., what is the probability measure after n iterations of F)? In particular, given a block b, what is the probability of the occurrence of this block in a configuration obtained from a random configuration after n iterations of a given rule?

The general question of finding the iterrates of the Bernoulli measure under a given CA has been extensively studied in recent years by many authors, including, among others, Lind (1984); Ferrari et al. (2000); Maass and Martinez (2003); Host et al. (2003); Pivato and Yassawi (2002, 2004); Maass et al. (2006) and Maass et al. (2006). In this paper, we will approach the problem from somewhat different angle, using very elementary methods and without resorting to advanced apparatus of ergodic theory and symbolic dynamics. We will consider iterates of the Bernoulli measure by analyzing patterns in preimage sets.

For a given block b, the set of n-step preimages is [f.sup.-n](b). Then, by the definition of the action of F on the initial measure, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

and consequently

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

Let us define the probability of occurrence of block b in a configuration obtained from the initial one by n iterations of the CA rule as

[P.sub.n] (b) = ([F.sup.n][[mu].sub.p])(C (b)). (6)

Using this notation, eq. (5) becomes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

If the initial measure is [[mu].sub.1/2], then all blocks of a given length are equally probable, and [P.sub.0](a) = 1/[2.sup.[absolute value of a]], where |a] is the length of the block a. For elementary CA rule, the length of n-step preimage of b is 2n + |b], therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (8)

This equation tells us that if the initial measure is symmetric ([[mu].sub.1/2]), then all we need to know in order to compute [P.sub.n] (b) is the cardinality of [f.sup.-n](b). One way to think about this is to draw a preimage tree for b. We start form b as a root of the tree, and determine all its preimages. Then each of these preimages is connected with b by an edge. They constitute level 1 of the preimage tree. Then, for each block of level 1, we again compute its preimages and we link them with that block, thus obtaining level 2. Repeating this operation ad infinitum, we obtain a tree such as the one shown in Figure 1. In that figure, five levels of the preimage tree for rule 172 rooted at 101 are shown, with only first level labelled.

[FIGURE 1 OMITTED]

Note that card [f.sup.-n](b) corresponds to the number of vertices in the n-th level of the preimage tree. One thus only needs to know cardinalities of level sets in order to use eq. (8), while the exact topology of connections between vertices of the preimage tree is unimportant. The key problem, therefore, is to enumerate level sets. In order to answer the question posed in the introduction, we need to compute [P.sub.n] (1) for rule 172, which, in turn, requires that we enumerate level sets of a preimage tree rooted at 1. It turns out that for rule 172 the preimage tree rooted at 1 is rather complicated, and that it is more convenient to consider preimage trees rooted at other blocks. In the next section, we will show how to express [P.sub.n](1) by some other block probabilities. From now on, f will exclusively denote the block evolution operator for rule 172.

4 Block probabilities

Since [f.sup.-1] = {010,011,101,111}, we have [P.sub.n+1](1) = [P.sub.n](010) + [P.sub.n](011) + [P.sub.n](101) + [P.sub.n](111). Due to consistency conditions (eq. 3), [P.sub.n](010) + [P.sub.n](011) = [P.sub.n](01), and we obtain

[P.sub.n+1](1) = [P.sub.n](01) + [P.sub.n](101) + [P.sub.n](111). (9)

This can be transformed even further by noticing that [P.sub.n](01) = [P.sub.n](001) + [P.sub.n](101), therefore

[P.sub.n](1) = [P.sub.n-1](001) + 2[P.sub.n-1](101) + [P.sub.n-1](111). (10)

By using eq. (8) and defining [c.sub.n] = [P.sub.n](1) we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (11)

This means that in order to compute [c.sub.n], we need to know cardinalities of n-step preimages of 001, 101, and 111.

5 Structure of preimage sets

The structure of level sets of preimage trees rooted at 001,101, and 111 will be described in the following three propositions.

Proposition 5.1 Block b belongs to [f.sup.-n](001) if and only if it has the structure

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (12)

where * represents arbitrary symbol from the set {0,1}.

Let us first observe that [f.sup.-1](001) = {00010,00011,10010,10011}, which means that [f.sup.-1](001) can be represented as ** 001 **. Similarly, therefore, [f.sup.-2](001) has the structure ***001 and by induction, for any n, the structure of [f.sup.-n](001) must be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proposition 5.2 Block b belongs to [f.sup.-n](101) if and only if it has the structure

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (13)

where [a.sub.i] [member of] {0,1} for i = 1,..., n and the string [a.sub.1][a.sub.2] ... [a.sub.n] does not contain any pair of adjacent zeros, that is. [a.sub.i][a.sub.i+1] [not equal to] 00 for all i = 1, ... , n - 1.

Two observations will be crucial for the proof. First of all, [f.sup.-1] (101) = {01101,11101}, thus [f.sup.-1](101) has the structure *1101. Furthermore, we have [f.sup.-1](1101) = {011101,101101,111101}, meaning that if 1101 appears in a configuration, and is not preceded by 00, then after application of the rule 172, 1101 will still appear, but shifted one position to the left. All this means that if b is to be an n-step preimage of 101, it must end with 1101. After each application of rule 172 to b, the block 1101 will remain at the end as long as it is not preceded by two zeros.

Now, let us note that [f.sup.-1](00) = {0000,0001,1000,1001,1100}, which means that preimage of 00 is either 1100 or *00*. Therefore, we can say that if 00 is not present in the string [a.sub.1][a.sub.2] ... [a.sub.n], it will not appear in its consecutive images under f. Thus, block 1101 will, after each iteration of f, remain at the end, and will never be preceded by two zeros. Eventually, after n iterations, it will produce 101, as shown in the example below.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

What is left to show is that not having 00 in [a.sub.1][a.sub.2] ... [a.sub.n] is necessary. This is a consequence of the fact that f (*00*) = 00, which means that if 00 appears in a string, then it stays in the same position after the rule 172 is applied. Indeed, if we had a pair of adjacent zeros in [a.sub.1][a.sub.2] ... [a.sub.n], it would stay in the same position when f is applied, and sooner or later block 1101, which is moving to the left, would come to the position immediately following this pair, and would be destroyed in the next iteration, thus never producing 101. Such aprocess is illustrated below, where after three iterations the block 1101 is destroyed due to "collision" with 00.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Proposition 5.3 Block b belongs to [f.sup.-n](111) if and only if it has the structure

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (14)

where [a.sub.i] [member of] {0,1} for i = 1,..., n and the string [a.sub.1][a.sub.2] ... [a.sub.n] satisfies the following three conditions:

(i) [a.sub.i][a.sub.i+1] [not equal to] 00 for all i = 2 ... n + 4;

(ii) [a.sub.n+3][a.sub.n+4][a.sub.n+5] [not equal to] 110 and [a.sub.n+2][a.sub.n+3][a.sub.n+4] [not equal to] 110;

(iii) if [a.sub.1][a.sub.2] [not equal to] 00, then [a.sub.n+1][a.sub.n+2][a.sub.n+3] [not equal to] 110.

We will present only the main idea of the proof here, omitting some tedious details. It will be helpful to inspect spatiotemporal pattern generated by rule 172 first, as shown in Figure 2. Careful inspection of this pattern reveals three facts, each of them easily provable in a rigorous way:

(F1) A cluster of two or more zeros keeps its right boundary in the same place for ever.

(F2) A cluster of two or more zeros extends its left boundary to the left one unit per time step as long as the left boundary is preceded by two or more ones. If the left boundary it is preceded by 01, it stays in the same place.

(F3) Isolated zero moves to the left one step at a time as long as it has at least two ones on the left. If an isolated zero is preceded by 10, it disappears in the next time step.

[FIGURE 2 OMITTED]

Let us first prove that (i)-(iii) are necessary. Condition (i) is needed because if we had 00 in the string [a.sub.2]... [a.sub.n+5], its left boundary would grow to the left and after n iterations it would reach sites in which we expect to find the resulting string 111.

Moreover, string [a.sub.1][a.sub.2] ... [a.sub.n+5] cannot have 011 at the end position, one site before the end, or two sites before the end. If it had, 0 preceded by two 1's would move to the left and, after n iterations, it would reach sites where we want to find 111. The only exception to this is the case when [a.sub.0][a.sub.1] = 00. In this case, even if 011 is in the second position from the end, it will disappear in step n - 1. This demonstrates that (ii) and (iii) are necessary.

In order to prove sufficiency of (i)-(iii), let us suppose that the string b satisfies all these conditions yet [f.sup.n](b) [not equal to] 111. This would imply that at least one of the symbols of [f.sup.n](b) is equal to zero. However, according to what we stated in F1-F3, zero can appear in a later configuration only as a result of growth of an initial cluster of two of more zeros, or by moving to the left if it is preceded by two ones. This, however, is impossible due to conditions (i)-(iii).

6 Enumeration of preimage strings

Once we know the structure of preimage sets, we can enumerate them. For this, the following lemma will be useful.

Lemma 6.1 The number of binary strings [a.sub.1][a.sub.2] ... [a.sub.n] such that 00 does not appear as two consecutive terms aiai+1 is equal to [F.sub.n+2], where [F.sub.n] is the n-th Fibonacci number.

This result will be derived using classical transfer-matrix method. Let g(n) be the number of binary strings [a.sub.1][a.sub.2] ... [a.sub.n] such that 00 does not appear as two consecutive terms [a.sub.i][a.sub.i+1]. We can think of such string as a walk of length n on a graph with vertices [v.sub.1] =0 and [v.sub.2] = 1 which has adjacency matrix A given by [A.sub.11] = 0, [A.sub.12] = [A.sub.21] = [A.sub.22] = 1. One can prove that the generating function for g,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (15)

can be expressed by G([lambda]) = [G.sub.11]([lambda]) + [G.sub.12]([lambda]) + [G.sub.21]([lambda]) + [G.sub.22]([lambda]), where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (16)

and where (M : j, i) denotes the matrix obtained by removing the j - th row and i - th column of M. Proof of this statement can be found, for example, in Stanley (1986). Applying this to the problem at hand we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (17)

By decomposing the above generating function into simple fractions we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (18)

where [psi] = 1/2 + 1/2 [square root of 5] is the golden ratio. Now, by using the fact that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (19)

and by using a similar expression for 1/[lambda] + 1 - [psi], we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (20)

where [F.sup.n] is the n-th Fibonacci number, [F.sub.n] = [[psi].sup.n] - (1 - [[psi].sup.n]/[square root of 5]. This implies that g(n) = [F.sub.n+2].

Proposition 6.1 The cardinalities of preimage sets of001, 100, 101 and 111 are given by

card [f.sup.-n] (001) = [4.sup.n], (21)

card [f.sup.-n](101) = [2.sup.n-1][F.sub.n+2], (22)

card [f.sup.-n](111) = [2.sup.n][F.sub.n+3]. (23)

Proof of the first of these formulae is a straightforward consequence of Proposition 5.1. We have 2n arbitrary binary symbols in the string b, thus the number of such strings must be [2.sup.2n] = [4.sup.n].

The second formula can be immediately obtained using Lemma 6.1 and Proposition 5.1. Since the first n - 1 symbols of [f.sup.-n](101) are arbitrary, and the remaining symbols form a sequence of n symbols without 00, we obtain

card [f.sup.-n](101) = [2.sup.n-1][F.sub.n+2]. (24)

In order to prove the third formula, we will use Proposition 5.3. We need to compute the number of binary strings [a.sub.1][a.sub.2] ... [a.sub.n+5] satisfying conditions (i)-(iii) of Proposition 5.3. Le us first introduce a symbol [[alpha].sub.1][[alpha].sub.2]... [[alpha].sub.k] to denote the string of length k in which no pair 00 appears. Then we define:

* A is the set of all strings having the form [[alpha].sub.1][[alpha].sub.2] ... [[alpha].sub.n+5],

* [A.sub.1] is the set of all strings having the form [[alpha].sub.1][[alpha].sub.2] ... [[alpha].sub.n+2]110,

* [A.sub.2] is the set of all strings having the form [[alpha].sub.1][[alpha].sub.2] ... [[alpha].sub.n+1]1101,

* [A.sub.3] is the set of all strings having the form [[alpha].sub.1][[alpha].sub.2] ... [[alpha].sub.n]11010,

* [A.sub.4] is the set of all strings having the form [[alpha].sub.1][[alpha].sub.2] ... [[alpha].sub.n]11011,

* B is the set of all strings having the form 001[[alpha].sub.1][[alpha].sub.2] ... [[alpha].sub.n+2],

* [B.sub.1] is the set of all strings having the form 001[[alpha].sub.1] [[alpha].sub.2]... [[alpha].sub.n-1]110,

* [B.sub.2] is the set of all strings having the form 001[[alpha].sub.1] [[alpha].sub.2]... [[alpha].sub.n-2]1101.

The set [OMEGA] of binary strings [a.sub.1][a.sub.2] ... [a.sub.n+5] satisfying conditions (i)-(iii) of Proposition 5.3 can be now written as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (25)

Since [A.sub.1] ... [A.sub.4] are mutually disjoint, and [B.sub.1] and [B.sub.2] are disjoint too, the number elements in the set [OMEGA] is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (26)

which, using Lemma 6.1, yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (27)

Using basic properies of Fibonacci numbers, the above simplifies to card [OMEGA] = 4[F.sub.n+3]. Now, since in the Proposition 5.3 the string [a.sub.1] ... [a.sub.n+5] is preceded by n - 2 arbitrary symbols, we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (28)

what was to be shown.

7 Density of ones

Using results of the previous section, eq. (11) can now be rewritten as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (29)

which simplifies to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (30)

or, more explicitly, to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (31)

Obviously, [lim.sub.n[right arrow][infinity]] [c.sub.n] = 1/8, in agreement with the numerical value reported in Wolfram (1994). We can see that [C.sub.n] converges toward [C.sub.[infinity]] exponentially fast, with some damped oscillations superimposed over the exponential decay. This is illustrated in Figure 3, where, in order to emphasize the aforementioned oscillations, instead of [c.sub.n] we plotted the ratio

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (32)

[FIGURE 3 OMITTED]

as a function of n. One can show that [d.sub.n] converges to the half of ratio divina (golden ratio), [psi]/2 [approximately equal to] 0.809016..., as illustrated in Figure 3. We can see from this figure that the convergence is very fast and that the agreement between numerical simulations and the theoretical formula is nearly perfect.

8 Further results

Results obtained in the previous two sections suffice to compute block probabilities for all blocks of length up to 3. Proposition 6.1 together with eq. (8) yields formulas for [P.sub.n](001), [P.sub.n](101), and [P.sub.n](111). Consistency conditions give [P.sub.n](01) = [P.sub.n](001) + [P.sub.n](101). Furthermore [P.sub.n](10) = [P.sub.n](01) due to the fact that [P.sub.n](10)+ [P.sub.n](00) = [P.sub.n](01)+ [P.sub.n] (00) = [P.sub.n](0). Applying consistency conditions again we have [P.sub.n](1) = [P.sub.n](10) + [P.sub.n](11), hence [P.sub.n](11) = [P.sub.n](1) -[P.sub.n](10), and, similarly, [P.sub.n](00) = [P.sub.n](0) -[P.sub.n](10). This gives us probabilities of all blocks of length 2. Probabilities of blocks of length 3 can be obtained in a similar fashion:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The only missing probability, [P.sub.n](100) is the same as [P.sub.n](001) because [P.sub.n](100) + [P.sub.n](000) = [P.sub.n](001) + [P.sub.n](000) = [P.sub.n](00). The following formulas summarize these results.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [L.sub.n] = 2[F.sub.n+1] - [F.sub.n] is the n-th Lucas number. We can also rewrite these formulas in terms of cardinalities of preimage sets using eq. (8), as stated below.

Theorem 8.1 Let f be the block evolution operator for CA rule 172. Then for any positive integer n we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

where [F.sub.n] is the n-th Fibonacci number, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], and [L.sub.n] is the n-th Lucas number, [L.sub.n] = [[psi].sup.n] + [(1 - [psi]).sup.n].

9 Concluding remarks

The method for computing block probabilities in cellular automata described in this paper is certainly not applicable to arbitrary CA rule. It will work only if the structure of level sets of preimage trees is sufficiently regular so that the level sets can be enumerated by some known combinatorial technique. Altough "chaotic" rules like rule 18, or complex rules such as rule 110 certainly do not belong to this category, in surprisingly many cases significant regularities can be detected in preimage trees. Usually, this applies to "simple" rules, those which in Wolfram classification belong to class I, class II, and sometimes class III. Rule 172 reported here is one of the most interesting among such rules, primarily because the density of ones does not converge exponentially to some fixed value as in many other cases, but exhibits subtle damped oscillations on top of the exponential decay. Furthermore, the appearance of Fibonacci and Lucas numbers in formulas for block probabilities is rather surprising.

One should add at this point that the convergence toward the steady state can be slower than exponential even in fairly "simple" cellular automata. Using similar method as in this paper, it has been found in Fuks and Haroutunian (2009) that in rule 14 the density of ones converges toward its limit value approximately as a power law. The exact formula for the density of ones in rule 14 involves Catalan numbers, and the structure of level sets is quite different than the one reported here. Rule 142 exhibits somewhat similar behavior too, as reported in Fuks (2006).

As a final remark, let us add that the results presented here assume initial measure [[mu].sub.1/2]. This can be generalized to arbitrary [[mu].sub.p]. In order to do this, one needs, instead of straightforward counting of preimages, to perform direct computation of their probabilities using methods based on Markov chain theory. Work on this problem is ongoing and will be reported elsewhere.

References

E. B. Dynkin. Markov Processes-Theorems and Problems. Plenum Press, New York, 1969.

P. A. Ferrari, A. Maass, S. Martinez, and P. Ney. Cesaro mean distribution of group automata starting from measures with summable decay. Ergodic Theory Dynam. Systems, 20(6):1657-1670, 2000.

H. Fuks. Dynamics of the cellular automaton rule 142. Complex Systems, 16:123-138, 2006.

H. Fuks and J. Haroutunian. Catalan numbers and power laws in cellular automaton rule 14. Journal of cellular automata, 4:99-110, 2009.

B. Host, A. Maass, and S. Martinez. Uniform Bernoulli measure in dynamics of permutative cellular automata with algebraic local rules. Discrete Contin. Dyn. Syst., 9(6):1423-1446, 2003.

D. A. Lind. Applications of ergodic theory and sofic systems to cellular automata. Phys. D, 10(1-2):36-44, 1984. Cellular automata (Los Alamos, N.M., 1983).

A. Maass and S. Martinez. Evolution of probability measures by cellular automata on algebraic topological markov chains. Biol. Res., 36(1):113-118, 2003.

A. Maass, S. Martinez, M. Pivato, and R. Yassawi. Asymptotic randomization of subgroup shifts by linear cellular automata. Ergodic Theory and Dynamical Systems, 26(04):1203-1224, 2006.

A. Maass, S. Martinez, and M. Sobottka. Limit measures for affine cellular automata on topological markov subgroups. Nonlinearity, 19:2137-2147, Sept. 2006.

M. Pivato and R. Yassawi. Limit measures for affine cellular automata. Ergodic Theory Dynam. Systems, 22(4): 1269-1287, 2002.

M. Pivato and R. Yassawi. Limit measures for affine cellular automata. II. Ergodic Theory Dynam. Systems, 24(6): 1961-1980, 2004.

R. P. Stanley. Enumerative combinatorics. Wadsworth and Brooks/Cole, Monterey, 1986.

S. Wolfram. Cellular Automata and Complexity: Collected Papers. Addison-Wesley, Reading, Mass., 1994.

Henryk Fuks ([dagger])

Department of Mathematics, Brock University, St. Catharines, ON L2S 3A1, Canada

([dagger]) The author acknowledges partial financial support from Natural Sciences and Engineering Research Counclil of Canada, in the form of a Discovery Grant.
Author: Printer friendly Cite/link Email Feedback Fuks, Henryk DMTCS Proceedings Report 1CANA Jan 1, 2010 4925 60/102 Null Boundary Cellular Automata based expander graphs. Block-sequential update schedules and Boolean automata circuits. Cellular automata Combinatorial probabilities Differential equations Geometric probabilities Probabilities Probability theory Robots