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.

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

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads