Printer Friendly

Orbits of the Bernoulli measure in single-transition asynchronous cellular automata.

1 Introduction

Mathematical theory of cellular automata can be developed using a variety of approaches. The most extensively used approach is the study of CA in the compact Cantor space [A.sup.Z] of symbolic sequences, where A is some finite alphabet. This approach proved to be very fruitful, and can now be considered a fully established sub-discipline of topological dynamics (Kurka, 2009).

The aforementioned approach, however, is not without problems. Suppose, for example, that F : [A.sup.Z] [right arrow] [A.sup.Z] is a CA rule with local function f, and [sigma] is the shift map. Then F and F[sigma] determine different dynamical systems on [A.sup.Z], with possibly radically different properties. For instance, if F is the identity map, then it is obviously non-chaotic, yet F[sigma] = [sigma] is chaotic. This is somewhat unsatisfactory in the view of the fact that [sigma] is in some sense a "simple" map--it is, after all, just a translation.

To avoid this problem, one can study CA on non-compact spaces, and indeed this approach has been steadily gaining momentum in recent years (Formenti and Kurka, 2009). Alternatively, the space of measures is often considered, or more precisely, the space [M.sub.A] of Borel shift-invariant probability measures on [A.sup.Z], equipped with the weak* topology. This space has the attractive property that F and F[sigma] determine the same dynamical system on [M.sub.A] and a number of interesting results have been established for dynamics of CA in [M.sub.A], e.g. by Kurka and Maass (2000), Pivato (2002), Kurka (2005), and others.

Among all measures in [M.sub.A], the uniform Bernoulli measure plays a special role in the dynamics of CA, first, because it is preserved by surjective CA and also, because it is a limit measure for linear CA (a property known as "asymptotic randomization")--for a review, see Pivato (2009) and references therein. A very natural question is therefore to ask: what can we say about the orbit of the Bernoulli measure under a CA rule F? For linear CA, the asymptotic randomization result mentioned above answers this question to some extent, but what can be said about nonlinear rules?

The approach of the authors was to consider this problem in depth for concrete CA rules, starting from particularly simple cases. Even then, it is still difficult to fully characterize consecutive iterates of the Bernoulli measure. However, since any shift-invariant probability measure on [A.sup.Z] is fully determined by its value on cylinder sets, it is often possible to compute measures of certain short cylinder sets after n iterations of F by taking advantage of the combinatorial structure of the CA rule. This works well for simple equicontinuous rules, as well as for almost-equicontinuous ones, as recently demonstrated for the case of almost-equicontinuous rule 172 (Fuks, 2010). Even for rules which are somewhat more complicated, such as the "traffic" rule 184 and its topological factor rule 142, significant results have been obtained (Fuks, 1999, 2006; Blank, 2003; Belitsky and Ferrari, 2005).

In this paper, we examine the same problem in the context of probabilistic rules. Can one compute iterates of the Bernoulli measure under simple probabilistic rules? Again, the situation appears to be similar as in the deterministic case. While the full characterization of iterates of the Bernoulli measure turns out to be very hard, measures of short cylinder sets can be computed explicitly if one takes advantage of the combinatorial structure of these rules. We will consider a special class of probabilistic rules, known as a-asynchronous CA. For the a-asynchronous version of a CA rule with local function f, one applies to each site rule f with probability a, or leaves the site unchanged with probability 1 - [alpha], and this is done for each site simultaneously and independently. We will furthermore restrict our attention to particularly simple [alpha]-asynchronous rules, namely those for which the local function f differs from the local function of the identity rule only for one particular neighbourhood configuration.

2 Definitions

We first define probabilistic CA in a traditional way, as a stochastic process. Let A = {0,1} be called a symbol set, and let elements of [A.sup.Z] be called configurations. Let s(t) [member of] [A.sup.Z] denote a configuration at time t, where t [member of] N. Suppose that

we have a collection of random variables [X.sub.i,v] taking values in A, indexed with i [member of] Z and v [member of] [A.sup.3].

We define define a nearest-neighbour binary probabilistic cellular automaton as a stochastic process

[S.sub.i](t + 1) = [X.sub.i,v(i,t)], (1)

where v(i, t) = {[s.sub.i-1](t), [s.sub.i](t), [s.sub.i+1](t)} will be called a neighbourhood vector. In general, the probability distribution of [X.sub.i,v] is assumed to be independent of i, although it may (and normally does) depend on the neighbourhood vector v.

We will be interested in a very special type of probabilistic CA, in which each cell is independently updated with some probability [alpha]. These rules were first studied experimentally by Fates and Morvan (2005), and subsequently called called [alpha]-asynchronous rules (Fates et al., 2006). They are formally defined as follows. Let f : A3 - A be a given function and let [alpha] [member of] [0,1] be a given parameter (called the synchrony rate). For these rules, random variables [X.sub.i,v] take value in the set {f ([v.sub.1], [v.sub.2], [v.sub.3]), [v.sub.2]} with probabilities, respectively, [alpha] and 1 - [alpha], that is,

Pr([X.sub.i,v] = f ([v.sub.1], [v.sub.2], [v.sub.3])) = [alpha], (2)

Pr([X.sub.i,v] = [v.sub.2]) = 1 - [alpha], (3)

for each v = {[v.sub.1], [v.sub.2], [v.sub.3]} [member of] [A.sup.3] and i [member of] Z. This can be understood as as probabilistic CA where at each site i we apply the local function f with probability or leave the site unchanged with probability 1 - [alpha], simultaneously and independently for all sites. For small a values and finite periodic configurations, this has an effect resembling asynchronous application of the rule f, hence the name (although in this paper we will be dealing with infinite configurations, so this feature will be irrelevant for us).

We wanted to understand at first only asynchronous rules for which the local function differs from the local function of the identity rule only for one neighbourhood configuration. These rules are shown in Table 2. Their Wolfram numbers are shown together with alternative designation as proposed by Fates et al. (2006). The last column shows the so-called minimal rule number , that is, smallest rule number in the equivalency class which includes the given rule, its spatial reflection, the rule obtained by the interchange of 1's and 0s (Boolean conjugacy), and the rule obtained by the superposition of spatial reflection and Boolean conjugacy. Note that all these rules in Fates notation are denoted by a single letter. Among them, only 76 (H), 140 (G), and 200 (E) are minimal and we will therefore consider only these rules. An asynchronous rule for which the local function f has Wolfram code W will be denoted by WA. We will therefore consider rules 76A, 140A, and 200A.

Note that the probabilistic cellular automaton can be fully defined if we specify the set of the so-called transition probabilities, to be denoted by

[omega] ([s.sub.i] (t + 1)|[s.sub.i-1](t)[s.sub.i](t)[s.sub.i+1](t)), (4)

and to be interpreted as the conditional probability that a site [s.sub.i](t) with nearest neighbours [s.sub.i-1](t) and [s.sub.i+1](t) changes its state to [s.sub.i](t + 1) in a single time step. Using this concept, we can define a probabilistic cellular automaton as a dynamical system in the space of measures, as follows.

Let [M.sub.A] be a space of Borel shift-invariant probability measures on [A.sup.Z], equipped with the weak * topology. Let, for any block (word) b = [b.sub.0][b.sub.1] ... [b.sub.r-1] [member of] [A.sup.r], [C.sub.i](b) denote the cylinder set

[C.sub.i](b) = {s [member of] [A.sup.Z] : [s.sub.i] = [b.sub.0], [s.sub.i+1] = [b.sub.1], ..., [s.sub.i+r-1] = [b.sub.r-1]}. (5)

Since we are dealing with shift-invariant measures, we drop the spatial index i in expressions involving measures of cylinder sets. Note that the measure in [M.sub.A] is uniquely defined by its values on cylinder sets.

Suppose now that the function [omega](x|x) : A x [A.sup.3] [right arrow] [0,1] is given. We define the transformation F: [M.sub.A] [right arrow] [M.sub.A] by defining, for any [mu] [member of] [M.sub.A] and c [member of] [A.sup.r],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

where r [member of] N.

For convenience, we also define 1-step block transition probability [omega] so that, for any b = [b.sub.0][b.sub.1] ... [b.sub.r] [b.sub.r+1] [member of] [A.sup.r+2] and any c = [c.sub.1][c.sub.2] ... [c.sub.r-1][c.sub.r] [member of] [A.sup.r],

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

Moreover, we define a n-step block transition probability [omega] recursively, so that, when n [greater than or equal to] 2 and for any blocks b [member of] [A.sup.r+2n], c [member of] [A.sup.r],

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

which may be written explicitly as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

Note that the n-step block transition probability [[omega].sup.n](c|b) can be intuitively understood as the conditional probability of seeing the block c on sites [1, r] after n iterations of F, conditioned on the fact that the original configuration contained the block b on sites [1 - n, r + n].

3 Response Surface

Let us now suppose that the initial state s(0) is not given explicitly, but that the state of each site is independently set to 1 with probability [rho] or to zero with probability 1 - [rho]. This is equivalent to saying that the initial probability measure is a shift-invariant Bernoulli measure. We then apply our probabilistic CA n times, and ask: what is the resulting probability measure? Since it is well known that this measure is uniquely determined by its value on all cylinder sets, it would be sufficient to compute probabilities of occurrences of all finite blocks in order to describe the measure completely. This, however, is very difficult even in simple cases, thus we will restrict our attention to a much simpler problem, namely computing probabilities of short words, such as words of length one. One can say that such single-symbol probabilities provide only a very coarse description of the measure, yet they are often useful, just like knowledge of the first moment of some unknown distribution is often valuable. In many practical problems, e.g., in mathematical modeling, one wants to know how a CA rule iterated over an initial configuration affects certain aggregate properties of the configuration, such as, for example, the density of 1's. For finite configurations, the density of ones is defined as the number of sites in state 1 divided by the total number of sites. For infinite configurations, which are the subject of this article, one could generalize this notion by taking the appropriate limit, but such limit may not always exist. Since we will be interested in orbits of translationally-invariant probability measures rather than individual configurations, it will be more convenient to define the density as the expected value of the cell state. For binary rules, if P(0) and P (1) are probabilities of occurrence of 0 and 1 in a configuration, the expected value of the cell state is P(0) x 0 + P(1) x 1 = P(1). For this reason, we will use the term "density" interchangeably with the probability of occurrence of 1 in a configuration.

To be more precise, let [[mu].sub.[rho]] be the Bernoulli measure such that [[mu].sub.[rho]](C(1)) = [rho], [[mu].sub.[rho]](C(0)) = 1 - [rho]. Let us define probability of occurrence of block b after n iterations of F as

[P.sub.n] (b) := ([F.sup.n] [[mu].sub.[rho]])(C(b)). (10)

Using the concept of transition probabilities, we can write

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

where the transition probability is defined in eq. (8) and (9). Note that [P.sub.0](a) is easy to compute,

