@article{EJP2325,
author = {Ana Bušić and Nazim Fatès and Jean Mairesse and Irène Marcovici},
title = {Density classification on infinite lattices and trees},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {18},
year = {2013},
keywords = {Cellular automata, interacting particle systems, density classification.},
abstract = {Consider an infinite graph with nodes initially labeled by independent Bernoullirandom variables of parameter p. We address the density classification problem, that is, we want to design a (probabilistic or deterministic)cellular automaton or a finite-range interacting particle system that evolves on this graph and decides whether p is smaller or larger than 1/2. Precisely, the trajectories should converge to the uniform configuration with only 0's if p<1/2, and only 1's if p>1/2. We present solutions to the problem on the regular grids of dimension d, for any d>1, and on the regular infinite trees. For the bi-infinite line, we propose some candidates that weback up with numerical simulations.
},
pages = {no. 51, 1-22},
issn = {1083-6489},
doi = {10.1214/EJP.v18-2325},
url = {http://ejp.ejpecp.org/article/view/2325}}