Central Limit Theorem for Majority Dynamics: Bribing Three Voters Suffices

The Erdős–Rényi random graph, $G_{n,p}$, is defined as the graph with a vertex set of size $n$ and each potential edge independently included with probability $p$. Given a graph and an intial coloring $R_{0}$ and $B_{0}$, we will let $R_{i}$ (resp. $B_{i}$) denote the set of vertices that are red (resp. blue) after $i$ steps of majority dynamics. The initial coloring $R_{0},B_{0}$ may be fixed or determined randomly, but in either case it will always be independent of the random graph $G_{n,p}$.

Asymptotic notation is understood to mean as the relevant parameter (typically $n$) tends to infinity. We say an event happens with high probability to mean its probability tends to $1$. All logarithms have base $e$. Finally, we use the standard notation $\Phi(t)=(2\pi)^{-1/2}\int_{-\infty}^{t}e^{-x^{2}/2}dx$ to denote the probability that a mean 0, variance 1 Gaussian random variable is at most $t$.

In studying majority dynamics on random graphs, a common approach is as follows. One first tries to control the number of red vertices after one [5, 23, 22] or two [9, 23] steps (hoping that in these initial steps, one color will have managed to establish a substantial lead). After this, one typically argues that with probability tending to 1, if any color ever manages to establish a sufficiently large lead, then this lead is going to increase even if the vertices were adversarially recolored (provided this recoloring preserves the number of vertices of each color).

The second part of this strategy (i.e., showing that with high probability large leads cannot be squandered) often involves some variant of a relatively direct union bound using the fact that the random graph is sufficiently expansive. On the other hand, the first part of this strategy (i.e., controlling the number of vertices of each color after one or two steps) is considerably more nuanced.

Following this general strategy, Benjamini, Chan, O’Donnell, Tamuz, and Tan [5] obtained rough estimates for the mean and variance of $|R_{1}|$ under the assumption that the initial coloring $R_{0},B_{0}$ is assigned uniformly at random with $|R_{0}|\geq|B_{0}|$. Their argument was based on a combination of Fourier analysis and spectral graph techniques, and using their estimates, they were able to prove that if $p\geq C/\sqrt{n}$ and $|R_{0}|\geq|B_{0}|$, then $\mathbb{P}(R_{4}=V)\geq 0.4-o(1)$. Thus, for $p\geq C/\sqrt{n}$, they proved that with probability at least $0.4$, for a randomized initial coloring of $G_{n,p}$, the color that was initially ahead will propagate to include all the vertices of the graph within at most four steps. When $p\geq C/n^{1/3}$, their same estimates on $|R_{1}|$ also prove that with probability at least $0.4$, the same result holds after at most 3 steps.

Analyzing the same setting, Fountoulakis, Kang, and Makai [9] improved on the first of these results by focusing instead on estimating the mean and variance of $|R_{2}|$. Namely, they proved that if $R_{0},B_{0}$ is chosen uniformly at random and $p\geq C/\sqrt{n}$, then with probability tending to 1, the color that was initially ahead will propagate to the entire graph within at most four steps.

For smaller values of $p$, Zehmakan [23] studied the case that the vertices of $G_{n,p}$ are each initially colored blue independently with probability $q$. For $q\leq 1/2-\omega(1/\sqrt{np})$ he proved that when $p\geq(1+\varepsilon)\log(n)/n$, then with high probability, majority dynamics converges to all vertices being red after a bounded number of steps. (For smaller $p$, there will be isolated blue vertices.) Gärtner and Zehmakan [11] also proved a similar result for $d$-regular random graphs. See [5] for several conjectures about how the majority dynamics process evolves for values of $p$ less than $C/\sqrt{n}$ and $|R_{0}|\sim|B_{0}|$.

Finally, in a different direction, Tran and Vu [22] considered the case that the initial coloring is fixed with $|R_{0}|-|B_{0}|\geq 10$. In this setting, they argued that with probability at least $90\%$, the graph $G_{n,1/2}$ will result in all of its vertices being red.

It is worth emphasizing that in the above papers, the key first step has been to analyze the distribution of $|R_{1}|$ or $|R_{2}|$. In fact, essentially all of these previous results have followed from some new estimate on the mean or variance of these random variables. To quote [5], “the main task is to analyze what happens at time 1.” This brings us to our primary result.

This provides an unqualified upper bound that $Var(|R_{1}|)=\mathcal{O}(n)$, and for a wide range of parameters, it also gives a central limit theorem. Crucially, the statement is for a given value of $|R_{0}|$ (which may certainly depend on $n$) as opposed to $|R_{0}|$ being a random variable. Conditioning on $|R_{0}|$ in this way enables us to control all the moments of $|R_{1}|$, whereas otherwise the variance in this quantity would be dominated by the variance of $|R_{0}|$.

Theorem 1 is proven by the method of moments, but to illustrate the main challenge, consider the calculation of the variance of $|R_{1}|$. The difficulty here is that one quickly arrives at this variance as a sum of covariances, but each covariance term is large in absolute value. Bounding this sum by its maximum term gives the incorrect asymptotic growth, and the key idea is therefore devising a way to analyze the large amount of cancellation in these sums. We do this by studying the relevant $p$-biased Fourier coefficients (with random variables viewed as functions of the edges present in $G_{n,p}$).

At this point, it is worth noting that for a wide range of parameters (concretely, for $|R_{0}|=|B_{0}|$ and $p$ constant) the distribution of $|R_{1}|$ converges to a normal, but the distribution of $|R_{2}|$ certainly will not. This is simply because if $|R_{1}|$ is sufficiently far from $n/2$ (e.g., at least $\Omega(\sqrt{n/p})$ away [see Proposition 3]) then this would force $|R_{2}|$ to be very far away from $n/2$. Thus, the mass of the distribution of $|R_{1}|$ is pushed very far away from $n/2$, resulting in a particularly bimodal distribution (having mean $n/2$, variance $\Omega(n^{2})$, but being bounded between $0$ and $n$). The distribution of $|R_{3}|$ would be even more exaggerated, and it would likely be essentially two peaks at $0$ and $n$. For many settings of parameters, we believe the distribution of $|R_{4}|$ would converge to literally two point masses at $0$ and $n$. Thus, we ask the following (with the unproven belief that $|R_{k}|$ is often only interesting for $k\in\{1,2\}$).

Regardless of the above, Theorem 1 is already strong enough to imply most of the known results (including the bounds on $|R_{2}|$ from [9]), but to leverage this we use the following.

For $\delta=0.499$, a result such as the above is not difficult to prove for sufficiently large $\alpha$, and in fact versions of this have also appeared in [5, 22]. But we state the above so as to improve the $\Delta=10$ case of $G_{n,1/2}$ as studied in Tran and Vu. In that setting, the constants involved are frustratingly important, and a proof with $\alpha=0.85$ becomes necessary.

From Theorem 1—and in fact merely from our variance estimate—we readily obtain:

The above gives us sufficient control of $|R_{1}|$ to immediately improve several results of Benjamini, Chan, O’Donnell, Tamuz, and Tan [5], which we summarize below.

A proof of part (a) was the main theorem of [9], but results (b) and (c) are new. Parts (a) and (b) directly generalize Theorems 2 and 3.9 (respectively) of [5], where these events were only proven to hold with probability at least 0.4. That said, essentially the only difference in our proof is that we are able to use Corollary 4, which strengthens a weaker result of their paper (namely Theorem 3.5 of [5]). Part (c) of our result also follows in this same way, and we include it here mostly for completeness.

As a second application, the following improves upon a recent paper of Tran and Vu [22].

Interpreting this in a somewhat playful light, the above result argues that if majority dynamics represents the propagation of opinions in a social network, then one side can obtain a noticeable advantage merely by bribing three extra vertices. This improves on a result of Tran and Vu [22] who argued a similar claim but with an initial lead of at least $10$.

The bottleneck in our argument is our reliance on Proposition 3, for which the value of $\alpha$ surprisingly becomes important. We make no claim that our constant $\alpha$ is especially close to the best possible, and sufficiently improving this constant would immediately prove a version of Theorem 6 for an initial lead of $1$ vertex. However, it is easy to imagine that such incremental refinements might be somewhat unsatisfactory, and we instead propose the following, which gets to the heart of the matter.

This conjecture, if true, would likely require a new approach, and we also believe the following stronger conjecture is true (which, in light of our central limit theorem, would exactly determine the value of $\varepsilon$ in Conjecture 7).

Simulations suggest that both conjectures are true, but we are unable to prove either even when $p$ is constant. One heuristic argument is that after the first step, one side is likely to have a relatively extreme advantage (e.g., in the case of $p$ constant, after one step one side will be winning by $\Omega(\sqrt{n})$). If we were to resample the random graph at this point, then such an advantage would be nearly impossible to squander. We aren’t sure how to make this argument rigorous, but we think a resolution of this either way would be very interesting.

Since $\mathbb{E}[Z]=0$, establishing (1) would immediately prove statement (i) of the theorem. As for statement (ii), suppose $\log(1/\mu)=o(\log(\sigma))$ and $\sigma\to\infty$. By Bernstein’s inequality, we have

Since $\sigma\to\infty$, and $\log(1/\mu)=o(\log(\sigma))$, this would imply $\Delta p\ll\sigma\sqrt{\log(\sigma)}$. Thus, we would need to have $\log(\sigma)=\mathcal{O}(\log(n/\Delta))$. Therefore, $\eqref{moments of Z}$ would imply that for all fixed $k$

And since $\log(1/\mu)=o(\log(\sigma))$ and $\log(1/\mu)=o(\log(n/\Delta))$, these error terms converge to zero for any fixed $k$. Thus, the moments of $Z/\sqrt{4n\mu}$ converge to those of the standard Gaussian, which establishes a central limit theorem by the method of moments.

Finally, we need to argue that if $\Delta p=\mathcal{O}(\sigma)$ and $\sigma\to\infty$, then the hypotheses of (ii) hold. For this, we simply note if $\Delta p=\mathcal{O}(\sigma)$, then $\mu$ is bounded below,¹¹1This is by an immediate application of the usual central limit theorem for the binomial random variables in the definition of $\mu$. and $\log(1/\mu)=\mathcal{O}(1)$.

Our proof of (1) is via standard techniques of ($p$-biased) Fourier analysis. We first give a brief review and relevant set up, but for more, we refer the reader to O’Donnell’s helpful text [18].

Let $\mathcal{E}={{V\choose 2}}$ and consider the space of functions mapping from $\{-1,1\}^{\mathcal{E}}\to\mathbb{R}$. Each input string is indexed by the $2$-element subsets of $V$, and each $\vec{x}\in\{-1,1\}^{\mathcal{E}}$ corresponds to a graph whose edge set is $\{e\ :\ x_{e}=1\}$. Consider the product measure on $\{-1,1\}^{\mathcal{E}}$ where each bit is independently equal to $1$ with probability $p$. With this, we identify random variables depending on $G\sim G_{|V|,p}$ and functions $f:\{-1,1\}^{\mathcal{E}}\to\mathbb{R}$ in the obvious way.

For each $S\subseteq\mathcal{E}$, we define the function $\Phi_{S}:\{-1,1\}^{\mathcal{E}}\to\mathbb{R}$ via

with $\Phi_{\emptyset}=1$. Then it can be checked that for all $S,T$ we have

These $\Phi_{S}$ therefore form an orthogonal basis for this space (with inner product $\langle f,g\rangle=\mathbb{E}[fg]$), and each $f$ can uniquely be written as

We will need the following Lemma, which we prove in an Appendix.

Let’s prove the moment estimate assuming Lemma 10.