2026-07-24T11:17:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3019 2024-03-06T10:33:44Z ddc:004 open_access

Probabilistic cellular automata, invariant measures, and perfect sampling Busic, Ana Mairesse, Jean Marcovici, Irene probabilistic cellular automata perfect sampling ergodicity In a probabilistic cellular automaton (PCA), the cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. A PCA can be viewed as a Markov chain whose ergodicity is investigated. A classical cellular automaton (CA) is a particular case of PCA. For a 1-dimensional CA, we prove that ergodicity is equivalent to nilpotency, and is therefore undecidable. We then propose an efficient perfect sampling algorithm for the invariant measure of an ergodic PCA. Our algorithm does not assume any monotonicity property of the local rule. It is based on a bounding process which is shown to be also a PCA. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ana Busic and Jean Mairesse and Irene Marcovici 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.296 urn:nbn:de:0030-drops-30190 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.296 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode