Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics

Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics Francesco d’Amore · Gran Sasso Science Institute, Italy Joel Rybicki · Humboldt-Universität zu Berlin, Germany Nobutaka Shimizu · Institute of Science Tokyo, Japan

arXiv:2610.40562v1 [cs.DC] 29 Oct 2026

Takeharu Shiraga · Chuo University, Japan Robin Vacus · Sorbonne Université, CNRS, LIP6, France

Abstract. How does the number of sampled opinions affect the time required to reach consensus in distributed consensus dynamics? We study the synchronous h-Majority, in which every node independently samples h nodes uniformly at random with replacement in each round and adopts a most frequent sampled opinion, breaking ties uniformly at random. We show that h-Majority achieves the nearly-optimal trade-off between the sample size and the consensus time, among a broad class of consensus dynamics. In particular, we prove the following results. • For every sample size h ≥ 3 and for every initial we prove that the process  configuration, n √ o n 1 e reaches consensus with high probability within O 1 + min min{h2 pmax ,1} , h rounds, where n is the number of nodes and pmax is the largest initial fraction of nodes supporting any single opinion. This is the first bound on the consensus time for h-Majority that holds for every h ≥ 3 and every initial configuration. • When the initially most popular opinion has a sufficiently large lead over every other opinion, we show that all nodes adopt this opinion with high probability within O(log n/ min{h2 pmax , 1}) rounds. • We establish a matching lower bound up to polylogarithmic factors for any fixed update rule that treats all opinions symmetrically and that selects either a sampled opinion or the node’s current opinion.

Contents 1 Introduction 1.1 Prior work on h-Majority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 2

2 Notation and definitions

4

