{'fraction_non_alphanumeric': 0.05192231470471661, 'fraction_numerical': 0.01854934601664685, 'mean_word_length': 3.6879722531896446, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 12, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the decomposition of stochastic cellular automata

In this paper we present two interesting properties of stochastic cellular automata that can be helpful in analyzing the dynamical behavior of such automata. The first property allows calculating cell-wise probability distributions over the state set of a stochastic cellular automaton, i.e. mages that show the average state of each cell during the stochastic cellular automaton evolution. The second property shows that stochastic cellular automata are equivalent to so-called stochastic mixtures of deterministic cellular automata. By means of this property, any stochastic cellular automaton can be decomposed into a set of deterministic systems, each of which contributes to the behavior of the stochastic system.


Introduction
Cellular Automata (CAs) are often used for constructing models in a variety of fields of application including chemistry, biology, medicine, physics, ecology and the study of socioeconomic interactions. In many of these settings, Stochastic CAs (SCAs) are considered due to the stochastic nature of the phenomenon being modeled or the lack of understanding of the exact rules driving the phenomenon [1,2]. Therefore, a better understanding of the dynamics of SCAs is crucial. Only a few methods for dealing with the analysis of models based on SCAs have been developed. In the case of many practical applications, sampling methods, relying on repetitive computer simulations are sufficient [3,4,5], especially in cases when the averaged behavior of the system is concerned. Techniques built on the mean-field theory can be used to study correlations and long-term behavior of SCAs [6]. The theory of Markov chains can be applied to provide analytical tools for analyzing the model's behavior [7] although in practice, due to the theoretical and computational complexity of such methods, the application scope is limited. This paper is devoted to providing effective analytical tools for the analysis of multi-state SCAs, which are based on deterministic CAs. Although the theoretical foundation of the presented results is already (at least partially) known in the literature [7,8,9], so far the applications are limited. Therefore, the main aim of this paper is to provide a complete, formal description of the discussed properties in a form that is suitable for applications and does not require a strong mathematical background, as well as to present examples that can motivate further applications in the domain of systems modeling.
The methods presented here are developed in the context of 1D SCAs on finite lattices, but can be easily generalized to the case of higher dimensions and infinite spaces.
Two main results are presented in this paper. The first one involves constructing images that show the cell-wise probability distribution over the state set, at any time step. The method is based on associating an SCA with a deterministic, Continuous CA (CCA). The second result shows the equivalence of SCAs and stochastic mixtures of deterministic CAs. Based on this finding, any SCA can be decomposed into a finite set of deterministic CAs, each of them contributing to the behavior of the stochastic system. An effective method for finding a decomposition is presented. It allows to uncover the deterministic component in the mixture with the highest impact on the behavior of the SCA. This paper is organized as follows. We start with some preliminaries and definitions in Section 2. In Section 3, we introduce the concept of CCAs and the formalism enabling the analysis of multi-state CAs. Section 4 contains the definition of multi-state SCAs and holds the main results of this paper. The paper is concluded with Section 5, discussing the experimental results that illustrate both properties. A summary is presented in Section 6.

Preliminaries
Informally, a CA is a discrete dynamical system in which the space is subdivided into discrete elements, referred to as cells. At every consecutive, discrete time step, each cell is assigned one of N states using a deterministic rule, which depends only on the previous state of the considered cell, and the states of its neighboring cells [10].
Formally speaking, let the state set S be a finite set of N > 1 elements. Elements of the set C = {c i | i = 1, . . . , M } will be referred to as cells. Every cell c i is assigned a state s(c i , t) ∈ S at each time step t ∈ N, according to a local, deterministic rule. The vector s(·, t) ∈ S M will be referred to as the configuration, and as the initial configuration when t = 0. The sequence (s(·, 0), s(·, 1), . . .) will be referred to as the space-time diagram of the CA. For technical reasons, we impose periodic boundary conditions, but our results do not depend on this assumption.
The mapping A : S M → S M satisfying: (for every t ∈ N) will be referred to as a global CA rule or simply a CA, if there exists a radius r ∈ N and a function f : S 2 r+1 → S satisfying: for every i and t ∈ N. Such a function f will be referred to as a local rule. Note that a local rule uniquely defines the global rule, while for a given global rule, multiple local rules exist. Additionally, it is assumed that r M . The sequence (c i−r , c i−r+1 , . . . , c i+r−1 , c i+r ) will be referred to as the neighborhood of cell c i and R = 2 r + 1 will denote the neighborhood size. For the sake of simplicity, s(c i−r , . . . , c i+r , t) ∈ S R will denote the state of the neighborhood of cell c i at time step t, and will be referred to as the neighborhood configuration at time step t.

Continuous CAs
There exist multiple ways of extending the definition of CAs to cover infinite state sets. Examples of such approaches include Coupled Map Lattices (CMLs) [11] and so-called fuzzy CAs [12,13,14]. In this section, we present Continuous CAs (CCAs), which can be seen as a generalization of the ideas presented in [12]. Our formalism is based on a polynomial representation of discrete CA rules. We start with formulating the continuous counterparts of binary CAs. After that we present a generalization to cover multi-state CAs.

Binary CAs
Binary CAs are widely studied [15,16], because they allow to evolve complex patterns and exhibit complex behavior despite their intrinsic simplicity. The state set of such a CA A is S = {0, 1} and its f : S R → S is uniquely defined by the following system of equalities: for all possible binary sequences (s 1 , . . . , s R ), where i is defined as i = 1 + (2), variables s i correspond to the states constituting the neighborhood configuration. The binary vector (l i ) 2 R i=1 will be referred to as the lookup table (LUT) of the local rule f . Following [12], we know that the function f can be expressed as the following polynomial: where n(s m , i) is defined as: The function ind is related to the binary representation of integers. In [12] a simpler formulation using the function bin is used. The construction presented here, although a bit more complicated in the binary setting, allows for an easier generalization to the multi-state case. It is defined in such a way that ind(i) [m] is the m-th digit, incremented by one, read from left to right, of the binary representation of the integer i − 1, padded with ones on the left, so that it always has length R. Consequently, it holds that: The values of ind(i) for R = 3 and i ∈ {1, . . . , 8} are shown below: ind(5) = (2, 1, 1), ind(6) = (2, 1, 2), ind(7) = (2, 2, 1), ind(8) = (2, 2, 2).
Using this notation, a CCA can be defined analogously to a binary CA, with two notable differences. Firstly, the state set of a CCA is the unit interval, i.e. S = [0, 1], and, secondly, the local rule f : [0, 1] R → [0, 1] is given by Eq. (4) with coefficients l i ∈ [0, 1]. We will refer to such a sequence (l i ) 2 R i=1 as a generalized LUT. It is easy to check that this definition of a CCA is formally correct. Note that this construction is directly related to the one presented in [12], where fuzzy CAs are constructed as polynomials representing fuzzified logical functions. Following the same line of reasoning, in [17] an alternative polynomial representation for the local rules of binary CAs is presented, which is consistent with a logical representation of the local rules.
In order to introduce the formalism that is needed in the multi-state setting, we present a slightly modified way of representing binary CAs compared to the one obtained through Eq. (4). Let us assume that the state set is given by Then the local rule is a function f : S R 2 → S 2 and can be represented as a vector function f = (f 1 , f 2 ), where f j : S R 2 → {0, 1}. Note that any s = (s 1 , s 2 ) ∈ S 2 satisfies s 2 = 1 − s 1 . Similarly, f 2 = 1 − f 1 , so that the local rule f can be defined using f 2 only. We define f 2 with a formula similar to Eq. (4): where for every i = 1, . . . , 2 R it holds that l i = (l i,1 , l i,2 ) ∈ S 2 and for every m ∈ {1, . . . , R}, s m = (s m,1 , s m,2 ) ∈ S 2 . Since s m,1 = 1 − s m,2 , we can rewrite the formula for n as: which can simplified to: and thus f 2 becomes: Having defined the function f 2 , we can prove the following fact, which gives a direct formula for f 1 .
Lemma 1. Function f 1 can be expressed as: Due to the above, we can write a general expression for f j , j = 1, 2, as: Resorting to this vector notation, a CCA can be defined with a state set: and a local rule f : S R c → S c given by Eq. (10) with (l j ) 2 R j=1 ∈ S 2 R c .

Example 2.
The local rule f 150 of ECA 150 presented in Example 1 can be rewritten in the context of the state set S 2 , as f : S 3 2 → S 2 , f = (f 1 , f 2 ). Note that for s i ∈ S 2 it holds that s i = (s i,1 , s i,2 ) for i = 1, 2, 3. The local rule f can be written as: f 1 (s 1 , s 2 , s 3 ) = s 1,2 s 2,2 s 3,1 + s 1,2 s 2,1 s 3,2 + s 1,1 s 2,2 s 3,2 + s 1,1 s 2,1 s 3,1 The representation given by Eq. (10) is equivalent to that given by Eq. (4), but allows for an easier generalization to multi-state CAs. Therefore, we will use it throughout the remainder of this paper.

Multi-state CAs
We start with generalizing the state set S 2 defined in Section 3.1 to the case of N states. Let S N ⊂ R N be the set of all base vectors of the N -dimensional Euclidean space, i.e.
Let the i-th state in a multi-state CA be represented by the base vector e i which has zeros everywhere, except at position i, where there is a one. For instance, if N = 3, then S 3 = {(1, 0, 0), (0, 1, 0), (0, 0, 1)}. For the sake of simplicity, in the remainder of this paper, we will write S instead of S N , assuming that N is fixed. We now generalize the function ind : {1, . . . , N R } → {1, . . . , N } R , defined previously for the binary case, to enumerate each of the N R neighborhood configurations. Let i ∈ {1, . . . , N R } be the index identifying a neighborhood configuration. We assume that such a configuration is formed of the following states: (e ind(i) [1] , e ind(i) [2] , . . . , e ind(i) [R] ).
The ordering of cells in neighborhoods can be chosen arbitrarily, but we assume that ind satisfies the following equation: The direct formula for calculating ind is given by: Essentially, ind(i) yields the positional representation of i − 1 in base N , padded with zeros on the left, so that it always has length R, where each of the digits is incremented by one. Hence, one finds easily: Any local rule f of an N -state, deterministic CA can be uniquely defined by writing down its outputs for all of the possible neighborhood configurations. Formally, let us consider the system of equations: where i ∈ {1, . . . , N R } and l i ∈ S. Similarly to the binary case, L = (l i ) N R i=1 ∈ S N R will be called the LUT of a multi-state CA. Basically, L is a matrix of N R columns and N rows, containing only 0s and 1s, in such a way that every column contains exactly one non-zero entry. Each of the matrices L ∈ S N R uniquely defines an N -state CA in terms of its local rule.
In order to define a CCA in the context of multiple states, we need to formally define its state set. Let S c be defined as: which is consistent with the definition for N = 2 given by Eq. (11). Note that any s ∈ S c satisfies s i = 1 − j =i s j . The set S c is commonly referred to as a standard (N − 1)-simplex [18].
In the case of a CCA, the local rule is a vector function f : where P ∈ S N R c . Note that s m is an element of S c ⊂ [0, 1] N for m = 1, . . . , R, such that s m,q ∈ [0, 1] for q = 1, . . . , N . We will refer to P as the generalized LUT of a CCA.
We will show that the definition given by Eq. (18) is formally correct, meaning that f defined with components f j satisfies f : Proof. Let Note that for every j ∈ {1, . . . , N } R , there exists exactly one i ∈ {1, . . . , N R } such that j = ind(i). Due to this, it holds that: By regrouping the elements of the sum S we may write: Since s R ∈ S c , we know that N i=1 s R,i = 1, and thus: By repeating this regrouping procedure R − 1 times, we finally get: Proposition 1. For any j ∈ {1, . . . , N }, and any s 1 , . . . , s R ∈ S c , it holds that: Proof. Firstly, f j (s 1 , . . . , s R ) ≥ 0 is fulfilled since all of the elements in the sum in Eq. (18) are non-negative. Therefore, it suffices to show that f j (s 1 , . . . , s R ) ≤ 1. Since P ij ≤ 1, we can write: Lemma 3. For any s 1 , . . . , s R ∈ S c , it holds that: Proof. The claim is proven by the following chain of equalities: Proposition 2. For any s 1 , . . . , s R ∈ S c it holds that: Proof. This proposition is a direct consequence of Lemma 3.
We have shown the correctness of the CCA definition. We conclude this section with the observation that the local rule f : S R → S of any N -state, deterministic, 1D CA can always be written in the form of Eq. (18), where s 1 , . . . , s R ∈ S, f j : S R → {0, 1} and N j=1 f j (s 1 , . . . , s R ) = 1. This shows that CCAs are a generalization of N -state, deterministic CAs.

Properties of SCAs
In this section, we provide a general definition of an N -state SCA, which is formulated using the notation introduced in Section 3 for multi-state CAs and CCAs. Subsequently, we show the nature of the relation between SCAs and CCAs. Finally, we present a method for decomposing an SCA into a set of deterministic CAs.

General construction of multi-state SCAs
We define SCAs, the stochastic counterpart of multi-state CAs. We assume that the state set S is given by Eq. (12), and contains all the standard base vectors e i . In such a setting, the states are assigned according to a probability distribution, which depends on the neighborhood configuration at the previous time step. Therefore, SCAs are not defined through a local rule, but rather by a set of conditional expressions: where j ∈ {1, . . . , N } and k ∈ {1, . . . , N R }. The conditional probabilities p kj in Eq. (22) must not depend on the choice of i and t. Note that for every k it holds that N j=1 p kj = 1, and for any k, j obviously p kj ∈ [0, 1], such that the vector p k = (p k1 , . . . , p kN ) ∈ S c for all k. Furthermore, the matrix P = (p kj ) can be considered an element of S N R c . Consequently, every element in S N R c uniquely defines the probability distribution of some local rule. The matrix P will be referred to as the probabilistic lookup table (pLUT). Such matrices are commonly known as stochastic matrices [19] and are typically used in the analysis of Markov chains. Any SCA is uniquely defined by a pLUT belonging to S N R c . Since we know from Section 3.2 that every element of S N R c uniquely defines a CCA, we elaborate on the relationship between an SCA defined by a pLUT P ∈ S N R c and a CCA defined by a generalized LUT P .

Relationship between CCAs and SCAs
In contrast to deterministic CAs, only the initial state s(·, 0) is known with certainty in the case of SCAs, while for s(·, t), t > 0, only a probability distribution can be calculated. Let π(c i , t | I 0 ) denote the probability distribution over the set of states S for the i-th cell at time step t, given that the evolution started from the initial condition I 0 , i.e. s(·, 0) = I 0 . Whenever it will not bring confusion, we will omit I 0 and write π(c i , t). Since there are N states, we need to specify N probabilities summing up to 1, to define π(c i , t). For this reason, let us represent π(c i , t) as a vector of probabilities, i.e. π(c i , t) ∈ S c , such that: where j = 1, . . . , N . When using SCAs in practical problem settings, one might be interested in computing the values of π(c i , t) for any t. Normally, this is achieved by means of sampling methods [3,4,5], i.e. multiple space-time diagrams are generated from the same initial condition and probability distributions are estimated, based on the frequencies of reaching any of the states in a given cell. Unfortunately, such an approach has serious drawbacks, especially in terms of the computational burden it brings along. Yet, one can calculate π(c i , t) much faster by relying on CCAs. π(c i , t + 1) = f (π(c i−r , t), . . . , π(c i+r , t)) , for any i and t.
Proof. Let k ∈ {1, . . . , N R } and j ∈ {1, . . . , N }, then p kj is the probability of reaching state e j if the neighborhood configuration was known to be (e ind(k) [1] , . . . , e ind(k) [R] ), which will be referred to as the k-th neighborhood.
Assuming that π(·, t) is known, the probability of cells (c i−r , . . . , c i+r ) being in the k-th neighborhood, can be calculated with the following formula: Due to the Total Probability Theorem, the probability of reaching state e j in at time step t + 1 is expressed as: Substituting Eqs. (22) and (25) in Eq. (26), we get: Taking into account the definition of the function f in Eq. (18), we can rewrite Eq. (27) as: P s(c i , t + 1) = e j = f j (π(c i−r , t), . . . , π(c i+r , t)) .
As shown above, the construction of CCAs is directly connected to the Total Probability Theorem, and thus it enables us to better understand the evolution of cell-wise probability distributions of SCAs. It is important to highlight that the evolution of those distributions is deterministic in SCAs, although the dynamical system itself is stochastic. The finding above agrees with [14], where a similar result in the case of binary CAs was shown. Yet, it was confined to study the asymptotic behavior of deterministic CAs. Interestingly, in [20] SCAs are defined as deterministic mappings of probability measures. Although the definition presented there is much more abstract, and suits mostly theoretical applications, it reassembles the main ideas of CCAs.

Decomposition of SCAs
In the previous subsection, we have shown that CCAs are directly related to SCAs, since the evolution of a CCA is equivalent to the evolution of the cell-wise probability distributions of an SCA. Here, we uncover the relationship between SCAs and deterministic, N -state CAs, and discuss the possibility of decomposing an SCA into deterministic CAs. Let us start with an introductory example motivating our general construction.
Example 4 (α-asynchronous CAs). Classically, states in deterministic CAs are updated synchronously, i.e. a new state is assigned to all cells simultaneously at every time step according to the local rule. Yet, different approaches of breaking the synchronicity of CAs have been proposed [21]. Interestingly, the choice of the update scheme, which defines the order or timing of cell state updates, has very important repercussions on the dynamical properties of CAs [22]. Here we focus on so-called α-asynchronous CAs (α-ACAs) [23].
Any α-ACA is defined by its deterministic counterpart A and a probability α, called the synchrony rate, which controls whether or not its cells are updated. More precisely, α is the probability of applying the local rule f of A, i.e.: Note that if α = 0, such a system remains at its initial configuration, whereas the system is equivalent to CA A if α = 1.
The essential property of the construction presented above is that an α-ACA can also be seen as a synchronous, stochastic system in which the local rule of A is selected with probability α, while the identity rule is selected with probability 1 − α. Hence, we may say that the rule of a CA A is stochastically mixed with the identity rule.
The idea behind α-ACA can be easily extended to the mixing of q ≥ 2 deterministic rules. Consider synchronous, deterministic CAs A 1 , A 2 , . . . , A q and probabilities α 1 , α 2 , . . . , α q that satisfy q i=1 α i = 1. Then, we define an SCA A in which the state of every cell at every consecutive time step is obtained by evaluating one of the local rules, corresponding to one of the A i . The rule is chosen randomly and independently for every cell at each time step with the selection probability for CA A i being α i . Such systems, referred to as stochastic mixtures of deterministic CAs in the remainder of this paper, have very interesting properties that are currently also investigated by others [24]. For technical reasons, we assume that the local rules of A 1 , . . . , A q are defined with a common radius r ≥ 0. Since each local rule with radius r < r can be represented equivalently as a local rule with radius r, we are not loosing generality with this assumption.
The first observation is a direct consequence of the definition presented above.
Fact 1. Assume that r ≥ 0 is the radius of the neighborhood of the local rules of automata A 1 , . . . , A q . Let R = 2 r + 1 and suppose that L i ∈ S N R is the LUT of CA A i for i = 1, . . . , q. Then the pLUT P ∈ S N R c of the stochastic mixture A satisfies: Linear combinations of the form 1] are commonly referred as convex combinations, which allows us to rephrase Fact 1 as: the pLUT of a stochastic mixture of deterministic CAs is the corresponding convex combination of the LUTs of the mixed CAs.
Having defined the concept of a stochastic mixture, we are interested in characterizing this class of SCAs. Interestingly, we are able to show that in general there are no characteristics that distinguish stochastic mixtures from other SCAs, since any SCA can be represented as a stochastic mixture. This fact is not surprising if we envisage a stochastic mixture of deterministic CAs as a convex combination of LUTs of deterministic CAs. We can rely on the classical Krein-Milman theorem from convex set theory [25]. It states that a compact convex set is the convex hull of its extreme points. In our context, the set S N R containing the LUTs of deterministic CAs is the set of extreme points of S N R c , which is convex and compact. The convex hull of S N R is the set of all possible convex combinations of elements from S N R , which is precisely the set of all stochastic mixtures of deterministic CAs. Due to this we can state the following theorem. The decomposition of a stochastic mixture into a convex combination described above is not unique, therefore many methods for constructing the decomposition can be formulated. In the proof of Proposition 4 we show one possible algorithm of which it will be shown in Proposition 5 that it uncovers the most influential component of the stochastic mixture.
Proposition 4. Let P ∈ S N R c . Then there exists a n * , such that for i = 1, 2, . . . , n * , we can define coefficients α i ∈ [0, 1], n * i=1 α i = 1 and matrices L i ∈ S N R , that satisfy: Proof. We start by defining auxiliary matrices P m , for m ≥ 0. Let: where, for m > 0: and L m = (L m ij ) such that: Note that, for any m, i, it holds that L m ij = 1 for only one value of j. Consequently L m ∈ S N R .
Firstly, note that α 1 is one of the elements of P 0 = P , so α 1 ∈ [0, 1]. Additionally, α 1 > 0, since if α 1 = 0, then for some i we would have max j P ij = 0, which contradicts the fact that j P ij = 1 for any i.
Secondly, note that for any i, j, it holds that P 0 ij ≥ 0. We will show next that the assumption P m−1 , it means that P m−1 ij ≥ α m . Since it was assumed that P m−1 ij ≥ 0, we see that P m ij ≥ 0 as well. Thirdly, following the argument above, we can easily show that for every i, j, m, it holds that P m ij ≤ P m−1 ij . This means that for every i, max j P m ij ≤ max j P m−1 ij , and thus α m+1 ≤ α m . Since α 1 ∈ ]0, 1], and α m ≥ 0 for any m, we see that α m ∈ [0, 1].
Note that for each i it holds that j P m ij = j P m−1 ij − α m . Expanding this recursively, gives us j P m ij = ( j P 0 ij ) − m l=1 α l . From the definition of a stochastic matrix, we know that j P 0 ij = 1, such that j P m ij = 1 − m l=1 α l , which means that the column sums in matrix P m are equal. Since for all m we have shown that P m ij ≥ 0, we know that for each m it holds 1 − m l=1 α l ≥ 0, therefore m l=1 α l ≤ 1. We further note that α m = 0 for some m, if and only if, P m−1 contains one zero column. Since we have shown that the column sums in P m are equal for any m, we know that α m = 0 if and only if, P m−1 = 0. Therefore, α m > 0 if and only if P m−1 = 0, which implies that in each of the columns of P m−1 there is at least one non-zero entry.
Let z(m) = #{(i, j) | P m ij = 0} denote the number of zeros in matrix P m . Note that if P m = 0, then z(m) < z(m + 1), which follows from the fact that if P m = 0, there exists P m ij = α m+1 > 0, and thus for at least one couple (i, j) we know that P m+1 ij = P m ij − α m+1 = 0. Since z(m) cannot be greater than the total number of elements in P m , it is not possible that z(m) < z(m + 1) for all m. As such, we know that there exist n * for which P n * = 0 and P n * −1 = 0, and thus n * l=1 α l = 1. Using the definition of P n * multiple times, we get: To illustrate the construction presented in the proof of Proposition 4, every step of the algorithm is visualized in the following example.
Example 5. Although Proposition 4 deals with stochastic matrices with dimensions corresponding to pLUTs, it is obvious that the same method can be used to decompose a stochastic matrix of arbitrary size. For simplicity, we apply the method to an exemplary 4 × 3 stochastic matrix P given by: According to Eqs. (30) and (32), we build matrices P 0 and L 1 : Note that we highlighted the selected maximal elements in each of the columns using boldfaced font. The boldfaced entries in P 0 correspond to the positions of one in matrices L 1 . Note that in the last column of P 0 , the choice for the maximal element is not unique. Yet, as given by Eq. (32), we pick the first of the entries from top to bottom. Picking the other possibility would affect the subsequent matrices L m and result in a different decomposition, but the coefficients α m would not be changed.
Following Eq. (31), we find that α 1 = 0.4. We proceed, and calculate P 1 and L 2 : and from this we see that α 2 = 0.3. We continue the procedure: and α 3 = 0.2. We proceed one more step and get: As mentioned earlier, the construction presented in the proof of Proposition 4 is one of many possibilities of decomposing a pLUT, but in the following proposition we will show that it enables us to capture the element of the mixture with the highest possible coefficient.
. . , p max , q = 1, . . . , q max , and let α p , β q ∈ [0, 1], L p , M q ∈ S N R be such that p α p = q β q = 1 and P = p α p L p = q β q M q . Let α p , L p be defined as in the proof of Proposition 4. Then max q β q ≤ α 1 = max p α p .
Proof. Let i, j be such that P ij = α 1 . Then for all k it holds that P ik ≤ α 1 . Let q ∈ {1, . . . , q max } and let l be such that M q il = 1. Since P = q β q M q , we know that β q ≤ P il , and thus β q ≤ P il ≤ α 1 . Therefore, for any q ∈ {1, . . . , q max } it holds that β q ≤ α 1 and thus max q β q ≤ α 1 .
The informal meaning of the above proposition is that the presented approach to decompose an SCA uncovers the deterministic rule that has the highest probability of being executed, and therefore is likely to have the highest influence on the behavior of the system. The exact relations between the dynamical behavior of SCAs and the dynamical characteristics of the components of stochastic mixtures are still under investigation.

