Limit Measures for Affine Cellular Automata, II

Let M be a monoid (e.g. the lattice Z^D), and A an abelian group. A^M is then a compact abelian group; a linear cellular automaton (LCA) is a continuous endomorphism F:A^M --> A^M that commutes with all shift maps. Let mu be a (possibly nonstationary) probability measure on A^M; we develop sufficient conditions on mu and F so that the sequence {F^N mu} (N=1,2,3,...) weak*-converges to the Haar measure on A^M, in density (and thus, in Cesaro average as well). As an applicati...

If M is a monoid (e.g. the lattice Z^D), and G is a finite (nonabelian) group, then G^M is a compact group; a `multiplicative cellular automaton' (MCA) is a continuous transformation F:G^M-->G^M which commutes with all shift maps, and where nearby coordinates are combined using the multiplication operation of G. We characterize when MCA are group endomorphisms of G^M, and show that MCA on G^M inherit a natural structure theory from the structure of G. We apply this structur...

Let M=Z^D be a D-dimensional lattice, and let A be an abelian group. A^M is then a compact abelian group; a `linear cellular automaton' (LCA) is a topological group endomorphism \Phi:A^M --> A^M that commutes with all shift maps. Suppose \mu is a probability measure on A^M whose support is a subshift of finite type or sofic shift. We provide sufficient conditions (on \Phi and \mu) under which \Phi `asymptotically randomizes' \mu, meaning that wk*lim_{J\ni j --> oo} \Phi^j \...

If A=Z/2, then A^Z is a compact abelian group. A `linear cellular automaton' is a shift-commuting endomorphism F of A^Z. If P is a probability measure on A^Z, then F `asymptotically randomizes' P if F^j P converges to the Haar measure as j-->oo, for j in a subset of Cesaro density one. Via counterexamples, we show that nonzero entropy of P is neither necessary nor sufficient for asymptotic randomization.

Abelian cellular automata (CA) are CA which are group endomorphisms of the full group shift when endowing the alphabet with an abelian group structure. A CA randomizes an initial probability measure if its iterated images weak *-converge towards the uniform Bernoulli measure (the Haar measure in this setting). We are interested in structural phenomena, i.e. randomization for a wide class of initial measures (under some mixing hypotheses). First, we prove that an abelian CA ra...

The asymptotic behavior of a cellular automaton iterated on a random configuration is well described by its limit probability measure(s). In this paper, we characterize measures and sets of measures that can be reached as limit points after iterating a cellular automaton on a simple initial measure, in the same spirit as SRB measures. In addition to classical topological constraints, we exhibit necessary computational obstructions. With an additional hypothesis of connectivit...

For the action of an algebraic cellular automaton on a Markov subgroup, we show that the Ces\`{a}ro mean of the iterates of a Markov measure converges to the Haar measure. This is proven by using the combinatorics of the binomial coefficients on the regenerative construction of the Markov measure.

A `right-sided, nearest neighbour cellular automaton' (RNNCA) is a continuous transformation F:A^Z-->A^Z determined by a local rule f:A^{0,1}-->A so that, for any a in A^Z and any z in Z, F(a)_z = f(a_{z},a_{z+1}) . We say that F is `bipermutative' if, for any choice of a in A, the map g:A-->A defined by g(b) = f(a,b) is bijective, and also, for any choice of b in A, the map h:A-->A defined by h(a)=f(a,b) is bijective. We characterize the invariant measures of bipermutative...

This paper is devoted to probabilistic cellular automata (PCA) on $\mathbb{N}$, $\mathbb{Z}$ or $\mathbb{Z}/n\mathbb{Z}$, depending of two neighbors, with a general alphabet $E$ (finite or infinite, discrete or not). We study the following question: under which conditions does a PCA possess a Markov chain as invariant distribution? Previous results in the literature give some conditions on the transition matrix (for positive rate PCA) when the alphabet $E$ is finite. Here we ...

We consider the typical asymptotic behaviour of cellular automata of higher dimension (greater than 2). That is, we take an initial configuration at random according to a Bernoulli (i.i.d) probability measure, iterate some cellular automaton, and consider the (set of) limit probability measure(s) as time tends to infinity. In this paper, we prove that limit measures that can be reached by higher-dimensional cellular automata are completely characterised by computability condi...