3 Proof overview 5 3.1 The three phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.2 The main obstacles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.3 Bounding the expected one-round growth of opinions (??) . . . . . . . . . . . . . . . 7 3.4 Preparation via coupling with Voter (Section 5.2) . . . . . . . . . . . . . . . . . . . . 9 3.5 Symmetry breaking via potential (Section 7) . . . . . . . . . . . . . . . . . . . . . . 9 3.6 Plurality consensus: amplification and the final phase (Section 6) . . . . . . . . . . . 10 3.7 The lower bound (Section 8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.8 Outline of the paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Further related work

13

5 Expected one-round growth 14 5.1 Gap between 1 and i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.2 Majorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6 Plurality consensus 6.1 Proof outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Amplification phases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Final phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Proof of Theorem 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29 30 30 39 40

7 Symmetry breaking 7.1 Proof outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Proof of the potential contraction (Lemma 7.4) . . . . . . . . . . . . . . . . . . . . . 7.3 Maximum proportion and weak opinions (Lemmas 7.3 and 7.5) . . . . . . . . . . . . 7.4 Emergence of the unique strong opinion (Proof of Lemma 7.2) . . . . . . . . . . . . . 7.5 Proof of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40 41 42 48 51 52

8 Lower bound on neutral h-input dynamics 53 8.1 Dynamics and statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 8.2 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 A Tools

65

1

Introduction

Understanding the computational power of simple local decision rules is key to designing lightweight distributed algorithms and analyzing models of collective behavior [HP01, BCN20]. Consensus dynamics, in which nodes repeatedly update their opinions based on local observations until reaching agreement, provide a basic yet fundamental setting for studying this power. Such dynamics are attractive in their simplicity: nodes typically retain no state between rounds other than their current opinion, but they can still often reach consensus remarkably fast [HP01, GL18, SS25, DGMSS11, BCNPST17, DAr26, BCNPT16, BCEKMN17, CMRSS25, dDGN25, dDGGN26, CGGNPS18]. In this setting, the natural computational resource is the amount of information nodes receive about the current state of the system: the more information nodes have, the faster consensus can be reached. However, for many dynamics, it is still poorly understood how much additional information can speed up the consensus time. Motivated by this, we address the general question about the trade-off between the total amount of information exchanged and the time to reach consensus: How much can additional information per update reduce the time to reach consensus? Our setting. To investigate this question, we consider the synchronous PULL(h) communication model [BKN19] on a fully connected network of n nodes. In each round, every node in parallel (i) samples h nodes chosen independently and uniformly at random with replacement, and (ii) chooses their new opinion by applying a (randomized) rule to the sample obtained (plus, possibly, the node’s current opinion). We further restrict attention to neutral rules that treat all opinion labels symmetrically, that is, there is no prior agreement on a total order (e.g., preferences) on the opinions. So far, prior work has largely focused on analyzing the consensus time of specific dynamics, often under restrictions on the initial opinion configuration, such as the total number k of initially present opinions or assuming that exactly one opinion is substantially more popular than others, or making specific assumptions about the sample size h [BCNPST17, BCNPT16, BCEKMN17, GL18, SS24, dDGN25, SS25, DAr26, CMRSS25, dDGGN26, BCNPS15, AABBHKL23, BBBEHKK22, CMRSS26, BCPTVZ24]. In contrast, we impose no such restrictions on the initial configuration, the number k of initial opinions, or the sample size h. Our results in a nutshell. As our main result, we prove a new upper bound on the consensus time of the widely studied h-Majority [BCNPST17, BCNPT16, BCEKMN17, GL18, SS25, DAr26, dDGN25]. In these dynamics, each node chooses its new opinion by adopting the most frequent opinion in the sample it obtained, breaking ties uniformly at random. We prove a new upper bound for any sample size h ≥ 3 and any number k ≥ 2 of initial opinions that holds for every initial configuration. In addition, we establish a general lower bound that holds for every dynamics in a large class of neutral dynamics. This lower bound matches our upper bound up to polylogarithmic factors, and gives new lower bounds for other previously studied consensus dynamics [BCPTVZ24, dDGGN26]. Both the upper and lower bounds hold with high probability.

1.1

Prior work on h-Majority

Despite its simple definition, analyzing the behavior of h-Majority is often highly non-trivial. In the special case when h ∈ {1, 2}, h-Majority has the same transition probabilities as Voter, in which

1

each node samples a single node uniformly at random and adopts its opinion.1 The expected consensus time of Voter is O(n) from any initial configuration, and can be Θ(n) on worst-case configurations [HP01, CEOR13]. The case h = 3 has been studied extensively, including under asynchronous updates or communication noise [BCNPST17, BCNPT16, BCEKMN17, GL18, CMRSS25, SS25, DAr26, dZ25]. Yet, even for the basic setting of synchronous updates, nearly optimal bounds on the consensus time for an arbitrary number k ≥ 2 of initial opinions were obtained only very recently in 2025 by Shimizu and Shiraga [SS25], followed by a tight characterization in terms of the maximum initial opinion density by D’Archivio [DAr26]. For h ≥ 4, prior work only provides a complete picture for the case of binary opinions (k = 2). In particular, consensus is reached in at most O(log n/ log h) rounds for odd h = o(n/ log n) [SS24]. Moreover, Berenbrink, Coja-Oghlan, Gebhard, Hahn-Klimroth, Kaaser, and Rau [BCGHKR23] showed that the consensus time of h-Majority for any h ≥ 1 stochastically dominates that of (h + 1)Majority, extending the result from [SS24] to even values of h as well. In contrast, much less is known when many opinions are involved (k ≥ 3), particularly when the number h of samples is super-constant. For any constant ε > 0, if k/h = O(n1/4−ε ), then consensus time is at least Ω(k/h2 ) rounds [BCNPST17]. For the case h = Ω(k log n), d’Amore, D’Archivio, Giakkoupis, and Natale [dDGN25] showed that when the initial gap between the two most popular opinions is sufficiently large, then plurality consensus is reached in O(log n) rounds. See Table 1 for more details.

1.2

Our results

We now summarize our main contributions. Let 2 ≤ k ≤ n and for i ∈ {1, . . . , k}, let pi be the fraction of nodes that initially hold opinion i. Without loss of generality, we assume p1 ≥ · · · ≥ pk e to hide factors polynomial in log n, and say that an event holds and write pmax = p1 . We use O with high probability if its probability is at least 1 − 1/nc for some constant c > 0. Unless stated otherwise, the sample size is an arbitrary fixed integer h ≥ 3. Table 1: Prior work on consensus-time bounds for h-Majority. h

Consensus time

Arbitrary 1 O((n/ log n)1/3 ) 3 O((n/ log n)1/4 ) 3 O(hn1/4−ε ) ≥4 O(n1/3−ε ) 3

k

Θ(n) (expected) O(k log n)∗ Ω(k log n)∗ Ω(k/h2 ) e 3) O(k e O(n3/4 )

Arbitrary √ O(n1/3 / log n)

3 3

Arbitrary

3

O(k log n) e 2/3 ) O(n

Reference

k

h

[HP01, CEOR13] 2 3 ≤ h = o(n/ log n) (odd) 2 ≥3 [BCNPST17] [BCNPST17] Arbitrary 3 Arbitrary ≥ Ck log n [BCNPST17] [BCNPT16] Arbitrary 3 [BCEKMN17]

Arbitrary

≥3

[GL18]

Arbitrary

≥3

Consensus time

Reference

O(log n/ log h) O(log n) √ e Θ(min{k, n}) O(log n)∗ √ e Θ(min{1/p n 1 , n})o

[SS24] [BCGHKR23] [SS25] [dDGN25] [DAr26]

√

e 1 + min 21 , n Θ h p1 h  ∗ log n O min{h 2 p ,1} 1

Thms. 1.1 and 1.3 Thm. 1.2

[GL18]

Here, ε ∈ (0, 1/4) is any fixed constant and C > 0 is sufficiently large. ∗

Plurality consensus under a sufficiently large initial gap and, where required, sufficiently large plurality support.

1.2.1

A general upper bound for h-Majority

First, we show a new general upper bound for the consensus time of h-Majority: Theorem 1.1 (Consensus time; see also For every initial configuration, h-Majority  n Theorem 7.1). √ o n 1 e reaches consensus within O 1 + min min{h2 pmax ,1} , h rounds with high probability. 1

For h = 2, uniform tie-breaking yields the same transition probabilities as adopting the first sampled opinion, which is exactly the Voter rule.

2

√ The two terms in Theorem 1.1 can be understood as follows. If pmax ≥ 1/(h n) initially, e + two phases which we call “symmetry breaking” and “amplification” yield consensus within O(1 2 1/(h pmax )) rounds. Otherwise, we show that the process reaches a configuration with pmax ≥ √ e + √n/h) rounds. Applying the same bound from this configuration yields 1/(h n) within O(1 e + √n/h) rounds, since 1/(h2 pmax ) ≤ √n/h. Combining the two cases consensus within another O(1 yields the minimum in Theorem 1.1. See Section 3 for more explanations, and Theorem 7.1 for an exact statement taking the logarithmic terms into account. √ e For h = 3, the bound is O(min{1/p max , n}), recovering the recent bound of D’Archivio [DAr26]. √ e Since pmax ≥ 1/k, it also recovers the worst-case bound O(min{k, n}) of Shimizu and Shiraga [SS25]. However, Theorem 1.1 is the first consensus time bound that holds for an arbitrary h ≥ 3, k ≥ 2, and an arbitrary initial configuration. e + If the initial configuration is nearly balanced (i.e.,√ pmax = Θ(1/k)), our bound is O(1 √ 2 min{k/h , n/h}). Theorem 1.1 implies that h = Ω( k) suffices from every initial configuration with at most k opinions, without any assumption on the initial gap. 1.2.2

Fast plurality consensus

We also prove plurality consensus, where all nodes eventually adopt the opinion supported by the largest number of nodes in the initial configuration, provided that there is a large enough gap between the initial plurality opinion and any other opinion. Theorem 1.2 (Plurality consensus). There q exists an absolute constant c > 0 such that, for every

initial configuration satisfying pmax − pi ≥ c min{hp2max · logn n for all i ≥ 2, h-Majority reaches pmax ,1}   n consensus on opinion 1 within O min{hlog rounds with high probability. 2p max ,1} For h = 3, Theorem 1.2 guarantees plurality consensus in O



log n pmax



rounds under a gap of order p log n/n, which matches the bound of D’Archivio [DAr26]. Furthermore, Theorem 1.2 weakens the requirement on h to obtain polylogarithmic-time plurality −1/2 e −1 consensus from h = Ω(p max ) to h = Θ(pmax ) compared to the state-of-the-art [dDGN25]. In particular, when the initial configuration is approximately balanced (pmax ≈ 1/k), the requirement √ e goes from Ω(k) to Θ( k). Finally, this bound on the plurality consensus time matches that of DéjàVu [dDGGN26]; see Section 4 for a more detailed comparison with prior work. 1.2.3

Lower bound for neutral h-input dynamics

Could a different update rule reach consensus faster than h-Majority using the same number of samples? To make the comparison fair, we consider neutral h-input dynamics in the PULL(h) model, which contain h-Majority as a special case. To select an opinion, each node applies the same fixed, possibly randomized rule, which depends only on the h samples and (possibly) its current opinion, and treats all opinion labels symmetrically – see Definition 8.3 for a formal statement. The following theorem gives a nearly matching lower bound for this class. Theorem 1.3 (Lower bound; see n also Theorem 8.4). As  o long as pmax < 1, every neutral h√ n 1 input dynamics requires Ω 1 + min min{h2 pmax ,1} , h√log n rounds to reach consensus with high probability.

3

Theorem 1.3 matches Theorem 1.1 up to logarithmic factors, establishing the near-optimality of h-Majority within the class of neutral h-input dynamics. The lower bound from Theorem 1.3 shows √ that the two time scales 1/ min{h2 pmax , 1} and n/h cannot be substantially improved by choosing a different neutral update rule. 
e h + min k , √n Since pmax ≥ 1/k, Theorem 1.1 implies that h-Majority takes a total of O h samples√per node until consensus, from every initial configuration with at most k opinions. Choosing √ e h = Θ( k) yields polylogarithmic-time consensus using O( k) samples per node. Conversely, when √ e k) pmax = Θ(1/k), Theorem 1.3 implies that every neutral h-input rule requires a total of Ω( samples per node until consensus, for every sample size h ≥ 1 fixed throughout the execution, since k ≤ n. Thus, this choice of h minimizes the worst-case total number of samples per node within this class, up to logarithmic factors.

2

Notation and definitions

In this section, we introduce notations that will be used throughout the paper. For a positive integer m, we write [m] = {1, . . . , m}. Multinomial distribution.

For x ∈ Zk≥0 with |x| = r, the multinomial coefficient is     r r r! = . = x1 ! · · · xk ! x x1 , . . . , x k

The count vector X of h independent samples from the probability vector p has the multinomial distribution with parameters (h, p), denoted by X ∼ Multinomial(h; p). For every x ∈ Zk≥0 with |x| = h, its probability mass function is Pr[X = x] =

 Y k h pxi i . x

(1)

i=1

h-Majority. h-Majority is formally defined as follows. For a fixed positive integer h and an initial configuration C(0) ∈ [k]n , h-Majority is a sequence of random variables (C(t))t=0,1,... , where C(t) = (Cv (t))v∈[n] ∈ [k]n . Given C(t) ∈ [k]n , the next configuration C(t + 1) is sampled according to the following rule: 1. Let p(t) = (pi (t))i∈[k] be the probability vector defined by pi (t) = |{v∈[n]:Cnv (t)=i}| . (u)

(u)

2. Independently for every node u ∈ [n], sample X(u) = (X1 , . . . , Xk ) ∼ Multinomial(h; p(t)). Then set Cu (t + 1) = Maj(X(u) ), where Maj(X(u) ) is an index attaining the largest coordinate of X(u) , chosen uniformly in case of a tie. All sampling and tie-breaking use fresh randomness, independent across nodes and rounds, and all nodes update simultaneously. We write Ft to denote the filtration generated by (C(s))s≤t , and use shorthand notation Prt [·], Et [·], and Vart [·] for Pr[· | Ft ], E[· | Ft ], and Var[· | Ft ], respectively, unless otherwise specified. Note that both the processes p(t) and C(t) are Markov chains. Finally, we define q(t) = Et [p(t + 1)], the one-round expected evolution of p(t).

4

3

Proof overview

A common strategy in the analysis of consensus dynamics is to break symmetry and then amplify the resulting advantage until consensus [GL18, CMRSS25, SS25, CMRSS26]. We follow this strategy in three phases, with all guarantees below holding with high probability. In each case, round 0 denotes the start of that phase. Let pmax (t) denote the density of the plurality opinion at time t.

3.1

The three phases

Phase I: Voter. In this phase, we start from an arbitrary initial configuration; however, the phase is only relevant in cases where pmax is very small. To show that pmax grows, we exploit the fact that many vanish. We couple h-Majority with Voter (i.e., 1-Majority) to show that  opinions  T pmax (T ) = Ω n log n for every fixed integer 1 ≤ T ≤ n log n. Consequently, the maximum density reaches   log n (log n)2 √ , pmax (t) ≥ c max (2) n h n  n o √ n)2 within O max (log n)3 , n(log rounds, for a sufficiently large constant c > 0; see Section 3.4. h Ignoring logarithmic factors, the coupling gives pmax (T ) = Ω(T /n), while the condition for exiting √ e √n/h) in this phase pmax (T ) = Ω(1/(h n)). Equating these two scales gives the time scale T = O( Theorem 1.1. Phase II: Symmetry breaking. After reaching the density threshold of Eq. (2), this phase deals with configurations where the gap between the most popular opinion, relabeled as opinion 1, and other opinions is not large enough. We exploit the sampling variance, which creates separations between tied or nearly tied opinions, and the positive expected multiplicative drift, which amplifies the separations that emerge. We propose a potential argument that captures these two effects in a single estimate. At the end of the phase, the most popular opinion has a constant relative gap: pi (t) ≤ 34 pmax (t) for every i which is not the In particular, this is enough for  plurality opinion.  ensuring plurality consensus. This takes O

log n min{h2 pmax (0),1}

Phase III: Amplification to consensus. as opinion 1, satisfies s

This phase starts when the plurality opinion, relabeled

p1 (0) − pi (0) ≥ c

p1 (0) log n · 2 min{h p1 (0), 1} n

rounds; see Section 3.5.

for every i ̸= 1

for a sufficiently large constant c > 0. The output of Phase II satisfies this condition because its constant relative gap is combined with the density lower bound in (2). Under this condition, the positive expected multiplicative drift amplifies the existing gaps between the most popular opinion and other competing opinions, while  concentration arguments control the variance. This yields n consensus (p1 (t) = 1) in at most O min{h2log additional rounds; see Section 3.6. pmax (0),1} Phase I can be skipped if the initial maximum density already satisfies (2). Under the assumption on the initial-gap in Theorem 1.2, we can start directly with amplification and obtainplurality  n 2 consensus. Intuition for the term min{h pmax (0), 1} in the time scale O min{h2log is given pmax (0),1} later in Section 3.3.

5

3.2

The main obstacles

The rest of this section describes the main obstacles, explains the technical ideas used to overcome them, and then outlines the main steps of the proofs. Obstacle 1: One-round expected evolution. A natural approach is to extend the recent analyses of 3-Majority by Shimizu and Shiraga [SS25] and D’Archivio [DAr26] to h-Majority. However, these analyses rely P on a simple exact formula for the one-round expected evolution q, namely qi = pi (1 + pi − j p2j ). For general h-Majority, a direct expression for qi involves summing over multinomial sample-count vectors and accounting for all possible ties for the maximum. Deriving useful estimates from this expression is difficult, as also noted by d’Amore, D’Archivio, Giakkoupis, and Natale [dDGN25, Section 3]. A key technique in prior work on 3-Majority is to track the gap between two opinion densities and establish conditions under which it grows in expectation [BCNPST17, GL18, CMRSS25, SS25, DAr26]. For a gap pi − pj , its drift is the expected one-round change (qi − qj ) − (pi − pj ) conditional on the current configuration; positive drift means that the gap increases in expectation. Our first main contribution is the following expected relative drift lemma, which bounds the amplification of the relative gap p1 /pi − 1. Lemma 3.1 (Expected relative drift). Fix a probability vector p with p1 = maxj pj , and let qi be the probability that a node adopts opinion i when applying the h-Majority rule to h independent samples from p. For every h ≥ 3 and i ̸= 1 with pi > 0,    q1 p1 1 2 min{h p1 , 1} . −1≥ −1 1+ qi pi 80 Thus, the relative advantage of the current largest opinion grows at rate min{h2 p1 , 1} in the expected update. The form of this bound is similar to that obtained in the recently-defined DéjàVu dynamics [dDGGN26], though its proof is of different nature (see Section 4 for details about DéjàVu and its analysis, which relies on Poisson races). We outline the proof of this lemma in Section 3.3. Obstacle 2: Symmetry breaking. When p1 = pi , symmetry gives q1 = qi , and the tie is preserved in expectation: a multiplicative estimate such as Lemma 3.1 does not explain how a gap is created. The existing plurality-consensus analyses of h-Majority [dDGN25] and DéjàVu [dDGGN26] start from a sufficiently large initial gap and establish its amplification, leaving symmetry breaking from an initially tied configuration untreated. For 3-Majority, conditional on C(t), the gap pi (t + 1) − pj (t + 1) between two fixed opinions i and j is a sum of independent node contributions. This lets us apply variance and anti-concentration estimates, which show that, with constant probability, the gap is of the order of its standard deviation, even when its conditional expectation is zero. For h-Majority, this gap still admits a representation as a sum of independent contributions, but it need not grow in expectation. For example, when h is large and there is a unique largest opinion, two non-leading opinions may both vanish, so their gap shrinks to zero. We therefore track amplification through the gap pmax (t) − pj (t) between a competitor and the current largest opinion, as in Lemma 3.1. However, this quantity in round t + 1 can no longer be written as a sum of independent random variables, even when conditioning on C(t), because the majority opinion in round t + 1 may differ from that in round t. Thus, controlling the expected evolution as in Lemma 3.1 does not suffice to extend the symmetry-breaking arguments for 3-Majority to h-Majority. Despite these obstacles, we establish the following symmetry-breaking guarantee. 6

Lemma 3.2 (Symmetry breaking, informal). Suppose that the initial configuration satisfies  2 √n pmax (0) ≥ c max (lognn) , log for a sufficiently large constant c > 0 (but we do not assume h n
any gap). For some T = O log n/ min{h2 pmax (0), 1} , with high probability there is a unique opinion i such that 3 pj (T ) < · pi (T ) for every j ̸= i. 4 The typical strategy for proving such a result is to analyze the creation of the gap and then its amplification in two separate stages. It was first used by Doerr, Goldberg, Minder, Sauerwald, and Scheideler [DGMSS11] and appears in later work on 3-Majority and 2-Choices [GL18, CMRSS25, SS25], as well as on UndecidedState [AABBHKL23, CMRSS26]. In contrast, our proof uses a simple potential argument that captures both phenomena simultaneously. This technique, the second main contribution of this paper, may therefore substantially simplify symmetry-breaking proofs across several consensus dynamics. We outline the argument in Section 3.5. Recall that the Phase I (the “Voter” phase) establishes the density condition (2). Together with this density condition, the lower bound makes the resulting gap large enough to start plurality amplification: s pmax (T ) log n pmax (T ) ≥ c′ · for every j ̸= i, pi (T ) − pj (T ) ≥ 2 4 min{h pmax (T ), 1} n where c′ > 0 is the constant required for plurality amplification in Section 3.6. We can therefore relabel opinion i as opinion 1 and restart the analysis at round T . Plurality amplification followed by the final phase then yields consensus; see Section 3.6.

3.3

Bounding the expected one-round growth of opinions (??)

Fix a round t and write p = p(t) and q = q(t). Relabel opinions so that p1 = maxj pj . Let X = (X1 , . . . , Xk ) be the count vector of h independent samples from p, where Xj is the number of occurrences of opinion j. Write Maj(X) for an opinion chosen uniformly at random among those with the largest count, and define Wi = {Maj(X) = i}, so that qi = Pr[Wi ]. Fix an opinion i = ̸ 1 with pi > 0. We compare Pr[W1 ] with Pr[Wi ] directly, without separately estimating either term. Lemma 3.1 gives    Pr[W1 ] p1 1 2 ≥1+ −1 1+ min{h p1 , 1} . (3) Pr[Wi ] pi 80 This controls the relative advantage of the current largest opinion over each competitor; Section 3.6 explains how to turn it into a multi-round analysis. The term min{h2 p1 , 1} is associated with collisions in the sample. Indeed, by a union bound,       k  h X 
h 2 Pr[the sample has a collision] ≤ min 1, pj ≤ min 1, p1 = O min{h2 p1 , 1} .   2 2 j=1

To understand why this term shows up in the bound, we need to connect h-Majority with Voter. Generate h samples and let the voter update copy a uniformly random position in the sample; this is equivalent to sampling one uniformly random node from the graph. If the h sampled opinions are all distinct, then h-Majority uniformly breaks the tie and hence has exactly the same update rule. Thus, under this coupling, h-Majority can differ from the voter update only when the sample contains a collision. Such collisions are therefore responsible for the amplification of relative gaps. 7

Probability transport arguments. If pi = p1 , the inequality is trivially true. If pi = 0, opinion i has zero probability of winning and there is nothing to prove. For the rest of this subsection, assume 0 < pi < p1 . For j ∈ {1, i} and any sample-count vector x with nonnegative integer entries summing to h, define µj (x) = Pr[Wj , X = x], the probability that Popinion j wins the majority rule k and the sampled configuration is x. Let X = {x ∈ {0, . . . , h} : j xj = h}. We define a bijection over X as follows: x 7→ x1↔i , where x1↔i is obtained by exchanging the entries of x1 and xi . We prove that µi (x) and µ1 (x1↔i ) are related through the following formula. µ1 (x1↔i ) = µi (x) + (ρ − 1)Ψ(x)µi (x),

(4)

where ρ = p1 /pi and Ψ(x) = (ρxi −x1 − 1)/(ρ − 1). To see this, consider a configuration x that contributes to Pr[Wi ], that is, where xi is maximum (possibly, with ties). The map x 7→ x1↔i restricted to such configurations is also a bijection between configurations that contribute to Pr[Wi ] and those that contribute to Pr[W1 ]. While moving from x (for Pr[Wi ]) to x1↔i (for Pr[W1 ]), the tie-winning probabilities are the same, while the sample probability gets multiplied by ρxi −x1 . xi −x1 µ (x), and µ (x1↔i ) − µ (x) = (ρxi −x1 − 1)µ (x), proving Eq. (4). Hence, µ1 (x1↔i i 1 i i P) = ρ Let S = x∈X Ψ(x)µi (x). Since x 7→ x1↔i is a bijection in X , we can express the difference Pr[W1 ] − Pr[Wi ] as a function of S and ρ as follows: X X Pr[W1 ] = µ1 (x1↔i ) = µi (x) (1 + (ρ − 1)Ψ(x)) = Pr[Wi ] + (ρ − 1)S. x∈X

x∈X

Proving Eq. (3) reduces to showing that S ≥ Pr[Wi ](1 + min{h2 p1 , 1}/80). Let ε = min{h2 p1 , 1}/80. If Ψ(x) ≥ (1P+ ε) for all configurations where xi is a maximum, then we would immediately get S ≥ (1 + ε) x∈X µi (x) = (1 + ε) Pr[Wi ]. Unfortunately, this is not the case. To give intuition behind the definition of Ψ (and, hence, S), consider a configuration x where opinion i is maximum (possibly, not unique). Now, depending on the entries xi and x1 in x, we have   xi = x1 ; 0, Ψ(x) = 1, xi = x1 + 1;   x −x −1 1 + ρ + . . . + ρ i 1 ≥ 1 + ρ, xi > x1 + 1. Therefore, for some configurations Ψ(x) < 1 + ε, while for other configurations Ψ(x) ≥ 1 + ρ ≥ 1 + ε. In our analysis, we compare the total probability mass (according to µi (x)) of configurations x that have xi > x1 + 1 with that of configurations x that have xi ≤ x1 + 1. We do that via what we call transport lemmas, that is, we compare probabilities of configurations x with µi (x) > 0 with configurations obtained by moving units from x1 to other entries of x, thus with larger values of Ψ(x). We call Ψ(x) the “score” of configuration x. The transport arguments differ according to whether hp1 ≤ 1/4 or hp1 > 1/4. In the smallsample case, at most h opinions appear in any sample, so the absent opinions carry total probability mass at least 1 − hp1 ≥ 3/4. This provides enough destinations to compare configurations with x1 > 0 to configurations with smaller x1 : we move one occurrence of opinion 1 to an absent opinion, keeping xi unchanged. For configurations with µi (x) > 0 and xi ≥ 2, iterating this transport reaches x1 = 0, where the score is at least 1 + ρ. The resulting mass comparisons, together with a separate transport for cases in which we have all distinct samples in a configuration, ensure that this surplus compensates for the tied configurations; see Lemmas 5.4 and 5.5. When hp1 > 1/4, absent opinions might not carry enough probability mass for the same argument to work. We instead move an occurrence of opinion 1 directly to opinion i, increasing xi − x1 by two. This transport relates tied configurations to configurations with surplus score; see Lemmas 5.4 and 5.10. 8

We remark that [dDGN25] also uses a transport argument, which inspired us to look for more general techniques based on probability transport arguments. We highlight the difference between our work and [dDGN25]. There, the authors prove that, if hp1 ≥ C log n, ties do not really matter. Their approach crucially relies on the assumption hp1 ≥ C log n. It is needed that each opinion j such that pj = Θ(p1 ) is sampled roughly Ω(log n) times with high probability in the multinomial sample, and the crucial ingredient is a lemma stating that the probability that opinion 1 wins (possibly with ties occurring) is comparable to the probability that opinion 1 wins without ties. This latter fact is not true for hp1 ≪ log n. Our transport lemmas are of different nature, and we do not employ the same argument here (even for the case hp1 ≥ C log n).

3.4

Preparation via coupling with Voter (Section 5.2)

The preparation phase raises the maximum density from 1/n (in the worst case) to the threshold in (2). We extend the majorization coupling argument for 3-Majority of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn, and Natale [BCEKMN17] to h-Majority for every h ≥ 2. Specifically, we construct a coupling under which p(h) (t) majorizes p(1) (t) almost surely for every t = 0, 1, . . ., provided p(h) (0) = p(1) (0). Here p(r) (t) denotes the vector of opinion densities of r-majority at round t, with r = 1 corresponding to Voter. We refer to Definition 5.13 for the formal definition of majorization. The key consequence is that, at every round t, the number of surviving opinions in (h) h-Majority (i.e., the number of indices i with pi (t) > 0) is at most that  in Voter.  n For every fixed integer 1 ≤ t ≤ n log n, Voter has at most κ(t) = O n log surviving opinions t with high probability [BCEKMN17]. The coupling gives the same upper bound  for h-Majority. Since  (h) 1 t the opinion densities sum to one, on this event pmax (t) ≥ κ(t) = Ω n log n . This yields (2) within the stated preparation time. The same coupling, combined with concentration for the density of an (h) (h) initially largest opinion in Voter, also gives pmax (t) ≥ 12 pmax (0) throughout the symmetry-breaking phase with high probability, provided the initial density satisfies (2). For k = 2, Berenbrink, Coja-Oghlan, Gebhard, Hahn-Klimroth, Kaaser, and Rau [BCGHKR23] constructed a majorization coupling of h-Majority and (h − 1)-Majority throughout their executions from the same initial configuration. This shows that increasing the sample size from h − 1 to h cannot increase the consensus time in the sense of stochastic dominance; they left open whether this conclusion extends to k > 2. Our analysis gives partial progress: for arbitrary k, we obtain a majorization coupling of one-round update of h-Majority and (h − 1)-Majority from the same configuration. Such a coupling can fail for different configurations; see Remark 5.20. Thus, the one-round comparison alone does not establish the corresponding comparison of consensus times.

3.5

Symmetry breaking via potential (Section 7)

We now explain how the potential argument overcomes Obstacle 2, allowing the largest opinion to change throughout the phase. For each opinion j, define the normalized squared gap Gj (t) and the decreasing function Φa by Gj (t) =

(pmax (t) − pj (t))2 1 and Φa (x) = , pmax (t) + pj (t) 1 + ax p

(t)−pj (t) grows, Gj (t) pmax (t)+pj (t)

where a > 0 is a carefully chosen parameter. As the normalized gap √max

increases and the potential Φa (Gj (t)) decreases. Thus, showing that the potential decreases provides a route to proving symmetry breaking. The key estimate is the following contraction in conditional expectation. 9

Lemma 3.3 (Potential contraction; Lemma 7.4). Fix t, an opinion i with pi (t) = pmax (t), and a pmax (t) 1 min{h2 pmax (t), 1}. Set a = nρ , then parameter 0 < ρ ≤ 80 28 . If j ̸= i and pj (t) ≥ 2  ρ  Et [Φa (Gj (t + 1))] ≤ 1 − Φa (Gj (t)). 420 The proof of this contraction combines the expected relative drift bound in Lemma 3.1 with moment estimates for the gap between a currently largest opinion and a fixed competitor. Assuming Lemma 3.3, the main argument is to iterate it and apply Markov’s inequality. Indeed, (t) (t) 6 ≤ 61 , so Φa (Gj (t)) ≥ 6+a pj (t) ≥ pmax implies Gj (t) ≤ pmax . Thus, a potential below this 2 6 (t) threshold already certifies that pj (t) < pmax . The contraction holds even when Gj (t) = 0, so the 2 same argument applies without an initial gap. A fixed opinion may itself become the leader, so we apply the argument to the pair potential Ψij (t) = Φa (max{Gi (t), Gj (t)}) for i ̸= j. It inherits the same contraction while both densities (t) are at least pmax : apply the lemma to an opinion attaining max{Gi (t), Gj (t)}. If both gaps 2 1 are zero, choose i as a largest opinion and apply the bound to j. Fix ρ = 160 min{h2 pmax (0), 1}  pmax (t) pmax (0) nρ and a = 28 . Let τ = inf t ≥ 0 : min{pi (t), pj (t)} ≤ be the first or pmax (t) ≤ 2 2 round when either member has density at most half the current maximum or the maximum is at most half its initial value. and Markov’s inequality, with this stopping rule, give  Iteration   applied  ρT log n a Pr[τ > T ] ≤ (1 + 6 ) exp − 420 . Consequently, for T = O , with high probability there is a ρ (t) round t ≤ T such that min{pi (t), pj (t)} ≤ pmax or pmax (t) ≤ pmax2 (0) ; the latter event is unlikely by 2 the argument in Section 3.4. Therefore, the potential cannot keep contracting while both opinions remain above this threshold. (s) For each opinion j, martingale concentration shows that, with high probability, if pj (s) ≤ pmax 2 at some round s ≤ T , then pj (T ) < 43 pmax (T ). Combining this with the pair-potential bound and taking a union bound over all i = ̸ j gives min{pi (T ), pj (T )} < 34 pmax (T ) for every pair, with high probability. Choosing an opinion i with pi (T ) = pmax (T ) gives pj (T ) < 34 pi (T ) for every j ̸= i, yielding the symmetry-breaking guarantee in Lemma 3.2.

3.6

Plurality consensus: amplification and the final phase (Section 6)

With the multinomial comparison in Lemma 3.1 at hand, we can derive one-round expected growth of the relative gaps and the leading density, provided that opinion 1 is the most frequent opinion at the current round. If the initial gap is large enough, concentration arguments turn these estimates into multi-round high-probability statements. In particular, p1 (t) remains the largest opinion and grows until it has no serious competitor. Write ∆i (t) = p1 (t) − pi (t) and ∆(t) = min q i>1 ∆i (t), keeping the opinion labels fixed throughout this phase. The phase starts with ∆(0) ≥ c

p1 (0) · logn n . Its central guarantee is as follows. min{h2 p1 (0),1}

Lemma 3.4 (One amplification phase). q For a sufficiently large constant c > 0, suppose opinion

p1 (0) · logn n . With probability at least 1 − 1/n2 , at min{h2 p1 (0),1} some round T = O(log(2p1 (0)/∆(0))/ min{h2 p1 (0), 1}), either p1 (T ) ≥ 3/5, or all of the following

1 is initially the largest and ∆(0) ≥ c

hold: p1 (T ) ≥ 2p1 (0), opinion 1 is still the largest, and ( s ) p1 (T ) log n p1 (T ) ∆(T ) ≥ max c · , . min{h2 p1 (T ), 1} n 32 10

The point of the second outcome is that the next phase starts with both a valid gap condition and a constant relative gap. The process is Markovian, so the same argument can be restarted at each successful phase. At most O(log n) phases suffice to reach density 3/5. The first phase costs O(log n/ min{h2 p1 (0), 1}) rounds; in every later phase, the logarithm of the density-to-gap ratio is bounded by a constant. Consequently, their total duration is still O(log n/ min{h2 p1 (0), 1}), rather than incurring an extra logarithmic factor. The concentration argument must track the accumulated noise, rather than demand that every round closely follows its expectation. Following the Freedman-based martingale framework developed by Cooper, Mallmann-Trenn, Radzik, Shimizu, and Shiraga [CMRSS25] and Shimizu and Shiraga [SS25], we expose the new opinions of the nodes one by one within each round. Since Freedman’s inequality applies to martingales, we normalize densities and gaps by the accumulated expected growth. Freedman’s inequality then controls the normalized density and gap martingales up to the relevant stopping times. Lemma 3.5 (Final phase). If p1 (0) ≥ 3/5, then h-Majority reaches consensus on opinion 1 within O(log n) rounds with probability at least 1 − 1/n2 . This final phase follows from the contraction of the total support of the other opinions once opinion 1 has a sufficiently large constant majority. Combining it with the amplification phases proves Theorem 1.2; adding preparation and symmetry breaking proves Theorem 1.1.

3.7

The lower bound (Section 8)

Our lower bound starts from a consequence of neutrality: no opinion can grow too quickly in expectation. Specifically, for every opinion i ∈ [k], we prove that Et [pi (t + 1)] − pi (t) ≤ 2h2 pmax (t)2 .

(5)

To see why, fix the current configuration and write pj = pj (t). As a baseline, consider the voter rule, which simply copies the first sampled opinion and hence selects opinion i with probability pi . When all sampled opinions are distinct, neutrality allows the rule to favor sample positions but not opinion labels, so any systematic advantage over this baseline (i.e., Et [pi (t + 1)] − pi (t)) must come from repetitions. We bound the additional selection probability by separating two cases:
• Opinion i appears at least twice. This event has probability at most h2 p2i , so its contribution is O(h2 p2i ). • Opinion i appears only once. A general neutral rule may prefer opinions that appear only once. Let S be the number of opinions appearing exactly once among the h sampled opinions. By neutrality, these S opinions are interchangeable after averaging over sample positions, so the contribution from such samples is at most the expectation of 1/S over them. To see how this compares with pi , fix the position of the unique i and let S ′ count the opinions appearing exactly once among the other h − 1 sampled opinions. When none of these sampled opinions equals i, we have S = 1 + S ′ . Summing over the h possible positions of i, and dropping the restriction that the other sampled opinions avoid i, bounds this contribution by  
h ′ ′ pi · E ≤ p E[h − S ] = p 1 + E[h − 1 − S ] , i i 1 + S′ where we use h/(1 + s) ≤ h − s for 0 ≤ s ≤ h − 1. Here h − 1 − S ′ counts the sample positions among the other h − 1 sampled opinions occupied by repeated opinions. In expectation, this 11

P 2 number is at most 2 h−1 j pj . Hence, the contribution to the right-hand side of (5) in this 2P 2 2 case is at most O(h pi j pj ). P Combining these two contributions and using pi ≤ pmax (t) and j p2j ≤ pmax (t) bounds the expected increase by O(h2 pmax (t)2 ). Keeping track of the constants gives (5). The drift bound (5) suggests a natural time scale for the maximum density to double. Indeed,
max Et [pi (t + 1)] ≤ pmax (t) 1 + 2h2 pmax (t) . i∈[k]

As long as pmax (t) < 2pmax (0), the multiplicative factor on the right-hand side is at most 1 + 4h2 pmax (0). When h2 pmax (0) is small, growth at this rate would require Ω(1/(h2 pmax (0))) rounds to double the maximum density. This explains the time scale arising from the conditional expected increments. To obtain a lower bound for the actual process, we must also control deviations arising from the variance of the process. Conditional on the current configuration, the support of each opinion is a sum of independent Bernoulli random variables. Together with (5), this gives   Et [pi (t + 1)] pmax (t) Vart [pi (t + 1)] ≤ =O (6) n n when h2 pmax (t) is small. Before the maximum density doubles, the sum of these conditional variances over T := O(1/(h2 pmax (0))) rounds is O(T · pmax (t)/n) = O(1/(h2 n)), corresponding to a √ standard-deviation scale of O(1/(h n)). We use Freedman’s inequality to control the accumulated variance and resulting deviations simultaneously for all opinions. A smaller one-round variance allows the drift-based lower bound to remain effective for smaller initial maximum densities. Thus, neutrality limits growth that comes from collisions to the time scale 1/ min{h2 pmax (0), 1}, while the variance of the process limits how long this argument can be maintained uniformly to the e √n/h). This explains why the lower bound contains the minimum of the same two time scale Ω( scales as the upper bound. Extension to rules that use the node’s current opinion. So far, we have considered dynamics in which nodes always comply with their samples by adopting one of the h sampled opinions. Our argument also extends to dynamics in which nodes may instead ignore the sampled opinions and retain their current opinion, even when it is absent from the sample. For example, 2-Choices ignores its samples when the two sampled opinions disagree, and DéjàVu capped at h samples ignores them when no opinion is sampled twice. This distinction between complying with and ignoring the samples is central to the comparison between 3-Majority and 2-Choices in Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn, and Natale [BCEKMN17]. For our lower bound, the relevant additional condition is that the rule retains the current opinion whenever it and the h sampled opinions are all distinct. Both 2-Choices and DéjàVu capped at h samples satisfy this condition. Such rules have smaller one-round density variance than the general bound in (6), which allows us to obtain a sharper consensus-time lower bound. In particular, for e 2-Choices, we recover the known Ω(1/p max (0)) lower bound of D’Archivio [DAr26]. See Section 8 for the precise variance estimate and lower bound.

3.8

Outline of the paper

We use the notation and definitions introduced in Section 2 throughout the paper. Section 5 analyzes the expected one-round growth of the opinions using an analysis of the multinomial 12

distribution. Section 6 then gives the time bound on plurality consensus. Section 7 analyzes the symmetry-breaking phase. Section 8 gives the time lower bound for uniform h-sampling dynamics.

4

Further related work

3-Majority and 2-Choices. The 3-Majority and 2-Choices are canonical examples of how a few samples can amplify plurality advantages and accelerate consensus without additional states [BCN20]. In 2-Choices, first studied implicitly for two opinions in [DGMSS11], each node adopts the common opinion of two independent uniform samples, retaining its own if they disagree. For two opinions, the analysis of [DGMSS11] gives a O(log n) worst-case consensus time with high probability for both dynamics, compared with Voter’s Θ(n) worst-case expected time [HP01]. 3-Majority with many opinions was first studied in [BCNPST17] and further analyzed in [BCNPT16, BCEKMN17, GL18]. The consensus times of both dynamics were determined up to polylogarithmic factors in the worst case with arbitrary k in [SS25], and for each initial configuration in terms of pmax in [DAr26]. For e every nonconsensus initial configuration, the stronger Ω(1/p max ) lower bound for 2-Choices (while √ e Ω(min{1/pmax , n}) for 3-Majority) holds with high probability. In the asynchronous model, only one node selected uniformly at random in each time step e updates its opinion. For 3-Majority, the worst-case consensus time is Θ(min{nk, n3/2 }) steps with high probability [CMRSS25]. For two opinions, exact formulas for the probability of consensus on each opinion are given for both dynamics in [DANM26, Corollaries 3 and 4]. DéjàVu. In DéjàVu [dDGGN26], each node samples opinions until one appears twice and then adopts the repeated opinion. Interestingly, this setting is equivalent to a Poisson race. Given a configuration with opinion densities p1 ≥ . . . ≥ pk , consider independent Poisson processes (Ni (t))t≥0 , one for each i ∈ [k], where Ni has rate pi . Let Ti = min{t ≥ 0 : Ni (t) = 2}, with the convention that Ti = ∞ if pi = 0. Note that Ti ∼ Gamma(2, pi ) for every i such that pi > 0. The probability that a node selects opinion i in DéjàVu is exactly Pr[Ti = minj∈[k] {Tj }]. This probability can be computed by exploiting properties of Gamma distributions. In its PULL(h) version, sampling is capped at h; if no repetition occurs, the node retains its current opinion. The Poisson race setting is linked to PULL(h) via the generalized birthday paradox: the probability that a collision occurs within h samples is equal to the probability that DéjàVu encounters a repeated opinion within the first h samples. For h ≥ 2, this dynamics reaches plurality consensus within O(log n/ min{h2 pmax , 1}) rounds with high probability, provided that npmax = ω(log n) and p1 − p2 is sufficiently large. To the best of our knowledge, this is the only other plurality consensus dynamics studied in the PULL(h) model. Note that our lower bound from Theorem 8.4 applies to DéjàVu as well. Combined with our upper bound for h-Majority, this shows that h-Majority is at least as efficient as DéjàVu in PULL(h), up to polylogarithmic factors, both in terms of convergence time and in terms of sample complexity. Moreover, the bounds give a polynomial separation in favor of h-Majority whenever √ pmax is polynomially smaller than 1/(h n). However, if we modify the definition of PULL(h) to allow adaptive stopping, DéjàVu can beat h-Majority in terms of sample complexity when h∥p∥2 is sufficiently large. Adaptive stopping in PULL(h) is defined as follows: in each round, a node samples (sequentially) at most h opinions, but stops at the i-th sample if the update rule is already determined by the first i samples. A more detailed comparison is given in Section 8.

13

Undecided-state dynamics. UndecidedState uses an auxiliary undecided state: a decided node becomes undecided upon observing a different decided opinion, while an undecided node adopts any decided opinion it observes; otherwise, its state is unchanged. The rule was introduced for two opinions in the population protocol model, where uniformly random pairs interact sequentially [AAE07]. For two opinions, the synchronous version reaches consensus within O(log n) rounds with high probability from any initial configuration with a decided node, and this bound is tight [CGGNPS18]. The binary synchronous dynamics has also been studied under uniform communication noise [DCN22]. For many opinions, early synchronous results required a sufficiently large initial plurality advantage [BCNPS15], whereas asynchronous consensus was proved within O(kn log n) √ interactions with high probability for k = O( n/ log2 n) from any initial configuration without undecided nodes [AABBHKL23]. Recent work covers arbitrary k in both models, accounting for possible absorption in the all-undecided state under synchronous updates [CMRSS26]. A variant that alternates phases of becoming undecided and adopting opinions achieves consensus within O(log2 n) synchronous rounds with high probability for arbitrary k [BBBEHKK22]. Minority. In Minority, each node adopts a least frequent opinion among those present in its sample, breaking ties uniformly at random. For two opinions, Becchetti, Clementi, Pasquale, Trevisan, Vacus, and Ziccardi [BCPTVZ24] proved polylogarithmic-time consensus under synchronous updates √ for a sufficiently large sample size h = Ω( n log n), whereas the expected consensus time can be exponential under asynchronous updates. D’Archivio and Vacus [DV26] established an almost-linear worst-case time lower bound for memory-less protocols with constant sample size in the related bit-dissemination problem. Minority is another interesting example of neutral h-input dynamics, so our general lower bound applies to it as well. Voter. The Voter rule, in which each node adopts the opinion of one uniformly sampled node, has been studied as a probabilistic polling mechanism for proportionate agreement: an opinion wins with probability equal to its initial fraction of supporters [HP01]. The linear voting framework generalizes such rules and gives winning probabilities and convergence-time bounds [CR16]. In our analysis, comparison with Voter provides a bound on the consensus time for h-Majority, which is useful when many opinions are present; see Section 5.2.

5

Expected one-round growth

In this section, we focus on a single step of the process. We omit the time index from the notation and assume that the entries of p = p(t) are sorted in decreasing order, p1 ≥ · · · ≥ pk . We write X = (X1 , . . . , Xk ) to denote a sample from the multinomial distribution with parameter (h, p). Recall that q = q(p) := Et [p(t + 1)], and that Maj(X) denotes the winning opinion (accounting for uniform tie-breaking). Finally, we define Wi = {Maj(X) = i}, so that qi = Pr[Wi ].

5.1

Gap between 1 and i

In this section, we study how the ratio between the majority opinion and any other opinion changes from step t to step t + 1. Theorem 5.1. Let h ≥ 3 and i ∈ [k] such that pi > 0. Then  
q1 Pr[W1 ] p1 = ≥1+ − 1 1 + 1/80 · min{h2 p1 , 1} . qi Pr[Wi ] pi 14

The theorem is trivial for i = 1. We will focus only on opinions i = ̸ 1. To prove the theorem, we will consider two differently behaving regimes: • if hp1 ≤ 1/4, then the samples are “sparse” and likely have few collisions, and • if hp1 ≥ 1/4, then the samples are “dense” and tend to have more collisions. 5.1.1

Multinomial sample spaces

Let X := {x ∈ Nk : |x| = h} be the support of the multinomial distribution. For x ∈ X , let M (x) := {j ∈ [k] : xj = ∥x∥∞ } be the set of opinions that have the highest frequency in x. For each i ∈ [k], we define the measure µi (x) := Pr[Wi ∩ {X = x}]. This is the probability that x contributes to i being the “winning opinion” in the sample. Clearly, X Pr[Wi ] = µi (x) = µi (X ). (7) x

Scoring functions. If pi = p1 , then the claim of Theorem 5.1 is trivially true. From now on, we fix i ∈ {2, . . . , k} such that 0 < pi < p1 . We write ρ = p1 /pi > 1, and define scoring functions that will be heavily used in the analysis: Ψ(x) :=

ρxi −x1 − 1 ρ−1

and

S :=

X

Ψ(x)µi (x).

x∈X

Note that Ψ is well-defined, since ρ > 1. These definitions rely on the following idea: for every x ∈ X , let x1↔i be the vector obtained from x by exchanging x1 and xi . As it turns out, µ1 (x1↔i ) can be easily expressed as a function of ρ, µi (x) and Ψ(x). We formalize this relationship in Lemma 5.2 and illustrate it in Fig. 1. Lemma 5.2. For every x ∈ X such that µi (x) > 0, µ1 (x1↔i ) = µi (x) + (ρ − 1) Ψ(x) µi (x). Proof. Since |M (x)| = |M (x1↔i )|, we get from Eq. (1): Pr[X = x1↔i ] = ρxi −x1 . Pr[X = x] Therefore, µ1 (x1↔i ) = µi (x) · ρxi −x1 = µi (x) · [1 + (ρ − 1) Ψ(x)] . This identity translates immediately to a nice relationship between S and Pr[W1 ] − Pr[Wi ]. Corollary 5.3. We have that Pr[W1 ] − Pr[Wi ] = (ρ − 1)S.

15

Figure 1: Intuition behind Lemma 5.2: for any x such that opinion i has a non-zero probability to win, there is a corresponding x1↔i that is more likely to be sampled while granting opinion 1 the same probability to win. Proof. Since the map: x → x1↔i is a bijection from X to X , X Pr[W1 ] = µ1 (x1↔i ) x∈X

=

X

[µi (x) + (ρ − 1) Ψ(x) µi (x)]

(by Lemma 5.2)

x∈X

= Pr[Wi ] + (ρ − 1)S. Equipped with Corollary 5.3, it now suffices to lower bound S to prove Theorem 5.1. More precisely, our target is S ≥ (1 + min{h2 p1 , 1}/80)µi (X ). On the support of µi , the score Ψ is zero when xi = x1 , one when xi = x1 + 1, and at least 1 + ρ when xi ≥ x1 + 2. Thus, relative to the needed score of 1 + min{h2 p1 , 1}/80, configurations x with µi (x) > 0 such that x1 = xi create a deficit larger than 1, while if x1 = xi − 1 the deficit is min{h2 p1 , 1}/80, and if x1 ≤ xi − 2 create a surplus. We compare the probability masses of these configurations through transport maps: the surplus must compensate for the deficit and still leave a margin proportional to min{h2 p1 , 1}µi (X ). As already mentioned in Section 3.3, we have two regimes: the case hp1 ≤ 1/4 and the case hp1 > 1/4. To analyze both regimes, the following sample sets will be useful. Partitioning samples in which i can win.

For all 1 ≤ t ≤ h and 0 ≤ s ≤ t, we define

Ct,s := {x : xi = t and x1 = s} ⊆ X .

(8)

Observe that any x with µi (x) > 0 has any opinion at most xi times. Hence, the disjoint sets Ct,s , where 1 ≤ t ≤ h and 0 ≤ s ≤ t, cover the support of µi . We also consider the following set E := {x ∈ X : xi = 2, x1 = 0 and xj ≤ 1 for j ∈ / {1, i}}. The mass of the set E is used to bound the mass of C1,0 and C1,1 sets. The reason to single out E is that the configurations in C1,1 and C1,0 on the support of µi have all sampled opinions distinct. Moving the occurrence of opinion 1 in a configuration of C1,1 to opinion i produces a configuration in E: opinion i becomes the unique winner, and its score increases from zero to 1 + ρ. Starting from C1,0 , moving an occurrence of another sampled opinion to i also produces a configuration in E, now increasing the score from one to 1 + ρ. The following lemma quantifies these two transports. 16

Lemma 5.4. We have µi (C1,0 ) ≤

2 µi (E) h(h − 1)pi

and

µi (C1,1 ) =

2 ρ µi (E) . h

Proof. Let Z1 , . . . , Zr be values sampled independently from the distribution p. Define θr := Pr[Z1 , . . . , Zr ∈ [k] \ {1, i} and they are pairwise distinct].

(9)

Note that θr ≤ θr−1 for any r > 1. We get that Pr[X ∈ E] =

  h 2 p θh−2 , 2 i

(10)

because if E happens, exactly two samples take the value i, the value 1 is never present, and the remaining h − 2 samples are pairwise distinct within [k] \ {1, i}. Observe that µi (E) = Pr[X ∈ E], because for any x ∈ E we have M (x) = {i}. Hence, Eq. (10) rewrites θh−2 =

Pr[X ∈ E] 2µi (E) = .
h 2 h(h − 1)p2i 2 pi

(11)

To show the first bound of the lemma, consider a sample x ∈ C1,0 . By definition, xi = 1. Moreover, if µi (x) > 0, then i ∈ M (x) and no other coordinate can exceed 1. Therefore, all sampled opinions are tied and |M (x)| = h. Since i is chosen uniformly at random to win from M (x), we get µi (C1,0 ) = Pr[X ∈ C1,0 ] · Pr[Wi | X ∈ C1,0 ] 1 = h pi θh−1 · h = pi θh−1 ≤ pi θh−2 . A similar reasoning in the case of C1,1 , where there are h choices for the position of 1 and h − 1 choices for the position of i, gives µi (C1,1 ) = h(h − 1) p1 pi θh−2 ·

1 = (h − 1) p1 pi θh−2 . h

Using Eq. (11) on both equations yields the desired statement. 5.1.2

Case of sparse samples: hp1 is small

In this section, we consider the case when hp1 ≤ 1/4. This roughly means the samples tend to have fairly few collisions. Recall the definition of Ct,s in Eq. (8). To analyze this case, we further define T :=

h [

Ct,t

T + := T \ C1,1

t=1

B :=

h [

Ct,0 ,

t=2

Here, T consists of samples, where opinion 1 and i are tied. The set B supplies surplus score to compensate for these ties: on the support of µi , its configurations have x1 = 0 and xi ≥ 2, hence score at least 1 + ρ.

17

Outline. Since all configurations outside T on the support of µi have score at least one, we obtain S ≥ µi (X \ T ) + ρµi (B) = Pr[Wi ] − µi (T ) + ρµi (B). Thus, we must show that the surplus ρµi (B) pays for the tied configurations and leaves a positive margin relative to Pr[Wi ]. Expanding T , we obtain S − Pr[Wi ] ≥ −µi (T + ) + ρµi (B) − µi (C1,1 ) . | {z } ζ

The transport bounds below show that µi (T + ) ≤ ζ/3 and ζ ≥ min{h2 p1 , 1} Pr[Wi ]/24. Together, these yield the required surplus: min{h2 p1 , 1} 2 Pr[Wi ]. S − Pr[Wi ] ≥ ζ ≥ 3 36 Analysis. The small-sample assumption makes it possible to reach configurations in B by repeatedly moving occurrences of opinion 1 to absent opinions. We have “enough” absent configurations because at most h opinions appear in a sample, so absent opinions carry total probability mass at least 1 − hp1 ≥ 3/4. This provides enough “destination mass”. The next lemma makes this comparison precise. Iterating it moves from Ct,s to Ct,0 , and in particular from the configurations in Ct,t to configurations with score at least 1 + ρ when t ≥ 2. Lemma 5.5. Let 1 ≤ s ≤ t ≤ h. If hp1 ≤ 1/4, then µi (Ct,s ) ≤

1 · µi (Ct,s−1 ). 3s

(12)

Proof. For x ∈ Ct,s , define Z(x) = {j ∈ [k] : xj = 0} to be the indices of x that contain the value zero. Since |x| = h and p1 is the largest entry in p, we have X X pj = 1 − pj ≥ 1 − hp1 . j ∈Z(x) /

j∈Z(x)

In particular, Z(x) ̸= ∅. For each j ∈ Z(x), define x1→j := x − e1 + ej = (x1 − 1, . . . , xj + 1, . . . , xk ) to be the vector, where we move one unit from the first coordinate to the jth coordinate. Note that x1 = s > 0 and x1→j ∈ Ct,s−1 . For any x such that µi (x) > 0, the definition of µi and applying Eq. (1) yields   Pr X = x1→j s pj s pj µi (x1→j ) |M (x)| |M (x)| = · = · ≥ , 1→j 1→j µi (x) Pr[X = x] |M (x )| p1 |M (x )| p1 where the last line follows from the fact |M (x1→j )| ≤ |M (x)|. In particular, we get that µi (x1→j ) ≥ µi (x)

s pj . p1

(13)

Now Eq. (13) implies X j∈Z(x)

µi (x1→j ) ≥ µi (x)

s X s(1 − hp1 ) pj ≥ µi (x) . p1 p1 j∈Z(x)

18

(14)

Finally, for y ∈ Ct,s−1 , define N (y) := |{(x, j) : x1→j = y, x ∈ Ct,s , j ∈ Z(x)}|. Observe that N (y) < h. Indeed, for every pair (x, j) counted by N (y), we have yj = 1 and j ̸= i. Moreover, once y and j are fixed, the vector x is uniquely determined. Since yi = t ≥ 1 and |y| = h, there are at most h − 1 possible indices j ̸= i such that yj = 1. Now we have X µi (Ct,s ) = µi (x) x∈Ct,s

X X p1 µi (x1→j ) s(1 − hp1 ) x∈Ct,s j∈Z(x) X p1 = N (y)µi (y) s(1 − hp1 ) ≤

(by Eq. (14)) (by regrouping the summands)

y∈Ct,s−1

≤ ≤

hp1 s(1 − hp1 )

X

µi (y)

(N (y) < h)

y∈Ct,s−1

1 µi (Ct,s−1 ). 3s

(hp1 ≤ 1/4 =⇒ hp1 /(1 − hp1 ) ≤ 1/3)

A corollary of the above lemma relates the probability mass of T + to that of B. Corollary 5.6. We have µi (T + ) ≤ 91 µi (B). Proof. We have that +

µi (T ) =

h X

(by definition of T + )

µi (Ct,t )

t=2 h X

1 · µi (Ct,0 ) 3t t! t=2 ! ! h h X X 1 · ≤ µi (Ct,0 ) 3r r! ≤

≤

r=2 h X r=2

≤ (e

t=2

1 · µi (B) 3r r!

1/3

(by iterating Eq. (12))

(by definition of B) ∞ X 1 (because = e1/3 ) r 3 r!

− 1 − 13 ) · µi (B)

r=0

≤ 91 µi (B). The same transport argument also shows that the mass of configurations with x1 = 0, namely C1,0 ∪ B, controls the entire winning probability of opinion i. Corollary 5.7. We have Pr[Wi ] ≤ e1/3 (µi (C1,0 ) + µi (B)). Proof. Note that {Ct,s : 1 ≤ t ≤ h, 0 ≤ s ≤ t} is a partition of the support of µi . Hence, X Pr[Wi ] = µi (x) (by Eq. (7)) x

19

=

≤

≤

h X t X

µi (Ct,s )

t=1 s=0 h X t X t=1 s=0 ∞ X s=0

= e1/3

1 3s s!

1 s 3 s!

h X

(by partition of the support)

· µi (Ct,0 )

! ·

h X

(by iterating Eq. (12)) !

µi (Ct,0 )

t=1

µi (Ct,0 )

(because

t=1

∞ X 1 = e1/3 ) 3t t! t=0

= e1/3 (µi (C1,0 ) + µi (B)).

(by definition of B)

The remaining mass to bound is that of C1,1 : transport to an absent opinion only reaches C1,0 , whose score is one and provides no surplus. Here we use the transport to E from Lemma 5.4. Since µi (C1,1 ) = 2ρµi (E)/h, we can use only a fraction 2/h of the surplus ρµi (E) to compensate for C1,1 . Since E ⊆ B, this payment leaves “free” at least a fraction 1 − 2/h of the total surplus ρµi (B); denote the remaining surplus by ζ. Moreover, ζ ≥ ρ(1 − 2/h)µi (E), so Lemma 5.4 also bounds ζ from below in terms of µi (C1,0 ). Together with Corollary 5.7, this converts the remaining surplus into a lower bound proportional to the entire winning probability Pr[Wi ]. Lemma 5.8. Define ζ := ρ µi (B) − µi (C1,1 ) and m := min{h2 p1 , 1}. Then (a) 3ζ ≥ µi (B), and m (b) ζ ≥ 24 Pr[Wi ].

Proof. By Lemma 5.4, we have 2ρ µi (E). h The first bound (a) of the lemma now follows from Eq. (15), since E ⊆ B and h ≥ 3, and so   2ρ 2 1 ζ ≥ ρµi (B) − µi (B) = ρ 1 − µi (B) ≥ µi (B). h h 3 ζ = ρµi (B) −

(15)

Next, we show an auxiliary bound 9 ζ ≥ µi (C1,0 ). m

(16)

To see why this holds, observe that 2ρ ζ = ρµi (B) − µi (E)   h 2 ≥ 1− ρµi (E) h   2 ρh(h − 1)pi ≥ 1− µi (C1,0 ) h 2 p1 (h − 1)(h − 2) m = µi (C1,0 ) ≥ µi (C1,0 ), 2 9

20

(by Eq. (15)) (by E ⊆ B) (by Lemma 5.4)

where the last inequality follows from the fact that h2 /9 ≤ (h − 1)(h − 2)/2 for h ≥ 3. The second bound (b) of the lemma now follows, as Pr[Wi ] ≤ e1/3 (µi (C1,0 ) + µi (B))   9 1/3 ≤ ζe +3 m 24 ≤ζ . m

(by Corollary 5.7) (by Eq. (16) and (a)) (because m ≤ 1 and e1/3 ≤ 2)

Lemma 5.9. If hp1 ≤ 1/4, then
S ≥ 1 + 1/36 · min{h2 p1 , 1} · Pr[Wi ]. Proof. By definition of Ψ, observe that any x such that µi (x) > 0 we have the following properties: (i) Ψ(x) = 0 for any x ∈ T , (ii) Ψ(x) ≥ 1 for any x ∈ / T , and (iii) Ψ(x) ≥ 1 + ρ for any x ∈ B. Using the above observations, we get that X S= Ψ(x)µi (x) x

≥

X x

µi (x) −

X

µi (x) +

x∈T

X

ρµi (x)

(by properties (i)–(iii))

x∈B

= Pr[Wi ] − µi (T ) + ρµi (B)

(by Eq. (7))

+

5.1.3

= Pr[Wi ] − µi (T ) − µi (C1,1 ) + ρµi (B)

(by definition of T + )

= Pr[Wi ] − µi (T + ) + ζ 1 ≥ Pr[Wi ] − ζ + ζ 3   min{h2 p1 , 1} 2 ≥ 1+ · · Pr[Wi ]. 24 3

(by definition of ζ) (by Corollary 5.6 and Lemma 5.8(a)) (by Lemma 5.8(b) and rearranging)

Case of dense samples: hp1 is large

In this regime, the bound 1 − hp1 no longer guarantees a positive constant mass of absent opinions, so the previous transport argument mapping to empty coordinates cannot be applied. Instead, we move an occurrence of opinion 1 directly to opinion i. This increases xi − x1 by two, suggesting that we group configurations by this difference rather than by the two counts separately. In particular, a configuration with a tie is transported to a configuration with score at least 1 + ρ. Let hp1 ≥ 1/4. We now consider the following sample sets D0 = {x ∈ X : xi = x1 }

D1 = {x ∈ X : xi = x1 + 1}

D≥2 = {x ∈ X : xi ≥ x1 + 2}.

Because µi (x) > 0 implies i ∈ M (x), we have that Pr[Wi ] = µi (D0 ) + µi (D1 ) + µi (D≥2 ).

21

(17)

Since Ψ is 0 on D0 , Ψ is always 1 on D1 , and Ψ is at least (1 + ρ) on D≥2 , we get that X S= Ψ(x) µi (x) x

≥ µi (D1 ) + (1 + ρ)µi (D≥2 ) = Pr[Wi ] + ρ µi (D≥2 ) − µi (D0 ). The challenge is now to bound µi (D0 ) and µi (D≥2 ). Outline.

We first prove the transport lemma stating that 4 1 ρµi (D≥2 ) ≥ µi (D0 ) + µi (D1 ). 3 40

Using the lower bound on S, this gives two bounds on the score: 1 1 S − Pr[Wi ] ≥ µi (D0 ) + µi (D1 ), 3 40 1 S − Pr[Wi ] ≥ ρµi (D≥2 ), 4 where the second follows because µi (D0 ) ≤ 34 ρµi (D≥2 ). Adding these bounds and using ρ > 1, we obtain
1 1 1 2 S − Pr[Wi ] ≥ µi (D0 ) + µi (D1 ) + ρµi (D≥2 ) 3 40 4
1 1 ≥ µi (D0 ) + µi (D1 ) + µi (D≥2 ) = Pr[Wi ]. 40 40 Thus, S ≥ (1 + 1/80) Pr[Wi ], which is the desired bound in this regime. Analysis.

As the first step toward this, we prove the following transport lemma.

Lemma 5.10. If hp1 ≥ 1/4, then 1 4 ρ µi (D≥2 ) ≥ µi (D0 ) + µi (D1 ). 3 40 Proof. Consider the following sets D0+ = {x ∈ D0 : x1 ≥ 2}

and

D1+ = {x ∈ D1 : x1 ≥ 1}.

Let x ∈ X such that x1 > 0. Then define τ (x) = (x1 − 1, . . . , xi + 1, . . . , xk ), i.e., one opinion 1 sample is switched to opinion i. Observe that if i ∈ M (x), then by Eq. (1) we get ρ · µi (τ (x)) = µi (x) ·

x1 |M (x)| · . xi + 1 |M (τ (x))|

By Eq. (18), we get the following bounds: (a) If x ∈ D0+ , then ρµi (τ (x)) ≥ 34 µi (x). Hence, ρµi (τ (D0+ )) ≥ 43 µi (D0+ ). (b) If x ∈ D1+ , then ρµi (τ (x)) ≥ 13 µi (x). Hence, ρµi (τ (D1+ )) ≥ 13 µi (D1+ ).

22

(18)

Moreover, we have that τ (D0+ ) ⊆ D≥2 and τ (D1+ ) ⊆ D≥2 . Since τ is injective on D0+ and D1+ , we get that τ (D0+ ), τ (D1+ ), E are disjoint subsets of D≥2 . Hence, we get that
ρµi (D≥2 ) ≥ ρ µi (τ (D0+ )) + µi (τ (D1+ )) + µi (E) 4 1 ≥ µi (D0+ ) + µi (D1+ ) + ρµi (E). (by (a) and (b)) 3 3 Next, we lower bound ρµi (E). Observe that µi (C1,1 ) = µi (D0 \ D0+ )

and

µi (C1,0 ) = µi (D1 \ D1+ ).

(19)

Applying Lemma 5.4, we get that  8ρ 2 + 40h(h − 1)pi 3h   8hp1 8ρ ≤ µi (E) · + 40h(h − 1)pi 3h   1 8 = µi (E)ρ · + 5(h − 1) 3h   1 8 ≤ µi (E)ρ ≤ µi (E)ρ + 10 9

1 4 µi (C1,0 ) + µi (C1,1 ) ≤ µi (E) · 40 3



(by Lemma 5.4) (by hp1 ≥ 1/4) (by ρ = p1 /pi ) (by h ≥ 3).

The claim of the lemma now follows by combining the above, as 1 4 ρµi (D≥2 ) ≥ µi (D0+ ) + µi (D1+ ) + ρµi (E) 3 3 4 1 1 4 ≥ µi (D0+ ) + µi (D1+ ) + µi (C1,0 ) + µi (C1,1 ) 3 3 40 3 1 1 4 4 + + + ≥ µi (D0 ) + µi (D1 ) + µi (D1 \ D1 ) + µi (D0 \ D0+ ) 3 3 40 3 4 1 ≥ µi (D0 ) + µi (D1 ). 3 40

(by the above) (by Eq. (19))

Lemma 5.11. If hp1 ≥ 1/4, then
S ≥ 1 + 1/80 · Pr[Wi ]. Proof. Recall that S=

X

Ψ(x)µi (x) ≥ Pr[Wi ] + ρµi (D≥2 ) − µi (D0 ).

x∈X

Thus, by rearranging, we have that S − Pr[Wi ] ≥ ρµi (D≥2 ) − µi (D0 )

(20)

Applying Lemma 5.10 to Eq. (20), we have 1 1 S − Pr[Wi ] ≥ µi (D0 ) + µi (D1 ) 3 40

(21)

By Lemma 5.10, we also have 34 ρµi (D≥2 ) ≥ µi (D0 ), so 1 S − Pr[Wi ] ≥ ρµi (D≥2 ) − µi (D0 ) ≥ ρµi (D≥2 ) 4 23

(22)

Hence, combining the above 1 1 1 2(S − Pr[Wi ]) ≥ µi (D0 ) + µi (D1 ) + ρµi (D≥2 ) 3  40 4 

(by Eqs. (21) and (22))

≥ 1/40 µi (D0 ) + µi (D1 ) + µi (D≥2 )

(because ρ > 1)

= 1/40 · Pr[Wi ]

(by Eq. (17)).

The claim now follows by rearranging, as S ≥ Pr[Wi ] + 1/80 · Pr[Wi ] = Pr[Wi ] · (1 + 1/80). 5.1.4

Proof of Theorem 5.1

Combining Lemma 5.9 and Lemma 5.11 yields S ≥ (1 + 1/80 · min{h2 p1 , 1}) · Pr[Wi ]. By Corollary 5.3, we have Pr[W1 ] − Pr[Wi ] = (ρ − 1)S   p1 − 1 (1 + 1/80 · min{h2 p1 , 1}) · Pr[Wi ] ≥ pi and rearranging gives the claimed bound. 5.1.5

A small corollary

Corollary 5.12. Suppose p1 = maxi∈[k] pi . Then, for every i ∈ [k], Pr[Wi ] ≤

pi Pr[W1 ] ≤ Pr[W1 ]. p1

In particular, it holds that Pr[W1 ] ≥ p1 . Proof. If pi > 0, the first inequality follows from Theorem 5.1. For pi = 0, it follows from Pr[Wi ] = 0; for i = 1, it is an equality. The second inequality follows from pi ≤ p1 . Summing the first inequality gives X Pr[W1 ] X Pr[W1 ] pi = . 1= Pr[Wi ] ≤ p1 p1 i

5.2

i

Majorization

We construct a coupling of synchronous h-Majority and Voter that preserves the majorization order at every round. The key ingredient compares one round of h-Majority and (h − 1)-Majority starting from the same opinion distribution. Recall that p is the current opinion distribution, X ∼ Multinomial(h; p) is a multinomial sample count vector, and Maj(X) is its winning opinion, with uniform tie-breaking. For sample count vectors, uppercase letters such as X denote random vectors, whereas lowercase letters such as x denote their fixed values. 24

We retain the sample-space and mode notation from Section 5.1.1. When the sample size varies, write  Y k r k Xr = {x ∈ Z≥0 : |x| = r}, νr (x) = Pr[X = x] = pxi i , x i=1

where X has distribution Multinomial(r; p) and 00 = 1. Thus Xh = X . Throughout this subsection, h ≥ 2; we allow r ≥ 1 to include the comparison with h − 1 when h = 2. Using the existing mode set M (x), define the second layer by L(x) = {i ∈ [k] : xi = ∥x∥∞ − 1}. We add a sample-size superscript to the measures and winner probabilities of Section 5.1.1: (r)

µi (x) = Pr[Wi ∩ {X = x}] = νr (x)

1{i∈M (x)} , |M (x)|

(r)

qi (p) = Pr[Wi ].

Here Wi is understood for sample size r. By the same identity as (7), X (r) (r) (r) qi (p) = µi (x), q(r) (p) = (qi (p))i∈[k] . x∈Xr (h)

(r)

In particular, µi = µi and q(h) (p) = q(p). In the proofs below, we fix p and abbreviate qi (p) (r) and q(r) (p) as qi and q(r) , respectively. For the synchronous process on n vertices, np(t + 1) | p(t) = p ∼ Multinomial(n; q(r) (p)),

Et [p(t + 1)] = q(r) (p).

All samples and tie-breaking choices are independent across vertices. Definition 5.13 (Majorization). For nonnegative vectors x, y ∈ Rk satisfying let x↓ , y↓ be their nonincreasing rearrangements. We write x ⪰ y if b X i=1

x↓i ≥

b X yi↓

Pk

i=1 xi =

Pk

i=1 yi ,

for every b ∈ [k].

i=1

The two processes. Write p(h) (t) and p(1) (t) for the empirical opinion distributions of synchronous h-Majority and Voter on the same number n of vertices with opinion set [k]. Voter is exactly 1-majority, so we denote its empirical distribution by p(1) (t). In Voter, each vertex independently copies the opinion of a uniformly sampled vertex, with replacement. Thus its next-round opinion count vector, given current distribution r, has distribution Multinomial(n; r). The corresponding distribution for h-Majority from p is Multinomial(n; q(h) (p)). Theorem 5.14 (Coupling of h-Majority and Voter). Let h ≥ 2, and let the initial empirical distributions satisfy p(h) (0) ⪰ p(1) (0). There exists a coupling of the two processes, with their correct marginal laws, such that Pr[p(h) (t) ⪰ p(1) (t) for every integer t ≥ 0] = 1. In particular, this holds when the two processes start from the same configuration. The next lemma shows that increasing the sample size makes the winner distribution larger in the majorization order; this is the key comparison used to prove Theorem 5.14. 25

Lemma 5.15. For every probability vector p and every integer h ≥ 2, it holds that q(h) (p) ⪰ q(h−1) (p). More precisely, if p1 ≥ · · · ≥ pk , then (h)

(h)

q1 (p) ≥ · · · ≥ qk (p),

(h−1)

q1

(h−1)

(p) ≥ · · · ≥ qk

(p),

and for every b ∈ [k], b b X X (h) (h−1) qi (p) ≥ qi (p) i=1

i=1

To compare prefix sums in the original opinion order, we first show that winner probabilities preserve the ordering of the current opinion frequencies. (r)

(r)

Lemma 5.16. Let h ≥ 2 and r ∈ {h − 1, h}. If pi ≥ pj , then qi (p) ≥ qj (p). Proof. As in Section 5.1.1, let xi↔j denote x with coordinates i and j exchanged, and set g(x) =

1{i∈M (x)} − 1{j∈M (x)} . |M (x)|

Swapping coordinates negates g, so g(xi↔j ) = −g(x). Using (7) with sample size r, X (r) X (r) (r) (r) qi − q j = (µi (x) − µj (x)) = νr (x)g(x). x∈Xr

x∈Xr

Since x 7→ xi↔j is a bijection of Xr , averaging this sum with its reindexed version and using g(xi↔j ) = −g(x) gives (r)

qi

(r)

− qj

1 X νr (x)g(x) + νr (xi↔j )g(xi↔j ) 2 x∈Xr 1 X (νr (x) − νr (xi↔j ))g(x). = 2

=

x∈Xr

If g(x) > 0, then xi > xj . Put d = xi − xj > 0. Using pi ≥ pj , we have   Y r i↔j pxℓ ℓ (pi pj )xj (pdi − pdj ) ≥ 0. νr (x) − νr (x ) = x ℓ̸=i,j

In particular, we have (νr (x) − νr (xi↔j ))g(x) ≥ 0. If g(x) < 0, the reversed argument makes the probability difference nonpositive, so again (νr (x) − νr (xi↔j ))g(x) ≥ 0. Thus every summand in the preceding expression for the winner-probability difference is nonnegative, and hence (r)

qi

(r)

− qj

=

1 X (νr (x) − νr (xi↔j ))g(x) ≥ 0. 2 x∈Xr

The next lemma relates sample sizes h and h − 1 by deleting one uniformly chosen sample, allowing us to compare their winner probabilities. Lemma 5.17 (Deletion construction). Let h ≥ 2 and X ∼ Multinomial(h; p). Given X, choose I with Pr[I = i | X] = Xi /h, and let Y = X − eI , where ei is the ith coordinate vector. Then the distribution of Y is identical to Multinomial(h − 1; p). 26

Proof. Generate h independent opinions with distribution p and delete a uniformly selected sample position, independently of the sampled opinions. Given their counts, the deleted opinion has distribution Xi /h. Given the deleted position, the remaining h − 1 opinions are still independent with distribution p. Their count vector is Y. Now we are ready to prove the key result (Lemma 5.15). Proof of Lemma 5.15. By relabeling, assume p1 ≥ · · · ≥ pk . By Lemma 5.16, it suffices to compare (x)∩[b]| prefix sums. Fix b ∈ [k] and put Fb (x) = |M|M (x)| . In view of the deletion construction of P xi Lemma 5.17, define Db (x) = i:xi >0 h (Fb (x) − Fb (x − ei )). Then, Lemma 5.17 yields b X

(h)

(qi

(h−1)

− qi

) = E[Db (X)].

(23)

i=1

We first evaluate Db for a fixed x ∈ Xh . Deleting a non-top opinion leaves M (x) unchanged. If a = |M (x)| ≥ 2, deleting a top opinion i leaves M (x) \ {i} as the top set. We obtain   ∥x∥∞ X |M (x) ∩ [b]| |M (x) ∩ [b]| − 1{i≤b} Db (x) = − = 0. h a a−1 i∈M (x)

If there is a unique top opinion i and L(x) = ∅, deleting i also leaves the top set unchanged, so Db (x) = 0. In the remainder of the proof, we consider count vectors x satisfying M (x) = {i} and L(x) ̸= ∅, since all other count vectors contribute zero to E[Db (X)]. For such a vector, deleting i creates the top set {i} ∪ L(x). Consequently, X xi Db (x) = (1{i≤b} − 1{j≤b} ). (24) h(|L(x)| + 1) j∈L(x)

Consider the finite set T = {(x, i, j) : x ∈ Xh , M (x) = {i}, j ∈ L(x)}. For each triple, xi = xj + 1, and the map Φ : (x, i, j) 7→ (x′ , j, i) for x′ = x − ei + ej is an involution of T . It exchanges the counts of i and j. In particular, x′j = xi and |L(x′ )| = |L(x)|. Pairing terms in (24) gives X xi (νh (x) − νh (x′ ))(1{i≤b} − 1{j≤b} ) 2E[Db (X)] = . (25) h(|L(x)| + 1) (x,i,j)∈T

This sum runs over all triples, so each pair is counted twice: once at (x, i, j) and once at its image (x′ , j, i) = Φ(x, i, j). The factor two on the left accounts for these two occurrences of the same paired contribution. Since the multinomial coefficient is unchanged by the swap,   Y h ′ νh (x) − νh (x ) = pxℓ ℓ (pi pj )xj (pi − pj ). x ℓ̸=i,j

If i ≤ b < j, then pi ≥ pj and both factors in the numerator of (25) are nonnegative. If j ≤ b < i, both factors are nonpositive. Otherwise the indicator difference is zero. Hence every summand is nonnegative, and (23) proves the required prefix inequality. Both winner distributions have total mass one, which completes the majorization assertion. 27

Corollary 5.18. For integers h ≥ r ≥ 2, q(h) (p) ⪰ q(r) (p) ⪰ p. Moreover, q(2) (p) = p. Proof. For two samples, choosing the more frequent opinion and breaking a tie uniformly is equivalent in distribution to choosing a uniformly random sample position; hence q(2) (p) = p. Iterating Lemma 5.15 from sample size two proves the claim. The next lemma turns a majorization comparison of probability vectors into a coupling of their multinomial count vectors that preserves the same order, as in Berenbrink et al. [BCEKMN17]. Lemma 5.19 (Multinomial coupling [BCEKMN17, Section 2.2 and Appendix A.3]). Let a, b ∈ [0, 1]k be probability vectors with a ⪰ b, and let n ≥ 1. There exists a jointly distributed pair (U, V) whose marginal distributions are Multinomial(n; a) and Multinomial(n; b), respectively, such that Pr[U ⪰ V] = 1. We now prove the coupling theorem, Theorem 5.14. Proof of Theorem 5.14. For any two current empirical distributions p ⪰ r, Corollary 5.18 gives q(h) (p) ⪰ p ⪰ r. By Lemma 5.19, we can therefore choose a joint next-round count vector (U, V) with respective marginal distributions Multinomial(n; q(h) (p)) and Multinomial(n; r), supported on U ⪰ V. Set the next empirical distributions to U/n and V/n. Since scaling both vectors by 1/n preserves majorization, this is a one-step coupling with the correct transition laws and with U/n ⪰ V/n almost surely. For each ordered pair of current states, fix one such joint transition law. The empirical state space is finite, so these choices define a joint Markov transition rule. Starting from the prescribed initial states, apply this rule at every round, using fresh randomness conditional on the current pair of states. Each marginal process has its original transition law. Induction gives Pr[p(h) (t) ⪰ p(1) (t)] = 1 for every t ≥ 0. The union of the exceptional events over the countably many rounds has probability zero, proving the simultaneous assertion. If vertex-level configurations are desired, for each coupled count vector choose a uniform assignment of its opinions to the n vertices, separately for each process. Independent identically distributed vertex updates are uniform conditional on their count vector, so this also recovers the correct configuration-level laws. Remark 5.20 (Scope of the comparison). The sample-size comparison in Lemma 5.15 compares expected next-round distributions from the same p. Although it yields the Voter coupling in Theorem 5.14, it does not by itself yield a trajectory coupling between h-Majority and (h − 1)majority. In particular, different starting distributions cannot be substituted into the statement merely because they are ordered by majorization. For example, with p = (1/2, 1/2, 0) and r = (1/2, 1/4, 1/4), we have p ⪰ r, whereas q(4) (p) = (1/2, 1/2, 0) ̸⪰ q(3) (r) = (9/16, 7/32, 7/32). The coupling transfers the known reduction in the number of opinions in Voter to h-Majority. Corollary 5.21 (Number of remaining opinions). There exists an absolute constant C > 0 such that the following holds. Consider h-Majority with h ≥ 2 on n ≥ 2 vertices, starting from an arbitrary initial configuration. For every fixed integer 1 ≤ T ≤ n log n, with high probability, (h)

|{i ∈ [k] : pi (T ) > 0}| ≤ (h)

Cn log n . T (h)

(h)

In particular, pmax (T ) ≥ T /(Cn log n) with high probability, where pmax (T ) = maxi∈[k] pi (T ). 28

Proof. Couple h-Majority and Voter from the same initial configuration using Theorem 5.14. If Voter has m remaining opinions at time T , then 1=

m X

m X

p(1) (T )↓ i ≤ p(h) (T )↓ i ≤ 1.

i=1

i=1

Hence, almost surely, (h)

(1)

|{i ∈ [k] : pi (T ) > 0}| ≤ |{i ∈ [k] : pi (T ) > 0}|. By [BCEKMN17, Lemma 3], Voter reaches at most m opinions within O((n/m) log n) rounds with probability at least 1 − 1/n, from any initial configuration. Taking m = min{n, ⌈Cn log n/(2T )⌉}, choosing the constant C in the statement sufficiently large, gives at most Cn log n/T opinions at time T with high probability (the case m = n is deterministic). The coupling comparison proves the claim.

6

Plurality consensus

In this section, we study the consensus time starting from a configuration in which symmetry is broken, that is, the majority opinion has a significant advantage over every other opinion. Without loss of generality, we assume that the process starts at time 0. We assume that opinion 1 is the majority opinion at time 0, but contrary to Section 5, we do not assume that the other opinions are sorted in decreasing order. We write ∆i (t) := p1 (t) − pi (t)

and

∆(t) := min ∆i (t) i>1

to denote the gaps with respect to opinion 1. Fix a sufficiently small absolute constant c > 0 and then a sufficiently large absolute constant C > 0 (depending on c). We define the growth-rate parameter γ(t) by γ(t) := min{h2 p1 (t), 1}. Under the hypotheses of Lemma 6.6, the relevant conditional growth factor within an amplification phase is at least 1 + cγ(0). Accordingly, the time scale of a phase is proportional to 1/(cγ(0)). We say that the configuration p(t) at time t is good if p1 (t) > 0 and s p1 (t) ln n · . (⋆) ∆(t) ≥ C γ(t) n Thus, the scale in the gap condition is expressed directly as p1 (t)/γ(t). Martingale notation. For a square-integrable martingale (Ms )s≥0 adapted to a filtration (Gs )s≥0 , its increments are ξs = Ms − Ms−1 , for s ≥ 1. Its predictable quadratic variation is Vs =

s X   E ξu2 | Gu−1 ,

V0 = 0.

u=1

Since the increments have conditional mean zero, Vs is the sum of their conditional variances. It measures the accumulated conditional variance and is the quantity appearing in Freedman’s inequality (Corollary A.6). We will show the following result, which is just a reformulation of Theorem 1.2. 29

Theorem 6.1. Let h ≥ 3. If the configuration p(0) is good in the sense of (⋆), then plurality consensus is reached in   ln n O γ(0) rounds with probability at least 1 − 1/n.

6.1

Proof outline

We start from a configuration at time 0 that is good in the sense of Eq. (⋆). We show that the density p1 (t) of the plurality opinion increases quickly until it reaches either twice its initial value p1 (0) or a sufficiently large constant (say, 3/5). We refer to the corresponding time period as an amplification phase. Once p1 (t) reaches 3/5, we show that the process quickly converges to consensus, and we refer to the corresponding time period as the final phase. Our analysis thus reduces to establishing high-probability bounds on the duration of each type of phase. To this end, our main technique is to consider a fine-grained filtration in which the new opinions of the nodes are revealed one by one in each round. We then control the process by applying Freedman’s inequality to this “node-exposure” filtration. To iterate the argument, we show that the configuration at the end of each amplification phase remains good. We also show that it satisfies an additional condition on the gap, namely ∆(t) ≥ p1 (t)/32. This property allows us to obtain tighter bounds on the duration of every amplification phase after the first. Freedman’s inequality (Corollary A.6) applies to martingales. That is why, in this section, we define martingales describing the evolution of p1 (t) and ∆(t) by normalizing these quantities by their expected growth. The martingales do not grow over time, implying that the two processes of interest p1 (t) and ∆(t) accumulate growth factors.

6.2

Amplification phases

We say that the phase started at round 0 succeeds at time t when either of the following occurs: 1. p1 (t) ≥ 3/5, or 2. p1 (t) ≥ 2p1 (0), ∆(t) ≥ p1 (t)/32, and the configuration p(t) is good (see Eq. (⋆)). Lemma 6.2. If the configuration p(0) is good, then the phase succeeds within    32 2 p1 (0) T := 2 ln cγ(0) ∆(0) rounds with probability at least 1 − 1/n2 . The remainder of the section is dedicated to the proof of Lemma 6.2, which is somewhat involved. We write p := p1 (0), and re-use some notations from Section 5: let Ft be the σ-algebra generated by the first t rounds, and let q(t) = Et [p(t + 1)] be the expected densities in round t + 1, conditional on the history up to round t. Furthermore, whenever p1 (t) > 0, define q1 (t) η(t) := , p1 (t) 30

with the convention that η(t) = 0 if p1 (t) = q1 (t) = 0. By Corollary 5.12, we have that η(t) ≥ 1 whenever opinion 1 is the unique maximum opinion at time t. Finally, we define H(t) :=

t−1 Y

η(s)

s=0

the accumulated growth of η (in other words, H(0) = 1 and H(t + 1) = η(t) H(t) for every t ≥ 0). We will use the values H(·) for normalisation. Stopping time. We define the stopping time τ as the first time before time T in which one of the following conditions holds: (i) p1 (t) ≥ 3/5, (ii) opinion 1 is not the unique maximum opinion, i.e., p1 (t) ≤ pi (t) for some i > 1, or (iii) p1 (t)/H(t) ∈ / [p/2, 2p]. If none of the above occur, we set τ = T . Observe that τ is a stopping time. Normalized densities and gaps. For t ≤ τ , we define the normalized density P (t) of opinion 1, and the normalized gap Di (·) between opinion 1 and opinion i, as P (t) :=

p1 (t) H(t)

and

Di (t) :=

∆i (t) . H(t)

For t > τ , we let P (t) := P (τ ), and Di (t) := Di (τ ), that is, we freeze these processes to their values at time τ . Analogously to ∆, we define D(t) := mini>1 Di (t). By definition of τ , for t < τ we have H(t) ≥ 1,

P (t) ∈ [p/2, 2p],

p1 (t) = H(t)P (t) ≥ p/2,

p1 (t) < 3/5,

(26)

and opinion 1 is the unique maximum opinion, i.e., D(t) > 0. Note that H(·) is non-decreasing up to time τ . For t < τ , the following equalities that follow from the definition of P and H will be useful later on: P (t) = 6.2.1

p1 (t) q1 (t) q1 (t) = = . H(t) H(t)η(t) H(t + 1)

(27)

Node-exposure filtration and probability theoretic tools

To get enough control on the variance of the updates, we define a more granular node-exposure filtration, which reveals the updates made by the nodes one-by-one. For each 0 ≤ j ≤ n, let Gt,j be the sigma-algebra generated by the configurations up to round t, together with the opinions adopted by the first j nodes in round t + 1. Thus, Gt,0 = Ft and Gt,n = Ft+1 . Finally, let G be the filtration given by G0,0 , . . . , G0,n = G1,0 , G1,1 , . . .. In particular, G contains F as a subsequence. The filtration G can be seen as splitting a round into n asynchronous updates. Conditional on Ft , these updates are mutually independent because all nodes sample their opinions from the configuration at the start of the round. Given a process X(t) adapted to Ft whose round increments can be decomposed as n X X(t + 1) − X(t) = ξ(t, j), j=1

31

we define its node-exposure interpolation by b j) := X(t) − X(0) + X(t,

j X

0 ≤ t < T,

ξ(t, a),

0 ≤ j ≤ n.

a=1

b 0) = X(t) − This considers the individual node contributions between consecutive rounds: X(t, b n) = X(t + 1) − X(0). If each ξ(t, j) is integrable, Gt,j -measurable, and satisfies X(0) and X(t, b is a martingale with respect to the node-exposure filtration, starting E[ξ(t, j) | Gt,j−1 ] = 0, then X at zero. We refer to it as the interpolated martingale. We will make repeated use of the following concentration bound, obtained by applying Freedman’s inequality to this martingale. Lemma 6.3. Let (X(t))Tt=0 be adapted to F such that X(t + 1) − X(t) =

n X

ξ(t, j),

j=1

where ξ(t, j) is Gt,j -measurable. Let B, V > 0 be fixed constants and suppose that almost surely E[ξ(t, j) | Gt,j−1 ] = 0,

|ξ(t, j)| ≤ B,

T −1 X n X

  E ξ(t, j)2 | Gt,j−1 ≤ V.

t=0 j=1

Then, for every a > 0, we have    Pr max |X(t) − X(0)| ≥ a ≤ 2 exp − 0≤t≤T

a2 2(V + Ba/3)

 .

b j) defined above. Its increments are Proof. Apply Corollary A.6 to the interpolated martingale X(t, b b 0) = bounded by B, and its predictable quadratic variation is bounded by V . Since X(t−1, n)− X(0, X(t) − X(0) for each 1 ≤ t ≤ T , the resulting bound implies the claim. 6.2.2

Density remains bounded

First we show that the process P (·) does not deviate too much from p by using Freedman’s inequality. Lemma 6.4. With probability at least 1 − 1/n4 , we have p/2 ≤ P (t) ≤ 2p

for all 0 ≤ t ≤ T.

(28)

Proof. Let 1 ≤ j ≤ n be a node and Zj (t + 1) be the indicator for whether node j adopted opinion 1 in round t + 1. Define, for t < τ , ξ(t, j) := 1{t<τ } ·

Zj (t + 1) − q1 (t) , nH(t + 1)

and set it to 0 for t ≥ τ . Observe that n X

Zj (t + 1) = np1 (t + 1).

j=1

32

For t < τ , combining the above with Eq. (27) and rearranging yields n X j=1

n

X 1 ξ(t, j) = (Zj (t + 1) − q1 (t)) = P (t + 1) − P (t). nH(t + 1)

(29)

j=1

For t ≥ τ , both sides are zero. Observe that because q1 (t) and H(t + 1) are Ft -measurable, and hence, Gt,j−1 -measurable, we have by conditional independence that E[Zj (t + 1) | Gt,j−1 ] = q1 (t)

and

E[ξ(t, j) | Gt,j−1 ] = 0.

For t < τ , we have H(t + 1) ≥ 1, so |ξ(t, j)| ≤ 1/n for all j ∈ [n]. For t ≥ τ , |ξ(t, j)| = 0 ≤ 1/n for all j ∈ [n]. Linearity of expectation and Zj (t + 1) = Zj2 (t + 1) gives E[(Zj (t + 1) − q1 (t))2 | Gt,j−1 ] = q1 (t)(1 − q1 (t)) ≤ q1 (t). Furthermore, on the event {t < τ }, which is Gt,j−1 -measurable, because H(t + 1) is also Gt,j−1 measurable, we get   E ξ(t, j)2 | Gt,j−1 ≤ ≤

1 n2 H(t + 1)2

E[(Zj (t + 1) − q1 (t))2 | Gt,j−1 ]

q1 (t) P (t) 2p = 2 ≤ 2. 2 2 n H(t + 1) (27) n H(t + 1) n

On {t ≥ τ }, ξ(t, j) is zero, so the same bound holds. In particular, we get that T −1 X n X t=0 j=1

  2T p . E ξ(t, j)2 | Gt,j−1 ≤ n

Setting B = 1/n, V = 2T p/n and a = p/2, and observing that Ba ≤ V , yields   a2 a2 np cnpγ(0) ≥ = =Ω (by definition of T ) 2(V + Ba/3) 4V 32T ln(2p/∆(0))   cn∆(0)2 γ(0) (since p ≥ ∆(0)) =Ω p = Ω(cC 2 ln n),

(by Eq. (⋆))

Thus Lemma 6.3 gives the claim with probability 1−1/n4 for a sufficiently large C, after fixing c. 6.2.3

One-round drift bounds

We now use Theorem 5.1 to establish bounds on the expected drift in a single round before time τ . Lemma 6.5. For i > 1 and t < τ , we have   128cγ(0)pi (t) q1 (t) − qi (t) ≥ η(t)∆i (t) 1 + . p1 (t)

(30)

Proof. If pi (t) = 0, then qi (t) = 0 and the claim is vacuous. Hence, assume pi (t) > 0. Since t < τ , we have from Eq. (26) that p1 (t) ≥ p/2. For brevity, we will drop the time notation t and only consider random variables at round t. Since p1 ≥ p/2, we have min{h2 p1 , 1} ≥ min{h2 p/2, 1} ≥ 33

min{h2 p, 1} γ(0) = . 2 2

Now further algebraic manipulations give     p1 min{h2 p1 , 1} q1 ≥1+ −1 · 1+ qi pi 80   2 min{h p1 , 1} ∆i · 1+ =1+ pi 80   p1 ∆i 2 = 1+ min{h p1 , 1} pi 80p1   p1 γ(0)∆i ≥ 1+ pi 160p1

(by Theorem 5.1) (using p1 /pi − 1 = ∆i /pi ) (by expanding and rearranging) (using min{h2 p1 , 1} ≥ γ(0)/2 ).

Note that since ∆i ≤ p1 and γ(0) ≤ 1, we have γ(0)∆i /(160p1 ) ≤ 1/160. Inverting the inequality and using η = q1 /p1 gives qi 1 γ(0)∆i 128cγ(0)∆i ≤ ≤1− ≤1− ηpi 1 + γ(0)∆i /(160p1 ) 320p1 p1

(31)

using 1/(1 + x) ≤ 1 − x/2 for 0 ≤ x ≤ 1 and choosing 0 < c ≤ 1/(128 · 320). The claim of the lemma now follows from using q1 = η p1 and p1 − pi = ∆i , as   128cγ(0)∆i q1 − qi ≥ η p1 − η pi 1 − p1 128cγ(0)ηpi ∆i = η(p1 − pi ) + p1   128cγ(0)pi = η ∆i 1 + . p1 Lemma 6.6. Let i > 1 and t < τ . Then we have (a) E[Di (t + 1) | Ft ] ≥ Di (t), and (b) if Di (t) < p/8, then also E[Di (t + 1) | Ft ] ≥ (1 + cγ(0)) Di (t), (c) if ∆(t) ≥ p1 (t)/32, then η(t) ≥ 1 + cγ(0). Proof. Consider a single round t < τ . The definition of Di (t + 1) = ∆i (t + 1)/H(t + 1), H(t + 1) = η(t)H(t), and using Lemma 6.5 gives     q1 (t) − qi (t) 128cγ(0)pi (t) ∆i (t + 1) E[Di (t + 1) | Ft ] = E | Ft = ≥ Di (t) 1 + . η(t)H(t) η(t)H(t) p1 (t) This gives the first claim. For brevity, we now omit writing t. If Di < p/8, then using definitions of Di and P and Eq. (26) we have 1−

pi ∆i Di p 1 = = < ≤ , p1 p1 P 8P 4

so pi /p1 ≥ 3/4. Plugging this into the previous bound gives the second claim, as   128cγ(0)pi Di 1 + ≥ Di (1 + 96cγ(0)) ≥ Di (1 + cγ(0)) . p1 34

For the third claim, observe that Eq. (31) in Lemma 6.5 and ∆i ≥ ∆ ≥ p1 /32 implies   128cγ(0)∆i qi ≤ ηpi 1 − ≤ ηpi (1 − 4cγ(0)) . p1 Now because 1 − p1 ≥ 2/5 ≥ 1/4, we get X 1 = q1 + qi ≤ ηp1 + η(1 − 4cγ(0))(1 − p1 ) = η − 4cγ(0)η(1 − p1 ) ≤ η − cγ(0)η. i>1

Using η ≥ 1 and rearranging gives η ≥ 1 + cγ(0). 6.2.4

Gaps grow and stay large

Let us write ϕ := 1 + cγ(0). Observe that ϕ

T /2

 ≥

2p ∆(0)

16 ,

(32)

because ln ϕ = ln(1 + cγ(0)) ≥ cγ(0)/2 and so (T /2) ln ϕ ≥ T cγ(0)/4 ≥ 16 ln(2p/∆(0)). We now consider a fixed opinion i > 1 and define the following two processes M (t) :=

t−1 X

(Di (s + 1) − E[Di (s + 1) | Fs ]) ,

(33)

ϕ−(s+1) (M (s + 1) − M (s)) .

(34)

s=0

W (t) :=

t−1 X s=0

It is easy to verify that these processes are martingales; in particular, M (·) is the martingale from the Doob decomposition of Di . They will be used to track the accumulated noise in the (normalized) gaps. Lemma 6.7. With probability at least 1 − 1/n3 , we have for each 0 ≤ t ≤ T |M (t)| ≤ p/32

and

|W (t)| ≤ ∆(0)/2.

Proof. For 1 ≤ j ≤ n and t ≥ 0, define the random variable   if node j adopts opinion 1 in round t, 1 := Yj (t) −1 if node j adopts opinion i in round t,   0 otherwise. Observe that

n X

Yj (t + 1) = np1 (t + 1) − npi (t + 1) = n∆i (t + 1).

j=1

For t < τ , we define ξ(t, j) :=

Yj (t + 1) − E[Yj (t + 1) | Ft ] nH(t + 1)

and set ξ(t, j) := 0 for t ≥ τ . Now observe that for t < τ we have n X j=1

n

ξ(t, j) =

X 1 · (Yj (t + 1) − E[Yj (t + 1) | Ft ]) nH(t + 1) j=1

35

∆i (t + 1) − E[∆i (t + 1) | Ft ] H(t + 1) = Di (t + 1) − E[Di (t + 1) | Ft ] =

= M (t + 1) − M (t). For t ≥ τ , we have that ξ(t, j) = 0 and M (t + 1) − M (t) = 0. Note that E[Yj (t + 1) | Ft ] = q1 (t) − qi (t)

and

E[Yj (t + 1)2 | Ft ] = q1 (t) + qi (t),

(35)

because   E Yj (t + 1)2 | Ft = 12 q1 + (−1)2 qi + 0 · (1 − q1 (t) − qi (t)). Clearly, |ξ(t, j)| ≤ 2/n, since H(·) ≥ 1 is non-decreasing until time τ . Using Eq. (35) and conditional independence, we can bound the variance E[(Yj (t + 1) − E[Yj (t + 1) | Ft ])2 | Gt,j−1 ] = E[Yj (t + 1)2 | Gt,j−1 ] − (E[Yj (t + 1) | Gt,j−1 ])2 ≤ E[Yj (t + 1)2 | Gt,j−1 ] = q1 (t) + qi (t) ≤ 2q1 (t). Since H(t + 1) is Ft -measurable, and hence, also Gt,j−1 -measurable, gives   E ξ(t, j)2 | Gt,j−1 ≤

2q1 (t) 2 n H(t + 1)2

2P (t) n2 H(t + 1) 4p ≤ 2 n ≤

(using Eq. (27)) (since P (t) ≤ 2p for t < τ ).

The predictable quadratic variation of the interpolated martingale associated with M is bounded as follows: T −1 X n X

  4T p E ξ(t, j)2 | Gt,j−1 ≤ n t=0 j=1    8p 32 2p ≤ ln n cγ(0) ∆(0)   3 p ≤O cnγ(0)∆(0)2   p2 =O . cC 2 ln n

(by choice of T ) (ln(2x) ≤ x2 for x = p/∆(0) ≥ 1) (by Eq. (⋆) since p(0) is good)

Let aM = p/32 and VM := 4T p/n and B := 2/n. Since BaM ≤ VM , Lemma 6.3 yields    
a2 Pr max |M (t)| ≥ p/32 ≤ 2 exp − M ≤ exp −Ω(cC 2 log n) . 0≤t≤T 3VM Similarly, for W , using bounds on the geometric series and definition of ϕ, we get T −1 X n X t=0 j=1

−1 h i 4p TX E (ϕ−(t+1) ξ(t, j))2 | Gt,j−1 ≤ ϕ−2(t+1) n t=0

36

≤

4p 4p 4p 4∆(0)2 ≤ = ≤ =: VW , n(ϕ2 − 1) n(ϕ − 1) cnγ(0) cC 2 ln n

since n∆(0)2 γ(0) ≥ C 2 p ln n by Eq. (⋆). Applying Lemma 6.3 with aW = ∆(0)/2 and BaW ≤ VW gives     a2W Pr max |W (t)| ≥ ∆(0)/2 ≤ 2 exp − 0≤t≤T 3VW     ∆(0)2 cC 2 ln n ≤ 2 exp − ≤ 2 exp − . 4 · 12∆(0)2 /(cC 2 ln n) 48 The claim now follows from the union bound and choosing C sufficiently large after fixing c. Lemma 6.8. Let i > 1 be an opinion. With probability at least 1 − 1/n3 , we have 1. Di (t) > 0 for each 0 ≤ t ≤ τ , and 2. Di (t) ≥ p/16 for each T /2 ≤ t ≤ τ . Proof. Assume the conditions of Lemma 6.7 hold. Let σ := min{s : Di (s) ≥ p/8}. For any 0 ≤ s < min{σ, τ }, we have that Di (s + 1) = E[Di (s + 1) | Fs ] + M (s + 1) − M (s)

(by rearranging Eq. (33))

≥ ϕDi (s) + M (s + 1) − M (s)

(by Lemma 6.6 since Di (s) < p/8)).

By dividing both sides by ϕs+1 , we get Di (s + 1) Di (s) M (s + 1) − M (s) − ≥ . s+1 s ϕ ϕ ϕs+1 Now by summing and telescoping we get for 0 ≤ t ≤ min{σ, τ } that t−1 

X Di (t) − Di (0) = t ϕ s=0

Di (s + 1) Di (s) − ϕs+1 ϕs

 ≥

t−1 X M (s + 1) − M (s) s=0

ϕs+1

= W (t),

which in turn gives us Di (t) ≥ ϕt (Di (0) + W (t)) ≥ ϕt (Di (0) − ∆(0)/2) ≥

ϕt ∆(0) >0 2

(36)

by rearranging and using that |W (t)| ≤ ∆(0)/2 by Lemma 6.7. For σ ≤ t ≤ τ , we have Di (t) = Di (σ) +

t−1 X

(E[Di (s + 1) | Fs ] − Di (s)) + M (t) − M (σ)

s=σ

≥ Di (σ) + M (t) − M (σ) ≥

p p p p − − = > 0. 8 32 32 16

This establishes the first claim, as Di (t) > 0 for 0 ≤ t ≤ τ . For the second claim, if τ < T /2, then the claim is vacuous. Therefore, suppose τ ≥ T /2. It suffices to show that σ ≤ T /2. For the sake of contradiction, suppose that σ > T /2. Hence, Di (T /2) < p/8 by definition of σ, but Di (T /2) ≥

ϕT /2 ∆(0) 2

(using Eq. (36)) 37

 2p 16 ∆(0) ≥ ∆(0) 2   2p ∆(0) =p ≥ · ∆(0) 2 

(using Eq. (32)) (using ∆(0) ≤ p),

which contradicts Di (T /2) < p/8. 6.2.5

Proof of the phase lemma

Lemma 6.2. If the configuration p(0) is good, then the phase succeeds within    32 2 p1 (0) := T 2 ln cγ(0) ∆(0) rounds with probability at least 1 − 1/n2 . Proof. If p ≥ 3/5, then the phase succeeds at time 0, so we restrict attention to the case p < 3/5. We consider the following events: A1 := {p/2 ≤ P (t) ≤ 2p for all 0 ≤ t ≤ T } , A2 := {D(t) > 0 for all 0 ≤ t ≤ T } , A3 := {D(t) ≥ p/16 for all T /2 ≤ t ≤ τ } . Initially absent opinions remain absent. Hence, for every initially absent opinion i, we have Di (t) = P (t) for all 0 ≤ t ≤ T . On A1 , we have P (t) ≥ p/2 for all 0 ≤ t ≤ T . Therefore, Di (t) > 0 for all 0 ≤ t ≤ T , and Di (t) ≥ p/16 for all T /2 ≤ t ≤ τ . By Lemmas 6.4 and 6.8 and a union bound over all initially present opinions other than opinion 1 (of which there are at most n − 1), we have Pr[A1 ∩ A2 ∩ A3 ] ≥ 1 − 1/n2 . In the remainder of the proof, we condition on these events. First, we consider the case that τ < T . Then by definition of τ , one of the following holds: (i) p1 (τ ) ≥ 3/5, (ii) opinion 1 is not the unique maximum opinion, i.e., D(τ ) ≤ 0, or (iii) p1 (τ )/H(τ ) ∈ / [p/2, 2p]. However, (ii) is incompatible with A2 , and (iii) is incompatible with A1 . Thus, it must be the case that p1 (τ ) ≥ 3/5, in which case the phase succeeds at time τ . Then, we consider the case that τ = T . A1 ∩ A2 ∩ A3 implies that for T /2 ≤ t ≤ T , we have ∆(t) D(t) p/16 1 = ≥ = , p1 (t) P (t) 2p 32 and hence, η(t) ≥ ϕ for T /2 ≤ t < T by Lemma 6.6. By definition of H and Eq. (32), we get   2p 16 T /2 H(T ) ≥ ϕ ≥ ≥ 512, ∆(0) because ∆(0) ≤ p. Furthermore, using the definition of A1 , we get p1 (T ) = H(T )P (T ) ≥

H(T )p ≥ 2p = 2p1 (0), 2

38

so the density of opinion 1 doubles. Observe that H(T )2 p2 min{2H(T )h2 p, 1} ∆(T )2 γ(T ) ≥ p1 (T ) 162 · 2H(T )p H(T )p min{h2 p, 1} ≥ 512 2 p γ(0) ≥ p ∆(0)2 γ(0) ≥ p ln n ≥ C2 . n Rearranging now gives s p1 (T ) ln n ∆(T ) ≥ C · , γ(T ) n

(by A1 and A3 ) (since H(T ) ≥ 1) (since H(T ) ≥ 512) (since ∆(0) ≤ p) (by Eq. (⋆))

so p(T ) is good. Since we already established that ∆(T ) ≥ p1 (T )/32 and p1 (T ) ≥ 2p1 (0), we conclude that the phase succeeds at time T .

6.3

Final phase

After O(log n) amplification phases, we are at a configuration, where the plurality opinion has density at least 3/5. From this configuration, it is easy to show that the process reaches consensus in O(log n) rounds with high probability. Lemma 6.9. If p1 (0) ≥ 3/5, then the process reaches consensus on opinion 1 in O(log n) rounds with probability at least 1 − 1/n2 . Proof. The technique is well-known [DGMSS11], but we nonetheless recall the arguments for the sake of completeness. First, we consider the case h P = 3. We condition throughout on the configuration at time t, assuming that p1 (t) ≥ 3/5. Let z = i>1 pi (t), let Z = n z be the number of nodes that do not have the majority opinion in round t, and let Z ′ be the same quantity in round t + 1. The probability to not adopt the majority opinion in round t + 1 is at most f (z) := z 2 (3 − 2z), and in particular E[Z ′ ] ≤ n f (z). Let A, B > 0 be sufficiently large constants. √ 2 (i) Consider the case Z ≥ A n log n. One can check that f (z) ≤ 22 25 z for z ≤ 5 , and for A large enough the Chernoff bound gives    2 !   23 2 1 2A ′ Pr Z ≥ Z ≤ exp − Z ≤ exp − log n = O(n−3 ). 25 n 25 625 √

p A n log n, i.e., z ≤ (A log n)/n. We have    ′  n Pr Z > B log n ≤ f (z)B log n B log n    n 3A log n B log n ≤ (using f (z) ≤ 3z 2 ) B log n n     3e A B log n n ≤ (using ≤ (en/k)k ) B k

(ii) Consider the case Z ≤

= O(n−3 ).

(for B large enough) 39

(iii) Consider the case Z ≤ B log n. Then   3B 2 log2 n Pr Z ′ > 0 ≤ E[Z ′ ] ≤ 3n z 2 ≤ . n Using (i), (ii) and a union bound, we obtain that the number of nodes without the majority opinion gets below B log n in O(log n) rounds and remains below this threshold for another log n rounds, with high probability. The desired statement follows by using (iii) over a few rounds. Finally, by Lemma 5.15, for every h > 3 and regardless of how the non-majority opinions are distributed, the probability of not adopting the majority opinion is at most f (z). Therefore, the proof also applies to every h > 3.

6.4

Proof of Theorem 6.1

Proof. Suppose we start with a good initial configuration and let K := ⌈log n⌉. We iteratively apply Lemma 6.2 to the initial configuration K times. Each phase starts where the preceding phase succeeds. By the union bound, all applications succeed with probability at least 1 − K/n2 , which we assume from now on. Let Tk be the number of rounds it takes for the kth phase to succeed. This means that after at most S = T1 + . . . + TK rounds we reach a configuration where opinion 1 has density at least 3/5. By a union bound and Lemma 6.9 applied to the configuration at time S, we get that plurality consensus is reached by round S + O(log n) with probability at least 1 − 1/n. It remains to bound S. By Lemma 6.2, we have that     2 p1 (0) log n 1 log =O . T1 = O γ(0) ∆(0) γ(0) because ∆(0) > 0 implies that ∆(0) ≥ 1/n. When applying Lemma 6.2 for the (k + 1)-th time for 1 ≤ k < K, if we have not reached density 3/5 for the initial plurality opinion, then by definition of success at time t = T1 + · · · + Tk , we have ∆(t) ≥ p1 (t)/32. Thus, we get that      1 2p1 (t) 1 Tk+1 = O log =O , γ(t) p1 (t)/32 γ(0) since the density at the start of each successful phase is at least its initial value, so γ(t) ≥ γ(0). Since K = O(log n), combining the above with the definition of γ(0) gives   log n S + O(log n) = O . γ(0)

7

Symmetry breaking

The goal of this section is to prove Theorem 1.1. More specifically, we prove the following theorem. Theorem 7.1. Let C > 0 be a sufficiently large constant. The following bounds hold with high probability:    C log n (log n)2 log n   if pmax (0) ≥ C max , √ ,  min{h2 p (0), 1} n h n max τconsensus ≤  √   n  C log n + (log n)2 for any initial configuration. h 40

To this end, we show that a unique dominant opinion emerges, even when the initial configuration is balanced. In this setting, the index of the opinion that achieves the maximum proportion may change over time. Recall that pmax (t) = maxi∈[k] pi (t) is the maximum proportion at time t and let It = min{i ∈ [k] : pi (t) = pmax (t)} denote the index attaining the maximum proportion at time t, breaking ties by the smallest index. In this section, we present the following lemma, which ensures that a unique strong opinion emerges as long as the initial opinion distribution has a sufficiently large maximum proportion. Lemma 7.2 (Emergence of the unique strong opinion). Suppose   (log n)2 log n pmax (0) ≥ C max , √ n h n   n for a sufficiently large constant C > 0. Then, for some T = O min{h2log , pmax (0),1}   3 Pr ∃j ̸= IT : pj (T ) ≥ pmax (T ) ≤ n−10 . 4 This lemma implies that the gap ∆(T ) between the largest and second-largest opinion proportions satisfies ∆(T ) ≥ pmax (T )/4 w.h.p. Combining this result with the following lemma, which controls downward fluctuations of the maximum proportion, we obtain the initial-gap condition of the plurality consensus result (Theorem 6.1). Lemma 7.3 (Maximum proportion remains large). For any T > 0,      npmax (0) pmax (0) ≤ exp −Ω . Pr ∃t ≤ T : pmax (t) ≤ 2 T

7.1

Proof outline

The key ingredient in the proof of Lemma 7.2 is the expected decrease of a well-constructed potential function. Let (pmax (t) − pj (t))2 for j ∈ [k] and t ≥ 0, pmax (t) + pj (t) 1 Φa (x) = for a ≥ 0 and x ≥ 0. 1 + ax

Gj (t) =

We prove the following one-step contraction property. Lemma 7.4 (Potential contraction lemma). Let t ≥ 0 be an arbitrary round. Let ρ be an arbitrary 1 parameter that does not depend on t and satisfies 0 < ρ ≤ 80 min{h2 pmax (t), 1}. Let a = nρ/28. Then, we have the following: 1. Let j ∈ [k] be an arbitrary opinion such that j ̸= It and pj (t) ≥ pmax (t)/2 hold. Then,  ρ  Et [Φa (Gj (t + 1))] ≤ 1 − Φa (Gj (t)). 420 2. Let i and j be an arbitrary pair of distinct opinions such that both pi (t) ≥ pmax (t)/2 and pj (t) ≥ pmax (t)/2 hold. Then,  ρ  Et [Φa (max{Gi (t + 1), Gj (t + 1)})] ≤ 1 − Φa (max{Gi (t), Gj (t)}). 420 41

1 min{h2 pmax (0), 1}. We can In the proof of Lemma 7.2, we use Lemma 7.4 (Item 2) with ρ = 160 choose this ρ since pmax (t) ≥ pmax (0)/2 holds w.h.p. by Lemma 7.3. Then, for any pair of opinions i and j satisfying pi (t) ≥ pmax (t)/2 and pj (t) ≥ pmax (t)/2, Lemma 7.4 (Item 2) ensures the potential function Φa (max{Gi (t), Gj (t)}) keeps decreasing with a factor of 1 − Ω(ρ) until one of the stopping conditions is met. Consequently, with high probability, at least one of the two opinions becomes weak by time T = O(log n/ρ), unless the maximum proportion falls below half its initial value. Once an opinion becomes weak, it is unlikely to become strong again within the time horizon under consideration. We assure this formally by the following lemma.

Lemma 7.5 (Weak cannot be strong). Let j be an arbitrary opinion such that pj (0) ≤ pmax (0)/2. Then, for any T > 0,      3 npmax (0) . Pr ∃t ≤ T : pj (t) ≥ pmax (t) ≤ exp −Ω 4 T Consequently, taking the union bound over all pairs of opinions, we can show that all but at most one opinion have become weak and cannot be strong at time T = O(log n/ρ). This completes the proof outline of Lemma 7.2. In the following, we first prove Lemma 7.4. Then, we prove Lemmas 7.3 and 7.5 using the same framework based on martingale concentration techniques. Finally, we combine these and prove Lemma 7.2.

7.2

Proof of the potential contraction (Lemma 7.4)

This section proves Lemma 7.4. First, we introduce the following basic lemma for the potential 1 function Φa (x) = 1+ax . Intuitively speaking, if a random process has both multiplicative and additive drift (Lemma 7.6(Item 1)) and its variance is sufficiently small (Lemma 7.6(Item 2)), the potential contracts multiplicatively in expectation. Lemma 7.6. Let X be a non-negative random variable with E[X 2 ] < ∞. For parameters x ≥ 0, r ∈ (0, 1], b > 0, and C ≥ 1, suppose the following two conditions hold: 1. E[X] ≥ (1 + r)x + b, 2. Var[X] ≤ Cb r (E[X] − x). Then, for a = r/(2Cb),  r  Φa (x). E[Φa (X)] ≤ 1 − 6C Proof. Write µ = E[X] for convenience. We use the following exact expansion around µ: 1 a(X − µ) a2 (X − µ)2 1 = − + . 1 + aX 1 + aµ (1 + aµ)2 (1 + aµ)2 (1 + aX) Multiplying both sides by 1 + ax and taking expectations, we obtain     1 + ax 1 + ax (1 + ax)a2 (X − µ)2 E = + E 1 + aX 1 + aµ (1 + aµ)2 1 + aX   2 1 + ax a Var[X] ≤ 1+ 1 + aµ 1 + aµ 42

(by E[X − µ] = 0) (by 1 + aX ≥ 1)

  a(µ − x) a2 Var[X] = 1− 1+ 1 + aµ 1 + aµ µ − x − aVar[X] a3 (µ − x)Var[X] − . =1− µ + 1/a (1 + aµ)2 

(37)

From Lemma 7.6(Item 2), we have Var[X] ≤ µ−x 2a . Hence, µ − x − aVar[X] ≥

µ−x . 2

Further, we have µ ≥ (1 + r)x + b > x (Lemma 7.6(Item 1)). Hence,   1 x + 1/a 1 µ + = µ − x + x + = (µ − x) 1 + a a µ−x ! 1 1 rx + ab b ≤ (µ − x) 1 + r rx + b    1 1 ≤ (µ − x) 1 + max , r ab Thus, from (37) with a = r/(2Cb), we have E[Φa (X)] 1 r 1 1
= 1 − ≤1− Φa (x) 2(2C + r) 2 1 + max r , ab holds. Since r ≤ 1 ≤ C, we obtain the claim. To apply Lemma 7.6, we need to ensure that some random variable X satisfies both the (p (t)−pj (t))2 multiplicative and additive drift conditions. Our key observation is that Gj (t) = pmax max (t)+pj (t) satisfies both of these drift properties. To estimate the expected value and variance of Gj (t), we use Zj (t) defined below. In the following, we use the notations of x+ = max{x, 0} and x− = min{x, 0} for x ∈ R.  2   (pIt−1 (t) − pj (t))+ (if p It−1 (t) + pj (t) ̸= 0), pIt−1 (t) + pj (t) Zj (t) = for j ∈ [k] and t ≥ 1.   0 (if pIt−1 (t) + pj (t) = 0). Technically, Zj (t) is much easier to handle than Gj (t) because It−1 is a fixed index once Ft−1 is determined. We now introduce the following lemma, which gives an appropriate estimation of the ratio of the sum of random variables. Lemma 7.7. Let X1 , X2 , . . . , Xn be n independent random variables such that Pr[Xi = 1] = p, Pr[Xi = −1] = q, and Pr[XP for each i ∈ [n]. Suppose 0 ≤ q ≤ p ≤ 1, p + q ≤ 1, i = 0] = 1 − p − q P and n(p + q) ≥ 1. Let X = ni=1 Xi and Y = ni=1 Xi2 . Let  2   X+ = Z = nY   0

2 1 Pn X i i=1 n + 1 Pn 2 X i=1 i n

(if Y ̸= 0), (if Y = 0).

Then, we have the following: 43

2

2

(p−q) pq 4pq 1. (p−q) p+q + n(p+q)2 ≤ E[Z] ≤ p+q + n(p+q)2 .

2. Var[Z] ≤ n7



(p−q)2 4pq p+q + n(p+q)2



. 2

(p−q) 4pq Proof of Lemma 7.7(Item 1). Let η = p−q p+q , s = (p+q)2 , and ν = p+q . First, we introduce the following random variables:

• For each i ∈ [n], let Bi ∈ {0, 1} be a binary random variable with Pr[Bi = 1] = p + q. • For each i ∈ [n], let Vi ∈ {−1, 0, 1} be a random variable with Pr[Vi = 1] = Pr[Vi = −1] = q 1−η p−q 2q 2 p+q = 2 and Pr[Vi = 0] = p+q = η. We have E[Vi ] = 0 and E[Vi ] = Var[Vi ] = p+q = 1 − η. p = 1+η • For each i ∈ [n], let Ui = Vi + 1{Vi =0} ∈ {−1, 1}. We have Pr[Ui = 1] = p+q 2 and q p−q 2 2 Pr[Ui = −1] = p+q = 1−η 2 . We have E[Ui ] = p+q = η, E[Ui ] = 1 and Var[Ui ] = 1 − η = s. d

Suppose all (Bi )ni=1 and (Vi )ni=1 are independent. By construction, (X1 , . . . , Xn ) = (B1 U1 , . . . , Bn Un ) and (Bi Ui )2 = Bi . Moreover, (Ui )ni=1 is an i.i.d. family independent of (Bi )ni=1 . Consequently, P P P conditional on i Bi = ℓ, the sum i Bi Ui has the same distribution as ℓi=1 Ui . Hence, for any ℓ ∈ [n] with Pr[Y = ℓ] > 0, we have  2 n X X i∈[n]:Xi2 =1 i  + Pn | Xi2 = ℓ n i=1 Xi2 i=1

 P  E[Z | Y = ℓ] = E

  2 P P n E | i=1 Bi = ℓ i∈[n]:Bi =1 Bi Ui +

=

nℓ  2  Pℓ E i=1 Ui + = . nℓ

(38)

P For ℓ ∈ [n], write U (ℓ) = ℓi=1 Ui . We next bound E[(U (ℓ) )2+ ] from above and below. Since x2+ ≤ x2 for all x ∈ R, we have (U (ℓ) )2+ ≤ (U (ℓ) )2 . Hence, E[(U (ℓ) )2+ ] ≤ E[(U (ℓ) )2 ] = Var[U (ℓ) ] + E[U (ℓ) ]2 = ℓ2 η 2 + ℓs

(39)

P P Let V (ℓ) = ℓi=1 Vi . From definition, we have U (ℓ) = V (ℓ) + ℓi=1 1{Vi =0} ≥ V (ℓ) . Hence, (U (ℓ) )2− ≤ 2 ≤ x2 holds. Further, from the (V (ℓ) )2− holds. Note that, for x ≤ y, x− ≤ y− holds and hence y− − symmetry of Vi , we have 1 ℓ(1 − η) ℓs ≤ . E[(U (ℓ) )2− ] ≤ E[(V (ℓ) )2− ] = E[(V (ℓ) )2+ ] = E[(V (ℓ) )2 ] = 2 2 2 d

Note that −(V (ℓ) )− = (V (ℓ) )+ holds since V (ℓ) is a sum of independent random variables symmetric about zero, it is also symmetric about zero. Further, x2− + x2+ = x2 holds for any x ∈ R, E[(U (ℓ) )2+ ] = E[(U (ℓ) )2 ] − E[(U (ℓ) )2− ] ≥ ℓ2 η 2 +

44

ℓs . 2

(40)

Combining Eqs. (38) to (40) and E[Y ] = n(p + q), we obtain E[Z] =

n X E[(U (ℓ) )2+ ] ℓ=1

nℓ

Pr[Y = ℓ] ≤

n
η 2 E[Y ] s Pr[Y > 0] 1X 2 s η ℓ + s Pr[Y = ℓ] = + ≤ν+ , n n n n ℓ=1

and n

1 X 2 s η 2 E[Y ] s Pr[Y > 0] s E[Z] ≥ η ℓ+ Pr[Y = ℓ] = + ≥ν+ n 2 n 2n 4n

(41)

ℓ=1

In the last inequality, we use Pr[Y = 0] = (1−(p+q))n ≤ e−n(p+q) ≤ e−1 ≤ 1/2 since n(p+q) ≥ 1. Proof of Lemma 7.7(Item 2). We use the notation introduced in the proof of the first assertion. By the conditional-distribution representation used in Eq. (38), for any ℓ ∈ [n], we have E[Z 2 | Y = ℓ] =

E[(X)4+ | Y = ℓ] E[(U (ℓ) )4+ ] E[(U (ℓ) )4 ] = ≤ . n 2 ℓ2 n2 ℓ2 n2 ℓ2

Here, we use x4+ ≤ x4 for any x ∈ R. Recall E[Ui ] = η and E[Ui2 ] = 1. Hence, from E[(U (ℓ) )2 ] = ℓ2 η 2 + ℓs (Eq. (39)), we have X X E[(U (ℓ) )4 ] = E[Ua Ub Uc Ud ] + E[Ua Ub Uc Ud ] a,b,c,d∈[ℓ]: |{a,b,c,d}|=4

≤

X a,b,c,d∈[ℓ]: |{a,b,c,d}|=4

=

X a,b,c,d∈[ℓ]: |{a,b,c,d}|=4

a,b,c,d∈[ℓ]: |{a,b,c,d}|≤3

  X 4 E[Ua ]E[Ub ]E[Uc ]E[Ud ] + E[Ua Ub Uc2 ] 2 a,b,c∈[ℓ]

X

η 4 + 6ℓ

E[Ua Ub ]

a,b∈[ℓ]

≤ ℓ4 η 4 + 6ℓE[(U (ℓ) )2 ] = ℓ4 η 4 + 6ℓ(ℓ2 η 2 + ℓs). Recall E[Y ] = n(p + q) and E[Y 2 ] ≤ n2 (p + q)2 + n(p + q). Hence, E[Z 2 ] ≤

n X ℓ4 η 4 + 6ℓ(ℓ2 η 2 + ℓs) ℓ=1

n 2 ℓ2

Pr[Y = ℓ] =

η 4 E[Y 2 ] + 6η 2 E[Y ] + 6s Pr[Y > 0] 7ν 6s ≤ ν2 + + 2. 2 n n n

Thus, from E[Z] ≥ ν ≥ 0 (Eq. (41)), we obtain Var[Z] ≤ E[Z 2 ] − E[Z]2 ≤ ν 2 +

7ν 6s 7 s + 2 − ν2 ≤ ν+ . n n n n

We apply Lemma 7.7 to Zj (t) to show the multiplicative and additive drift for Zj (t). We use the following calculation, which is a natural consequence of Theorem 5.1 and Corollary 5.12. Lemma 7.8. Suppose that p1 = maxi∈[k] pi . Let j ≥ 2 be any opinion such that pj ≥ p1 /2. Let ρ be a parameter satisfying 0 < ρ ≤ (1/80) min{h2 p1 , 1}. Then,  (q1 − qj )2 q1 qj 1 ρ  (p1 − pj )2 + ≥ 1 + + . 2 q1 + q j n(q1 + qj ) 2 p1 + pj 5n 45

Proof. According to Theorem 5.1, we have qq1j − 1 ≥ (1 + ρ)



p1 pj − 1



q

. This implies that q1j ≤

pj pj p1 +ρ(p1 −pj ) ≤ p1 . Additionally, q1 ≥ p1 holds from Corollary 5.12. Therefore,

(q1 − qj )2 q1 + q j

 = p1

q1 p1

q

1 − q1j

2

q 1 + q1j

 ≥ p1

p

1 − p1 +ρ(pj1 −pj )

2

 =

p 1 + p1j

2

(p − pj )2 1+ρ  1  . p p1 + p j 1 + ρ 1 − p1j p

q

Here, in taking the above inequality, we used the bound q1j ≤ p1 +ρ(pj1 −pj ) for the numerator, and pj qj q1 ≤ p1 for the denominator, respectively.

1+ρ 1+ρ Since pj ≥ p1 /2 from the assumption, we have 1+ρ(1−p ≥ 1+ρ/2 ≥ 1 + ρ3 . Thus, j /p1 )

(q1 − qj )2 (p1 − pj )2 − ≥ q1 + q j p1 + p j



1+

 (p1 − pj )2 2ρ (p1 − pj )2 ρ 2 ≥ . −1 · 3 p1 + pj 3 p1 + pj

Next, combining pj ≥ p1 /2 and q1 ≥ p1 (Corollary 5.12), we have   (q −q )2 4q1 qj . Hence, Further, we have q11 +qjj = (q1 + qj ) 1 − (q1 +q 2 j)

(1/2)2 p21 (p1 −pj )2 q1 +qj p1 p1 +pj ≤ (3/2)p1 ≤ 6 ≤ 6 .

    (q1 − qj )2 (p1 − pj )2 (q1 − qj )2 (p1 − pj )2 4q1 qj 1 1 5 − . − ≥ − ≥ q1 + q j p1 + p j n(q1 + qj ) q1 + q j p1 + p j n 6 (q1 + qj )2 (q −q )2

(42)

(43)

(p −p )2

The first inequality follows since Eq. (42) implies q11 +qjj − p11 +pjj ≥ 0 and q1 ≥ p1 ≥ 1/n. By taking a weighted average of Eq. (42) and Eq. (43) with weights 3/4 and 1/4, respectively, we obtain   (q1 − qj )2 (p1 − pj )2 4q1 qj ρ (p1 − pj )2 1 5 − ≥ · + − . q1 + q j p1 + pj 2 p1 + p j 4n 6 (q1 + qj )2 q q

Adding n(q11+qj j )2 to both sides, we obtain the claim. We now prove Lemma 7.4. Proof of Lemma 7.4(Item 1). We outline the main steps of the proof as follows. First, we establish that Φa (Gj (t+1)) ≤ Φa (Zj (t+1)). Next, to utilize Lemma 7.6, we check condition Lemma 7.6(Item 1) by computing Et [Zj (t + 1)], and verify condition Lemma 7.6(Item 2) by estimating Vart [Zj (t + 1)]. Consider the function f (x) = function is non-decreasing in x:

(x−b)2+ x+b for x, b ≥ 0, where we set f (x) = 0 when x = b = 0. This 2 for x ≤ b, f (x) = 0, and for x > b, we have f (x) = (x−b) x+b with

derivative f ′ (x) = (x−b)(3b+x) > 0. Hence, (x+b)2 Gj (t + 1) =

(pmax (t + 1) − pj (t + 1))2+ (pIt (t + 1) − pj (t + 1))2+ ≥ = Zj (t + 1). pmax (t + 1) + pj (t + 1) pIt (t + 1) + pj (t + 1)

Here, the first equality follows since (pmax (t + 1) − pj (t + 1))2 = (pmax (t + 1) − pj (t + 1))2+ always holds. The inequality is due to the fact that pmax (t + 1) ≥ pIt (t + 1). Since a ≥ 0, we obtain Φa (Gj (t + 1)) ≤ Φa (Zj (t + 1)). Now, we show the following bound on Et [Zj (t + 1)]:  ρ 1 Et [Zj (t + 1)] ≥ 1 + Gj (t) + . 2 5n 46

(44)

(45)

To see this, we condition on Ft and apply Lemma 7.7 to (Xv )v∈[n] with Xv = 1{Cv (t+1)=It } − 1{Cv (t+1)=j} , where we recall that Cv (t) ∈ [k] is the opinion of a node v at the beginning of round t. P P Then, we have n1 v∈[n] Xv = pIt (t + 1) − pj (t + 1), n1 v∈[n] Xv2 = pIt (t + 1) + pj (t + 1), and hence P 2 ( n1 v∈[n] Xv )+ Zj (t + 1) = 1 P . Further, let X2 v∈[n]

n

v

p∗ := pIt (t) = pmax (t),

q∗ := Pr[Cv (t + 1) = It ] = Pr[Xv = 1], t

t

and let qj := Pr[Cv (t + 1) = j] = Pr[Xv = −1]. t

t

Then n(q∗ + qj ) ≥ nq∗ ≥ 1 holds by Corollary 5.12. Therefore, we can apply Lemma 7.7 and obtain Et [Zj (t + 1)] ≥

(q∗ − qj )2 q∗ qj + . q∗ + q j n(q∗ + qj )2

(46)

Hence, applying Lemma 7.8 with p∗ and q∗ in the roles of p1 and q1 , respectively, and with pj = pj (t), we obtain Eq. (45). Here, ρ ≤ (1/80) min{h2 p∗ , 1} and Gj (t) =

(pmax (t) − pj (t))2 (p∗ − pj (t))2 = . pmax (t) + pj (t) p∗ + pj (t)

Finally, we show the following relation between Vart [Zj (t + 1)] and Et [Zj (t + 1)]: Vart [Zj (t + 1)] ≤

14 (Et [Zj (t + 1)] − Gj (t)). nρ

(47)

To see this, we use Eq. (42) in the proof of Lemma 7.8. We have   (q∗ − qj )2 (q∗ − qj )2 (p∗ − pj )2 1 ρ (q∗ − qj )2 − ≥ 1− ≥ . q∗ + q j p∗ + p j 1 + 2ρ/3 q∗ + q j 2 q∗ + q j 2ρ 1 Note that 1 − 1+2ρ/3 = 3+2ρ ≥ ρ/2 since ρ ≤ 1/80 ≤ 1/2. Again, applying Lemma 7.7 with ρ ≤ 1/2, we have

Et [Zj (t + 1)] −

(p∗ − pj )2 (p∗ − pj )2 (q∗ − qj )2 q∗ qj ≥ + − p∗ + pj q∗ + q j n(q∗ + qj )2 p∗ + pj 2 q∗ qj ρ (q∗ − qj ) + ≥ 2 q∗ + q j n(q∗ + qj )2   4q∗ qj ρ (q∗ − qj )2 ≥ + 2 q∗ + q j n(q∗ + qj )2 nρ ≥ Vart [Zj (t + 1)], 14

(by Eq. (46))

(by Lemma 7.7(Item 2))

and we obtain Eq. (47). Consequently, Eqs. (45) and (47) ensure that the conditions Lemma 7.6(Items 1 and 2) are satisfied with parameters x = Gj (t), r = ρ/2, b = 1/(5n), C = 35, and a = r/(2Cb) = nρ/28. We obtain  ρ  Et [Φa (Zj (t + 1))] ≤ 1 − Φa (Gj (t)). 420 Combining it with Eq. (44), we obtain the claim. 47

Proof of Lemma 7.4(Item 2). Choose ℓt ∈ {i, j} \ {It } such that Gℓt (t) = max{Gi (t), Gj (t)}, breaking ties by the smallest index. Such a choice is possible because i = ̸ j implies that at least one of i and j differs from It = min{i ∈ [k] : pi (t) = pmax (t)}, and GIt (t) = 0 ≤ Gl (t) for every l ∈ [k]. In particular, ℓt is Ft -measurable. Since Φa is nonincreasing, we obtain Et [Φa (max{Gi (t + 1), Gj (t + 1)})] ≤ Et [Φa (Gℓt (t + 1))]  ρ  ≤ 1− Φa (Gℓt (t)) 420   ρ = 1− Φa (max{Gi (t), Gj (t)}). 420

7.3

(since ℓt ∈ {i, j}) (by Lemma 7.4(Item 1))

Maximum proportion and weak opinions (Lemmas 7.3 and 7.5)

This section shows Lemmas 7.3 and 7.5. Both are consequences of a martingale inequality based on the Bernstein condition (Definition A.1). To begin with, we show the following common framework for the proofs of Lemmas 7.3 and 7.5. Lemma 7.9. Fix an integer T ≥ 1. Let Ft be a natural filtration generated by (C(s))s≤t . Let (X(t))t∈N0 be a sequence of non-negative real-valued random variables adapted to (Ft )t∈N0 . Suppose that, for every t ∈ [T ], conditional on Ft−1 , the following conditions hold: Et−1 [X(t)] X(t−1) 1. Et−1 [pI (t)] ≤ pmax (t−1) , t−1

2. X(t)−Et−1 [X(t)] satisfies the one-sided



b bEt−1 [pIt−1 (t)] n, n



-Bernstein condition for some b ≥ 1.

X(0) Let θ ∈ (0, 1] and I ∈ (0, θ) be parameters and suppose pmax (0) ≤ θ − I. Then,

    I 2 npmax (0) X(t) ≥ θ ≤ exp − . Pr ∃t ∈ {0, . . . , T } : pmax (t) 4b(2T + I/3) Proof of Lemma 7.9. Define the following parameters: • For t ≥ 0, let θt = θ −

I It + . 2 2T

We have 0 < θ − I2 = θ0 ≤ θt . Further, θt ≤ θ holds for all t ∈ {0, . . . , T }. We will frequently I use the fact that θt − θt−1 = 2T in the proof. • For i ∈ [k] and t ≥ 0, let Yi (t) = θt pi (t) − X(t). In particular, write Y (t) = θt pmax (t) − X(t). n o X(t) + ≥ θ • Let τ + = inf t ≥ 0 : pmax t and let τ = min{τ , T }. (t) • Let Z(t) = −Y (t ∧ τ ) and M (t) = exp(λZ(t)), where λ = 2bTIn/2 +Ib/3 .

48

Recall Et−1 [pIt−1 (t)] ≥ pIt−1 (t − 1) = pmax (t − 1) holds from Corollary 5.12. Hence, for τ > t − 1, we have   I Et−1 [pIt−1 (t)] − Et−1 [X(t)] Et−1 [YIt−1 (t)] = θt−1 + 2T   Et−1 [pIt−1 (t)] I pmax (t − 1)Et−1 [X(t)] + = θt−1 pmax (t − 1) − Et−1 [pIt−1 (t)] pmax (t − 1) Et−1 [pIt−1 (t)] 2T Et−1 [pIt−1 (t)] I ≥ (θt−1 pmax (t − 1) − X(t − 1)) + Et−1 [pIt−1 (t)] pmax (t − 1) 2T I ≥ Y (t − 1) + (48) Et−1 [pIt−1 (t)]. 2T The first inequality follows from the assumption Lemma 7.9(Item 1):

Et−1 [X(t)] Et−1 [pIt−1 (t)]

X(t−1) ≤ pmax (t−1) .

The second inequality follows from the fact that θt−1 pmax (t − 1) − X(t − 1) ≥ 0 for τ > t − 1 and Et−1 [pIt−1 (t)]/pmax (t − 1) ≥ 1. Eq. (48) implies that Y (t − 1) ≤ Et−1 [θt pIt−1 (t) − X(t)] − I 2T Et−1 [pIt−1 (t)] for τ > t − 1. Additionally, we have Y (t) = θt pmax (t) − X(t) ≥ θt pIt−1 (t) − X(t). Hence, Z(t) − Z(t − 1) = 1{τ >t−1} (Y (t − 1) − Y (t))  
I Et−1 [pIt−1 (t)] . ≤ 1{τ >t−1} θt Et−1 [pIt−1 (t)] − pIt−1 (t) + (X(t) − Et−1 [X(t)]) − 2T By Lemma A.3 (Items 2 and 4), the centered random variable Et−1 [pIt−1 (t)] − pIt−1 (t) satisfies a Bernstein condition. Since θt2 ≤ 1 for τ > t − 1, applying Lemma A.2 (Items 2 and 3) shows that
1{τ >t−1} θt Et−1 [pIt−1 (t)] − pIt−1 (t) satisfies the Bernstein condition with parameters   1 1{τ >t−1} Et−1 [pIt−1 (t)] , . n n Note that θt2 ≤ 1 for τ > t − 1. Hence, from the assumption Lemma 7.9(Item 2) and Lemma A.2 (Item 6),

1{τ >t−1} θt Et−1 [pIt−1 (t)] − pIt−1 (t) + (X(t) − Et−1 [X(t)])  41  {τ >t−1} bEt−1 [pIt−1 (t)] satisfies one-sided 2b , -Bernstein condition. n n Now, we introduce the following basic claim: Claim 7.10. Let D, s, R > 0 and J ≥ 0 be parameters. Suppose X satisfies one-sided (D, sJ)R Bernstein condition. Then, for λ = s/2+DR/3 , E[eλ(X−JR) ] ≤ 1. Proof of Claim 7.10. By the choice of λ, we have 1−

λD s/2 λs = > 0 and = R. 3 s/2 + DR/3 2(1 − λD/3)

Hence, by Definition A.1, E[e

λ(X−JR)

 ] ≤ exp

λ2 Js − λJR 2(1 − λD/3)



49

 = exp λJ



λs −R 2(1 − λD/3)

 = 1.

We condition on Ft−1 and apply Claim 7.10 with the following parameters:

X = 1{τ >t−1} θt Et−1 [pIt−1 (t)] − pIt−1 (t) + (X(t) − Et−1 [X(t)]) , I R = 2T Et−1 [pIt−1 (t)], s = Then, we obtain

4bEt−1 [pIt−1 (t)] In/2 R , D = 2b n n , J = 1{τ >t−1} , and λ = s/2+DR/3 = 2bT +Ib/3 .

Et−1 [M (t)] M (t − 1) = Et−1 [exp(λ(Z(t) − Z(t − 1)))]    
I ≤ Et−1 exp λ1{τ >t−1} θt Et−1 [pIt−1 (t)] − pIt−1 (t) + (X(t) − Et−1 [X(t)]) − Et−1 [pIt−1 (t)] 2T ≤ 1, i.e., (M (t))t∈N0 is a supermartingale. Hence, we have      X(0) λpmax (0)I E[M (T )] ≤ E[M (0)] = exp −λpmax (0) θ0 − ≤ exp − . pmax (0) 2 X(0) Here, we use the assumption of pmax (0) ≤ θ − I and θ0 = θ − I/2. Further,     X(t) X(t) ≥ θ ≤ Pr ∃t ≤ T : ≥ θt Pr ∃t ≤ T : pmax (t) pmax (t) + = Pr[τ ≤ T ]

≤ Pr[Z(T ) ≥ 0] = Pr[M (T ) ≥ 1] ≤ E[M (T )]. The second inequality follows since τ + ≤ T ⇒ Y (τ + ∧ T ) ≤ 0 and Y (τ + ∧ T ) = −Z(T ) from definition. Proof of Lemma 7.3. Let c↓max = 1/2. We apply Lemma 7.9 with X(t) = (1 − c↓max )pmax (0), b = 1, X(0) ↓ θ = 1, and I = c↓max . We have pmax (0) = 1 − cmax = θ − I. From Et−1 [pIt−1 (t)] ≥ pIt−1 (t − 1) = pmax (t − 1) (Corollary 5.12), the condition of Lemma 7.9 (Item 1) holds. Further, X(t) − Et−1 [X(t)] satisfies the assumption of Lemma 7.9 (Item 2) since X(t) is a constant. Hence, applying Lemma 7.9, we obtain !!      X(0) pmax (0) npmax (0) Pr ∃t ≤ T : ≥ θ ≤ exp −Ω T = exp −Ω . 1 pmax (t) T n + n

Proof of Lemma 7.5. Let cweak = 1/2. We apply Lemma 7.9 with X(t) = pj (t), b = 1, θ = 1 − cweak 2 , p (0)

X(0) j I = cweak /2, We have pmax (0) = pmax (0) ≤ 1 − cweak = θ − I. We have E

[p (t)]

p (t−1)

t−1

t−1

p (t−1)

t−1 j j j 1. Et−1 [pI (t)] ≤ pI (t−1) = pmax (t−1) from Corollary 5.12,

2. pj (t) − Et−1 [pj (t)] satisfies and 4).



1 Et−1 [pIt−1 (t)] n, n



50

Bernstein condition from Lemma A.3 (Items 2

Note that Et−1 [pj (t)] ≤ Et−1 [pIt−1 (t)] holds from Corollary 5.12. Hence, applying Lemma 7.9, !!      X(t) pmax (0) npmax (0) Pr ∃t ≤ T : ≥ θ ≤ exp −Ω T = exp −Ω . 1 pmax (t) T n + n

7.4

Emergence of the unique strong opinion (Proof of Lemma 7.2)

Proof of Lemma 7.2. Set cweak = c↓max = 1/2 and define ↓ τmax = inf{t ≥ 0 : pmax (t) ≤ (1 − c↓max )pmax (0)},

τiweak = inf{t ≥ 0 : pi (t) ≤ (1 − cweak )pmax (t)} for i ∈ [k]. ↓ For a pair of distinct opinions i and j, let τi,j = min{τiweak , τjweak , τmax }. Furthermore, set ρ = 2 min{h pmax (0), 1}/160 and a = nρ/28. From definition, pmax (t) ≥ pmax (0)/2 for all t < τi,j . Hence, ρ ≤ ρt = (1/80) min{h2 pmax (t), 1} for all t < τi,j . Let r = ρ/420, X(t) = (1 − r)−t Φa (max{Gi (t), Gj (t)}), and Y (t) = X(t ∧ τi,j ). Set T = ′ ⌈C log n/r⌉ for a sufficiently large constant C ′ > 0. (Y (t))t∈N0 is a supermartingale since

Et−1 [Y (t) − Y (t − 1)] = 1{τi,j >t−1} Et−1 [X(t) − X(t − 1)] = 1{τi,j >t−1} (1 − r)−t (Et−1 [Φa (max{Gi (t), Gj (t)})] − (1 − r)Φa (max{Gi (t − 1), Gj (t − 1)})) ≤ 0. 1 1 The last inequality follows from Lemma 7.4 (Item 2). Since Φa (x) = 1+ax for any 0 ≤ x ≤ 1, ≥ 1+a

E[Y (T )] ≥ E[1{τi,j >T } Y (T )] = E[1{τi,j >T } (1 − r)−T Φa (max{Gi (T ), Gj (T )})] ≥ Pr[τi,j > T ]

(1 − r)−T . 1+a

Hence, we obtain Pr[τi,j > T ] ≤ (1 + a)(1 − r)T E[Y (T )] ≤ (1 + a)(1 − r)T E[Y (0)] ≤ 2n exp (−rT ) ≤ n−20 .

(49)

Note that we have 160 1 = . ρ min{h2 pmax (0), 1} and   (log n)2 (log n)2 1 pmax (0) ≥ ⇔ pmax (0) ≥ 160 max 1, 2 ρn n h pmax (0) ( ) √ 160(log n)2 160 log n √ ⇔ pmax (0) ≥ max , . n h n Now, consider the following events: 51

(50)

1. Let Si (t) be the event that pi (t) ≥ (1 − cweak 2 )pmax (t). ↓ 2. Let Ai,j be the event that τmax > T and τiweak > T and τjweak > T . ↓ 3. Let Bi,j be the event that τmax > T and {τiweak ≤ T or τjweak ≤ T } and Si (T ) and Sj (T ).

Then,     [k] Pr ∃{i, j} ∈ : Si (T ) and Sj (T ) 2     [k] ↓ ≤ Pr ∃{i, j} ∈ : τmax ≤ T or Ai,j or Bi,j 2 h i ↓ ≤ Pr τmax ≤T     [k] ↓ weak weak + Pr τmax > T and ∃{i, j} ∈ : τi > T and τj >T 2 h i ↓ + Pr τmax > T and ∃i ∈ [k] : τiweak ≤ T and Si (T ) .

(51)

Now, we estimate each term in the above inequality. First, from Lemma 7.3, we have       h i npmax (0)ρ npmax (0) ↓ ≤ exp −Ω ≤ n−15 . Pr τmax ≤ T ≤ exp −Ω T log n For the second term, applying the union bound and Eq. (49) we have h i X ↓ Eq. (51) ≤ Pr τmax > T and τiweak > T and τjweak > T ≤ n−15 . i,j∈[k]:i̸=j

Finally, for the third term, we have h i ↓ Pr τmax > T and τjweak ≤ T and Sj (T ) h i ≤ Pr τjweak ≤ T and pmax (τjweak ) > (1 − c↓max )pmax (0) and Sj (T ) i h = E 1{τ weak ≤T and pmax (τ weak )>(1−c↓ )pmax (0)} Pr[Sj (T ) | Fτ weak ] max j j j " !!# npmax (τjweak ) ≤ E 1{τ weak ≤T and pmax (τ weak )>(1−c↓ )pmax (0)} exp −Ω max j j T ≤ n−20 . Here, we use Lemma 7.5 in the last inequality. Taking the union bound, we obtain the claim.

7.5

Proof of Theorem 1.1

Proof of Theorem 7.1. Let p∗ = C1 max From Eq. (50),

n

(log n)2 log n , h√n n

o

for a sufficiently large constant C1 > 0.

C2 (log n)2 pmax (0) ≥ p∗ ⇒ pmax (0) ≥ ⇔ pmax (0) ≥ n min{h2 pmax (0), 1} 52

s C2

pmax (0) (log n)2 · min{h2 pmax (0), 1} n

for a sufficiently large constant C2 > 0.  First, consider the case where pmax (0) ≥ p∗ . Then, we apply Lemma 7.2: For some TL = n O min{h2log , pj (TL ) ≤ 34 pmax (TL ) ⇔ pmax (TL ) − pj (TL ) ≥ pmax4(TL ) holds for all j = ̸ ITL pmax (0),1} w.h.p. Further, from Lemma 7.3, we have pmax (TL ) ≥ pmax (0)/2 ≥p∗ /2 w.h.p. Thus,  we can apply log n Theorem 1.2 and the process reaches consensus within additional O min{h2 pmax (TL ),1} rounds w.h.p. We obtain the claim from pmax (TL ) ≥ pmax (0)/2. Next, consider the case where pmax (0) < p∗ . Then, set TS = ⌈C3 p∗ n log n⌉ for a sufficiently large constant C3 > 0. Applying Corollary 5.21, pmax (TS ) ≥ p∗ with high probability. Hence, starting from TS , we can proceed  in the  same way√as in the first case. The total time for this case is bounded n(log n)2 log n 3 by O TS + min{h2 p∗ ,1} = O (log n) + and we obtain the claim. h

8

Lower bound on neutral h-input dynamics

We prove the consensus-time lower bound for rules that may use both the sampled opinions and the updating vertex’s current opinion.

8.1

Dynamics and statement

In this section, we write LX for the distribution of a random variable X. We describe an update algorithm by a fixed distribution LW over functions from [k] × [k]h to [k]. Each such function takes a vertex’s current opinion and an ordered vector of h sampled opinions and returns its new opinion. We refer to the current opinion together with the h sampled opinions as the h + 1 inputs to the rule. We write W for a generic random function with this distribution. The distribution LW is the same for all vertices and rounds; it specifies the algorithm, including any internal randomness. A deterministic update rule corresponds to a distribution concentrated on a single function. We consider synchronous updates. At the beginning of each round t, every vertex v draws a fresh independent copy Wv (t) of W. Independently of this draw, it samples h vertices uniformly with replacement and records their current opinions in the ordered vector Z(v) (t). The sampling is independent across vertices, and vertex v updates to Cv (t + 1) = Wv (t)(Cv (t), Z(v) (t)). For a permutation σ : [k] → [k] and z ∈ [k]h , write σz = (σ(z1 ), . . . , σ(zh )). Definition 8.1 (h-input rules and neutrality). Fix integers k ≥ 2 and h ≥ 1. An h-input rule is a distribution LW of a random variable W taking values in the set of functions from [k] × [k]h to [k] such that, for every c ∈ [k] and z = (z1 , . . . , zh ) ∈ [k]h , Pr[W(c, z) ∈ {c, z1 , . . . , zh }] = 1. The rule is neutral if, for every permutation σ : [k] → [k], every c, i ∈ [k], and every z ∈ [k]h , Pr[W(c, z) = i] = Pr[W(σ(c), σz) = σ(i)]. The neutrality condition in Definition 8.1 concerns opinion labels, while input positions can be exploited by the specific update rule. This includes rules that adopt the first repeated opinion in the sample sequence, as in h-DéjàVu; see Example 8.7. We also introduce the following parameter, which allows us to refine the lower bound for dynamics such as DéjàVu. Definition 8.2. For Pignore ∈ [0, 1], an h-input rule LW is Pignore -ignoring if, for every input (c, x1 , . . . , xh ) ∈ [k]h+1 with distinct entries, it holds that Pr[W(c, x1 , . . . , xh ) = c] ≥ Pignore 53

Intuitively, Pignore is a lower bound on the probability that a vertex ignores the sampled opinions and retains its current opinion when all h + 1 inputs are distinct. Note that any h-input dynamics is 0-ignoring. DéjàVu capped at h samples, defined in Example 8.7, is 1-ignoring. Definition 8.3 (W-dynamics). Let LW be an h-input rule as in Definition 8.1, and let n ≥ 2. The W-dynamics starts from a fixed configuration C(0) ∈ [k]n and, in each round t ≥ 0, updates all vertices v ∈ [n] simultaneously according to Cv (t + 1) = Wv (t)(Cv (t), Z(v) (t)). Here, at the beginning of round t, conditional on C(0), . . . , C(t), the vertices independently choose pairs (Wv (t), Z(v) (t)). For each vertex v, Wv (t) has the same distribution as W, and, independently of Wv (t), the vector (v) (v) Z(v) (t) = (Z1 (t), . . . , Zh (t)) is obtained by sampling h vertices uniformly with replacement from [n], possibly including v, and taking their opinions at time t. As in the h-Majority setting, we use C(t), p(t), pmax (t), and τconsensus for the configuration, opinion densities, maximum density, and consensus time. We use the filtration Ft and the notation Prt [·], Et [·], Vart [·], and q(t) from Section 2, now for this process. Conditional on Ft , the sample vectors have distribution p(t)⊗h and are independent across vertices. By Definition 8.1, consensus is absorbing and an opinion absent initially can never appear. We now establish a general lower bound on the consensus time of neutral h-input dynamics. Theorem 8.4. Suppose pmax (0) < 1 and h ≥ 1. For any neutral h-input dynamics, the consensus time is at least T with probability at least 1 − 1/n, where    √ 1 n T = Ω 1 + min , √ . min{h2 pmax (0), 1} h log n Moreover, if the dynamics is Pignore -ignoring, then the lower bound can be improved to ( )! √ 1 n n T = Ω 1 + min , , p , min{h2 pmax (0), 1} h2 log n h (1 − Pignore ) log n where the last term is omitted when Pignore = 1. In particular, for Pignore = 1, one may take    n 1 , . T = Ω 1 + min min{h2 pmax (0), 1} h2 log n

(52)

Example 8.5 (Majority and minority). For z ∈ [k]h , let Top(z) be the set of opinions with the 1 highest frequency in z. Then Pr[W(c, z) = i] = {i∈Top(z)} |Top(z)| corresponds to the h-Majority protocol. Similarly, let Bot(z) be the set of opinions with the lowest frequency among those present in z. 1 Then Pr[W(c, z) = i] = {i∈Bot(z)} |Bot(z)| corresponds to the h-minority protocol, studied for k = 2 in [BCPTVZ24]. Both are neutral h-input rules in the sense of Definition 8.1 for every number of opinions. Example 8.6 (2-Choices). For h = 2, the (deterministic) rule ( z1 , z1 = z2 , W(c, (z1 , z2 )) = c, z1 ̸= z2 is a neutral 2-input rule, even when the retained opinion is absent from the sample. Its W-dynamics is 2-Choices [SS25].

54

Example 8.7 (DéjàVu in PULL(h)). DéjàVu in PULL(h) works as follows: each node reads samples in order and stops at the first repeated opinion or after h samples, whichever occurs first [dDGGN26]. In the standard PULL(h), the node must still sample all h opinions, even if its next opinion is determined earlier. In case of adaptive sampling, the node may stop sampling as soon as it sees a duplicate opinion. If r ∈ {2, . . . , h} is the smallest index for which zr ∈ {z1 , . . . , zr−1 }, the rule returns zr ; if no such index exists, it returns c. We may generate the entire vector z = (z1 , . . . , zh ) in advance and leave its unused suffix unread. This representation has the same update distribution as sampling until the stopping condition is met, and it defines a neutral h-input rule in the sense of Definition 8.1. The case h = 2 is exactly 2-Choices. √ Theorems 7.1 and 8.4 imply that, for h ≥ 3, when pmax ≪ 1/(h n), h-Majority can be asymptotically faster, with the following ratio between their convergence times holding with high probability:   1 TDV e √ =Ω , THM h n pmax where TDV and THM denote the consensus times for DéjàVu and h-Majority, respectively, starting from the same initial configuration. For a dynamics with consensus time T , we define its sample complexity as the random variable S that is the average over all nodes of the total number of samples drawn by a node before consensus. In the standard PULL(h), every node draws exactly h samples in every round, so the sample complexity is exactly hT . Consequently, with high probability, the sample complexities of h-Majority and DéjàVu satisfy, respectively,    √ 1 e h + min SHM = O , n hpmax and

 1 . hpmax e √n) samples per node, whereas DéjàVu In particular, in this regime, h-Majority uses at most O( e requires Ω(1/(hp max )) samples per node. Thus, with high probability,   SDV 1 e √ =Ω . SHM h n pmax √ This gives a polynomial separation whenever pmax is polynomially smaller than 1/(h n). In case of adaptive sampling, DéjàVu can reduce its sample complexity. Fix any constant ε > 0. Suppose that the initial configuration satisfies np1 = ω(log2 n) and, for a sufficiently large constant λ > 0, s   1 p1 p1 − p2 ≥ λ max , log n. nh2 n  e SDV = Ω h +

Suppose further that ( h = Ω min

n−1/4+ε 1 ,√ p1 p1

)!

Then, [dDGGN26, Theorem 3] gives, with high probability, adaptive SHM adaptive SDV

e (max{1, h∥p∥ }) . =Ω 2 55

.

Thus, when h∥p∥2 is sufficiently large, DéjàVu uses fewer samples than h-Majority, even though their convergence times are comparable up to logarithmic factors. In the standard PULL(h), the expression h + 1/(hp1 ) is minimized when h2 p1 = Θ(1). The upper bound on the adaptive sample complexity of DéjàVu in [dDGGN26] is also minimized up to constant factors by this choice of h. Applying Theorem 8.4 (Eq. (52)) to 2-Choices recovers the consensus-time lower bound in [DAr26], whereas it establishes optimality (up to polylogarithmic factors) of the upper bound of DéjàVu for plurality consensus under the assumptions of [dDGGN26].

8.2

Proof

We first bound the probability that a neutral rule selects a specified opinion from independent inputs. Lemma 8.8 (Selection probability). Let W be a neutral h-input rule as in Definition 8.1, and let p = (p1 , . . . , pk ) be a probability vector. Let Z = (Z1 , . . . , Zh+1 ) ∼ p⊗(h+1) be independent of W. Then, for every i ∈ [k],     h+1 2 Pr[W(Z1 , (Z2 , . . . , Zh+1 )) = i] ≤ pi 1 + h(h − 1)∥p∥2 + pi . 2 Proof. Set m = h + 1 and write W(z) = W(z1 , (z2 , . . . , zm )). Let Si be the set of vectors in [k]m containing exactly one i, and let Sing(y) count the opinions appearing exactly once in a vector y. We first bound the probability of selecting i when Z ∈ Si . Let τij swap labels i and j, with τii the identity. On Si ∩ Sj , this map is a bijection preserving both Pr[Z = z] and Sing(z), since i and j each occur once. Neutrality gives Pr[W(z) = i] = Pr[W(τij z) = j]. Consequently, Pr[W(Z) = i, Z ∈ Si ] =

k X X j=1 z∈Si ∩Sj

=

k X X j=1 z∈Si ∩Sj

=

k X X j=1 z∈Si ∩Sj

≤

Pr[W(z) = i] Pr[Z = z] Sing(z) Pr[W(τij z) = j] Pr[Z = τij z] Sing(τij z) Pr[W(z) = j] Pr[Z = z] Sing(z)

X Pr[Z = z] z∈Si

Sing(z)

.

P The first equality Puses j 1{z∈Sj } = Sing(z); the third is the change of variables z 7→ τij z. The last inequality uses j Pr[W(z) = j] = 1. Let U = (U1 , . . . , Uh ) ∼ p⊗h and write S = Sing(U). Summing over the m possible positions of the unique i gives X Pr[Z = z] X Pr[U = y] = mpi Sing(z) 1 + Sing(y) h z∈Si

y∈([k]\{i})

X Pr[U = y] 1 + Sing(y) y∈[k]h  
m = pi E ≤ pi m − E[S] . 1+S ≤ mpi

56

Here 0 ≤ S ≤ h = m − 1, and m/(1 + s) ≤ m − s for such values of S because (m − s)(1 + s) − m = s(m − 1 − s) ≥ 0. Ph r=1 1{Ur =j} be the number of occurrences of opinion j. Since P To bound E[S], let Nj = = h and each opinion with Nj = 1 accounts for exactly one entry, h − S counts the entries N j j whose opinion appears at least twice. Thus X h−S = Nj j:Nj ≥2

X

≤

Nj (Nj − 1)

j:Nj ≥2

=2

 k  X Nj j=1

2

X

=2

1{Ur =Us } .

1≤r<s≤h

The inequality uses Nj − 1 ≥ 1 when Nj ≥ 2. The last equality counts pairs of positions with equal
opinions: opinion j occurs at Nj different positions and therefore gives N2j such pairs. Taking P 2 expectations and using Pr[Ur = Us ] = j pj = ∥p∥22 yields   h E[S] ≥ h − 2 ∥p∥22 = h − h(h − 1)∥p∥22 . 2 This also holds for h = 1, when the sum over pairs is empty. Thus   Pr[W(Z) = i, Z ∈ Si ] ≤ pi 1 + h(h − 1)∥p∥22 .

(53)

By Definition 8.1, the rule can select i only if i occurs among its inputs. Therefore, if W(Z) = i and Z ∈ / Si , at least two entries of Z equal i. A union bound gives   X m 2 Pr[W(Z) = i, Z ∈ / Si ] ≤ Pr[Zr = Zs = i] = p . (54) 2 i 1≤r<s≤m

Adding Eqs. (53) and (54) and substituting m = h + 1 proves the claim. Then, we bound the one-round expected growth and variance of any opinion density. Lemma 8.9. For any neutral h-input dynamics that is Pignore -ignoring, the following holds. Fix t ≥ 1. Conditional on Ft−1 , for every i ∈ [k], we have 1. Et−1 [pi (t)] ≤ pi (t − 1) + 2h2 pmax (t − 1)2 . 2. Vart−1 [pi (t)] ≤

(2(1−Pignore )+5h2 pmax (t−1))pmax (t−1) n

.

Proof. Throughout the proof, we condition on Ft−1 and omit the time argument t − 1 from the density notation: we write pj = pj (t − 1) for every j ∈ [k], p = p(t − 1), and pmax = pmax (t − 1). In particular, X X pi ≤ pmax , ∥p∥22 = p2j ≤ pmax pj = pmax . j

57

j

For Lemma 8.9(Item 1), choose a vertex V uniformly from [n], independently of the dynamics. Its current opinion has law p, and conditional on any choice of V , its h sampled opinions have law p⊗h , independently of its update rule. Thus the entire input vector has law p⊗(h+1) and is independent of the rule W. Averaging over V and applying Lemma 8.8, we obtain n

1X Pr [Cv (t) = i] = Pr [CV (t) = i] t−1 t−1 n v=1     h+1 pi ≤ pi 1 + h(h − 1)∥p∥22 + 2    h+1 ≤ pi + h(h − 1) + p2max ≤ pi + 2h2 p2max . 2
= (3h2 − h)/2 ≤ 2h2 . The last inequality uses h(h − 1) + h+1 2 For Lemma 8.9(Item 2), let X = (X1 , . . . , Xh ) ∼ p⊗h independently of W, and set Et−1 [pi (t)] =

ai = Pr[W(i, X) ̸= i]. This is the conditional probability that a vertex currently holding i leaves that opinion. There are npi such vertices, so Lemma A.3(Item 3) and Lemma 8.9(Item 1) give nVart−1 [pi (t)] ≤ Et−1 [pi (t)] − pi +

2 n

X

ai

v∈[n] Cv (t−1)=i

≤ 2h2 p2max + 2pi ai .

(55)

Let D be the event that i, X1 , . . . , Xh are pairwise distinct. By Definition 8.2 and independence of the rule and the samples, Pr[W(i, X) ̸= i, D] ≤ (1 − Pignore ) Pr[D] ≤ 1 − Pignore . A collision occurs precisely when some Xr = i or some Xr = Xs with r < s. Hence Pr[Dc ] ≤

h X

Pr[Xr = i] +

r=1

X

Pr[Xr = Xs ]

1≤r<s≤h

 X   h h = hpi + p2j = hpi + ∥p∥22 . 2 2 j

Splitting according to D and Dc therefore gives   h ai ≤ 1 − Pignore + hpi + ∥p∥22 . 2 Combining Eqs. (55) and (56) and using pi , ∥p∥22 ≤ pmax , we obtain     h nVart−1 [pi (t)] ≤ 2h2 p2max + 2pi 1 − Pignore + hpi + ∥p∥22 2
2 ≤ 2(1 − Pignore )pmax + 2h + 2h + h(h − 1) p2max
≤ 2(1 − Pignore ) + 5h2 pmax pmax . Here 2h2 + 2h + h(h − 1) = 3h2 + h ≤ 5h2 for h ≥ 1. Dividing by n proves the variance bound. 58

(56)

We are now ready to complete the proof of Theorem 8.4. Proof of Theorem 8.4. We prove the parameterized bound for Pignore -ignoring dynamics with     1   T = q    32 min h2 p (0) + 32h2 log n + h 32(1−Pignore ) log n , 1  max   n n

(57)

Write Pcomply = 1 − Pignore and set r 32 log n 1 32Pcomply log n + . L = pmax (0) + n h n l m 1 2 Then the time in the theorem is T = 32 min{h 2 L,1} . If 32h L ≥ 1, then T = 1, and the claim follows from pmax (0) < 1. Henceforth assume 32h2 L < 1, so that T ≤

1 1 +1≤ , 2 32h L 16h2 L

2L < 1.

(58)

Let A = {i ∈ [k] : pi (0) > 0}. By Definition 8.1, absent opinions cannot appear, and |A| ≤ n. Define τ = inf{t ≥ 0 : pmax (t) ≥ 2L}. Since pmax (0) ≤ L, we have τ ≥ 1. For each i ∈ A, define a stopped martingale by (i)

Yt

=

t X

1{τ >s−1} (pi (s) − Es−1 [pi (s)]) ,

(i)

Y0

= 0.

s=1

To check that it is a martingale, note that, for every s ≥ 1, (i)

Ys(i) − Ys−1 = 1{τ >s−1} (pi (s) − Es−1 [pi (s)]) . This expression has conditional mean zero given Fs−1 because {τ > s − 1} ∈ Fs−1 . Using Lemma 8.9(Item 1) and the telescoping sum, gives (i) pi (T ∧ τ ) − pi (0) = YT +

(i)

≤ YT +

T X s=1 T X

1{τ >s−1} (Es−1 [pi (s)] − pi (s − 1)) 1{τ >s−1} 2h2 pmax (s − 1)2

s=1 (i)

(i)

≤ YT + 8h2 L2 T ≤ YT +

L . 2

(59)

Here in the last two inequalities we have used that pmax (s − 1) < 2L on {τ > s − 1} and Eq. (58). (i) (i) By Lemma A.3(Item 4) and Lemma 8.9(Item 2), conditional on Fs−1 , Ys − Ys−1 satisfies the (1/n, s∗ )-Bernstein condition, where s∗ =

4Pcomply L + 20h2 L2 . n 59

(i)

(i)

Indeed, on {τ > s − 1}, Ys − Ys−1 satisfies the (1/n, s∗ )-Bernstein condition because
2Pcomply + 5h2 pmax (s − 1) pmax (s − 1) (2Pcomply + 10h2 L)2L ≤ = s∗ ; n n (i)

(i)

on {τ ≤ s − 1}, Ys − Ys−1 = 0. Thus, in Corollary A.5, we may take ss−1 = s∗ for every s ∈ [T ]. For every t ≤ T , this gives t X ss−1 = ts∗ ≤ T s∗ , s=1

so we may choose W = T s∗ in Corollary A.5. We first bound the denominator W + (hD)/3 in the exponent of Corollary A.5. Substituting h = L/2, D = 1/n, and W = T s∗ into that corollary, this denominator becomes T s∗ + L/(6n). Here h denotes the parameter of the corollary, not the number of sampled opinions. The definition of L gives Pcomply nL2 nL2 ≤ , L ≤ . h2 32 log n 32 log n Together with Eq. (58), these imply T s∗ +

  L 1 Pcomply 5L L ≤ + + 6n n 4h2 4 6   1 Pcomply 17L = + n 4h2 12   2 L 5L2 L2 1 17 + = ≤ . ≤ 4 12 32 log n 96 log n 16 log n

Apply Corollary A.5 with h = L/2, D = 1/n, and W = T s∗ . Since the event at time T is contained in the corresponding crossing event, we obtain     L L2 /8 (i) Pr YT ≥ ≤ exp − ≤ exp(−2 log n) = n−2 . (60) 2 T s∗ + L/(6n) If τ ≤ T , some i ∈ A satisfies pi (T ∧ τ ) = pi (τ ) ≥ 2L. (i) YT ≥ L/2. A union bound and Eq. (60) therefore yield Pr[τ ≤ T ] ≤

X i∈A

Since pi (0) ≤ L, Eq. (59) then gives

  L 1 (i) Pr YT ≥ ≤ |A|n−2 ≤ . 2 n

On {τ > T }, we have pmax (t) < 2L < 1 for every 0 ≤ t ≤ T , so consensus has not occurred by time T . Consequently, 1 Pr[τconsensus ≥ T ] ≥ Pr[τ > T ] ≥ 1 − , n as claimed. It remains to express (57) in the form stated in the theorem. Set r 32(1 − Pignore ) log n 32h2 log n 2 a = h pmax (0), b= , c=h . n n Writing M = max{min{a, 1}, min{b, 1}, min{c, 1}}, we have M ≤ min{a + b + c, 1} 60

≤ min{a, 1} + min{b, 1} + min{c, 1} ≤ 3M.

(61)

Taking reciprocals in (61) and using ⌈u⌉ = Θ(1 + u) for u > 0, the choice of T in (57) satisfies      1 1 1 1 = Θ 1 + min . (62) T =Θ 1+ , , M min{a, 1} b c Here a reciprocal with zero denominator is omitted; removing the truncations from b and c changes the expression by at most a constant factor because of the additive 1. Substituting a, b, c into (62) proves the parameterized bound in Theorem 8.4. When Pignore = 1, we have c = 0, so the same substitution gives (52) directly. Every neutral h-input dynamics is 0-ignoring. In this case, let r 32h2 log n , x= n so that b = x2 and c = x. Since x2 ≤ x when x ≤ 1, while both terms are absorbed by the truncation at 1 when x ≥ 1, we have
min{a + x + x2 , 1} = Θ min{a + x, 1} . (63) Consequently, setting Pignore = 0 in (57) and applying (63), followed by (61) with the three terms a, x, 0, gives    √ 1 n T = Ω 1 + min , √ . min{h2 pmax (0), 1} h log n This is the first bound in the theorem.

61

Acknowledgements The authors are grateful to Niccolò D’Archivio for facilitating the collaboration that led to this publication.

AI methodology We used GPT-5.4, GPT-5.5, GPT-5.6, and GPT-6 to assist with proofs and exposition. The key ideas originated with the authors. The tool materially affected the proofs in Sections 5 to 8. For the multinomial analysis (Section 5), we identified three regimes and attempted to formulate transport lemmas inspired by [dDGN25]. Given these regimes and our preliminary attempts, GPT-5.4 and later GPT-5.5 produced suitable transport lemmas and proofs by May 2026; earlier attempts without this guidance had been unsuccessful. We subsequently identified how to merge two of these regimes, further simplifying the analysis. For the plurality consensus section (Section 6), we proposed applying Freedman’s inequality [Fre75] to the multinomial estimates. GPT-5.5 produced a complicated proof with several phases, giving a first draft proof in June. Through subsequent iterations with GPT-5.6 and GPT-6, we substantially simplified and improved the argument to a single amplification phase. For the symmetry breaking section (Section 7), we also used GPT-6 to simplify proofs, including the design of potential functions and expectation calculations, and to help make a symmetry argument rigorous. The authors had independently developed a proof of the symmetry breaking result (Lemma 7.2) before discussions with AI led to the simpler potential-based argument presented in Lemma 7.4. As for the lower bound section (Section 8), the authors developed a weaker version of Theorem 1.3 which held only for dynamics where nodes adopt an opinion that is actually sampled. GPT-6 proposed a simple extension to dynamics where a node can retain its own opinion, which we further generalized by introducing the parameter Pignore . The authors verified the correctness and originality of all content, including references. This manuscript has been written by humans, for humans.

References [AABBHKL23]

Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. “Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model”. In: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC 2023). 2023, pp. 13–23. doi: 10.1145/3583668.3594589 (cit. on pp. 1, 7, 14).

[AAE07]

Dana Angluin, James Aspnes, and David Eisenstat. “A Simple Population Protocol for Fast Robust Approximate Majority”. In: Distributed Computing: 21st International Symposium (DISC 2007). 2007, pp. 20–32. doi: 10.1007/978-3-540-75142-7 5 (cit. on p. 14).

[BBBEHKK22]

Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. “Fast Consensus via the Unconstrained Undecided State Dynamics”. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022). 2022, pp. 3417–3429. doi: 10.1137/1.9781611977073.135 (cit. on pp. 1, 14).

62

[BCEKMN17]

Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. “Ignore or Comply? On Breaking Symmetry in Consensus”. In: Proceedings of the 2017 ACM Symposium on Principles of Distributed Computing (PODC 2017). 2017, pp. 335–344. doi: 10.1145/3087801.3087817 (cit. on pp. 1, 2, 9, 12, 13, 28, 29).

[BCGHKR23]

Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. “On the Hierarchy of Distributed Majority Protocols”. In: 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs). 2023, 23:1–23:19. doi: 10.4230/LIPICS.OPODIS.2022.23 (cit. on pp. 2, 9).

