Title: Ergodicity and mixing rate of one-dimensional cellular automata
Author: Kihong Park, Computer Science Department, Boston University
Date: July 22, 1996

Abstract:

One-and two-dimensional cellular automata which are known to be
fault-tolerant are very complex.  On the other hand, only very simple
cellular automata have actually been proven to lack fault-tolerance,
i.e., to be mixing.  The latter either have large noise probability 
$\eps$ or belong to the small family of two-state nearest-neighbor 
monotonic rules which includes local majority voting.

For a certain simple automaton $L$ called the soldiers rule, this problem 
has intrigued researchers for the last two decades since $L$ is clearly 
more robust than local voting: in the absence of noise, $L$ eliminates any 
finite island of perturbation from an initial configuration of all 0's or 
all 1's.  The same holds for a 4-state monotonic variant of $L$, $K$,
called two-line voting.  We will prove that the probabilistic cellular 
automata $K_\eps$ and $L_\eps$ asymptotically lose all information about 
their initial state when subject to small, strongly biased noise.  The 
mixing property trivially implies that the systems are ergodic.

The finite-time information-retaining quality of a mixing system can be
represented by its relaxation time $\Relax(\cdot)$, which measures the time 
before the onset of significant information loss.  This is known to grow 
as $(1/\eps)^c$ for noisy local voting.  The impressive error-correction 
ability of $L$ has prompted some researchers to conjecture that 
$\Relax(L_\eps)=2^{c/\eps}$.  We prove the tight bound
$2^{c_1\log^2 1/\eps} < \Relax(L_\eps) < 2^{c_2\log^2 1/\eps}$ for a biased 
error model.  The same holds for $K_\eps$.  Moreover, the lower bound is 
independent of the bias assumption.

The strong bias assumption makes it possible to apply sparsity/renormalization 
techniques, the main tools of our investigation, used earlier in the 
opposite context of proving fault-tolerance.