Central limit theorem for majority dynamics: Bribing three voters suffices

Ross Berkowitz and Pat Devlin

Stochastic Processes and their Applications, 2022, vol. 146, issue C, 187-206

Abstract: Given a graph G and some initial labeling σ:V(G)→{Red,Blue} of its vertices, the majority dynamics model is the deterministic process where at each stage, every vertex simultaneously replaces its label with the majority label among its neighbors (remaining unchanged in the case of a tie). We prove—for a wide range of parameters—that if an initial assignment is fixed and we independently sample an Erdős–Rényi random graph, Gn,p, then after one step of majority dynamics, the number of vertices of each label follows a central limit law. As a corollary, we provide a strengthening of a theorem of Benjamini, Chan, O’Donnell, Tamuz, and Tan about the number of steps required for the process to reach unanimity when the initial assignment is also chosen randomly.

Keywords: Majority dynamics; Random graph; Central limit theorem; Fourier analysis (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414922000102
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:146:y:2022:i:c:p:187-206

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2022.01.010

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().