[BCN20]

Luca Becchetti, Andrea Clementi, and Emanuele Natale. “Consensus Dynamics”. In: ACM SIGACT News 51 (1 2020), pp. 58–104. doi: 10.1145/3388392.3388403 (cit. on pp. 1, 13).

[BCNPS15]

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. “Plurality Consensus in the Gossip Model”. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015. Ed. by Piotr Indyk. 2015, pp. 371– 390. doi: 10.1137/1.9781611973730.27 (cit. on pp. 1, 14).

[BCNPST17]

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. “Simple Dynamics for Plurality Consensus”. In: Distributed Computing 30.4 (2017), pp. 293–306. doi: 10.1007/s00446- 016- 0289- 4 (cit. on pp. 1, 2, 6, 13).

[BCNPT16]

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. “Stabilizing Consensus with Many Opinions”. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). 2016, pp. 620–635. doi: 10.1137/1.9781611974331.ch46 (cit. on pp. 1, 2, 13).

[BCPTVZ24]

Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. “The Minority Dynamics and the Power of Synchronicity”. In: Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024. Ed. by David P. Woodruff. 2024, pp. 4155–4176. doi: 10.1137/1.9781611977912.144 (cit. on pp. 1, 14, 54).

[BKN19]

Lucas Boczkowski, Amos Korman, and Emanuele Natale. “Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 Bits”. In: Distributed Computing 32.3 (2019), pp. 173–191. doi: 10.1007/s00446-0180330-x (cit. on p. 1).