[P.sub.0](a) = [[rho].sup.# of 1's in a] [(1 - [rho]).sup.# of 0's in a], (12)

by the definition of Bernoulli measure.

Since some of the transition probabilities may be zero, we define, for any block b [member of] [G.sup.r], the set of n-step block preimages,

supp [[omega].sup.n](b|x) = {a [member of] [A.sup.r+2n] : [[omega].sup.n](b|a) > 0}. (13)

Then we can write (11) as

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

In what follows, we will show how to compute [P.sub.n](1) for the three aforementioned asynchronous rules. For a given a and n, the graph of [P.sub.n](1) versus [P.sub.0](1) will be called response curve. We use this terminology analogous to signal processing theory: a probabilistic CA can be viewed as a black box, for which the input is given in the form of density of 1's in the initial measure ([P.sub.0](1) = [rho]), and, after n iterations, we obtain output density, that is, [P.sub.n] (1). For the special case [rho] = 1/2, we use the notation [P.sup.(s).sub.n] (1) which will be called a symmetric response curve. We will also plot [P.sub.n](1) as a function of both [rho] and the synchrony rate [alpha], and this 3D graph will be called response surface. Most of the time, we will be interested in the limit n [right arrow] [infinity], to be denoted as

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

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

4 Rule 200A

Consider an a-asynchronous rule defined as

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

and [omega](0|b) = 1 - [omega](1|b) for all b [member of] [A.sup.3]. Note that if [alpha] = 1, then this rule is equivalent to the deterministic Rule 200. In order to simplify notation, we define [beta] = 1 - [alpha].

We wish to find a response surface for Rule 200A. In order to apply eq. (14), we begin by finding the set of all potential preimage blocks and their respective transition probabilities.

Proposition 4.1 The set supp [[omega].sup.n](1|x) consists of all blocks of the form

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

Proof: From eq. (17), we can see that an element in state 0 will always remain in state 0, so any block which does not have the above form will never be transformed to a single 1 under n iterations of Rule 200A. Similarly, a block in our set could produce a single 1, with some non-zero probability. []

We now define the following subset of supp [[omega].sup.n](1|x), [B.sub.n] = {[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proposition 4.2 For any block b [member of] supp [[omega].sup.n](1|x) \ [B.sub.n], we have [[omega].sup.n](1|b) = 1.

Proof: In every element of the set supp [[omega].sup.n](1|x) [B.sub.n], the central block will either be 011, 110 or 111. From eq. (17), we can see that these blocks will always be preserved under application of Rule 200A. []

Proposition 4.3 For any block b [member of] [B.sub.n], we have [[omega].sup.n](1|b) = [[beta].sup.n].

Proof: In each iteration, the 0s in the centre block will be preserved with probability 1, so we only need to consider the transition 010 [right arrow] 1, which occurs in each iteration of Rule 200A with probability [beta]. []

We may now use eq. (14) and consider the sets and transition probabilities described in Propositions 4.2 and 4.3, to conclude that

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

[FIGURE 1 OMITTED]

Therefore, the asymptotic density of 1's is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Figure 1(a) shows the graph of P(1) as a function of [rho] and [alpha].

When [rho] = 1 /2, the response curve is given by

[P.sup.(s).sub.n] (1) = 3/8 + 1/8 [[beta].sup.n]. (20

This response curve is plotted in Figure 1(b). together with results of computer simulations in which we measured density in an array of length 20000, iterated [10.sup.5]/[alpha] times with [alpha] > 0.1, assuming periodic boundary conditions, averaged over 100 runs. One can see that the response curve is remarkably close to the simulations curve for a finite lattice.

Basic Blocks For Rule 200A, we were also able to find explicit formulae for probabilities of each of the eight blocks in [A.sup.3], to be called basic blocks. We once again use eq. (14). We omit tedious details of these calculations, which are very similar to what has been presented above for [P.sub.n](1). We only present a summary of these findings in Table 2, where the set of all n-step preimage blocks of each basic block is shown, together with corresponding initial probabilities and respective transition probabilities. These results can be used to find formulae for probabilities of basic blocks, such as, for example,

[P.sub.n](000) = [[rho].sup.2][(1 - [rho]).sup.2](1 + [rho]) + [rho][(1 - [rho]).sup.2](1 - 2[[rho].sup.2])[[beta].sup.n] - [[rho].sup.2][(1 - [rho]).sup.3][[beta].sup.2n].

[TABLE 2 OMITTED]

We show below probabilities of all eight basic blocks in the special case when [rho] = 1/2, together with asymptotic probabilities, assuming [alpha] [not equal to] 0.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

5 Rule 140A

The next rule to be considered has transition probabilities defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (21)

and [omega](0|b) = 1 - [omega](1|b) for all b [member of] [A.sup.3]. Note that if [alpha] = 1, then this rule is equivalent to deterministic Rule 140.

We first find the set of all preimage blocks and their respective transition probabilities.

Proposition 5.1 The set supp [[omega].sup.n](1|x) consists of all blocks of the form

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

Proof: From eq. (21), we can see that a site in state 0 will always remain in state 0, so that for any block b' [member of] [A.sup.2n+1] \ supp [[omega].sup.n] (1|x), we have [[omega].sup.n](1|b') = 0. A block in supp [[omega].sup.n](1|x), however, could produce a single 1 with some non-zero probability.

To determine transition probabilities, we divide the set of preimage blocks into subsets. We start by defining [C.sup.k.sub.n] supp [[omega].sup.n] (1|x) to be the set of blocks of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

where 0 [less than or equal to] k - 1 [less than or equal to] n. The value of k - 1 indicates the number of 1's before the first potential occurrence of 0 is located, counted to the right of the underlined central 1. Note that if k - 1 = n then the block may not contain any 0's to the right of the centre. We also define the set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and note that the complement of [C.sub.n] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proposition 5.2 For any block [c.sup.*] e supp [[omega].sup.n](1|x) \ [C.sub.n], we have [[omega].sup.n](1|[c.sup.*]) = 1.

Proof: From eq. (21), the centre block 0[1.bar] will be preserved for the first (n - 1)-steps with probability 1. Finally, any block 0[1.bar]* will be transformed to a single 1 with probability 1. []

Proposition 5.3 For any block c [member of] [C.sup.k.sub.n], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: To simplify calculations let us use the notation [[gamma].sup.k.sub.n] = [[omega].sup.n](1|c). To calculate this transition probability, we will first write a formula for n-step transition probability recursively in terms of possible (n - 1)-step transition probabilities. We do so by considering specific cases of the value of k.

1. When k = 1 , consider the following transition:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The shaded transition will occur with probability [beta].

2. When 2 [less than or equal to] k [less than or equal to] n, consider the following transition:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We know that x = 1 with probability [beta], resulting in a block in [C.sup.k.sub.n-1], and x = 0 with probability [alpha], resulting in a block in [C.sup.k-1.sub.n-1].

3. When k = n +1, consider the following transition:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

which will occur with probability 1.

Combining these cases, we obtain the following recursive formula

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

This recursive equation can be solved to give the desired result. To see this, consider first the case of k = 1 or k = n + 1, when our formula follows trivially from eq. (23). When 2 [less than or equal to] k [less than or equal to] n, our formula can be proved by induction with respect to n. When n = 2, we only have the case of k = 2, where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now, we consider the following inductive step, for 3 [less than or equal to] k [less than or equal to] n,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A similar procedure can be used to prove the formula when k = 2, thus completing the proof. []

We may now use eq. (14) and consider the sets and transition probabilities described in Propositions 5.2 and 5.3, concluding that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (24)

where

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

Further simplification of eq. (24) and (25) is possible, using the following two summation identities. Lemma 5.1

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: We use the binomial identity as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Lemma 5.2 When [rho] [not equal to] and [alpha] [not equal to] 0, we have

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

Proof: We prove this identity by induction. When n = 2, both sides of the identity equal to [rho][beta]. If we denote by h(n) the left hand side of eq. (26), then h(n +1) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 2 OMITTED]

Now, using the inductive hypothesis of eq. (26) and Lemma 5.1, we simplify h(n +1) as follows,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Using Lemmas 5.1 and 5.2, we can now simplify eq. (24) and (25) to give

[P.sub.n](1) = [rho](1 - [rho]) + [[rho].sup.2] [(1 - (1 - [rho])[alpha]).sup.n]. (27)

The asymptotic density, therefore, is given by

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

Figure 2(a) shows the graph of P(1) vs. [alpha] and [rho].

In the special case when [rho] = 1/2, we obtain

[P.sup.(s).sub.n] (1) = 1/4 + 1/4 [(1 - [alpha]/2).sup.n]. (29)

In Figure 2(b), the graph of [P.sup.(s).sub.n] (1) is shown as a function of a, as given in eq. (29). The same figure shows results of computer simulation of iterations of Rule 140, in which this rule was applied to an array of length 20000, iterated 100000/[alpha] times for [alpha] > 0.1 and 1000000 times for [alpha] [less than or equal to] 0.1, with periodic boundary conditions, and the results were averaged over 100 runs.

Basic Blocks For Rule 140A, we were also able to find explicit formulae for probabilities each of the eight basic blocks. Once again omitting details, in Table 3 we show the set of n-step preimage blocks for four of the eight basic block, together with corresponding initial probabilities and respective transition probabilities. One can use this table together with consistency conditions for block probabilities to find formulae for probabilities of all eight basic blocks. We summarize these results as follows, where we assume that [alpha] [not equal to] 0.

[TABLE 3 OMITTED]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

6 Rule 76A

Rule 76 is the most difficult to analyze. Its transition probabilities are defined as

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

and [omega](0|b) = 1 - [omega](1|b) for all b [member of] [A.sup.3]. If [alpha] = 1, then this rule is equivalent to deterministic Rule 76.

In this section, we will use the Kroenecker delta function, defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

We now find the set of all potential preimage blocks and their respective transition probabilities. We start by defining [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to be the set of blocks of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where 1 [less than or equal to] [k.sub.1], [k.sub.2] [less than or equal to] n. The values of [k.sub.1], [k.sub.2] refer to the number of 1's to the left and right, respectively, of the centre [1.bar] before the first potential occurence of a 0. Note that if [k.sub.1] = n or [k.sub.2] = n, then the block may not contain any 0's to the left or right of the centre.

Proposition 6.1 The set supp [[omega].sup.n] (1|x) consists of all blocks in

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: From eq. (30), we can see that a site in state 0 will always remain in state 0, so that for any block e' [member of] supp [[omega].sup.n](1|x) \ [E.sub.n], we have [[omega].sup.n](1|e') = 0. A block in supp [[omega].sup.n](1|x), however, could produce a single 1 with some non-zero probability. []

We were not able to obtain explicit formulae for transition probabilities for this rule, but we were able to find recursive formulae for them.

Proposition 6.2 For any block belonging to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], to be denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof:

The proof of this proposition is rather long and tedious. It is similar in structure to the derivation of eq. (23). Since we were unable to derive a closed-form expression for the sums contained in the above transition probability, we omit the details of the derivation here. The full proof is available upon request.

If we consider eq. (14) and Proposition 6.2, we conclude that

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

The response curve (Figure 3(a)) is plotted using eq. (31) for n = 15/[alpha] for [alpha] > 0.1 and n = 150 when [alpha] [less than or equal to] 0.1.

The symmetric response curve is given by

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

In Figure 3(b), [P.sup.(s).sub.n] (1), given by eq. (32) is plotted with together with results of directly simulated iterations of Rule 76. For the theoretical plot, we used n = 15/[alpha] for [alpha] > 0.1 and n =150 when [alpha] [less than or equal to] 0.1. For the simulated plot, an array of length 20000 was iterated 100000/[alpha] times with [alpha] > 0.1 and 1000000 times with [alpha] [less than or equal to] 0.1, with periodic boundary conditions, averaged over 100 runs. We can see that as before, there is a close agreement between the theoretical and experimental results.

7 Conclusion

We have demonstrated that for single-transition asynchronous rules it is possible to find explicit expressions for probabilities of 1 after n iterations of the rule, starting from the Bernoulli measure. In two cases these expressions are explicit, in the third case we found a recursive formula. Furthermore, for rules 200A and 140A, one can also compute probabilities of blocks of length 3 (thus, by using consistency conditions, also of length 2). These results provide partial characterization of the orbit of Bernoulli measure under the action of single-transition asynchronous rules.

[FIGURE 3 OMITTED]

We hope that these results are useful in future research on probabilistic rules, in the following context. There exist various methods for computing approximate orbits of measures in CA and related system, such as, for example, mean-field approximation and its generalization, called a local structure theory (Gutowitz et al., 1987). The quality of these approximations is often judged by comparison of their predictions with computer experiments. This is not entirely satisfactory for a number of reasons, among them the fact that simulations are only possible for finite systems. Having some benchmark cases for which exact solutions are known, such as those presented here, will help to evaluate quality of approximate methods in a more rigorous fashion. Work in this direction is currently in progress.

Acknowledgements

One of the authors (HF) acknowledges financial support from the Natural Sciences and Engineering Research Council of Canada (NSERC) in the form of Discovery Grant. This work was made possible by the facilities of the Shared Hierarchical Academic Research Computing Network (SHARCNET:www.sharcnet.ca) and Compute/Calcul Canada. Authors wish to thank N. Fates for reading of the manuscript and useful comments. They also thank to anonymous referees for constructive reports which helped to improve the paper.

References

V. Belitsky and P. A. Ferrari. Invariant measures and convergence properties for cellular automaton 184 and related processes. Journal of Statistical Physics, 118:589-623, 2005.

M. Blank. Ergodic properties of a simple deterministic traffic flow model. Journal of Statistical Physics, 111:903-930, 2003.

N. Fates and M. Morvan. An experimental study of robustness to asynchronism for elementary cellular automata. Complex Systems, 16:1-27, 2005.

N. Fates, D. Regnault, N. Schabanel, and E. Thierry. Asynchronous behavior of double-quiescent elementary cellular automata. In J. Correa, A. A. Hevia, and M. Kiwi, editors, LATIN 2006: Theoretical Informatics, volume 3887 of LNCS, pages 455-466, 2006.

E. Formenti and P. Kurka. Dynamics of cellular automata in non-compact spaces. In R. A. Meyers, editor, Encyclopedia of Complexity and System Science. Springer, 2009.

H. Fuks. Exact results for deterministic cellular automata traffic models. Phys. Rev. E, 60:197-202, 1999.

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

H. Fuks. Probabilistic initial value problem for cellular automaton rule 172. DMTCS proc., AL:31-44, 2010.

H. A. Gutowitz, J. D. Victor, and B. W. Knight. Local structure theory for cellular automata. Physica D, 28:18-48, 1987.

P. Kurka. On the measure attractor of a cellular automaton. Discrete and Continuous Dynamical Systems, pages 524 - 535, 2005.

P. Kurka. Topological dynamics of cellular automata. In R. A. Meyers, editor, Encyclopedia of Complexity and System Science. Springer, 2009.

P. Kurka and A. Maass. Limit sets of cellular automata associated to probability measures. Journal of Statistical Physics, 100:1031-1047, 2000.

M. Pivato. Conservation laws in cellular automata. Nonlinearity, 15(6):1781, 2002.

M. Pivato. Ergodic theory of cellular automata. In R. A. Meyers, editor, Encyclopedia of Complexity and System Science. Springer, 2009.

Henryk Fuks and Andrew Skelton

Department of Mathematics and Statistics, Brock University, St. Catharines, Canada.
Tab. 1: Single transition rules.

Wolfram   Fates   Minimal
code      code     rule

205         A       76
206         B       140
220         C       140
236         D       200
200         E       200
196         F       140
140         G       140
76          H       76
COPYRIGHT 2012 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2012 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Fuks, Henryk; Skelton, Andrew
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:1CANA
Date:Jan 1, 2012
Words:5363
Previous Article:Selfsimilarity, simulation and spacetime symmetries.
Next Article:Conservation laws and invariant measures in surjective cellular automata.
Topics:

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |