Probabilistic cellular automata, invariant measures, and perfect sampling

Details Probabilistic cellular automata, invariant measures, and perfect sampling Probabilistic cellular automata, invariant measures, and perfect sampling

2010-10-15

arxiv.org/abs/1010.3133v2

Mathematics

Probability

Scientific paper

A probabilistic cellular automaton (PCA) can be viewed as a Markov chain. The cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. We investigate the ergodicity of this Markov chain. A classical cellular automaton is a particular case of PCA. For a 1-dimensional cellular automaton, 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. Last, we focus on the PCA Majority, whose asymptotic behavior is unknown, and perform numerical experiments using the perfect sampling procedure.

Affiliated with

Also associated with

No associations

Rating

Probabilistic cellular automata, invariant measures, and perfect sampling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Probabilistic cellular automata, invariant measures, and perfect sampling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic cellular automata, invariant measures, and perfect sampling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-203870