Density classification on infinite lattices and trees (Q388922)

A configuration on a finite or countably infinite group \(G\) of cells associates independent Bernoulli random variables with each cell. The density classification problem is to decide whether zeros or ones dominate by designing a dynamical process on the configuration space so that it converges weakly to the configuration with all its digits equal to the initially dominating digit. Two kinds of dynamical processes are considered: a probabilistic cellular automaton with discrete time, and a continuous time process for interacting particle systems. Various conjectures and results from the literature are briefly surveyed. The aim of the paper is to consider the density classification problem for infinite regular trees and for infinite integer lattices of dimension \(d\). Complications for \(d=1\) are noted and solutions are proposed that are backed up by simulation results.