New interface

# Probabilistic initial value problem for cellular automaton rule 172

Abstract : We present a method of solving of the probabilistic initial value problem for cellular automata (CA) using CA rule 172 as an example. For a disordered initial condition on an infinite lattice, we derive exact expressions for the density of ones at arbitrary time step. In order to do this, we analyze topological structure of preimage trees of finite strings of length 3. Level sets of these trees can be enumerated directly using classical combinatorial methods, yielding expressions for the number of $n$-step preimages of all strings of length 3, and, subsequently, probabilities of occurrence of these strings in a configuration obtained from the initial one after $n$ iterations of rule 172. The density of ones can be expressed in terms of Fibonacci numbers, while expressions for probabilities of other strings involve Lucas numbers. Applicability of this method to other CA rules is briefly discussed.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [13 references]

https://hal.inria.fr/hal-01185497
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 2:16:49 PM
Last modification on : Tuesday, March 7, 2017 - 3:06:51 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:20:59 AM

### File

dmAL0103.pdf
Publisher files allowed on an open archive

### Citation

Henryk Fuks. Probabilistic initial value problem for cellular automaton rule 172. Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010, Nancy, France. pp.29-40, ⟨10.46298/dmtcs.2761⟩. ⟨hal-01185497⟩

Record views