Analysis of α-asynchronous ECAs
Through this experiment, we have analyzed the behavior of α-asynchronous ECAs. For a given rule, the cell-wise distance between the space-time diagram of the deterministic rule, and the space-time diagram of a CCA representation of an α-ACA variant for α ranging from 0 to 1 was measured. More formally, if A is an ECA rule, and A α the CCA representation of the α-asynchronous variant of A for α ∈ [0, 1], we measured the distance D(α) between space-time diagrams defined as:  Table  1.
the global rule A, t times to input I 0 . In this experiment, we choose M = T = 69. Unsurprisingly, it turned out that most pronounced discrepancies between the parallel evolutions are observed when α approaches 1. For that reason, we restrict the further discussion to α ∈ [0.9, 1]. We classified the ECAs according to the behavior of the function D (the contents of the classes is shown in Table 1): • Class I: D(α) is almost 0, for all α ∈ [0.9, 1] (Figure 1a), • Class II: D(α) smoothly decreases towards 0, as α increases (Figure 1b), • Class IIIa: there is a very sudden drop of D(α) as α approaches 1 (Figure 1c), • Class IIIb: there is a very sudden drop of D(α) as α approaches 1, and the behavior is not monotonic (Figure 1d).
The interpretation of the classes is as follows. Rules belonging to Class I, are resistant to α-asynchronicity, which means that introducing the asynchronicity aspect does not affect the behavior, or that its impact is negligible. Rules belonging to Class II are affected by the asynchronicity, but the impact on the final behavior is proportional to the synchrony rate α, i.e. the behavior steadily approaches the deterministic case, as α approaches one. Rules belonging to Classes IIIa and IIIb are sensitive to α-asynchronicity, meaning that the behavior of the system changes drastically as soon as α is smaller than 1. Class IIIb can be distinguished from Class IIIa, by the noisy behavior of D(α) for α close to one. The cause of the differences is not yet uncovered.

Stochastic density classifiers
We consider the SCA defined by the local rule C 3 introduced in [26,27]. This rule is defined by the pLUT shown in Table 2. Note that this pLUT uses the standard notation for its state set S = {0, 1}, and its entries constitute the probabilities of reaching state 1. It was shown both analytically and experimentally, that this rule is a stochastic solution for the classical density classification problem (DCP) [26] with arbitrary precision, i.e. by varying the parameter η we can achieve any probability p < 1 of successful classification. The DCP was introduced in [28,29].
Using the CCA representation, we can visualize the average behavior of the C 3 . In Figure 2, the first 80 rows of the averaged space-time diagram (time goes from top to bottom) obtained using the CCA representation of C 3 with η = 0.1 are shown, together with three typical space-time diagrams obtained by direct evaluation of the SCA rule C 3 . All images were obtained using the same initial condition involving 29 cells out of which 16 were black (state 1). As can be inferred from Figure 2, two samples lead to behavior that is similar to the one displayed by the average space-time diagram, while the one depicted in Figure 2d behaves differently, and leads to a wrong classification. Since the probability of obtaining a correct classification for the initial condition at stake was estimated to be 90.1% on the basis of 10000 repetitions, the impact of the erroneous cases on the averaged image is hardly visible. One of the most interesting questions within the analysis of DCP solutions relates to the expected time of convergence towards the outcome of the classification and how this relates to the number of cells. Figure 3 depicts the average convergence time calculated over an ensemble of 5000 random initial conditions for different numbers of cells and values of η, both for the CCA and SCA representation. The initial conditions were generated as follows. For every initial condition independently, a number p ∈ ]0, 1[ was selected randomly, and then the initial states were selected with p being the probability of selecting state 0. Such a selection procedure assures that each of the possible densities has the same probability in the ensemble of initial conditions, and thus we can evaluate the classifier across a diverse set of densities.
In the case of the CCA representation, we cannot expect reaching a truly homogeneous, global state. Therefore we evolved it until the maximum, absolute difference between the states of any two cells was lower than 0.001. Then, we verified whether the average of the states was closer to 1 or 0. In the case of the SCA, for each of the 5000 initial conditions, 100 simulations were performed, and the results were averaged. The results for small grid sizes (smaller than 200) are similar for both representations and agree with the findings presented in [26,27]. Yet, the computing time when using the CCA representation is significantly lower than in the case of SCAs. This indicates that the CCA representation of SCAs proposed in this paper might enable substantial reduction of the required computing time. Moreover, using the CCA representation, we are able to get more insight into the behavior of the dynamical system by plotting the evolution of the density over time. Figure 4 shows the results of such an experiment. For the sake of clarity, these results are based on an ensemble of 400 initial conditions (69 cells) out of which 200 had a density greater than a half (green), while the other 200 had a density lower than the half (red). The ensemble of initial configurations was the same for all values of η. Note that the range of the horizontal axis differs across plots. From Figure 4, we can infer that the time and quality of classification increases with decreasing η. Due to computational costs involved in evolving and averaging SCAs directly, drawing and analyzing such plots has became possible only due to the introduction of CCAs.
In this paper, we will refer to this subclass as totalistic SCAs. By applying the decomposition algorithm given by Proposition 4, we can prove the following fact showing their structure.
Fact 2. Any totalistic SCA can be written as a stochastic mixture of the following ECAs: 128, 150, 232, 254, where up to three of those rules are applied with non-zero probability.
We can determine the regions in the (p 1 , p 2 )-plane where a given deterministic CA has the highest probability of application, i.e. where it is dominant. These regions are given by: • ECA 128 is dominant, if p 1 < 0.5 and p 2 < 0.5, • ECA 150 is dominant, if p 1 < 0.5 and p 2 > 0.5, • ECA 232 is dominant, if p 1 > 0.5 and p 2 < 0.5, • ECA 254 is dominant, if p 1 > 0.5 and p 2 > 0.5.
Note that if p 1 = 0.5 or p 2 = 0.5, there is no unique, dominant rule, therefore we have omitted those cases in the description above.
The dynamical characteristics of the four ECAs that compose the totalistic SCAs differ significantly. Rules 128 and 254 are simple -they belong to Class I according to Wolfram's classification [16], and their maximum Lyapunov exponents (MLEs) [30] equals −∞, which means that any changes to their initial configuration do not influence their long-term behavior. Rule 232 belongs to complexity Class II, and its MLE is positive, but very close to zero. In contrast, rule 150 is a Class III rule, and its MLE is the highest among all ECAs, which highlights the fact that this rule is sensitive to the smallest perturbation of its initial configuration. Since rules 150 and 232 are relatively more complex than rules 128 and 254, we might expect a distinct behavior of the stochastic mixture in regions where the former are dominant.
In order to verify this we set up an experiment involving a random initial condition of M = 49 cells which was evolved 100 times for T = 49 time steps. Such a procedure, for the same initial condition, was repeated for multiple different choices of (p 1 , p 2 ) using a 100 × 100 homogenous grid, resulting in a The results for the minimum, mean and maximum of ∆(p 1 , p 2 ) and ∆ T (p 1 , p 2 ) are shown in Figure 6. As can be seen from the charts, the distance is especially high in those regions where the application probability α 150 is high, i.e. where p 1 > 0.5 and p 2 < 0.5, and near the line p 2 = −p 1 in the quarter p 1 < 0.5, p 2 > 0.5. The first region is the one where ECA 150 is dominant, while ECA 232 is dominant in the second one, but with ECA 150 having a substantially high application probability as well. Although the Hamming distance is just a simple indication of complexity, we already see a strong influence of the ECA 150 component.
The findings presented above suggest that analyzing the elements of a stochastic mixture unveil information on the dynamics of an SCA. Further research in this direction is undertaken to understand the influence of different dynamical classes of deterministic rules in the stochastic mixtures.

Summary
In this paper, two basic, yet important properties of SCAs were discussed. We have shown, both theoretically and practically that SCAs can be effectively analyzed in the context of deterministic CAs and CCAs. The stochastic mixture representation of SCAs in some cases allows to understand the underlying dynamics, while the CCA representation allows to quickly uncover the averaged behavior of the system. Further research is undertaken to further expand the application scope of the presented methods. (f) min ∆ T (p 1 , p 2 ) Figure 6: Impact of the probabilities p 1 and p 2 on the distances of space-time diagrams ∆(p 1 , p 2 ) and the final configurations after T = 49 time steps ∆ T (p 1 , p 2 ) of the totalistic SCA, obtained from the same initial condition.