Back to search

Boston University Computer Science Department

Ergodicity and Mixing Rate of One-Dimensional Cellular Automata

Abstract

dc:description.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 ε 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ε and Lε 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(⋅), which measures the time before the onset of significant information loss. This is known to grow as (1/ε)^c for noisy local voting. The impressive error-correction ability of L has prompted some researchers to conjecture that Relax(Lε) = 2^(c/ε). We prove the tight bound 2^(c1log^21/ε) < Relax(Lε) < 2^(c2log^21/ε) for a biased error model. The same holds for Kε. 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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
Boston University Computer Science Department
Year dc:date.issued
1997

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Park, Kihong

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Citation
Park, Kihong. "Ergodicity and mixing rate of one-dimensional cellular automata", Technical Report BUCS-1996-015, Computer Science Department, Boston University, July 22, 1996. [Available from: http://hdl.handle.net/2144/1591]

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Park, Kihong. Ergodicity and Mixing Rate of One-Dimensional Cellular Automata. doctoral thesis, Boston University Computer Science Department, 1997. https://hdl.handle.net/2144/1591