Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2014 Sep;21(9):699-708.
doi: 10.1089/cmb.2014.0074. Epub 2014 Jul 7.

Probabilistic cellular automata

Alexandru Agapie  1 , Anca Andreica, Marius Giuclea
Affiliations

Probabilistic cellular automata

Alexandru Agapie et al. J Comput Biol. 2014 Sep.

Abstract

Cellular automata are binary lattices used for modeling complex dynamical systems. The automaton evolves iteratively from one configuration to another, using some local transition rule based on the number of ones in the neighborhood of each cell. With respect to the number of cells allowed to change per iteration, we speak of either synchronous or asynchronous automata. If randomness is involved to some degree in the transition rule, we speak of probabilistic automata, otherwise they are called deterministic. With either type of cellular automaton we are dealing with, the main theoretical challenge stays the same: starting from an arbitrary initial configuration, predict (with highest accuracy) the end configuration. If the automaton is deterministic, the outcome simplifies to one of two configurations, all zeros or all ones. If the automaton is probabilistic, the whole process is modeled by a finite homogeneous Markov chain, and the outcome is the corresponding stationary distribution. Based on our previous results for the asynchronous case-connecting the probability of a configuration in the stationary distribution to its number of zero-one borders-the article offers both numerical and theoretical insight into the long-term behavior of synchronous cellular automata.

Keywords: binary lattice; cellular automata; detailed balance equation; finite homogeneous Markov chain; stationary distribution.

PubMed Disclaimer

Figures

<b>FIG. 1.</b>
FIG. 1.
Stationary distribution for three-neighborhood synchronous automata, n = 106.
<b>FIG. 2.</b>
FIG. 2.
Stationary distribution for five-neighborhood synchronous automata Sync 2.
See this image and copyright information in PMC

References

    1. Agapie A.2010. Simple form of the stationary distribution for 3D cellular automata in a special case. Physica A. 389, 2495–2499
    1. Agapie A., and Aus der Fuenten T.2008. Stationary distribution for a majority voter model. Stoch. Models. 24, 503–512
    1. Agapie A., Agapie M., Rudolph G., et al. . 2013. Convergence of evolutionary algorithms on the n-dimensional continuous space. IEEE Trans. on Cybernetics. 43, 1462–1472 - PubMed
    1. Agapie A., Höns R., and Agapie Ad.2010. Limit behavior of the exponential voter model. Math. Soc. Sci. 59, 271–281
    1. Agapie A., Mühlenbein H., and Höns R.2004. Markov chain analysis for one-dimensional asynchronous cellular automata. Methodol. Comput. Appl. 6, 181–201

Publication types

LinkOut - more resources