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.