[CEOR13]

Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. “Coalescing Random Walks and Voting on Connected Graphs”. In: SIAM Journal on Discrete Mathematics 27 (4 2013), pp. 1748–1758. doi: 10.1137/120900368 (cit. on p. 2).

[CGGNPS18]

Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. “A Tight Analysis of the Parallel UndecidedState Dynamics with Two Colors”. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). 2018, 28:1–28:15. doi: 10.4230/LIPICS.MFCS.2018.28 (cit. on pp. 1, 14).

63

[CMRSS25]

Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. “Asynchronous 3-Majority Dynamics with Many Opinions”. In: Proceedings of the 2025 ACM-SIAM Symposium on Discrete Algorithms (SODA 2025). 2025, pp. 4095–4131. doi: 10.1137/1.9781611978322.140 (cit. on pp. 1, 2, 5–7, 11, 13).

[CMRSS26]

Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions”. In: Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing (PODC 2026). 2026, pp. 77–87. doi: 10.1145/3796701.3815920 (cit. on pp. 1, 5, 7, 14).

[CR16]

Colin Cooper and Nicolás Rivera. “The Linear Voting Model”. In: Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP) (2016). doi: 10.4230/LIPIcs.ICALP.2016.144 (cit. on p. 14).

[DANM26]

Niccolò D’Archivio, Hind AlMahmoud, Emanuele Natale, and Frederik MallmannTrenn. “Order statistics in population protocols via simple dynamics”. en. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC ’26: ACM Symposium on Principles of Distributed Computing (Egham United Kingdom). 2026, pp. 425–436. doi: 10.1145/3796701.3815922 (cit. on p. 13).

[DAr26]

Niccolò D’Archivio. Consensus Time in 3-Majority and 2-Choices Is Determined by the Maximum Initial Opinion Density. 2026. doi: 10.48550/arXiv.2606.11778. arXiv: 2606.11778 [cs.DC] (cit. on pp. 1–3, 6, 12, 13, 56).

[DCN22]

Francesco D’Amore, Andrea Clementi, and Emanuele Natale. “Phase Transition of a Nonlinear Opinion Dynamics with Noisy Interactions”. In: Swarm Intelligence 16.4 (2022), pp. 261–304. doi: 10.1007/s11721-022-00217-w (cit. on p. 14).

[dDGGN26]

Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, Frédéric Giroire, and Emanuele Natale. “Brief Announcement: DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus”. In: Proceedings of the 2026 ACM Symposium on Principles of Distributed Computing (PODC 2026). 2026, pp. 437–440. doi: 10.1145/3796701.3815926 (cit. on pp. 1, 3, 6, 13, 55, 56).

[dDGN25]

Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, and Emanuele Natale. “On the h-Majority Dynamics with Many Opinions”. In: 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs). 2025, 27:1–27:24. doi: 10.4230/LIPICS.DISC.2025.27 (cit. on pp. 1–3, 6, 9, 62).

[DGMSS11]

Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. “Stabilizing Consensus with the Power of Two Choices”. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011). 2011, pp. 149–158. doi: 10.1145/1989493.1989516 (cit. on pp. 1, 7, 13, 39).

[DV26]

Niccolò D’Archivio and Robin Vacus. “On the limits of information spread by memory-less agents”. In: Distributed Comput. 39.1 (2026), p. 3. doi: 10.1007/S00446025-00500-Z (cit. on p. 14).

[dZ25]

Francesco d’Amore and Isabella Ziccardi. “Phase transition of the 3-majority opinion dynamics with noisy interactions”. In: Theoretical Computer Science 1028 (2025), p. 115030. doi: 10.1016/j.tcs.2024.115030 (cit. on p. 2).

64

[FGL15]

Xiequan Fan, Ion Grama, and Quansheng Liu. “Exponential inequalities for martingales with applications”. en. In: Electronic Journal of Probability 20 (2015), pp. 1–22. doi: 10.1214/EJP.v20-3496 (cit. on p. 67).

[Fre75]

David A. Freedman. “On Tail Probabilities for Martingales”. In: The Annals of Probability 3.1 (1975), pp. 100–118. doi: 10.1214/aop/1176996452 (cit. on pp. 62, 67).

[GL18]

Mohsen Ghaffari and Johannes Lengler. “Nearly-Tight Analysis for 2-Choice and 3-Majority Consensus Dynamics”. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018). 2018, pp. 305–313. doi: 10.1145/3212734.3212738 (cit. on pp. 1, 2, 5–7, 13).

[HP01]

Yehuda Hassin and David Peleg. “Distributed Probabilistic Polling and Applications to Proportionate Agreement”. In: Information and Computation 171.2 (2001), pp. 248–268. doi: 10.1006/inco.2001.3088 (cit. on pp. 1, 2, 13, 14).

[SS24]

Nobutaka Shimizu and Takeharu Shiraga. “Quasi-majority functional voting on expander graphs”. en. In: Random structures & algorithms (2024). doi: 10.1002/rsa. 21224 (cit. on pp. 1, 2).

[SS25]

Nobutaka Shimizu and Takeharu Shiraga. “3-Majority and 2-Choices with Many Opinions”. In: Proceedings of the 2025 ACM Symposium on Principles of Distributed Computing (PODC 2025). 2025, pp. 207–217. doi: 10.1145/3732772.3733511 (cit. on pp. 1–3, 5–7, 11, 13, 54, 65).

A

Tools

Definition A.1 (Bernstein condition ([SS25])). Let D and s be non-negative parameters. A random variable X satisfies (D, s)-Bernstein condition if for all λ ∈ R with |λ|D < 3,   λ2 s/2 λX E[e ] ≤ exp . 1 − (|λ|D)/3 It satisfies one-sided (D, s)-Bernstein condition if the same bound holds for all λ ≥ 0 with λD < 3. Lemma A.2 (Basic properties of Bernstein condition ([SS25])). Let X and Y be random variables. We have the following: 1. If E[X] = 0 and |X| ≤ D, then X satisfies (D, Var[X])-Bernstein condition. 2. If X satisfies (D, s)-Bernstein condition, then X satisfies (D′ , s′ )-Bernstein condition for any D′ ≥ D and s′ ≥ s. 3. If X satisfies (D, s)-Bernstein condition, then aX satisfies (|a|D, a2 s)-Bernstein condition for any a ∈ R. 4. If X satisfies one-sided (D, s)-Bernstein condition and Y ⪯ X, then Y satisfies one-sided (D, s)-Bernstein condition. such that each Xi satisfies (D, si )-Bernstein 5. If X1 , . . . , Xn are Pnindependent randomPvariables n condition, then i=1 Xi satisfies (D, i=1 si )-Bernstein condition. 6. If X1P , . . . , Xn are random variables such that each Xi satisfies (D, si )-Bernstein condition, Pn n then i=1 Xi satisfies (nD, n i=1 si )-Bernstein condition. 65

We use the notation of Section 2 for a general opinion process. Lemma A.3. Suppose that, for every t ≥ 0, the random variables (Cv (t + 1))v∈[n] are conditionally independent given Ft . Then, for every t ≥ 0 and i ∈ [k], the following hold conditional on Ft : 1. If Prt [Cv (t + 1) = i] does not depend on v ∈ [n], then Et [pi (t + 1)] = Prt [Cv (t + 1) = i]. 2. Vart [pi (t + 1)] ≤ Et [pin(t+1)] .   P 3. Vart [pi (t + 1)] ≤ n1 Et [pi (t + 1)] − pi (t) + n2 v∈[n]:Cv (t)=i Prt [Cv (t + 1) ̸= i] .
4. pi (t + 1) − Et [pi (t + 1)] satisfies n1 , Vart [pi (t + 1)] -Bernstein condition. Proof of Lemma A.3(Item 1). Since Prt [Cv (t + 1) = i] does not depend on v ∈ [n], we obviously obtain 1 X 1 X Et [1{Cv (t+1)=i} ] = Pr[Cv (t + 1) = i] = Pr[Cv (t + 1) = i]. Et [pi (t + 1)] = t t n n v∈[n]

v∈[n]

Proof of Lemma A.3(Item 2). From the independence of (Cv (t + 1))v∈[n] , we have i E [p (t + 1)] 1 X 1 X h 2 t i Vart [pi (t + 1)] = 2 Vart [1{Cv (t+1)=i} ] ≤ 2 Et 1{Cv (t+1)=i} = . n n n v∈[n]

v∈[n]

1 P

Note that Et [pi (t + 1)] = n

v∈[n] Et [1{Cv (t+1)=i} ].

Proof of Lemma A.3(Item 3). We have Vart [pi (t + 1)] = Vart [pi (t + 1) − pi (t)]   1 X = 2 Vart 1{Cv (t+1)=i} − 1{Cv (t)=i} n v∈[n]
2 i 1 X h Et 1{Cv (t+1)=i} − 1{Cv (t)=i} ≤ 2 n v∈[n]

 1 X  Et 1{Cv (t+1)=i} − 1{Cv (t)=i} + 21{Cv (t)=i} 1 − 1{Cv (t+1)=i} 2 n v∈[n]   X 1 2 Pr[Cv (t + 1) ̸= i]. = Et [pi (t + 1)] − pi (t) + t n n

=

v∈[n]:Cv (t)=i

Note that (a − b)2 = a − b + 2b(1 − a) holds for any a, b ∈ {0, 1}. −Et [1

1

]

Proof of Lemma A.3(Item 4). Write Yv = {Cv (t+1)=i} n {Cv (t+1)=i} for convenience. Then, pi (t + P 1) − Et [pi (t + 1)] = v∈[n] Yv . Note that (Yv )v∈[n] are independent random variables. Applying  P  Lemma A.2 (Item 5) shows that pi (t + 1) − Et [pi (t + 1)] satisfies n1 , v∈[n] Vart [Yv ] -Bernstein condition. Since   X X Vart [Yv ] = Vart  Yv  = Vart [pi (t + 1) − Et [pi (t + 1)]] = Vart [pi (t + 1)], v∈[n]

v∈[n]

we obtain the claim. 66

Theorem A.4 (Theorem 2.6 of [FGL15]). Let (Xt )t∈N0 be a real-valued supermartingale associated with a filtration (Ft )t∈N0 . Assume that Vt−1 , t ∈ [T ] are positive and Ft−1 -measurable random variables. Suppose that Et−1 [exp(λ(Xt − Xt−1 ))] ≤ exp(f (λ)Vt−1 ) holds for all t ∈ [T ] and for a positive function f for some λ ∈ (0, ∞). Then, for all h, W > 0, " # t X Pr ∃t ≤ T, Xt − X0 ≥ h and Vi−1 ≤ W ≤ exp (−λh + f (λ)W ). i=1

Corollary A.5. Let (Xt )t∈N0 be a real-valued supermartingale associated with a filtration (Ft )t∈N0 . Suppose that, for every t ≥ 1, conditional on Ft−1 , the difference Xt − Xt−1 satisfies the one-sided (D, st−1 )-Bernstein condition. Then, for any h, W > 0, " #   t X h2 /2 . Pr ∃t ≤ T, Xt − X0 ≥ h and si−1 ≤ W ≤ exp − W + (hD)/3 i=1

2

λ /2 h Proof. We apply Theorem A.4 with the following parameters: λ = W +(hD)/3 , f (λ) = 1−(λD)/3 , Vt = st . Note that Et−1 [exp(λ(Xt − Xt−1 ))] ≤ exp(f (λ)st−1 ) holds from the assumption that Xt − Xt−1 satisfies one-sided (D, st−1 )-Bernstein condition. Then, we obtain " #   t X λ2 /2 Pr ∃t ≤ T, Xt − X0 ≥ h and si−1 ≤ W ≤ exp −λh + W 1 − (λD)/3 i=1   h2 /2 = exp − . W + (hD)/3

We obtain the following two-sided form of Freedman’s inequality [Fre75]. Corollary A.6 (Freedman’s inequality). Let (Mt )N t=0 be a martingale with respect to a filtration (Gt )N , and assume M = 0. Let ξ = M − M for 1 ≤ t ≤ N . Assume |ξt | ≤ B almost surely 0 t t t−1 t=0 for every 1 ≤ t ≤ N . Let t X   Vt = E ξs2 | Gs−1 . s=1

Then, for every r > 0 and every V > 0,  Pr[∃t ≤ N : |Mt | ≥ r and Vt ≤ V ] ≤ 2 exp −

r2 2(V + Br/3)

 .

Proof. Since Mt is a martingale, E[ξt | Gt−1 ] = 0. By the first item of Lemma A.2, conditional on Gt−1 , both ξt and −ξt satisfy the one-sided (B, st−1 )-Bernstein condition, where   st−1 = E ξt2 | Gt−1 . Extend Mt to be constant after time N P. Apply Corollary A.5 to Mt and −Mt with D = B, h = r, W = V , and T = N . For both signs, ti=1 si−1 = Vt . A union bound over the two signs gives the result.

67

Related documents

• Random sample consensus#6334
• RAFT Consensus Reliability in Wireless Networks: Probabilistic Analysis#16717
• The threshold for online balancing of i.i.d. binary vectors#1084877
• Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold#1400220
• Consensus Formation and Change are Enhanced by Neutrality.#351734