stochastic cellular automaton

{{Short description|Cellular automaton with probabilistic rules}}

Stochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting Markov chains{{citation

| last = Toom | first = A. L.

| isbn = 978-3-540-08450-1

| mr = 0479791

| publisher = Springer-Verlag, Berlin-New York

| series = Lecture Notes in Mathematics | volume = 653

| title = Locally Interacting Systems and their Application in Biology: Proceedings of the School-Seminar on Markov Interaction Processes in Biology, held in Pushchino, March 1976

| year = 1978}}{{cite book|title=Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis|author1=R. L. Dobrushin |author2=V. I. Kri︠u︡kov |author3=A. L. Toom |year=1978|publisher=Manchester University Press |url=https://books.google.com/books?id=0Wa7AAAAIAAJ&q=locally+interacting+markov+chains+toom+Dobrushin&pg=PA181|isbn=9780719022067}} are an important extension of cellular automaton. Cellular automata are a discrete-time dynamical system of interacting entities, whose state is discrete.

The state of the collection of entities is updated at each discrete time according to some simple homogeneous rule. All entities' states are updated in parallel or synchronously. Stochastic cellular automata are CA whose updating rule is a stochastic one, which means the new entities' states are chosen according to some probability distributions. It is a discrete-time random dynamical system. From the spatial interaction between the entities, despite the simplicity of the updating rules, complex behaviour may emerge like self-organization. As mathematical object, it may be considered in the framework of stochastic processes as an interacting particle system in discrete-time.

See {{cite book|title=Probabilistic Cellular Automata

| first1=R. | last1 =Fernandez

| first2=P.-Y. | last2=Louis

| first3=F. R. |last3=Nardi

|doi =10.1007/978-3-319-65558-1_1

| editor-last1=Louis |editor-first1=P.-Y.

| editor-last2=Nardi |editor-first2=F. R.

|publisher=Springer

|date=2018

|isbn=9783319655581

|chapter=Chapter 1: Overview: PCA Models and Issues | s2cid=64938352 }}

for a more detailed introduction.

PCA as Markov stochastic processes

As discrete-time Markov process, PCA are defined on a product space $E=\prod_{k \in G} S_k$ (cartesian product) where $G$

is a finite or infinite graph, like $\mathbb Z$ and where $S_k$ is a finite space, like for instance

$S_k=\{-1,+1\}$ or $S_k=\{0,1\}$ . The transition probability has a product form

$P(d\sigma | \eta) = \otimes_{k \in G} p_k(d\sigma_k | \eta)$ where

$\eta \in E$ and $p_k(d\sigma_k | \eta)$ is a probability distribution on $S_k$ .

In general some locality is required $p_k(d\sigma_k | \eta)=p_k(d\sigma_k | \eta_{V_k})$ where

$\eta_{V_k}=(\eta_j)_{j\in V_k}$ with ${V_k}$ a finite neighbourhood of k. See [https://tel.archives-ouvertes.fr/tel-00002203v1 P.-Y. Louis PhD] for a more detailed introduction following the probability theory's point of view.

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.{{citation|title=Simulating physics with cellular automata|journal=Physica D|first=G.|last=Vichniac|volume=10|issue=1–2|year=1984|pages=96–115|doi=10.1016/0167-2789(84)90253-7|bibcode = 1984PhyD...10...96V }}.

Some categories of models were studied from a statistical mechanics point of view.

= Cellular Potts model =

There is a strong connection{{cite book|title=Probabilistic Cellular Automata

| first1=Sonja E. M. | last1 =Boas

| first2=Yi| last2=Jiang

| first3=Roeland M. H. |last3=Merks

|first4=Sotiris A. |last4=Prokopiou

|first5=Elisabeth G. |last5=Rens

|doi =10.1007/978-3-319-65558-1_18

| editor-last1=Louis |editor-first1=P.-Y.

| editor-last2=Nardi |editor-first2=F. R.

|publisher=Springer

|date=2018

|isbn=9783319655581

|chapter=Chapter 18: Cellular Potts Model: Applications to Vasculogenesis and Angiogenesis | hdl=1887/69811 }}

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.