Models of complex systems built from simple, locally interacting components arise in many fields, including statistical physics, biology, artificial intelligence, communication networks, etc. The quest to understand and to quantify the fundamental limits on the ability of such systems to store and process information has led to a variety of interesting and insightful results that draw upon probability, combinatorics, information theory, discrete and continuous dynamical systems, etc. In this post, I would like to focus on a model of distributed storage that was analyzed in 1975 by Donald Dawson in a very nice paper, which deserves to be more widely known.
The system Dawson analyzed is an instance of a Probabilistic Cellular Automaton (PCA), i.e., a system consisting of a discrete collection of nodes, each of which has a discrete state. The configuration of the automaton at each time is specified by listing the state of each node. The state of each node at time is determined stochastically by its own state, as well as by the states of its neighbors, at time , independently of everything else. One of the key questions in the theory of PCAs is whether a given automaton is ergodic, i.e., if its configuration eventually “forgets” the initial condition. Thus, Dawson’s result is a sufficient condition for ergodicity of a PCA.
Now let’s move on to precise definitions. Consider an undirected graph . The neighborhood of a vertex , denoted by , is the set of all vertices that are connected to by an edge. We will also denote the set consisting of and all of its neighbors by . Let us fix a finite alphabet ; for each vertex , let denote a copy of . A configuration is an assignment of a symbol to each vertex . Thus, is the space of all configurations. We will denote a generic configuration by ; for any set , we will denote by the natural projection of onto : .
Now let’s consider the following model of a distributed one-bit memory cell. Let be a random variable, which is the bit we wish to store. We also pick two probability measures and on . Given , we draw the initial configuration at random according to . We allow arbitrary correlations between the different ‘s, so our storage is distributed in this sense. Now let’s suppose that the state of each vertex evolves stochastically in discrete time according to a local Markov model: for each , we have a channel (random transformation) with input alphabet and output alphabet . Then the configuration at time evolves according to the law
with the initial conditions ,