License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.296
URN: urn:nbn:de:0030-drops-30190
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3019/
Go to the corresponding LIPIcs Volume Portal

Busic, Ana ; Mairesse, Jean ; Marcovici, Irene

Probabilistic cellular automata, invariant measures, and perfect sampling

pdf-format:
29.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{busic_et_al:LIPIcs:2011:3019,
  author =	{Ana Busic and Jean Mairesse and Irene Marcovici},
  title =	{{Probabilistic cellular automata, invariant measures, and perfect sampling}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{296--307},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3019},
  URN =		{urn:nbn:de:0030-drops-30190},
  doi =		{10.4230/LIPIcs.STACS.2011.296},
  annote =	{Keywords: probabilistic cellular automata, perfect sampling, ergodicity}
}

Keywords: probabilistic cellular automata, perfect sampling, ergodicity
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI