Top Qs
Timeline
Chat
Perspective
Stochastic cellular automaton
Cellular automaton with probabilistic rules From Wikipedia, the free encyclopedia
Remove ads
A stochastic cellular automaton (SCA), also known as a probabilistic cellular automaton (PCA), is a type of computational model. It consists of a grid of cells, where each cell has a particular state (e.g., "on" or "off"). The states of all cells evolve in discrete time steps according to a set of rules.
![]() | This article may be too technical for most readers to understand. (June 2013) |
Unlike a standard cellular automaton where the rules are deterministic (fixed), the rules in a stochastic cellular automaton are probabilistic. This means a cell's next state is determined by chance, according to a set of probabilities that depend on the states of neighboring cells.[1]
Despite the simple, local, and random nature of the rules, these models can produce complex global patterns through processes like emergence and self-organization. They are used to model a wide variety of real-world phenomena where randomness is a factor, such as the spread of forest fires, the dynamics of disease epidemics, or the simulation of ferromagnetism in physics (see Ising model).
As a mathematical object, a stochastic cellular automaton is a discrete-time random dynamical system. It is often analyzed within the frameworks of interacting particle systems and Markov chains, where it may be called a system of locally interacting Markov chains.[2][3] See [4] for a more detailed introduction.
Remove ads
Formal definition
Summarize
Perspective
From the perspective of probability theory, a stochastic cellular automaton is a discrete-time Markov process. The configuration of all cells at a given time is a state in a product space . Here, is a graph representing the grid of cells (e.g., ), and each is the finite set of possible states for the cell (e.g., ).
The transition probability, which defines the dynamics, has a product form:
where is the next configuration and is a probability distribution on .
Locality is a key requirement, meaning the probability of a cell changing its state depends only on the states of its neighbors. This is expressed as , where is a finite neighborhood of cell and are the states of the cells in that neighborhood. See [5] for a more detailed introduction from this point of view.
Remove ads
Examples of stochastic cellular automaton
Majority cellular automaton
There is a version of the majority cellular automaton with probabilistic updating rules. See the Toom's rule.
Relation to lattice random fields
PCA may be used to simulate the Ising model of ferromagnetism in statistical mechanics.[1] Some categories of models were studied from a statistical mechanics point of view.
Cellular Potts model
There is a strong connection[6] between probabilistic cellular automata and the cellular Potts model in particular when it is implemented in parallel.
Non Markovian generalization
The Galves–Löcherbach model is an example of a generalized PCA with a non Markovian aspect.
Remove ads
References
Further reading
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads