Search for: All records

The global steady state of a system in thermal equilibrium exponentially favors configurations with lesser energy. This principle is a powerful explanation of self-organization because energy is a local property of configurations. For nonequilibrium systems, there is no such property for which an analogous principle holds, hence no common explanation of the diverse forms of self-organization they exhibit. However, a flurry of recent empirical results has shown that a local property of configurations called “rattling” predicts the steady states of some nonequilibrium systems, leading to claims of a far-reaching principle of nonequilibrium self-organization. But for which nonequilibrium systems is rattling accurate, and why? We develop a theory of rattling in terms of Markov processes that gives simple and precise answers to these key questions. Our results show that rattling predicts a broader class of nonequilibrium steady states than has been claimed and for different reasons than have been suggested. Its predictions hold to an extent determined by the relative variance of, and correlation between, the local and global “parts” of a steady state. We show how these quantities characterize the local-global relationships of various random walks on random graphs, spin-glass dynamics, and models of animal collective behavior. Surprisingly, we find that the core idea of rattling is so general as to apply to equilibrium and nonequilibrium systems alike. 

Local interactions of uncoordinated individuals produce the collective behaviors of many biological systems, inspiring much of the current research in programmable matter. A striking example is the spontaneous assembly of fire ants into "bridges" comprising their own bodies to traverse obstacles and reach sources of food. Experiments and simulations suggest that, remarkably, these ants always form one bridge - instead of multiple, competing bridges - despite a lack of central coordination. We argue that the reliable formation of a single bridge does not require sophistication on behalf of the individuals by provably reproducing this behavior in a self-organizing particle system. We show that the formation of a single bridge by the particles is a statistical inevitability of their preferences to move in a particular direction, such as toward a food source, and their preference for more neighbors. Two parameters, η and β, reflect the strengths of these preferences and determine the Gibbs stationary measure of the corresponding particle system’s Markov chain dynamics. We show that a single bridge almost certainly forms when η and β are sufficiently large. Our proof introduces an auxiliary Markov chain, called an "occupancy chain," that captures only the significant, global changes to the system. Through the occupancy chain, we abstract away information about the motion of individual particles, but we gain a more direct means of analyzing their collective behavior. Such abstractions provide a promising new direction for understanding many other systems of programmable matter. 

Local interactions of uncoordinated individuals produce the collective behaviors of many biological systems, inspiring much of the current research in programmable matter. A striking example is the spontaneous assembly of fire ants into "bridges" comprising their own bodies to traverse obstacles and reach sources of food. Experiments and simulations suggest that, remarkably, these ants always form one bridge - instead of multiple, competing bridges - despite a lack of central coordination. We argue that the reliable formation of a single bridge does not require sophistication on behalf of the individuals by provably reproducing this behavior in a self-organizing particle system. We show that the formation of a single bridge by the particles is a statistical inevitability of their preferences to move in a particular direction, such as toward a food source, and their preference for more neighbors. Two parameters, η and β, reflect the strengths of these preferences and determine the Gibbs stationary measure of the corresponding particle system’s Markov chain dynamics. We show that a single bridge almost certainly forms when η and β are sufficiently large. Our proof introduces an auxiliary Markov chain, called an "occupancy chain," that captures only the significant, global changes to the system. Through the occupancy chain, we abstract away information about the motion of individual particles, but we gain a more direct means of analyzing their collective behavior. Such abstractions provide a promising new direction for understanding many other systems of programmable matter.