Majority dynamics on trees and the dynamic cavity method

Abstract

A voter sits on each vertex of an infinite tree of degree $k$, and has to decide between two alternative opinions. At each time step, each voter switches to the opinion of the majority of her neighbors. We analyze this majority process when opinions are initialized to independent and identically distributed random variables. In particular, we bound the threshold value of the initial bias such that the process converges to consensus. In order to prove an upper bound, we characterize the process of a single node in the large $k$-limit. This approach is inspired by the theory of mean field spin-glass and can potentially be generalized to a wider class of models. We also derive a lower bound that is nontrivial for small, odd values of $k$.

Published in at http://dx.doi.org/10.1214/10-AAP729 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Cavity method for quantum spin glasses on the Bethe lattice
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph

Cited by in corpus (24)

• Inferring the origin of an epidemic with a dynamic message-passing algorithm
• Dynamic message-passing equations for models with unidirectional dynamics
• Large deviations of cascade processes on graphs
• Dynamic mean-field and cavity methods for diluted Ising systems
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• Majority Dynamics and the Retention of Information
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• Variational approximations for stationary states of Ising-like models
• Causal analysis, Correlation-Response and Dynamic cavity
• Competition, Collaboration, and Optimization in Multiple Interacting Spreading Processes
• A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
• A theory of non-equilibrium local search on random satisfaction problems
• Communication cost of consensus for nodes with limited memory
• Self-organized Segregation on the Grid
• Dynamical Phase Transitions in Graph Cellular Automata
• Cluster approximations for the TASEP: stationary state and dynamical transition
• Backtracking Dynamical Cavity Method
• The matrix product approximation for the dynamic cavity method
• Nonequilibrium dynamics of the Ising model on heterogeneous networks with an arbitrary distribution of threshold noise
• Small-Coupling Dynamic Cavity: a Bayesian mean-field framework for epidemic inference
• Phase Transitions in Biased Opinion Dynamics with 2-choices Rule
• Majority dynamics with one nonconformist
• Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm