Paper deep dive
DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus
Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, Frédéric Giroire, Emanuele Natale
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 94%
Last extracted: 4/10/2026, 1:57:34 AM
Summary
The paper introduces 'DéjàVu', a minimalistic distributed consensus mechanism where agents query neighbors until they encounter a duplicate opinion, which they then adopt. This protocol avoids the need for counters or fixed sample sizes required by traditional h-Majority dynamics. The authors provide a rigorous analysis demonstrating that DéjàVu is competitive with h-Majority in convergence time and often more communication-efficient, while also establishing a theoretical framework linking the protocol to Poisson clock races and generalized birthday paradoxes.
Entities (4)
Relation Signals (3)
DéjàVu → solves → Plurality Consensus
confidence 95% · We propose a new, extremely simple mechanism called DéjàVu... yielding a powerful primitive for plurality consensus.
DéjàVu → iscompetitivewith → h-Majority
confidence 90% · demonstrates that it is competitive with h-majority and, in some regimes, substantially more communication-efficient
DéjàVu → operatesin → PULL(h) model
confidence 90% · Our main result is a high-probability bound on the convergence time of DéjàVu in the PULL(h) model.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of k opinions, aims to agree on the initially most frequent one. In this setting, h-majority is arguably the simplest and most studied protocol, in which each agent samples the opinion of h neighbors uniformly at random and updates its opinion to the most frequent value in the sample. We propose a new, extremely simple mechanism called DéjàVu: an agent queries neighbors until it encounters an opinion for the second time, at which point it updates its own opinion to the duplicate value. This rule does not require agents to maintain counters or estimate frequencies, nor to choose any parameter (such as a sample size h); it relies solely on the primitive ability to detect repetition. We provide a rigorous analysis of DéjàVu that relies on several technical ideas of independent interest and demonstrates that it is competitive with h-majority and, in some regimes, substantially more communication-efficient, thus yielding a powerful primitive for plurality consensus.
Tags
Links
- Source: https://arxiv.org/abs/2604.03648v2
- Canonical: https://arxiv.org/abs/2604.03648v2
Trouble viewing inline? Open PDF directly →
Full Text
187,499 characters extracted from source content.
Expand or collapse full text
DéjàVu: A Minimalistic Mechanism for Distributed Plurality Consensus Francesco d’Amore Gran Sasso Science Institute, Italy Niccolò D’Archivio INRIA, COATI, Université Côte d’Azur, France George Giakkoupis INRIA Rennes Frédéric Giroire INRIA, COATI, Université Côte d’Azur, France Emanuele Natale INRIA, COATI, Université Côte d’Azur, France Abstract We study the plurality consensus problem in distributed systems where a population of extremely simple agents, each initially holding one of k opinions, aims to agree on the initially most frequent one. In this setting, h-Majority is arguably the simplest and most studied protocol, in which each agent samples the opinion of h neighbors uniformly at random and updates its opinion to the most frequent value in the sample. We propose a new, extremely simple mechanism called DéjàVu: an agent queries neighbors until it encounters an opinion for the second time, at which point it updates its own opinion to the duplicate value. This rule does not require agents to maintain counters or estimate frequencies, nor to choose any parameter (such as a sample size h); it relies solely on the primitive ability to detect repetition. We provide a rigorous analysis of DéjàVu that relies on several technical ideas of independent interest and demonstrates that it is competitive with h-Majority and, in some regimes, substantially more communication-efficient, thus yielding a powerful primitive for plurality consensus. 1 Introduction Plurality consensus is a fundamental problem in distributed computing and multi-agent systems, where a collection of agents, each initially holding one of k possible opinions, seeks to agree on the initially most frequent opinion [BCN20]. This problem serves as a building block for various distributed tasks, with fundamental applications that range from coordination in swarm robotics to modeling collective behavior in biology [FN19]. The core challenge in these scenarios lies in achieving consensus rapidly and reliably using agents with limited memory, computational power, and local information, often in the absence of a central coordinator or global identifiers [SHA07]. A standard approach to plurality consensus is the h-Majority dynamics, in which an agent queries h random neighbors and updates its opinion to the majority among them (if one exists) [BCN+17]. The underlying communication model is the ℒℒPULL(h) model where, at each discrete-time round, each agent can observe the opinion of a sample of agents of size h, sampled independently and uniformly at random [DGH+87]. While h-Majority is effective and has been extensively analyzed [DDG+25, CMR+25], it requires agents to query a fixed number of neighbors and perform a count-based comparison. This implies a need for explicit counting capabilities and knowledge of the parameter h. Motivated by the quest for minimal computational assumptions, relevant for molecular computing, nanorobotics, or biological modeling [FHK17, FNR24], we ask: is it possible to achieve efficient plurality consensus without explicit counting? We answer this question affirmatively by proposing and analyzing DéjàVu, a minimal protocol based solely on repetition detection. In the DéjàVu protocol, an agent does not count or collect a fixed number of samples. Instead, it sequentially queries neighbors and stops as soon as it sees the same opinion for the second time. It then adopts this “duplicate” opinion as its new state. This rule relies exclusively on the ability to recognize a previously seen value within a short sampling window, a primitive operation that is simpler than arithmetic counting. Our main contribution is a rigorous analysis of DéjàVu that demonstrates its efficiency and robustness. We prove that, starting from a configuration with sufficient bias toward a plurality opinion, the system converges to consensus on that opinion with high probability. Our analysis shows that DéjàVu acts as a powerful amplifier of plurality bias. Moreover, DéjàVu is not only competitive with the h-majority rule, but in some regimes can be more communication-efficient. Specifically, we upper bound with high probability the total number of samples required by DéjàVu until consensus, showing that this quantity adapts naturally to the distribution of opinions and can be smaller than that of a fixed-h rule when the plurality opinion has large enough support. We present a more detailed overview of our results in Section 1.1. Our analysis relies on several technical contributions of independent interest. First, we establish an exact equivalence between the DéjàVu dynamics and Poisson clock races, providing a robust framework for analyzing sampling-based stopping times. Second, we prove the bias-amplification property of the protocol by leveraging Newton’s inequalities on elementary symmetric sums of the opinion frequencies. This allows us to show that the probability ratio of adopting the plurality opinion is monotone in the sample size. Finally, we characterize the protocol’s communication complexity as a function of the ℓ2 _2-norm of the opinion distribution through a generalized birthday paradox analysis, demonstrating its inherent adaptivity to the system’s state. A more detailed overview of our technical contributions is given in Section 1.2. The protocol’s connection to Poisson races, a framework often used to model decision-making in neural systems [TOW83], suggests that DéjàVu may also serve as a plausible model for biological consensus, where exact counting is cognitively expensive [DHN22]. However, our primary focus is its effectiveness as a distributed algorithm. By replacing fixed sample sizes with a dynamic stopping condition, DéjàVu offers a novel design principle for distributed consensus that prioritizes agent simplicity and communication efficiency. 1.1 Our Contribution Our main result is a high-probability bound on the convergence time of DéjàVu in the ℒℒPULL(h) model. Here and throughout the paper, w.h.p. means with probability at least 1−1/nc1-1/n^c for some constant c>0c>0, where n is the number of nodes. In the following, given any round t≥0t≥ 0, we denote by C(t)=(C1(t),…,Ck(t))C^(t)=(C_1^(t),…,C_k^(t)) the configuration of the system at round t, that is, Ci(t)C_i^(t) denotes the number of nodes supporting opinion i at time t. We omit the dependence on t when it is clear from the context. Theorem 1. Let h≥2h≥ 2 and C=(C1,…,Ck)C=(C_1,…,C_k) be an initial system configuration where each agent supports an opinion in 1,…,k\1,…,k\, with C1≥C2≥⋯≥CkC_1≥ C_2≥·s≥ C_k. Assume that C1=ω(logn)C_1=ω ( n ) and that, for a large enough constant λ>0λ>0, C1−C2≥λmaxnh2,C1logn.C_1-C_2≥λ \ nh^2,C_1 \ n. DéjàVu converges to consensus on the first opinion w.h.p. in O((n(h2C1)+1)logn)O ( ( n(h^2C_1)+1) n ) rounds. We emphasize that the hypotheses of the previous theorem are very general compared with the state of the art for h-Majority. The condition C1=Ω(logn)C_1= ( n ) is necessary for any high-probability guarantee. Moreover, when C1≥n/h2C_1≥ n/h^2, the required bias is essentially optimal, since it matches the scale of the standard deviation. This is the case, for instance, as soon as h≥kh≥ k. Furthermore, the convergence time is essentially optimal, as we discuss below. We remark that a general upper bound on the convergence time of h-Majority matching the Ω(k/h2) (k/h^2) lower bound shown in [BCN+17] is still an open problem, with ongoing recent progress [DDG+25]. Our next result is a generalization of the previous lower bound, which allows for a more general comparison of DéjàVu with h-Majority. Theorem 2 (Generalization of Theorem 4.12 in [BCN+17]). Let ε>0 >0 be any arbitrarily small constant and C=(C1,…,Ck)C=(C_1,…,C_k) be the starting system configuration, with C1≥…≥CkC_1≥…≥ C_k and C1≤n/100C_1≤ n/100. For h=Ω(n3/4+ε/C1)h= (n^3/4+ /C_1), w.h.p., h-Majority requires at least Ω(n/(h2C1)+1) (n/(h^2C_1)+1 ) rounds to reach consensus. Thus, the convergence times of DéjàVu and h-Majority match over a wide range of configurations. Our next theorem compares the number of samples required by DéjàVu and h-Majority until consensus, and shows that DéjàVu is more sample-efficient over a large range of configurations. In fact, we conjecture that DéjàVu is always more sample-efficient than h-Majority. Theorem 3. Let C=(C1,…,Ck)C=(C_1,…,C_k) be a system configuration such that C1≥⋯≥CkC_1≥·s≥ C_k, C1=ω(log2n)C_1=ω ( ^2n ), and that, for a large enough constant λ>0λ>0, C1−C2≥λmaxnh2,C1logn.C_1-C_2≥λ \ nh^2,C_1 \ n. Let SdS_d and SmS_m be the numbers of samples until consensus of, respectively, DéjàVu and h-Majority. Fix any arbitrarily small constant ε>0 >0. For h=Ω(minn3/4+ε/C1,n/C1)h= ( \n^3/4+ /C_1, n/C_1\), w.h.p. we have Sd⋅O(max1,h‖C‖2n)log3n≤Sm if ‖C‖2=O(nlogn) and h‖C‖2≥nlogn,Sd⋅O(max1,h‖C‖2n)logn≤Sm otherwise. cases&S_d· O ( \1,h C_2n )\ ^3n≤ S_m if C_2=O( n n) and h C_2≥ n n,\\ &S_d· O ( \1,h C_2n )\ n≤ S_m otherwise. cases As soon as h‖C‖2≫nlog3nh C_2 n ^3n and C1−C2=ω(C1logn)C_1-C_2=ω( C_1 n), it is guaranteed that Sd<SmS_d<S_m. In particular, if the lower bound on h-Majority does not apply, a node running h-Majority still samples at least h opinions in the first round. In this regime, Theorem 3 shows that the average number of samples per node before convergence in DéjàVu is either competitive with or strictly smaller than that of h-Majority. Roadmap. The rest of the paper is organized as follows. In Section 1.2, we provide an overview of the main technical ideas behind the proofs of our results, and in Section 2 we discuss related work. In Section 3, we introduce the model and the notation used throughout the paper. Sections 4, 5 and 6 contain the analysis of the bias amplification mechanism of DéjàVu, leading to the proof of Theorem 1. The lower bound for h-Majority (Theorem 2) is proved in Section 7, and the sample-efficiency result (Theorem 3) is proved in Section 8. We conclude with open questions in Section 9. 1.2 Main Technical Ideas In this section we highlight the original technical ideas used in the proof of our main theorems. In the following, let C=(C1,…,Ck)C=(C_1,…,C_k) be the configuration of the system at a given time, where CiC_i is the number of nodes supporting opinion i, and let pi=Ci/np_i=C_i/n be the corresponding density. Let p=(p1,…,pk)p=(p_1,…,p_k) denote the vector of opinion densities. We assume without loss of generality that C1≥…≥CkC_1≥…≥ C_k. For every i∈[k]i∈[k], let Ci′C_i be the random variable counting the number of nodes supporting opinion i at the next round. Let ℳiM_i be the event that an agent updates to opinion i when the number of samples is unbounded. A key idea in the proof of Theorem 1 is to study the ratio Pr(ℳ1∣C)Pr(ℳ2∣C), (M_1 C ) (M_2 C ), namely, the ratio between the probability of updating to the plurality opinion and the probability of updating to the second most frequent opinion. Poisson race in the ℒℒ∗PULL^* model for bias amplification. To bound the aforementioned ratio, we couple the DéjàVu process to a continuous-time process, inspired by the technique of Poisson approximation for Balls-into-Bins processes [MU05]. This equivalence is given in Section 4, and the resulting continuous-time process turns out to be an instance of a so-called Poisson race problem [RUA07], where we are required to estimate the probability that a certain Poisson clock is the first to ring for the second time. Our result is also new in that context and of independent interest. Such estimation, combined with a way to decompose the probability ratio given in Section 4, allows us to prove that (pipj)2≥Pr(ℳi∣C)Pr(ℳj∣C)≥(pipj)2pi+3pj3pi+pj, ( p_ip_j )^2≥ (M_i C ) (M_j C )≥ ( p_ip_j )^2 p_i+3p_j3p_i+p_j, for each i≤ji≤ j (see Lemma 4). The previous inequality is derived in a model in which an agent can collect arbitrarily many samples, which we denote by ℒℒ∗PULL^*. In the ℒℒPULL(h) model, where DéjàVu(h) can collect at most h samples, many agents do not see a repeated opinion and therefore keep their current opinion. From ℒℒ∗PULL^* to ℒℒPULL(h). In order to relate the two models, we thus need to estimate the probability ratio when we condition on the event that an agent sees an opinion twice within its h samples, and to estimate how many agents will actually update. The first part is given in Section 5, where we leverage Newton’s inequalities for symmetric polynomials (Lemma 54) to prove the following key result (formally stated in Lemma 6). Let H be the number of samples until an agent samples an opinion a second time. Then, for all opinions i,j∈[k]i,j∈[k] such that pi≥pjp_i≥ p_j, and for all h=2,…,k+1h=2,…,k+1, we have (pipj)2≥Pr(ℳi,H≤h∣C)Pr(ℳj,H≤h∣C)≥Pr(ℳi∣C)Pr(ℳj∣C). ( p_ip_j )^2≥ (M_i,H≤ h C ) (M_j,H≤ h C )≥ (M_i C ) (M_j C )~. In other words, truncating the sample size at h can only improve the ratio of the winning probabilities. The second part is to estimate the number of agents that will actually update by sampling twice an opinion. We do so by proving upper and lower bounds on the probability that a repeated opinion appears within the first h samples, namely a generalized birthday paradox for a non-uniform distribution. The lower bound relies on a Chen-Stein estimate due to Arratia et al. [AGG89]. We remark that the aforementioned question can be viewed as a generalized birthday paradox over a non-uniform distribution, a fundamental problem that is of independent interest [GH12]. We obtain the following lemma, which we prove in Section 5.1 (Lemma 9). Let D be the number of agents that see an opinion twice within the first h samples, for any given h≥2h≥ 2. Then, [D∣C]=n⋅Θ(minh2‖p‖22,1)if h‖p‖2=o(1),Θ(n)otherwise. E[D C]= casesn· ( \h^2\|p\|_2^2,1\ )&if h\|p\|_2=o(1),\\ (n)&otherwise. cases Expected amplification of the bias in ℒℒPULL(h). In Section 6.1, we combine previous results and algebraic manipulations to get a lower bound on the amplification of the multiplicative bias in expectation: [C1′∣C][Ci′∣C]≥C1Ci+Ω(minC1nh2,1)(C1Ci−1). E[C _1 C] E[C _i C]≥ C_1C_i+ ( \ C_1nh^2,1 \ ) ( C_1C_i-1 )~. We turn the previous inequality into an expected additive amplification for the bias in Section 6.2, as follows. Let the current and next bias be Δi=C1−Ci _i=C_1-C_i and Δi′=C1′−Ci′ _i =C_1 -C_i , respectively. Then, it holds that [Δj′∣C]≥Δj(1+Ω(minC1nh2,1)). E[ _j C]≥ _j (1+ ( \ C_1nh^2,1 \ ) ). Amplification of the bias in concentration. We use Bernstein’s inequality to obtain concentration around the preceding estimate and to show that the bias-growth condition is preserved from one round to the next. In Lemma 27 we prove that Pr(Δi′≥Δi(1+Ω(minC1nh2,1))∣C)≥1−n−Θ(1), ( _i ≥ _i (1+ ( \ C_1nh^2,1 \ ) ) C )≥ 1-n^- (1), whenever C1=Ω(logn)C_1= ( n), C1≤3n/4C_1≤ 3n/4, and Δi≥λmaxnh2,C1logn, _i≥λ \ nh^2,C_1 \ n, for a sufficiently large constant λ>0λ>0. The proof splits into two regimes, depending on whether nC1nC_1 is at most or at least a constant multiple of ‖C‖22\|C\|_2^2. In the genuinely unbalanced regime, we prove stronger expectation bounds both for the bias and for the plurality opinion, which compensate for the larger concentration error. Combining these ingredients, we show that the bias condition can be iterated round by round until the plurality opinion exceeds 3n/43n/4. More precisely, we prove that C1C_1 exceeds 3n/43n/4 within O((nh2C1+1)logn)O ( ( nh^2C_1+1 ) n ) rounds w.h.p. Once this threshold is reached, we merge all non-plurality opinions into a single competing opinion and prove, via a coupling argument, that this binary process stochastically dominates the remaining consensus time of the original process. In the binary setting, DéjàVu coincides with 22-Choices when h=2h=2, and with 33-Majority when h>2h>2, so the remaining time to consensus is O(logn)O( n) w.h.p. Lower bound for h-Majority. There is a known lower bound of Ω(k/h2+1) (k/h^2+1) rounds for the h-Majority dynamics when h=Ω(k/n1/4−ε)h= (k/n^1/4- ) by [BCN+17], which holds w.h.p. In Section 7 we take inspiration from the proof technique of [BCN20] and generalize the lower bound to Ω(n/(C1h2)+1) (n/(C_1h^2)+1) rounds for the h-Majority dynamics when h=Ω(n3/4+ε/C1)h= (n^3/4+ /C_1). The argument essentially consists in showing that any opinion cannot grow faster than a multiplicative factor 1+h2C1/n1+h^2C_1/n every round w.h.p. with the right initial conditions. Number of samples. In Section 8 we study the number of samples required by DéjàVu to converge in ℒℒPULL(h). In this part, we assume C1=ω(log2n)C_1=ω( ^2n), as required by our sample-complexity theorem. First, in Section 8.1 we prove that, in all majority-boosting opinion dynamics, the 2-norm of the configuration is a submartingale. We say that a dynamics is majority boosting whenever Ci≥Cj>0C_i≥ C_j>0 implies (Ci′∣C)(Cj′∣C)≥CiCj E (C _i C ) E (C _j C )≥ C_iC_j. Inspired by [S25], which studies the evolution of the configuration norm for both the 33-Majority and the 22-Choices dynamics, we then use a one-sided Bernstein-type inequality (Freedman’s inequality) to show that, with high probability, the 2-norm of the configuration does not decrease significantly throughout the execution of DéjàVu (see Section 8.2). More specifically, if C(t)C^(t) denotes the configuration of the system at time t≥0t≥ 0, we show that ‖C(t)‖22=Ω(‖C(0)‖22) C^(t)_2^2= ( C^(0)_2^2) for all rounds t up to consensus time, from which our stated sample-complexity bound follows. Finally, in Section 8.3 we leverage the lower bound on the consensus time for the h-Majority dynamics to compare the number of samples needed for consensus by DéjàVu with that needed by the h-Majority dynamics. 2 Related Work The study of DéjàVu falls within the broader area of opinion dynamics, and more generally simple computational dynamics [MT17, BCN20]. Informally, these are synchronous consensus protocols based on simple update rules that do not change over time. Well-studied examples include the h-Majority dynamics, the Undecided-State dynamics, and the 22-Choices dynamics. In this section, we summarize the results most closely related to our contribution. As throughout the paper, whenever we refer to a configuration C=(C1,…,Ck)C=(C_1,…,C_k), we assume without loss of generality that C1≥⋯≥CkC_1≥·s≥ C_k. In particular, C1C_1 denotes the plurality opinion, and the additive bias of the configuration is at least C1−C2C_1-C_2. Unless otherwise specified, all statements in this section hold w.h.p. We stress that our focus is on plurality consensus, i.e., convergence to the initially most supported opinion, rather than consensus to an arbitrary opinion. Accordingly, when summarizing prior work, we distinguish between results that guarantee plurality consensus and those that only guarantee consensus to some opinion. The closest works to our contribution are those analyzing the h-Majority dynamics, which has been widely investigated in the distributed computing community [BCN+17, BCE+17, BCG+22, GL18, CMR+25, S25, DDG+25]. Most previous works analyzed the 33-Majority dynamics, that is, the h-Majority when h=3h=3. The first work providing bounds on the 33-Majority dynamics was [BCN+17] (presented at SPAA’14), which established an O(λlogn)O(λ n) upper bound on the convergence time, w.h.p., provided that C1≥n/λC_1≥ n/λ and that the bias is Ω(λnlogn) ( λ n n). They further showed that h-Majority cannot converge in less than Ω(n/h2) (n/h^2) rounds from certain configurations. Subsequently, [BCN+16] established an upper bound of O((k2logn+klogn)(k+logn))O ((k^2 n+k n)(k+ n) ) rounds to reach consensus that holds w.h.p., with the hypothesis that the number of opinions k initially present satisfies k≤nαk≤ n^α for a suitable positive constant α<1α<1. Later, the bound was improved in [BCN+17], which showed an upper bound of O(mink,(n/logn)1/3logn)O( \k,(n/ n)^1/3\ n) rounds that holds w.h.p., provided that the bias of the initial configuration is at least cmin2k,(n/logn)1/3nlognc \2k,(n/ n)^1/3\n n for some constant c>0c>0. In the same work, the authors also proved a lower bound of Ω(klogn) (k n) rounds to reach consensus w.h.p. when the initial configuration is almost balanced, namely when C1≤n/k+(n/k)1−εC_1≤ n/k+(n/k)^1- for some ε>0 >0 and k≤(n/logn)1/4k≤(n/ n)^1/4. The 33-Majority dynamics is closely related to another popular process, the 22-Choices dynamics, defined as follows: each agent samples two neighbors u.a.r. with repetition, observes their opinions, and adopts that opinion if the two samples agree; otherwise, it keeps its current opinion. It can be viewed as a variant of 33-Majority in which one of the three opinions is the agent’s current opinion, so that ties are broken in favor of the current state. Despite being very similar, it has been shown that the two dynamics exhibit different behaviors. [BCE+17] proved a generic lower bound of Ω(mink,n/logn) ( \k,n/ n\) rounds to reach consensus starting from the initial perfectly balanced configuration that holds w.h.p. for the 22-Choices dynamics. Furthermore, they proved that the 33-Majority dynamics works better in symmetric configurations (i.e., with no initial bias) when, e.g., maxi∈[k]0(i)=O(logn) _i∈[k]\c_0(i)\=O( n). In particular, the 33-Majority reaches consensus in time at most O(n3/4log7/8n)O(n^3/4 ^7/8n) w.h.p., regardless of further assumptions on the initial configuration, whereas the 22-Choices requires time Ω(n/logn) (n/ n) whenever C1=O(logn)C_1=O( n). The authors of [BCE+17] were the first to notice that, when the number of opinions k is large, the 33-Majority dynamics is polynomially (in k) faster than the 22-Choices dynamics. The work [GL18] improved upon [BCN+17] and showed that the convergence time to consensus is O(klogn)O(k n), with high probability, for both the 22-Choices dynamics with k=O(n/logn)k=O( n/ n) and the 33-Majority dynamics with k=O(n1/3/logn)k=O(n^1/3/ n) opinions. This upper bound is tight because it matches the lower bound by [BCN+17], at least as long as k≤(n/logn)1/4k≤(n/ n)^1/4. Furthermore, the authors showed that the unconditional convergence time of the 33-Majority dynamics is O(n2/3log3/2n)O(n^2/3 ^3/2n) w.h.p., without any further hypothesis. A more recent work [S25] provided the tightest analysis of both the 33-Majority and the 22-Choices dynamics. The authors proved that, w.h.p., the 33-Majority dynamics reaches consensus in O(klogn)O(k n) rounds if k=o(n/logn)k=o( n/ n), while it takes time O(nlog2n)O( n ^2n) for other values of k. Furthermore, they showed that plurality consensus is ensured w.h.p. as long as the initial bias is ω(nlogn)ω( n n). As for the 22-Choices dynamics, they proved that, w.h.p., it reaches consensus in O(klogn)O(k n) rounds if k=o(n/log2n)k=o(n/ ^2n), while it takes time O(nlog3n)O(n ^3n) otherwise. In this case, plurality consensus is ensured w.h.p. as long as the initial bias is ω(C1logn)ω( C_1 n), which matched the lower bound given by [BCE+17] up to logarithmic factors. As for the asynchronous setting, [BCG+22] showed that the dynamics converges in O(nlogn)O(n n) rounds w.h.p., when k=2k=2. A more general result was given in [CMR+25], which proved that the convergence time is O(minknlog2n,n3/2log3/2n)O( \kn ^2n,n^3/2 ^3/2n\), w.h.p., for any number of initial opinions. [CMR+25] also provided a generic lower bound of Ω(minkn,n3/2/logn) ( \kn,n^3/2/ n\) rounds to reach consensus that holds w.h.p. when the initial configuration is almost-balanced. Other works analyzed the 33-Majority dynamics in settings in which communication can be corrupted by some form of noise, which tries to capture the instability of real-world environments [DZ22, DZ25], while others analyzed the process when one opinion is preferred, in the sense that there is some probability that an agent spontaneously adopts the preferred opinion [LGP22, CMQ+23]. The regime h≫1h 1 is much less understood. The authors of [BCG+22] showed that, when k=2k=2, the h-Majority exhibits a probabilistic hierarchy: for any given t, the probability that the h-Majority converges to consensus within time t is smaller than that of the (h+1)(h+1)-majority dynamics. Whether the hierarchy holds for the general case with k>2k>2 is still open. For large h, the work [BCN+17] provided a lower bound of Ω(k/h2+1) (k/h^2+1) rounds to reach consensus that holds w.h.p. The only matching upper bound in the literature was recently provided by [DDG+25], which showed that h-Majority converges in O(logn)O( n) rounds whenever h=ω(nlogn/C1)h=ω(n n/C_1), C1=ω(logn)C_1=ω( n), and the initial bias is ω(C1)ω( C_1). This result showed that the lower bound of Ω(k/h2+1) (k/h^2+1) rounds to reach consensus that holds w.h.p. by [BCN+17] cannot be pushed further than Ω(klog2n/h+1) (k ^2n/h+1) in the worst case. The general case with arbitrary h and no initial bias is a major open question in the area. Before providing a direct comparison of DéjàVu with the h-Majority and the 22-Choices dynamics, we briefly summarize the results on the Undecided-State dynamics. In the Undecided-State dynamics, at each round, each agent pulls a single neighboring opinion x uniformly at random. If the agent’s former opinion y differs from x, the agent becomes undecided. Once undecided, the agent adopts the next opinion it encounters. It was first introduced by [AAE08], and then multiple papers analyzed its behavior [PVV09, CGG+18, AAB+23, B+22, EES25, BCN+15], even in the presence of noisy communication [DCN20, DCN22] or stubborn agents [BBH24]. We do not provide a full overview of the literature on the Undecided-State dynamics, but we mention that in the synchronous setting [BCN+15] proved convergence in time O(klogn)O(k n) whenever k=O((nlogn)1/3)k=O((n n)^1/3), w.h.p. In [AAB+23], the authors investigate the asynchronous setting and prove that the protocol converges to consensus in O(knlogn)O(kn n) rounds, w.h.p., whenever k≤nlog2nk≤ n ^2n. These results are tight as [EES25] proved a lower bound for the asynchronous setting: they showed that the protocol takes at least Ω(knlogn) (kn n) rounds, w.h.p., even with large bias allowed, when k=o(n/logn)k=o( n/ n). Several regimes remain open, especially in the synchronous setting. At the current state of the art, the Undecided-State dynamics performs similarly to 22-Choices, except that the bias required for convergence is always at least Ω(nlogn) ( n n). For this reason, a separate comparison with DéjàVu would add little here. 2.1 Comparison of DéjàVu with h-Majority The h-Majority dynamics is known to converge to plurality consensus in time O(logn)O( n) whenever the initial additive bias is at least ω(C1)ω( C_1) and h=ω(nlogn/C1)h=ω(n n/C_1), which becomes h=ω(klogn)h=ω(k n) in almost-balanced configurations with k opinions [DDG+25]. For arbitrary k and 4≤h=O(nlogn/C1)4≤ h=O(n n/C_1), we do not have upper bounds yet. However, [BCN+17] provided a lower bound of Ω(k/h2+1) (k/h^2+1) rounds, provided that h=Ω(k/n1/4−ε)h= (k/n^1/4- ) for any arbitrarily small constant ε>0 >0. In this work, we generalize this lower bound (Theorem 2). For h=3h=3, the convergence time of h-Majority is O(klogn)O(k n) when k=o(n/logn)k=o( n/ n), and O(nlog2n)O( n ^2n) otherwise. Moreover, plurality consensus is ensured when the initial additive bias is at least ω(nlogn)ω( n n) [S25]. Our upper bound on the convergence time of DéjàVu (Theorem 1) matches that of the h-Majority at least in the studied regime h≫1h 1, and almost matches our lower bound of Ω(n/(h2C1)+1) (n/(h^2C_1)+1) rounds needed by the h-Majority to converge when h=Ω(n3/4+ε/C1)h= (n^3/4+ /C_1). When h=3h=3, the convergence time becomes O((n/C1)logn)O((n/C_1) n), matching that of the 33-Majority when C1=Ω(n)C_1= ( n). For smaller values of C1C_1, the 33-Majority converges faster than our upper bound, but does not guarantee plurality consensus. We emphasize that the scope of this work is plurality consensus; general consensus is left for future work (see also Section 9). Note that the bias we require for plurality consensus is always competitive with the state of the art required by the h-Majority dynamics: we lose at most a logn n multiplicative factor. 2.1.1 Comparison of DéjàVu with 22-Choices As for the 22-Choices dynamics, note that DéjàVu for h=2h=2 is exactly equivalent to it, so all results on the 22-Choices dynamics apply to DéjàVu. When restricted to h=2h=2, our analysis is worse than the state of the art analysis for 22-Choices in terms of the minimum bias required to reach plurality consensus, which is ω(C1logn)ω( C_1 n) [S25]. Our requirement on the bias for constant values of h is comparable to that required by the 33-Majority, namely ω(nlogn)ω( n n), and remains comparable to the state of the art for h-Majority as h grows, reaching ω(C1logn)ω( C_1 n) when h≫n/C1h n/C_1, which is the same bias required by 22-Choices. 3 Preliminaries Consider a complete graph of n nodes/agents with self-loops. At time t=0t=0, each node supports one out of k opinions. Time is synchronous and dictated by some global clock. In the ℒℒ∗PULL^* model, the protocol DéjàVu works as follows: At each round, agents start sampling opinion u.a.r. with repetition from the network. The moment an agent samples for the second time some opinion x, it adopts x. Trivially, since there are k opinions, update takes place in at most k+1k+1 samples. After all nodes have updated, time increases by 1 and the nodes repeat the same protocol. In ℒℒPULL(h), the number of samples is capped at h, for any given h≥2h≥ 2. If a node does not sample twice any opinion after h samples, it will simply update by keeping its own opinion. After each update, time increases by 1 and the nodes repeat the same protocol. Note that if h=2h=2, DéjàVu is exactly the 22-Choices protocol: hence, in some sense, DéjàVu is a generalization of 22-Choices. Given any round t≥0t≥ 0, we denote by C(t)=(C1(t),…,Ck(t))C^(t)=(C_1^(t),…,C_k^(t)) the configuration of the system at round t, that is, by Ci(t)C_i^(t) we denote the number of nodes supporting opinion i at time t. We omit the dependence on t when it is clear from the context. Conditioned on a configuration C at some round t≥0t≥ 0, we denote by C′=(C1′,…,Ck′)C =(C_1 ,…,C_k ) the random configuration at time t+1t+1. Given any configuration C at time t≥0t≥ 0, let pi=Ci/np_i=C_i/n be the density of opinion i at time t, and p=(p1,…,pk)p=(p_1,…,p_k) the configuration of densities at time t. Similarly to C′C , we also denote by p′=(p1′,…,pk′)p =(p_1 ,…,p_k ) the random densities at time t+1t+1. Given a configuration C at time t≥0t≥ 0, we also define qiq_i as the expected amount of agents that update to opinion i in the next round by sampling opinion i twice in ℒℒPULL(h). Let Q=∑i∈[k]qiQ= _i∈[k]q_i. Furthermore, we define ℳiM_i as the event that an agent updates to opinion i when running DéjàVu in ℒℒ∗PULL^*. We are interested in analyzing the growth of the bias of the configuration, that is, given a configuration C=(C1,…,Ck)C=(C_1,…,C_k) at time t≥0t≥ 0, the bias of C is Δ=maxi∈[k]minj≠iΔi,j = _i∈[k]\ \j≠ i\\ _i,j\\, where Δi,j=Ci−Cj _i,j=C_i-C_j. Usually, given a configuration C, we will assume that it is ordered, that is, C1≥…≥CkC_1≥…≥ C_k and, hence, Δ=C1−C2 =C_1-C_2. In such a case, we also set Δi=C1−Ci _i=C_1-C_i. Similarly to before, given an ordered configuration C, we define Δi′=C1′−Ci′ _i =C_1 -C_i . Also, when we start from an ordered configuration C=(C1,…,CkC=(C_1,…,C_k) at time 0, we define Δj(t)=C1(t)−Cj(t) ^(t)_j=C_1^(t)-C_j^(t) for every j∈[k]j∈[k]. In the following, given a vector x=(x1,…,xm)x=(x_1,…,x_m), we write ‖x‖=‖x‖2=∑i∈[m]xi2 x= x_2= _i∈[m]x_i^2. 4 Amplification of the multiplicative bias of DéjàVu in ℒℒ∗PULL^* In this section, we focus on the ℒℒ∗PULL^* model. This alternative perspective allows us to derive upper and lower bounds on the expected amplification of the multiplicative bias at the next round, presented in the next lemma. We denote by ℳjM_j the event that an agent adopts opinion j after one round of DéjàVu in ℒℒ∗PULL^*. Lemma 4. Consider an ordered configuration C at any given time. For any i≤j∈[k]i≤ j∈[k], we have pi2pj2⋅pi+3pj3pi+pj≤Pr(ℳi∣C)Pr(ℳj∣C)≤pi2pj2 p_i^2p_j^2· p_i+3p_j3p_i+p_j≤ (M_i C ) (M_j C )≤ p_i^2p_j^2 Its proof relies on an equivalent continuous-time interpretation of the sampling process based on a Poisson race argument. This viewpoint allows us to directly compare Pr(ℳi∣C)Pr(ℳj∣C) (M_i C ) (M_j C ) without explicitly accounting for the remaining opinions. For completeness, we first establish the equivalence between the ℒℒ∗PULL^* dynamics and the corresponding Poisson race formulation. The proof of Lemma 4 will follow. In our model ℒℒ∗PULL^*, an agent following DéjàVu repeatedly samples opinions u.a.r. from a system with configuration (C1,…,Ck) (C_1,…,C_k ) until some opinion is observed for the second time. Formally, let i∈0,1ke_i∈\0,1\^k denote the standard basis vector with a 1 in the i-th position and 0 elsewhere, i.e., (i)j=1if j=i,0otherwise,for all j∈[k]. (e_i )_j= cases1&if j=i,\\ 0&otherwise, cases all j∈[k]. Let Sjj∈ℕ \S_j \_j∈ N be i.i.d. random variables such that Pr(Sj=i)=Ci/n (S_j=e_i )=C_i/n. These random variables describe the outcomes of the samples of opinions. Let (X1(ℓ),…,Xk(ℓ))=∑j=1ℓSj∼Multinomial(ℓ,(C1/n,…,Ck/n)), (X_1^( ),…,X_k^( ) )= _j=1 S_j ( , (C_1/n,…,C_k/n ) )~, describing the outcome of the first ℓ samples. Let Li≔minℓ∈ℕ:Xi(ℓ)=2L_i \ ∈ N:X_i^( )=2 \, the first time opinion i gets 22 samples, and L≔mini∈[k]LiL _i∈[k] \L_i \, so that only after the L-th sample, the whole sample contains 22 occurrences of an opinion. According to DéjàVu’s update rule, the agent adopts opinion i if and only if i=argminj∈[k]Lj.i= argmin_j∈[k] \L_j \. An equivalent way to model this process is the so-called Poisson race. Let Yi(t),t≥0i∈[k] \Y_i(t),t≥ 0 \_i∈[k] be independent homogeneous Poisson processes with support on 0,1,2,… \0,1,2,… \, meaning that 1. For all t≥0t≥ 0, Yi(t)∼Poisson(Ci⋅t)Y_i(t) (C_i· t). 2. The process Yi(t),t≥0 \Y_i(t),t≥ 0 \ has independent increments, i.e. for any times 0≤t0<t1<⋯<tn0≤ t_0<t_1<·s<t_n, the random variables Yj(ti+1)−Yj(ti)i=0n−1 \Y_j(t_i+1)-Y_j(t_i) \_i=0^n-1 are mutually independent. where Yi(t)Y_i(t) counts the number of samples of opinion i up to time t. Note that this continuous time is distinct from the discrete time of the samples. Let Ti=inft>0:Yi(t)=2T_i= \t>0:Y_i(t)=2 \ be the time opinion i is sampled for the second time. We say that the index i wins the Poisson race if i=argminj∈[k]Tj.i= argmin_j∈[k] \T_j \. Theorem 5. The protocol DéjàVu in ℒℒ∗PULL^* can be modeled equivalently by a Poisson race; in other words, we have Pr(ℳi∣C)=Pr(“i wins the Poisson race”) (M_i C )= (``$i$ wins the Poisson race" ) Proof. By the fact that, for all t≥0t≥ 0 and i∈[k]i∈[k], Yi(t)∼Poisson(Ci⋅t)Y_i(t) (C_i· t) and (Yi(t))i∈[k] (Y_i(t) )_i∈[k] are mutually independent, we can apply Theorem 45 and we obtain that ((Yi(t))i∈[k]∣∑i∈[k]Yi(t)=1)∼Multinomial(1,(C1/n,…,Ck/n))∼S1. ( (Y_i(t) )_i∈[k] _i∈[k]Y_i(t)=1 ) (1, (C_1/n,…,C_k/n ) ) S_1. (1) Let Y(t)=∑i∈[k]Yi(t)Y(t)= _i∈[k]Y_i(t). Since independence is preserved under summation and the sum of Poisson r.v. is a Poisson r.v. we have that Y(t)Y(t) is a homogeneous Poisson process with support on 0,1,2,… \0,1,2,… \ s.t. 1. For all t≥0t≥ 0, Y(t)∼Poisson(t)Y(t) (t). 2. The process Y(t),t≥0 \Y(t),t≥ 0 \ has independent increments. Let the stopping times τ(s)≔inft≥0:Y(t)≥sτ^(s) \t≥ 0:Y(t)≥ s \ for all s∈ℕs∈ N. Since Yi(t)Y_i(t) is an independent homogeneous Poisson process, we have that the r.v.s Yi(t+τ(s))−Yi(τ(s))Y_i(t+τ^(s))-Y_i(τ^(s)) and Yi(t)Y_i(t) are independent and identically distributed, for all t≥0,s∈ℕ,i∈[k]t≥ 0,s∈ N,i∈[k]. This fact, together with Eq. 1, implies that if the number of total samples in the interval [τ(s),t+τ(s)][τ^(s),t+τ^(s)] is equal to one, then the distribution of any opinion i in that interval is Multinomial(1,(C1/n,…,Ck/n))Multinomial (1, (C_1/n,…,C_k/n ) ); in formulas, we have that for all t>0t>0 and all s∈ℕs∈ N, ((Yi(t+τ(s))−Yi(τ(s)))i∈[k]∣Y(t+τ(s))−Y(τ(s))=1)∼S1. ( (Y_i(t+τ^(s))-Y_i(τ^(s)) )_i∈[k] Y(t+τ^(s))-Y(τ^(s))=1 ) S_1. (2) Since for all t,ε>0t, >0, Pr(Y(t+ε)−Y(t)≥1)=Pr(Y(ε)≥1)=1−exp(−ε)→ε→00, (Y(t+ )-Y(t)≥ 1 )= (Y( )≥ 1 )=1- - → 00, we have that τ(s)=inft≥0:Y(t)=sτ^(s)= \t≥ 0:Y(t)=s \. Therefore, we obtain that Pr(Y(τ(s+1))=s+1,Y(τ(s))=s)=1, (Y(τ^(s+1))=s+1,Y(τ^(s))=s )=1, and, by setting t=τ(s+1)−τ(s)t=τ^(s+1)-τ^(s), from Eq. 2 we have that Pr((Yi(τ(s+1))−Yi(τ(s)))i∈[k]=x) ( (Y_i(τ^(s+1))-Y_i(τ^(s)) )_i∈[k]=x ) = =\ Pr(Y(τ(s+1))−Y(τ(s))=1)⋅Pr((Yi(τ(s+1))−Yi(τ(s)))i∈[k]=x∣Y(τ(s+1))−Y(τ(s))=1) (Y(τ^(s+1))-Y(τ^(s))=1 )· ( (Y_i(τ^(s+1))-Y_i(τ^(s)) )_i∈[k]=x Y(τ^(s+1))-Y(τ^(s))=1 ) = =\ Pr(Sj=x), (S_j=x ), for all x in the probability space. Moreover, by the fact the increments of the process Y(t)Y(t) are independent, as the samples (Sj)j∈[ℕ] (S_j )_j∈[ N], we obtain, for all ℓ∈ℕ ∈ N, that (X1(ℓ),…,Xk(ℓ))=∑j∈[ℓ]Sj∼∑j∈[ℓ](Yi(τ(j))−Yi(τ(j−1)))i∈[k]=(Yi(τ(ℓ)))i∈[k]. (X_1^( ),…,X_k^( ) )= _j∈[ ]S_j _j∈[ ] (Y_i(τ^(j))-Y_i(τ^(j-1)) )_i∈[k]= (Y_i(τ^( )) )_i∈[k]. In particular, this implies that Ti T_i =inft>0:Yi(t)=2 = \t>0:Y_i(t)=2 \ =τ(mins∈ℕ:Yi(τ(s))=2) =τ ( \s∈ N:Y_i(τ^(s))=2 \ ) ∼τ(mins∈ℕ:Xi(s)=2) τ ( \s∈ N:X_i^(s)=2 \ ) =τ(Li). =τ (L_i ). Since, by definition, τ(s)τ^(s) is non-decreasing in s, the index that minimizes τ(Li)τ\! (L_i ) also minimizes LiL_i, concluding the proof of Theorem 5. ∎ We have established that an equivalent way to model this protocol is the following. Let Xi(t),t≥0i∈[k] \X_i(t),t≥ 0 \_i∈[k] independent Poisson processes with support on 0,1,2,… \0,1,2,… \ s.t. Xi(t)∼Poisson(ci⋅t),X_i(t) (c_i· t), where cic_i counts the number of agents with opinion i at the current configuration. In this way, Xi(t)X_i(t) counts the number of samples of opinion i up to time t. Let Ti=inft≥0:Xi(t)=2T_i= \t≥ 0:X_i(t)=2 \ be the time opinion i is sampled twice. An agent adopts opinion i if i=argminj∈[k]Tj.i= argmin_j∈[k] \T_j \. Proof of Lemma 4. Suppose the sequence of samples is infinite (it extends beyond the point when some opinion is sampled twice). Let T be the time an opinion ℓ∉i,j ∉\i,j\ is sampled twice. Formally, T≔minℓ∈[k]∖i,jTℓ,T _ ∈[k] \i,j \ \T_ \, where TℓT_ is the first time opinion ℓ is sampled twice. Let Xi,j≔Xi(T)+Xj(T).X_i,j X_i(T)+X_j(T). We have Pr(ℳi∣C)Pr(ℳj∣C) (M_i C ) (M_j C ) =Pr(Xi(T)=2∣Xi,j=2)⋅Pr(Xi,j=2)+Pr(Ti<Tj∣Xi,j≥3)⋅Pr(Xi,j≥3)Pr(Xj(T)=2∣Xi,j=2)⋅Pr(Xi,j=2)+Pr(Tj<Ti∣Xi,j≥3)⋅Pr(Xi,j≥3) = (X_i(T)=2 X_i,j=2 )· (X_i,j=2 )+ (T_i<T_j X_i,j≥ 3 )· (X_i,j≥ 3 ) (X_j(T)=2 X_i,j=2 )· (X_i,j=2 )+ (T_j<T_i X_i,j≥ 3 )· (X_i,j≥ 3 ) By the standard inequality minx1y1,x2y2≤x1+x2y1+y2≤maxx1y1,x2y2 \ x_1y_1, x_2y_2 \≤ x_1+x_2y_1+y_2≤ \ x_1y_1, x_2y_2 \, we obtain Pr(ℳi∣C)Pr(ℳj∣C) (M_i C ) (M_j C ) ≥minPr(Xi(T)=2∣Xi,j=2)Pr(Xj(T)=2∣Xi,j=2),Pr(Ti<Tj∣Xi,j≥3)Pr(Tj<Ti∣Xi,j≥3). ≥ \ (X_i(T)=2 X_i,j=2 ) (X_j(T)=2 X_i,j=2 ),\ (T_i<T_j X_i,j≥ 3 ) (T_j<T_i X_i,j≥ 3 ) \. Pr(ℳi∣C)Pr(ℳj∣C) (M_i C ) (M_j C ) ≤maxPr(Xi(T)=2∣Xi,j=2)Pr(Xj(T)=2∣Xi,j=2),Pr(Ti<Tj∣Xi,j≥3)Pr(Tj<Ti∣Xi,j≥3). ≤ \ (X_i(T)=2 X_i,j=2 ) (X_j(T)=2 X_i,j=2 ),\ (T_i<T_j X_i,j≥ 3 ) (T_j<T_i X_i,j≥ 3 ) \. Since T is a deterministic function of Xℓ(t),t≥0ℓ∈[k]∖i,j \X_ (t),t≥ 0 \_ ∈[k] \i,j \, it is independent of Xi(t),t≥0 \X_i(t),t≥ 0 \ and Xj(t),t≥0 \X_j(t),t≥ 0 \. Therefore, conditioning on T=t \T=t \, we have Xi(T)∼Poisson(pi⋅t)X_i(T) (p_i· t) and Xj(T)∼Poisson(pj⋅t)X_j(T) (p_j· t) for all t≥0t≥ 0. Let Bx∼Binomial(x,pipi+pj)B_x (x, p_ip_i+p_j). By applying Theorem 45, we obtain (Xi(T)∣Xi,j=x)∼Bx (X_i(T) X_i,j=x ) B_x, (Xj(T)∣Xi,j=x)=x−Bx (X_j(T) X_i,j=x )=x-B_x, and therefore Pr(Xi(T)=2∣Xi,j=2)Pr(Xj(T)=2∣Xi,j=2)=(pipi+pj)2(pjpi+pj)2=pi2pj2. (X_i(T)=2 X_i,j=2 ) (X_j(T)=2 X_i,j=2 )= ( p_ip_i+p_j )^2 ( p_jp_i+p_j )^2= p_i^2p_j^2. Moreover, Pr(Ti<Tj∣Xi,j≥3)Pr(Tj<Ti∣Xi,j≥3)=(pipi+pj)2+2(pipi+pj)2pjpi+pj(pjpi+pj)2+2(pjpi+pj)2pipi+pj=pi2pj2⋅pi+3pj3pi+pj, (T_i<T_j X_i,j≥ 3 ) (T_j<T_i X_i,j≥ 3 )= ( p_ip_i+p_j)^2+2( p_ip_i+p_j)^2 p_jp_i+p_j( p_jp_i+p_j)^2+2( p_jp_i+p_j)^2 p_ip_i+p_j= p_i^2p_j^2· p_i+3p_j3p_i+p_j, where we used that Pr(Ti<Tj∣Xi,j≥3) (T_i<T_j X_i,j≥ 3 ) is the probability that the extraction sequence contains no occurrence of opinion j before the second occurrence of i, plus the probability that the sequence contains both i and j and the last relevant extraction is i. We conclude that pi2pj2⋅pi+3pj3pi+pj≤Pr(ℳi∣C)Pr(ℳj∣C)≤(pipj)2. p_i^2p_j^2· p_i+3p_j3p_i+p_j≤ (M_i C ) (M_j C )≤ ( p_ip_j )^2. This concludes the proof of Lemma 4. ∎ 5 From PULL* to PULL(h) The Poisson clocks equivalence used in Lemma 4 crucially relies on the fact that the sampling sequence is infinite. Consequently, this equivalence no longer holds when analyzing DéjàVu under the ℒℒ(h)PULL(h) model, where the number of samples is capped at h. Interestingly, conditioning on the event that an agent observes the same opinion twice within the first h samples further amplifies the multiplicative bias in favor of larger opinions. The goal of this section is to prove the following lemma, which allows us to transfer the bounds established for the ℒℒ∗PULL^* model to the ℒℒ(h)PULL(h) model. Lemma 6. Let H be the number of samples until an agent samples an opinion a second time. Then, for all opinions i,j∈[k]i,j∈[k] such that pi≥pjp_i≥ p_j, and for all h=2,…,k+1h=2,…,k+1, we have Pr(ℳi∣C)Pr(ℳj∣C)≤Pr(ℳi,H≤h∣C)Pr(ℳj,H≤h∣C)≤pi2pj2. (M_i C ) (M_j C )≤ (M_i,H≤ h C ) (M_j,H≤ h C )≤ p_i^2p_j^2. For h≥k+1h≥ k+1, the event H≤h \H≤ h \ coincides with H≤k+1 \H≤ k+1 \, since after k+1k+1 samples some opinion must repeat. The proof contains several algebraic manipulations, but the main idea is to manipulate the multinomial distribution and apply Newton’s inequalities to elementary symmetric sums of the probabilities. For any h,i≤kh,i≤ k, let Cih⊆[k]∖iC_i^h [k] \i\ denote the collection of all subsets S of [k]∖i[k] \i\ having cardinality h. Each such set S∈CihS∈ C_i^h indexes one monomial of the h-th elementary symmetric polynomial in the variables pj:j≠i\p_j:j≠ i\, namely ∏j∈Spj. _j∈ Sp_j. Consequently, eh([k]∖i)≔∑S∈Cih∏j∈Spje_h([k] \i \) _S∈ C_i^h _j∈ Sp_j is exactly the h-th elementary symmetric sum in the variables pjj≠i\p_j\_j≠ i. It satisfies the following monotonicity property in h. Claim 7. We have that for 2≤h≤k−22≤ h≤ k-2 and for all opinion i,j∈[k]i,j∈[k] s.t. pi≥pjp_i≥ p_j, ∑S∈Cih∏ℓ∈Spℓ∑S∈Cjh∏ℓ∈Spℓ≤∑S∈Cih−1∏ℓ∈Spℓ∑S∈Cjh−1∏ℓ∈Spℓ _S∈ C_i^h _ ∈ Sp_ _S∈ C_j^h _ ∈ Sp_ ≤ _S∈ C_i^h-1 _ ∈ Sp_ _S∈ C_j^h-1 _ ∈ Sp_ Proof. Let Rh≔eh([k]∖i)eh([k]∖j).R_h e_h([k] \i\)e_h([k] \j\). Put C=[k]∖i,jC=[k] \i,j\. We have eh([k]∖i)=eh(C)+pjeh−1(C),eh([k]∖j)=eh(C)+pieh−1(C).e_h([k] \i\)=e_h(C)+p_j\,e_h-1(C), e_h([k] \j\)=e_h(C)+p_i\,e_h-1(C). Hence, setting E≔eh(C),F≔eh−1(C),G≔eh−2(C),E e_h(C), F e_h-1(C), G e_h-2(C), we may write Rh=E+pjFE+piF,Rh−1=F+pjGF+piG.R_h= E+p_jFE+p_iF, R_h-1= F+p_jGF+p_iG. To compare RhR_h and Rh−1R_h-1, we compute Rh≤Rh−1⇔(E+pjF)(F+piG)≤(E+piF)(F+pjG).R_h≤ R_h-1\ \ (E+p_jF)(F+p_iG)≤(E+p_iF)(F+p_jG). Expanding both sides and canceling common terms, this inequality becomes (pi−pj)(EG−F2)≤0.(p_i-p_j)\,(EG-F^2)≤ 0. Since pi≥pjp_i≥ p_j, the last inequality is equivalent to F2≥EG.F^2≥ EG. Newton’s inequalities state that em(C)2≥em−1(C)em+1(C)for 1≤m≤|C|−1.e_m(C)^2≥ e_m-1(C)\,e_m+1(C) 1≤ m≤|C|-1. Taking m=h−1m=h-1, gives that, for 2≤h≤|C|=k−22≤ h≤|C|=k-2, we have eh−1(C)2≥eh−2(C)eh(C),e_h-1(C)^2≥ e_h-2(C)\,e_h(C), i.e. F2≥EGF^2≥ EG. Therefore Rh≤Rh−1R_h≤ R_h-1. This proves the claim for every h such that 2≤h≤k−22≤ h≤ k-2. ∎ We now study the multinomial distribution conditioned on the number of samples until the agent observes an opinion twice, and obtain the following. Claim 8. Let H be the number of samples until an agent samples an opinion a second time. We have, for all opinions i,j∈[k]i,j∈[k] such that pi≥pjp_i≥ p_j and all h=3,…,k+1h=3,…,k+1, that Pr(ℳi∣H=h−1,C)Pr(ℳj∣H=h−1,C)≥Pr(ℳi∣H=h,C)Pr(ℳj∣H=h,C) (M_i H=h-1,C ) (M_j H=h-1,C )≥ (M_i H=h,C ) (M_j H=h,C ) Proof. For every i∈[k]i∈[k], the event ℳi∩H=hM_i∩ \H=h \ occurs exactly when opinion i appears once among the first h−1h-1 samples, all remaining opinions observed in those h−1h-1 samples are distinct, and the h-th sample is again i. Therefore, Pr(ℳi,H=h∣C) (M_i,H=h C ) =((h−1)!pi∑S∈Cih−2∏j∈Spj)pi = ((h-1)!\ p_i _S∈ C_i^h-2 _j∈ Sp_j )p_i =(h−1)!pi2∑S∈Cih−2∏j∈Spj. =(h-1)!\ p_i^2 _S∈ C_i^h-2 _j∈ Sp_j. If h=3h=3, then Pr(ℳi∣H=3,C)Pr(ℳj∣H=3,C)=pi2∑ℓ≠ipℓpj2∑ℓ≠jpℓ=pi2(1−pi)pj2(1−pj)≤pi2pj2=Pr(ℳi∣H=2,C)Pr(ℳj∣H=2,C), (M_i H=3,C ) (M_j H=3,C )= p_i^2 _ ≠ ip_ p_j^2 _ ≠ jp_ = p_i^2(1-p_i)p_j^2(1-p_j)≤ p_i^2p_j^2= (M_i H=2,C ) (M_j H=2,C ), where the inequality follows from pi≥pjp_i≥ p_j. For 4≤h≤k4≤ h≤ k, by the previous identity and 7, we obtain Pr(ℳi∣H=h,C)Pr(ℳj∣H=h,C)=pi2∑S∈Cih−2∏j∈Spjpj2∑S∈Cjh−2∏j∈Spj≤pi2∑S∈Cih−3∏j∈Spjpj2∑S∈Cjh−3∏j∈Spj=Pr(ℳi∣H=h−1,C)Pr(ℳj∣H=h−1,C). (M_i H=h,C ) (M_j H=h,C )= p_i^2 _S∈ C_i^h-2 _j∈ Sp_jp_j^2 _S∈ C_j^h-2 _j∈ Sp_j≤ p_i^2 _S∈ C_i^h-3 _j∈ Sp_jp_j^2 _S∈ C_j^h-3 _j∈ Sp_j= (M_i H=h-1,C ) (M_j H=h-1,C ). Finally, for h=k+1h=k+1, since Cik−1C_i^k-1 contains the single set [k]∖i[k] \i\, we have Pr(ℳi∣H=k+1,C)Pr(ℳj∣H=k+1,C)=pi2∏ℓ≠ipℓpj2∏ℓ≠jpℓ=pipj. (M_i H=k+1,C ) (M_j H=k+1,C )= p_i^2 _ ≠ ip_ p_j^2 _ ≠ jp_ = p_ip_j. On the other hand, Pr(ℳi∣H=k,C)Pr(ℳj∣H=k,C)=pi2ek−2([k]∖i)pj2ek−2([k]∖j)=pipj⋅∑ℓ≠i1/pℓ∑ℓ≠j1/pℓ≥pipj, (M_i H=k,C ) (M_j H=k,C )= p_i^2e_k-2([k] \i\)p_j^2e_k-2([k] \j\)= p_ip_j· _ ≠ i1/p_ _ ≠ j1/p_ ≥ p_ip_j, because pi≥pjp_i≥ p_j implies 1/pi≤1/pj1/p_i≤ 1/p_j. Hence, Pr(ℳi∣H=k+1,C)Pr(ℳj∣H=k+1,C)≤Pr(ℳi∣H=k,C)Pr(ℳj∣H=k,C). (M_i H=k+1,C ) (M_j H=k+1,C )≤ (M_i H=k,C ) (M_j H=k,C ). ∎ Proof of Lemma 6. The following inequalities are all equivalent: Pr(ℳi,H≤h∣C)Pr(ℳj,H≤h∣C)≥Pr(ℳi∣C)Pr(ℳj∣C) (M_i,H≤ h C ) (M_j,H≤ h C )≥ (M_i C ) (M_j C ) ⇔ (∑ℓ=2k+1Pr(ℳj,H=ℓ∣C))(∑ℓ=2hPr(ℳi,H=ℓ∣C)) \ ( _ =2^k+1 (M_j,H= C ) ) ( _ =2^h (M_i,H= C ) ) ≥ ≥\ (∑ℓ=2k+1Pr(ℳi,H=ℓ∣C))(∑ℓ=2hPr(ℳj,H=ℓ∣C)) ( _ =2^k+1 (M_i,H= C ) ) ( _ =2^h (M_j,H= C ) ) ⇔ (∑ℓ=h+1k+1Pr(ℳj,H=ℓ∣C))(∑ℓ=2hPr(ℳi,H=ℓ∣C)) \ ( _ =h+1^k+1 (M_j,H= C ) ) ( _ =2^h (M_i,H= C ) ) ≥ ≥\ (∑ℓ=h+1k+1Pr(ℳi,H=ℓ∣C))(∑ℓ=2hPr(ℳj,H=ℓ∣C)) ( _ =h+1^k+1 (M_i,H= C ) ) ( _ =2^h (M_j,H= C ) ) ⇔ Pr(ℳi,H≤h∣C)Pr(ℳj,H≤h∣C)≥Pr(ℳi,H>h∣C)Pr(ℳj,H>h∣C), \ (M_i,H≤ h C ) (M_j,H≤ h C )≥ (M_i,H>h C ) (M_j,H>h C ), where in the second equivalence we canceled in both sides the symmetrical part of the sum. We will prove the last equation holds. We have that Pr(ℳi,H≤h∣C)Pr(ℳj,H≤h∣C) (M_i,H≤ h C ) (M_j,H≤ h C ) =∑ℓ=2hPr(H=ℓ∣C)Pr(ℳi∣H=ℓ,C)∑ℓ=2hPr(H=ℓ∣C)Pr(ℳj∣H=ℓ,C) = _ =2^h (H= C ) (M_i H= ,C ) _ =2^h (H= C ) (M_j H= ,C ) ≥minℓ=2,…,hPr(ℳi∣H=ℓ,C)Pr(ℳj∣H=ℓ,C) ≥ _ =2,…,h (M_i H= ,C ) (M_j H= ,C ) =Pr(ℳi∣H=h,C)Pr(ℳj∣H=h,C), = (M_i H=h,C ) (M_j H=h,C ), where the last equality holds by 8. Similarly, we have Pr(ℳi,H>h∣C)Pr(ℳj,H>h∣C) (M_i,H>h C ) (M_j,H>h C ) ≤maxℓ=h+1,…,k+1Pr(ℳi∣H=ℓ,C)Pr(ℳj∣H=ℓ,C) ≤ _ =h+1,…,k+1 (M_i H= ,C ) (M_j H= ,C ) =Pr(ℳi∣H=h+1,C)Pr(ℳj∣H=h+1,C) = (M_i H=h+1,C ) (M_j H=h+1,C ) ≤Pr(ℳi∣H=h,C)Pr(ℳj∣H=h,C). ≤ (M_i H=h,C ) (M_j H=h,C ). To conclude the proof of Lemma 6, we show that Pr(ℳi∣C)Pr(ℳj∣C) (M_i C ) (M_j C ) =Pr(ℳi,H>1∣C)Pr(ℳj,H>1∣C) = (M_i,H>1 C ) (M_j,H>1 C ) ≤maxℓ=2,…,k+1Pr(ℳi∣H=ℓ,C)Pr(ℳj∣H=ℓ,C) ≤ _ =2,…,k+1 (M_i H= ,C ) (M_j H= ,C ) =Pr(ℳi∣H=2,C)Pr(ℳj∣H=2,C) = (M_i H=2,C ) (M_j H=2,C ) =pi2pj2. = p_i^2p_j^2. ∎ 5.1 Generalized birthday paradox In this section we provide upper and lower bounds on the probability of seeing an opinion twice in h samples. Our goal is to prove the following lemma. Lemma 9. Let C be an ordered configuration. Recall that H≤h \H≤ h \ is the event that an agent samples an opinion twice within the first h samples. For every h≥2h≥ 2, we have 2−11minh2‖p‖22,1≤Pr(H≤h∣C)≤minh2‖p‖22,1.2^-11 \h^2 p_2^2,1 \≤ (H≤ h C )≤ \h^2 p_2^2,1 \. As a simple corollary of Lemma 9, we obtain the following. Corollary 10. Let C be an ordered configuration. Given a sample size h≥2h≥ 2 and an opinion probability density p, let D be the number of agents that update by seeing an opinion twice within the h samples. Writing Q≔Pr(H≤h∣C),Q (H≤ h C), we have [D∣C]=nQ E[D C]=nQ, and therefore 2−11nminh2‖p‖22,1≤[D∣C]≤nminh2‖p‖22,1.2^-11n \h^2\|p\|_2^2,1 \≤ E[D C]≤ n \h^2\|p\|_2^2,1 \. We start by proving an upper bound on the probability of seeing an opinion twice within the first h samples. Lemma 11. Let (X1,…,Xk) (X_1,…,X_k ) be distributed as a multinomial random vector with parameters h and (p1,…,pk)(p_1,…,p_k). Then Pr(∪i∈[k]Xi>1)≤h22∑j∈[k]pj2 ( _i∈[k] \X_i>1 \ )≤ h^22 _j∈[k]p_j^2 Proof. Let Z1,…,ZhZ_1,…,Z_h be the h i.i.d. samples with distribution (p1,…,pk)(p_1,…,p_k). Observe that ⋃i∈[k]Xi>1 _i∈[k]\X_i>1\ occurs if and only if there exist two distinct samples having the same opinion. For a<ba<b, define Ia,b=Za=Zb.I_a,b=1\Z_a=Z_b\. Then Pr(⋃i∈[k]Xi>1)=Pr(∑a<bIa,b≥1)≤∑a<bPr(Za=Zb), \! ( _i∈[k]\X_i>1\ )= \! ( _a<bI_a,b≥ 1 )≤ _a<b (Z_a=Z_b), where the last inequality follows from the union bound. Since Pr(Za=Zb)=∑j∈[k]pj2, (Z_a=Z_b)= _j∈[k]p_j^2, and there are (h2)≤h22 h2≤ h^22 pairs, we obtain Pr(⋃i∈[k]Xi>1)≤h22∑j∈[k]pj2. \! ( _i∈[k]\X_i>1\ )≤ h^22 _j∈[k]p_j^2. ∎ Lemma 12 (Concentration D). Let C be an ordered configuration, and let D be the number of agents that update by seeing an opinion twice within the first h samples. Write Q≔Pr(H≤h∣C),[D∣C]=nQ.Q (H≤ h C), E[D C]=nQ. Then, for every constant a>0a>0, there exists a constant Ka>0K_a>0 such that, if nQ≥KalognnQ≥ K_a n, then Pr(D∈[nQ2,3nQ2]|C)≥1−1na. \! (D∈ [ nQ2, 3nQ2 ]\, |\,C )≥ 1- 1n^a. Proof. Since each agent updates independently with probability Q, conditional on C we have D∼Bin(n,Q).D (n,Q). Applying the multiplicative Chernoff bound with β=1/2β=1/2, we obtain Pr(D∉[nQ2,3nQ2]|C)≤2exp(−nQ12). \! (D∉ [ nQ2, 3nQ2 ]\, |\,C )≤ 2 \! (- nQ12 ). Therefore, if nQ≥KalognnQ≥ K_a n with Ka≥12(a+1)K_a≥ 12(a+1), then 2exp(−nQ12)≤1na,2 \! (- nQ12 )≤ 1n^a, concluding the proof. ∎ In order to provide a lower bound we will need that h‖p‖2h p_2 is smaller than some small constant. We will extend the result by monotonicity. We will use a result by [AGG89]. In order to state it, we need to introduce some notation. Let I be a finite index set. For α∈Iα∈ I, let XαX_α be a Bernoulli r.v. with Pr(Xα=1)=pα>0 (X_α=1)=p_α>0. Let W=∑α∈IXαW= _α∈ IX_α and λ=[W]λ= E[W]. For each α∈Iα∈ I, suppose we are given a Bα⊆IB_α I, with α∈Bα∈ B_α: we will think of BαB_α as the set such that XαX_α is independent (or “nearly” independent) of XβX_β for each β∈I∖Bαβ∈ I B_α. For any two α,β∈Iα,β∈ I, let pαβ=[XαXβ]p_αβ= E[X_αX_β]. Furthermore, let sα s_α =[|[Xα−pα∣∑β∈I∖BαXβ]|]. = E [ E [X_α-p_α _β∈ I B_αX_β ] ]. Now set b1 b_1 =∑α∈I∑β∈Bαpαpβ; = _α∈ I _β∈ B_αp_αp_β; b2 b_2 =∑α∈I∑β∈Bα∖αpαβ; = _α∈ I _β∈ B_α \α\p_αβ; b3 b_3 =∑α∈Isα. = _α∈ Is_α. The following holds by [AGG89, Theorem 1]: |Pr(W=0)−e−λ|≤1−1eλ⋅(b1+b2+b3). (W=0)-e^-λ ≤ 1- 1e^λ·(b_1+b_2+b_3). (3) We prove the following. Theorem 13. Let (X1,…,Xk)∼Multinomial(h;p)(X_1,…,X_k) (h;p), where p=(p1,…,pk)p=(p_1,…,p_k) and h≥2h≥ 2. Let C=h‖p‖2C=h p_2. Then, Pr(∩i∈[k]Xi≤1)≤exp[−C2/4]+(1−exp[−C2/2])(2C2h+2C). ( _i∈[k]\X_i≤ 1\ )≤ [-C^2/4]+(1- [-C^2/2]) ( 2C^2h+2C ). Proof. Let Y1,…,YhY_1,…,Y_h be i.i.d. random variables taking values in 1,…,k\1,…,k\ with Pr(Yt=i)=pi (Y_t=i)=p_i. Define the multinomial counts Xi=∑t=1hYt=i,i=1,…,k,X_i= _t=1^h1\Y_t=i\, i=1,…,k, so that (X1,…,Xk)∼Multinomial(h;p)(X_1,…,X_k) (h;p). For 1≤a<b≤h1≤ a<b≤ h define the pair-collision events and indicators Aab=Ya=Yb,ξab=Aab,A_ab=\Y_a=Y_b\, _ab=1_A_ab, and let W=∑1≤a<b≤hξab.W= _1≤ a<b≤ h _ab. Then W counts the number of colliding pairs among the h draws. Observe that ∀i,Xi≤1⇔Y1,…,Yh are all distinct⇔W=0. \∀ i,\ X_i≤ 1 \\ \ \Y_1,…,Y_h are all distinct\\ \ \W=0\. Let I=(a,b):1≤a<b≤hI=\(a,b):1≤ a<b≤ h\ index the indicators. For α=(a,b)∈Iα=(a,b)∈ I define Bab=(c,d)∈I:c,d∩a,b≠∅.B_ab=\(c,d)∈ I:\c,d\∩\a,b\≠ \. If (c,d)∉Bab(c,d)∉ B_ab then c,d∩a,b=∅\c,d\∩\a,b\= , and hence ξab _ab is independent of ξβ∈I∖Bab \ _β \_β∈ I B_ab. Therefore the term b3b_3 in Eq. 3 equals 0. Define pab=[ξab]=Pr(Ya=Yb)=∑i=1kpi2=‖p‖22,p_ab= E[ _ab]= (Y_a=Y_b)= _i=1^kp_i^2= p_2^2, and note that |I|=(h2)|I|= h2. Hence λ=[W]=∑(a,b)∈Ipab=(h2)‖p‖22.λ= E[W]= _(a,b)∈ Ip_ab= h2 p_2^2. We bound the quantities b1b_1 and b2b_2 from Eq. 3, namely b1=∑α∈I∑β∈Bαpαpβ,b2=∑α∈I∑β∈Bαβ≠α[ξαξβ].b_1= _α∈ I\ _β∈ B_αp_αp_β, b_2= _α∈ I\ _ subarraycβ∈ B_α\\ β≠α subarray E[ _α _β]. Since pα=‖p‖22p_α= p_2^2 for all α and |Bab|=2h−3|B_ab|=2h-3 for every (a,b)(a,b), we have b1=(h2)(2h−3)‖p‖24=λ(2h−3)‖p‖22.b_1= h2(2h-3) p_2^4=λ(2h-3) p_2^2. Next, if β∈Babβ∈ B_ab and β≠(a,b)β≠(a,b) then the two pairs share exactly one index, so for distinct a,b,ca,b,c, [ξabξac]=Pr(Ya=Yb=Yc)=∑i=1kpi3. E[ _ab _ac]= (Y_a=Y_b=Y_c)= _i=1^kp_i^3. Each (a,b)(a,b) has exactly 2(h−2)2(h-2) such elements β≠(a,b)β≠(a,b) in BabB_ab, hence b2=(h2) 2(h−2)∑i=1kpi3.b_2= h2\,2(h-2) _i=1^kp_i^3. Using ∑ipi3≤‖p‖∞∑ipi2≤‖p‖23 _ip_i^3≤ p_∞ _ip_i^2≤ p_2^3, we get b2≤(h2) 2(h−2)‖p‖23=2(h−2)λ‖p‖2.b_2≤ h2\,2(h-2) p_2^3=2(h-2)λ p_2. Then b1=λ(2h−3)‖p‖22≤2λh‖p‖22=2λ(h‖p‖2)2h=2C2λh,b_1=λ(2h-3) p_2^2≤ 2λ h p_2^2=2λ (h p_2)^2h=2C^2\, λh, and b2≤2(h−2)λ‖p‖2≤2hλ‖p‖2=2Cλ.b_2≤ 2(h-2)λ p_2≤ 2hλ p_2=2C\,λ. Moreover, λ=(h2)‖p‖22≤h22‖p‖22=12(h‖p‖2)2=C22,λ= h2 p_2^2≤ h^22 p_2^2= 12(h p_2)^2= C^22, and λ=(h2)‖p‖22≥h24‖p‖22=14(h‖p‖2)2=C24,λ= h2 p_2^2≥ h^24 p_2^2= 14(h p_2)^2= C^24, By Eq. 3, using b3=0b_3=0, |Pr(W=0)−e−λ|≤(b1+b2+b3)1−e−λ=(b1+b2)1−e−λ. | (W=0)-e^-λ |≤(b_1+b_2+b_3) 1-e^-λ=(b_1+b_2) 1-e^-λ. Hence, Pr(W=0)≤exp[−C2/4]+(1−exp[−C2/2])(2C2h+2C). (W=0)≤ [-C^2/4]+(1- [-C^2/2]) ( 2C^2h+2C ). ∎ We are ready to put together upper and lower bounds and prove Lemma 9. Proof of Lemma 9. Set c1≔18,c2≔12,c3≔116.c_1 18, c_2 12, c_3 116. Consider first the case C=h‖p‖2≤c1C=h p_2≤ c_1. By Theorems 13 and 11, we have that (1−exp(−C22))(1−2C2h−2C)≤Pr(H≤h∣C)≤2(1−exp(−C22)). (1- (- C^22 ) ) (1- 2C^2h-2C )≤ (H≤ h C )≤ 2 (1- (- C^22 ) ). Since C≤c1C≤ c_1, we have C2/2≤1/128C^2/2≤ 1/128, and therefore e−C2/2≤1−C24.e^-C^2/2≤ 1- C^24. Thus C24(1−2C2h−2C)≤Pr(H≤h∣C)≤C2. C^24 (1- 2C^2h-2C )≤ (H≤ h C )≤ C^2. As C2/h=h‖p‖22≤C≤c1C^2/h=h p_2^2≤ C≤ c_1, we have 1−2C2h−2C≥1−4C≥12,1- 2C^2h-2C≥ 1-4C≥ 12, and therefore C28≤Pr(H≤h∣C)≤C2. C^28≤ (H≤ h C )≤ C^2. Assume now that C=h‖p‖2>c1C=h p_2>c_1. If ‖p‖2>c1 p_2>c_1, then Pr(H≤h∣C)≥Pr(Y1=Y2∣C)=‖p‖22>c12=164. (H≤ h C )≥ (Y_1=Y_2 C )= p_2^2>c_1^2= 164. Otherwise ‖p‖2≤c1 p_2≤ c_1. If ‖p‖2≥c1/2 p_2≥ c_1/2, then Pr(H≤h∣C)≥Pr(H≤2∣C)=‖p‖22≥c124=1256. (H≤ h C )≥ (H≤ 2 C )= p_2^2≥ c_1^24= 1256. If instead ‖p‖2<c1/2 p_2<c_1/2, let h′≔⌊c1/‖p‖2⌋h c_1/ p_2 . Then h′≥1h ≥ 1, h′<h <h, and h′‖p‖2≥c1−‖p‖2>c12=c3,h′‖p‖2≤c1.h p_2≥ c_1- p_2> c_12=c_3, h p_2≤ c_1. In the latter subcase, there exists h′<h <h such that c3≤h′‖p‖2≤c1c_3≤ h p_2≤ c_1. Since C=h‖p‖2>c1C=h p_2>c_1, this also implies h≥3h≥ 3, and therefore h′≥2h ≥ 2. Applying the first case to h′h , we obtain Pr(H≤h∣C)≥Pr(H≤h′∣C)≥h′2‖p‖228≥c328=12048. (H≤ h C )≥ (H≤ h C )≥ h 2 p_2^28≥ c_3^28= 12048. Combining the two cases, we conclude that Pr(H≤h∣C)≥12048minC2,1. (H≤ h C )≥ 12048 \C^2,1 \. ∎ 5.2 Some basic inequalities In the next section, we derive from Lemma 6, several basic inequalities that will be useful throughout the rest of the paper. Claim 14. Let C be an ordered configuration. For any opinions i,j∈[k]i,j∈[k], it holds 13pi2pj2≤qiqj≤3pi2pj2. 13 p_i^2p_j^2≤ q_iq_j≤ 3 p_i^2p_j^2. Proof. By Lemma 6, we know that if pi>pjp_i>p_j, we have that qiqj≤pi2pj2≤3pi2pj2. q_iq_j≤ p_i^2p_j^2≤ 3 p_i^2p_j^2. Also, by the standard inequality minx1y1,x2y2≤x1+x2y1+y2≤maxx1y1,x2y2 \ x_1y_1, x_2y_2 \≤ x_1+x_2y_1+y_2≤ \ x_1y_1, x_2y_2 \, we have qiqj≥pi2pj2pi+3pj3pi+pj≥pi2pj2min13,3=13pi2pj2. q_iq_j≥ p_i^2p_j^2 p_i+3p_j3p_i+p_j≥ p_i^2p_j^2 \ 13,3 \= 13 p_i^2p_j^2. Taking the reciprocal in both equation we prove also the case pj<pip_j<p_i, concluding the proof of 14. ∎ Claim 15. Let C be an ordered configuration. For all opinions i∈[k]i∈[k], it holds pi23‖p‖22≤qiQ≤3pi2‖p‖22. p_i^23 p_2^2≤ q_iQ≤ 3p_i^2 p_2^2. Proof. By 14 for all i,j∈[k]i,j∈[k], qiqj≥13pi2pj2 q_iq_j≥ 13 p_i^2p_j^2. Therefore, we obtain Qqi=∑j∈[k]qjqi≥∑j∈[k]13pj2pi2=‖p‖223pi2. Qq_i= _j∈[k] q_jq_i≥ _j∈[k] 13 p_j^2p_i^2= p_2^23p_i^2. Taking the reciprocal of both sides, we conclude the proof of the upper bound to qi/Qq_i/Q. On the other hand, we know that for all i,j∈[k]i,j∈[k], qiqj≤3pi2pj2 q_iq_j≤ 3 p_i^2p_j^2. Similarly, we have Qqi=∑j∈[k]qjqi≤∑j∈[k]3pj2pi2=3‖p‖22pi2. Qq_i= _j∈[k] q_jq_i≤ _j∈[k]3 p_j^2p_i^2= 3 p_2^2p_i^2. Taking the reciprocal of both sides, we conclude the proof of 15. ∎ Claim 16. Let C be an ordered configuration. For any opinion j s.t. pj>c1p1p_j>c_1p_1 for some constant c1>0c_1>0, it holds qjQ≥c13pj. q_jQ≥ c_13p_j. Proof. By 15, we have qjQ≥pj23∑ℓ∈[k]pℓ2≥pj23p1≥c13pj. q_jQ≥ p_j^23 _ ∈[k]p_ ^2≥ p_j^23p_1≥ c_13p_j. ∎ Claim 17. For all opinions i∈[k]i∈[k], it holds q1qi≥p12pi2p1+3pi3p1+pi≥2p12pi(p1+pi). q_1q_i≥ p_1^2p_i^2 p_1+3p_i3p_1+p_i≥ 2p_1^2p_i(p_1+p_i). Proof. By Lemmas 6 and 4, we have that q1qi≥p12pi2p1+3pi3p1+pi. q_1q_i≥ p_1^2p_i^2 p_1+3p_i3p_1+p_i. We will then prove that p12pi2p1+3pi3p1+pi≥2p12pi(p1+pi). p_1^2p_i^2 p_1+3p_i3p_1+p_i≥ 2p_1^2p_i(p_1+p_i). Since p1>0p_1>0, we divide both sides by p12p_1^2. The inequality is equivalent to 1pi2p1+3pi3p1+pi≥2pi(p1+pi). 1p_i^2 p_1+3p_i3p_1+p_i\;≥\; 2p_i(p_1+p_i). Multiplying both sides by the positive quantity pi2(3p1+pi)(p1+pi)p_i^2(3p_1+p_i)(p_1+p_i), we obtain the equivalent inequality (p1+3pi)(p1+pi)≥ 2pi(3p1+pi).(p_1+3p_i)(p_1+p_i)\;≥\;2p_i(3p_1+p_i). Expanding both sides, p12+4p1pi+3pi2≥ 6p1pi+2pi2.p_1^2+4p_1p_i+3p_i^2\;≥\;6p_1p_i+2p_i^2. Rearranging terms gives p12−2p1pi+pi2≥0,p_1^2-2p_1p_i+p_i^2≥ 0, which is (p1−pi)2≥0.(p_1-p_i)^2≥ 0. Since this holds for all p1≥pip_1≥ p_i, the claim follows. ∎ Now we bound the variance of Ci(t)C^(t)_i conditioning on the previous round. Lemma 18. Let C be an ordered configuration. We have that Var[Ci′∣C]≤Ciminch2‖p‖22,1(1+3pi‖p‖22).Var [C _i C]≤ C_i \c\,h^2 p_2^2,1 \ (1+ 3p_i\|p\|_2^2 ). Proof. Let DiD_i be the number of agents adopting opinion i after seeing it twice, and let D=∑i∈[k]DiD= _i∈[k]D_i. Then D∼Bin(n,Pr(H≤h∣C))D (n, (H≤ h C)). Conditional on D=dD=d, we have Ci′=Bi+(Ci−Hi),Bi∼Bin(d,qiQ),Hi∼Hypergeom(n,Ci,d).C_i =B_i+(C_i-H_i), B_i \! (d, q_iQ ), H_i (n,C_i,d). We have that [Var(Ci′∣D,C)∣C] E[Var(C_i D,C) C] =[DqiQ(1−qiQ)+Dpi(1−pi)n−Dn−1|C] = E [D q_iQ (1- q_iQ )+Dp_i(1-p_i) n-Dn-1\, |\,C] ≤[DqiQ+Dpi|C] ≤ E [D q_iQ+Dp_i\, |\,C] =nPr(H≤h∣C)(qiQ+pi) =n (H≤ h C) ( q_iQ+p_i ) ≤nPr(H≤h∣C)pi(3pi‖p‖22+1). ≤ n (H≤ h C)p_i ( 3p_i p_2^2+1 ). Moreover, we have Var[(Ci′∣D,C)∣C] [ E(C_i D,C) C] =Var[DqiQ+(n−D)pi∣C] =Var[D q_iQ+(n-D)p_i C] =(qiQ−pi)2Var[D∣C] = ( q_iQ-p_i )^2Var[D C] =(qiQ−pi)2nPr(H≤h∣C)(1−Pr(H≤h∣C)) = ( q_iQ-p_i )^2n (H≤ h C) (1- (H≤ h C) ) ≤nPr(H≤h∣C)(qiQ+pi) ≤ n (H≤ h C) ( q_iQ+p_i ) ≤nPr(H≤h∣C)pi(3pi‖p‖22+1). ≤ n (H≤ h C)p_i ( 3p_i p_2^2+1 ). Therefore, we obtain that Var[Ci′∣C] [C_i C] =[Var(Ci′∣D,C)∣C]+Var[(Ci′∣D,C)∣C] = E[Var(C_i D,C) C]+Var[ E(C_i D,C) C] ≤2nPr(H≤h∣C)pi(3pi‖p‖22+1) ≤ 2n (H≤ h C)p_i ( 3p_i p_2^2+1 ) ≤2nminch2‖p‖22,1pi(3pi‖p‖22+1) ≤ 2n \ch^2 p_2^2,1 \p_i ( 3p_i p_2^2+1 ) (by Lemma 9 ) (by @crefcreftypecap~refnumlemma:tight_bound_probability_collision ) Since npi=Cinp_i=C_i, this proves the claim after adjusting the absolute constant. ∎ 6 Amplification of the multiplicative and additive bias in ℒℒPULL(h) 6.1 Expected amplification of the multiplicative bias The following lemma characterizes the expected growth of the ratio C1/CiC_1/C_i. Its proof relies on partitioning the agents into two groups: those who, after h samples, observe two occurrences of the same opinion and update accordingly, and those who retain their current opinion. The first group is responsible for amplifying the bias in favor of C1C_1. The argument therefore builds on two ingredients: Corollary 10, which provides the expected size of this group, and Lemma 4, which quantifies the bias of these agents toward adopting opinion 1. Lemma 19. Let K≔2−11K 2^-11 and η≔2−16η 2^-16. Then, for any system configuration C=(C1,C2,…,Ck)C= (C_1,C_2,…,C_k ) with C1=maxCiC_1= \C_i \ and for every i∈2,…,ki∈ \2,…,k \ such that Ci>0C_i>0, after one round of DéjàVu it holds [C1′∣C][Ci′∣C]≥C1Ci+ηminC1nh2,1(C1Ci−1). E[C _1 C] E[C _i C]≥ C_1C_i+η \ C_1nh^2,1 \ ( C_1C_i-1 ). Moreover, for every such i and for any integer d∈[[D]2,3[D]2]d∈[ E[D]2, 3 E[D]2], [C1′∣D=d,C][Ci′∣D=d,C]≥C1Ci+ηminC1nh2,1(C1Ci−1). E[C _1 D=d,C] E[C _i D=d,C]≥ C_1C_i+η \ C_1nh^2,1 \ ( C_1C_i-1 ). Since the proof of this lemma requires carefully handling a ratio, we divide it into several sublemmas covering different cases. Lemma 20. Let C be an ordered configuration. Let K≔2−11K 2^-11. If h2‖p‖22<1h^2 p_2^2<1 and Kp1h2<6Kp_1h^2<6, then for any integer d∈[[D]2,3[D]2]d∈[ E[D]2, 3 E[D]2] [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C]≥C1Ci+Kp1h224(C1Ci−1). E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C]≥ C_1C_i+ Kp_1h^224 ( C_1C_i-1 ). Proof. By Lemma 9 and by hypothesis, we know that Q≥Kh2‖p‖22Q≥ Kh^2 p_2^2, for some constant K>0K>0. Therefore, conditioning on the event D=dD=d, we have that dn≥K2h2‖p‖22 dn≥ K2h^2 p_2^2. We have [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C] E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C] = = q1Q⋅Q+p1(1−Q)qiQ⋅Q+pi(1−Q),q1Q⋅dn+p1(1−dn)qiQ⋅dn+pi(1−dn) q_1Q· Q+p_1(1-Q) q_iQ· Q+p_i(1-Q), q_1Q· dn+p_1(1- dn) q_iQ· dn+p_i(1- dn) ≥ ≥ q1Q⋅Q+p1qiQ⋅Q+pi,q1Q⋅dn+p1qiQ⋅dn+pi, b/c q1qi≥p1pi q_1Q· Q+p_1 q_iQ· Q+p_i, q_1Q· dn+p_1 q_iQ· dn+p_i, b/c q_1q_i≥ p_1p_i ≥ ≥ q1Q⋅K2⋅h2∑jpj2+p1qiQ⋅K2⋅h2∑jpj2+pi, b/c Q,dn≥K2h2‖p‖22 and q1qi≥p1pi q_1Q· K2· h^2 _jp_j^2+p_1 q_iQ· K2· h^2 _jp_j^2+p_i, b/c Q, dn≥ K2h^2 p_2^2 and q_1q_i≥ p_1p_i = = 1∑jqj/q1⋅K2h2∑jpj2+p1qi/q1∑jqj/q1⋅K2h2∑jpj2+pi 1 _jq_j/q_1· K2h^2 _jp_j^2+p_1 q_i/q_1 _jq_j/q_1· K2h^2 _jp_j^2+p_i ≥ ≥ 1∑j3pj2/p12⋅K2h2∑jpj2+p1qi/q1∑j3pj2/p12⋅K2h2∑jpj2+pi, by 17 b/c q1qj≥p1pj 1 _j3p_j^2/p_1^2· K2h^2 _jp_j^2+p_1 q_i/q_1 _j3p_j^2/p_1^2· K2h^2 _jp_j^2+p_i, by @crefcreftype~refnumeq:qdqlb2 b/c q_1q_j≥ p_1p_j = = p12⋅K2h2+3p1p12⋅qiq1⋅K2h2+3pi p_1^2· K2h^2+3p_1p_1^2· q_iq_1· K2h^2+3p_i ≥ ≥ p12⋅K2h2+3p1pi⋅p1+pi2⋅K2h2+3pi, by 17 p_1^2· K2h^2+3p_1p_i· p_1+p_i2· K2h^2+3p_i, by @crefcreftypecap~refnumeq:qdqlb2 = = p1pi⋅p1⋅K2h2+3p1+pi2⋅K2h2+3 p_1p_i· p_1· K2h^2+3 p_1+p_i2· K2h^2+3 = = p1pi⋅p1⋅K2h2+312(1+pip1)p1⋅K2h2+3 p_1p_i· p_1· K2h^2+3 12 (1+ p_ip_1 )p_1· K2h^2+3 ≥ ≥ p1pi⋅(1+1−12(1+pip1)6K2p1h2), b/c x+3cx+3≥1+1−c6x for x∈[0,3],c∈[0,1]. p_1p_i· (1+ 1- 12 (1+ p_ip_1 )6 K2p_1h^2 ), b/c x+3cx+3≥ 1+ 1-c6x for x∈[0,3],c∈[0,1]. = = p1pi+Kp1h224(p1pi−1) p_1p_i+ Kp_1h^224 ( p_1p_i-1 ) ∎ Lemma 21. Let C be an ordered configuration. Let K≔2−11K 2^-11. If h2‖p‖22<1h^2 p_2^2<1 and Kp1h2>6Kp_1h^2>6, then for any integer d∈[[D]2,3[D]2]d∈[ E[D]2, 3 E[D]2] [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C]≥C1Ci+17(C1Ci−1)if p1pi<287C1Ciif p1pi>2 E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C]≥ cases C_1C_i+ 17 ( C_1C_i-1 ) &if p_1p_i<2\\ 87 C_1C_i &if p_1p_i>2 cases Proof. By Lemma 9 and by our hypothesis, we know that Q≥Kh2‖p‖22Q≥ Kh^2 p_2^2, for some constant K>0K>0. Therefore, conditioning on the event D=dD=d, we have that dn≥K2h2‖p‖22 dn≥ K2h^2 p_2^2. We have [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C] E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C] =q1Q⋅Q+p1(1−Q)qiQ⋅Q+pi(1−Q),q1Q⋅dn+p1(1−dn)qiQ⋅dn+pi(1−dn) = q_1Q· Q+p_1(1-Q) q_iQ· Q+p_i(1-Q), q_1Q· dn+p_1(1- dn) q_iQ· dn+p_i(1- dn) ≥q1Q⋅Q+p1qiQ⋅Q+pi,q1Q⋅dn+p1qiQ⋅dn+pi, b/c q1qi≥p1pi ≥ q_1Q· Q+p_1 q_iQ· Q+p_i, q_1Q· dn+p_1 q_iQ· dn+p_i, b/c q_1q_i≥ p_1p_i ≥q1Q⋅K2⋅h2∑jpj2+p1qiQ⋅K2⋅h2∑jpj2+pi, b/c Q,dn≥K2h2‖p‖22 and q1qi≥p1pi ≥ q_1Q· K2· h^2 _jp_j^2+p_1 q_iQ· K2· h^2 _jp_j^2+p_i, b/c Q, dn≥ K2h^2 p_2^2 and q_1q_i≥ p_1p_i =1∑jqj/q1⋅K2h2∑jpj2+p1qi/q1∑jqj/q1⋅K2h2∑jpj2+pi = 1 _jq_j/q_1· K2h^2 _jp_j^2+p_1 q_i/q_1 _jq_j/q_1· K2h^2 _jp_j^2+p_i ≥1∑j3pj2/p12⋅K2h2∑jpj2+p1qi/q1∑j3pj2/p12⋅K2h2∑jpj2+pi, by 17 b/c q1qj≥p1pj ≥ 1 _j3p_j^2/p_1^2· K2h^2 _jp_j^2+p_1 q_i/q_1 _j3p_j^2/p_1^2· K2h^2 _jp_j^2+p_i, by @crefcreftype~refnumeq:qdqlb2 b/c q_1q_j≥ p_1p_j =p12⋅K2h2+3p1p12⋅qiq1⋅K2h2+3pi = p_1^2· K2h^2+3p_1p_1^2· q_iq_1· K2h^2+3p_i ≥p12⋅K2h2+3p1pi⋅p1+pi2⋅K2h2+3pi, by 17 ≥ p_1^2· K2h^2+3p_1p_i· p_1+p_i2· K2h^2+3p_i, by @crefcreftype~refnumeq:qdqlb2 =p1pi⋅p1⋅K2h2+3p1+pi2⋅K2h2+3 = p_1p_i· p_1· K2h^2+3 p_1+p_i2· K2h^2+3 =p1pi⋅p1⋅K2h2+312(1+pip1)p1⋅K2h2+3 = p_1p_i· p_1· K2h^2+3 12 (1+ p_ip_1 )p_1· K2h^2+3 ≥p1pi⋅612(1+pip1)3+3, b/c K2p1h2≥3 ≥ p_1p_i· 6 12 (1+ p_ip_1 )3+3, b/c K2p_1h^2≥ 3 =p1pi⋅43+pip1. = p_1p_i· 43+ p_ip_1. If p1pi<2 p_1p_i<2, we have that 43+pip1≥1+17(p1pi−1) 43+ p_ip_1≥ 1+ 17( p_1p_i-1), and, therefore, we obtain that [C1′∣D=d,C][Ci′∣D=d,C]≥p1pi+17(p1pi−1). E[C _1 D=d,C] E[C _i D=d,C]≥ p_1p_i+ 17 ( p_1p_i-1 ). If, instead, p1pi≥2 p_1p_i≥ 2, we have that [C1′∣D=d,C][Ci′∣D=d,C] E[C _1 D=d,C] E[C _i D=d,C] ≥p1pi⋅43+pip1 ≥ p_1p_i· 43+ p_ip_1 ≥p1pi⋅87. ≥ p_1p_i· 87. ∎ Lemma 22. Let C be an ordered configuration. Let K≔2−11K 2^-11. Let c≔K2(K+4)c K2(K+4). If h2‖p‖22>1h^2 p_2^2>1, then for any integer d∈[[D]2,3[D]2]d∈[ E[D]2, 3 E[D]2] [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C]≥C1Ci+(1+c)(C1Ci−1)if qiQ≥12pi(1+c)C1Ciif qiQ<12pi E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C]≥ cases C_1C_i+(1+c) ( C_1C_i-1 ) &if q_iQ≥ 12p_i\\ (1+c) C_1C_i &if q_iQ< 12p_i cases Proof. By Lemma 9 and our hypothesis, we know that Q≥KQ≥ K, for some constant K>0K>0. Therefore, conditioning on the event D=dD=d, we have that dn≥K2 dn≥ K2. We have [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C] E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C] =q1Q⋅Q+p1(1−Q)qiQ⋅Q+pi(1−Q),q1Q⋅dn+p1(1−dn)qiQ⋅dn+pi(1−dn) = q_1Q· Q+p_1(1-Q) q_iQ· Q+p_i(1-Q), q_1Q· dn+p_1(1- dn) q_iQ· dn+p_i(1- dn) ≥q1Q⋅K2+p1qiQ⋅K2+pi, b/c q1qi≥p1pi. ≥ q_1Q· K2+p_1 q_iQ· K2+p_i, b/c q_1q_i≥ p_1p_i. Therefore, if qiQ≥12pi q_iQ≥ 12p_i, we obtain [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C] E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C] ≥q1Q⋅K2+p1qiQ⋅K2+pi ≥ q_1Q· K2+p_1 q_iQ· K2+p_i =p1pi+qiK2QqiK2Q+pi(q1qi−p1pi) = p_1p_i+ q_i K2Qq_i K2Q+p_i ( q_1q_i- p_1p_i ) ≥p1pi+Kpi/4Kpi/4+pi(q1qi−p1pi) ≥ p_1p_i+ Kp_i/4Kp_i/4+p_i ( q_1q_i- p_1p_i ) ≥p1pi+K+4(p12pi2(p1+3pi)(3p1+pi)−p1pi), by 17 ≥ p_1p_i+ KK+4 ( p_1^2p_i^2 (p_1+3p_i)(3p_1+p_i)- p_1p_i ), by @crefcreftypecap~refnumeq:qdqlb2 ≥p1pi+K2(K+4)(p1pi−1), b/c x(x+3)3x+1≥32−12xif x≥1. ≥ p_1p_i+ K2(K+4) ( p_1p_i-1 ), b/c x(x+3)3x+1≥ 32- 12x $x≥ 1$. If, instead, qiQ<12pi q_iQ< 12p_i, we have [C1′∣C][Ci′∣C],[C1′∣D=d,C][Ci′∣D=d,C] E[C _1 C] E[C _i C], E[C _1 D=d,C] E[C _i D=d,C] ≥q1Q⋅K2+p1qiQ⋅K2+pi ≥ q_1Q· K2+p_1 q_iQ· K2+p_i =p1(q1K2p1Q+1)pi(qiK2piQ+1) = p_1 ( q_1K2p_1Q+1 )p_i ( q_iK2p_iQ+1 ) ≥p1(q1K2p1Q+1)pi(K4+1) ≥ p_1 ( q_1K2p_1Q+1 )p_i ( K4+1 ) ≥p1(K2+1)pi(K4+1), b/c q1Q>p1. ≥ p_1 ( K2+1 )p_i ( K4+1 ), b/c q_1Q>p_1. Since K2+1K4+1=2K+4K+4=1+K+4≥1+K2(K+4)=1+c, K2+1 K4+1= 2K+4K+4=1+ KK+4≥ 1+ K2(K+4)=1+c, this proves the second branch of the claim. ∎ Proof of Lemma 19. If h2‖p‖22<1h^2 p_2^2<1 and Kp1h2<6Kp_1h^2<6, the claim follows from the first sublemma, since p1=C1/np_1=C_1/n. If h2‖p‖22<1h^2 p_2^2<1 and Kp1h2≥6Kp_1h^2≥ 6, then the second sublemma gives [C1′∣C][Ci′∣C]≥C1Ci+17(C1Ci−1) E[C_1 C] E[C_i C]≥ C_1C_i+ 17 ( C_1C_i-1 ) or even [C1′∣C][Ci′∣C]≥87C1Ci. E[C_1 C] E[C_i C]≥ 87 C_1C_i. In either case, [C1′∣C][Ci′∣C]≥C1Ci+ηminC1nh2,1(C1Ci−1), E[C_1 C] E[C_i C]≥ C_1C_i+η \ C_1nh^2,1 \ ( C_1C_i-1 ), because η≤1/7η≤ 1/7 and minC1nh2,1≤1 \ C_1nh^2,1 \≤ 1. The same argument applies conditional on D=dD=d. Finally, if h2‖p‖22>1h^2 p_2^2>1, then p1≥‖p‖22p_1≥ p_2^2, hence h2p1≥h2‖p‖22>1h^2p_1≥ h^2 p_2^2>1, so minC1nh2,1=1. \ C_1nh^2,1 \=1. The third sublemma yields either [C1′∣C][Ci′∣C]≥C1Ci+K2(K+4)(C1Ci−1), E[C_1 C] E[C_i C]≥ C_1C_i+ K2(K+4) ( C_1C_i-1 ), or [C1′∣C][Ci′∣C]≥(1+K+4)C1Ci≥C1Ci+K+4(C1Ci−1). E[C_1 C] E[C_i C]≥ (1+ KK+4 ) C_1C_i≥ C_1C_i+ KK+4 ( C_1C_i-1 ). Since η≤K2(K+4)η≤ K2(K+4), this proves the claim. Again, the same argument works conditional on D=dD=d. ∎ 6.2 Expected amplification of the additive bias The next lemma translates the expected increase in multiplicative bias into an increase in additive bias, provided that C1C_1 is not too large. Moreover, it quantifies the growth of the majority opinion C1C_1 and of Δj′C1′ _j C _1. The growth of the latter quantity will be useful to ensure the bias at the next round continues to satisfy the initial condition. Lemma 23. Let γ≔2−19γ 2^-19. Then the following holds. Consider a configuration C such that C1≥C2≥…≥Ck>0C_1≥ C_2≥…≥ C_k>0. Furthermore, suppose C1<34nC_1< 34n. Then, for every j∈2,…,kj∈ \2,…,k \, we have [Δj′∣C]≥Δj(1+γminC1nh2,1), E [ _j C]≥ _j (1+γ \ C_1nh^2,1 \ ), (4) [Δj′∣C][C1′]≥Δ2C1(1+γ/3minC1nh2,1), E [ _j C] E [C _1]≥ _2 C_1 (1+γ/3 \ C_1nh^2,1 \ ), (5) [Δj′∣C][C1′∣C]≥ΔjC1[C1′∣C]C1 E[ _j C] E[C_1 C]≥ _j C_1 E[C_1 C]C_1 (6) [C1′∣C]≥C1+γα(C1,h)7(C1−C2) E[C_1 C]≥ C_1+ γα(C_1,h)7 (C_1-C_2 ) (7) Moreover, the bound in Equation 5 is uniform in j, since Δj≥Δ2 _j≥ _2 for every j≥2j≥ 2. Proof. Let α≔α(C1,h)=ηminC1nh2,1α α(C_1,h)=η \ C_1nh^2,1 \, for η=2−19η=2^-19. By Lemma 19, we have that for all j∈2,…,kj∈ \2,…,k \ [C1′∣C][Cj′∣C]≥C1Cj+αC1−CjCj≥C1Cj+αC1−C2Cj, E[C_1 C] E[C_j C]≥ C_1C_j+α C_1-C_jC_j≥ C_1C_j+α C_1-C_2C_j, and that [C1′∣C]≥C1 E [C_1 C]≥ C_1. Take reciprocal and sum over j∈[k]j∈[k] and obtain that n[C1′∣C]≤n−C1C1+α(C1−C2)+1. n E[C_1 C]≤ n-C_1C_1+α(C_1-C_2)+1. This rewrites as [C1′∣C]≥(C1+α(C1−C2))n+α(C1−C2). E[C_1 C]≥ (C_1+α (C_1-C_2 ) ) nn+α (C_1-C_2 ). Since α<1α<1 and we are assuming that C1<34nC_1< 34n, we have 7C1+α(C1−C2)6<8C16<n 7C_1+α(C_1-C_2)6< 8C_16<n. It is easy to check that this implies [C1′∣C]≥C1+α7(C1−C2), E[C_1 C]≥ C_1+ α7 (C_1-C_2 ), proving Equation 7. By applying Lemma 19 again, we obtain for all j∈2,…,kj∈ \2,…,k \ [C1′−Cj′∣C] E[C_1 -C _j C] =[C1′∣C](1−[Cj′∣C][C1′∣C]) = E[C_1 C] (1- E[C_j C] E[C_1 C] ) ≥[C1′∣C](1−CjC1+α7(C1−Cj)) ≥ E[C_1 C] (1- C_jC_1+ α7 (C_1-C_j ) ) (8) This implies that [C1′−Cj′∣C] E[C_1 -C _j C] ≥(C1+α7(C1−C2))((C1−Cj)(1+α7)C1+α7(C1−Cj)) ≥ (C_1+ α7 (C_1-C_2 ) ) ( (C_1-C_j)(1+ α7)C_1+ α7 (C_1-C_j ) ) (by Equation 7) (by @crefcreftypecap~refnumeq:growth_majority_opinion_expectation ) ≥(C1−Cj)(1+α7), ≥(C_1-C_j)(1+ α7), proving Equation 4. Equations 8 and 7 imply also that [C1′−Cj′∣C] E[C_1 -C _j C] ≥[C1′−C2′∣C] ≥ E[C_1 -C _2 C] ≥[C1′∣C](C1−C2)(1+α7)C1+α7(C1−C2) ≥ E[C_1 C] (C_1-C_2 )(1+ α7) C_1+ α7 (C_1-C_2 ) =[C1′∣C]Δ2C11+α71+α7C1−C2C1 = E[C_1 C] _2 C_1 1+ α7 1+ α7 C_1-C_2C_1 ≥[C1′∣C]Δ2C11+α7 ≥ E[C_1 C] _2 C_1 1+ α7 ≥[C1′∣C]Δ2C1(1+α21) ≥ E[C_1 C] _2 C_1 (1+ α21 ) (1+x≥1+x3 for x∈[0,3]) ( 1+x≥ 1+ x3 for x∈[0,3] ) proving Equation 5. By Equation 8 we have that [Δj′∣C] E[ _j C] ≥[C1′∣C](Δj(1+α/7)C1+α7Δj) ≥ E[C_1 C] ( _j(1+α/7)C_1+ α7 _j ) ≥[C1′∣C](ΔjC1) ≥ E[C_1 C] ( _jC_1 ) (Δj≤C1). ( _j≤ C_1 ). Rearranging the last equation we proved Equation 6 and concluded the proof of Lemma 23. ∎ In the next lemma we show that whenever the configuration is unbalanced, the bias grows considerably more. Lemma 24 (Bias growth in the genuinely unbalanced regime). Suppose the current ordered configuration is C=(C1,…,Ck)C=(C_1,…,C_k), with C1=ω(logn)C_1=ω( n) and C1≤45nC_1≤ 45n. Fix an opinion i∈2,…,ki∈ \2,…,k \ such that Ci>0C_i>0. Assume ‖p‖22<p1+pi24,Δi≥λmaxnh2,C1logn p_2^2< p_1+p_i24, _i≥λ \ nh^2,C_1 \ n for a sufficiently large absolute constant λ>0λ>0. Then [Δi′∣C]≥Δi(1+(p1+pi)minh2‖p‖22,1212‖p‖22). E[ _i C]≥ _i (1+ (p_1+p_i) \h^2 p_2^2,1 \2^12 p_2^2 ). Proof. Since the following three facts hold q1−qiQ=q1+qiQ⋅q1qi−1q1qi+1, q_1-q_iQ= q_1+q_iQ· q_1q_i-1 q_1q_i+1, the function f(x)≔(x−1)/(x+1)f(x) (x-1)/(x+1) is increasing on (0,∞)(0,∞), and q1qi≥2p12pi(p1+pi), q_1q_i≥ 2p_1^2p_i(p_1+p_i), by 17, we obtain that q1qi−1q1qi+1≥f(2p12pi(p1+pi))=2p12pi(p1+pi)−12p12pi(p1+pi)+1. q_1q_i-1 q_1q_i+1≥ f\! ( 2p_1^2p_i(p_1+p_i) )= 2p_1^2p_i(p_1+p_i)-1 2p_1^2p_i(p_1+p_i)+1. Therefore q1−qiQ≥q1+qiQ⋅2p12pi(p1+pi)−12p12pi(p1+pi)+1. q_1-q_iQ≥ q_1+q_iQ· 2p_1^2p_i(p_1+p_i)-1 2p_1^2p_i(p_1+p_i)+1. By 15, q1+qiQ≥p12+pi23‖p‖22 q_1+q_iQ≥ p_1^2+p_i^23 p_2^2, and we obtain q1−qiQ≥p12+pi23‖p‖22⋅2p12pi(p1+pi)−12p12pi(p1+pi)+1. q_1-q_iQ≥ p_1^2+p_i^23 p_2^2· 2p_1^2p_i(p_1+p_i)-1 2p_1^2p_i(p_1+p_i)+1. Moreover, 2p12pi(p1+pi)−12p12pi(p1+pi)+1=(p1−pi)(2p1+pi)2p12+p1pi+pi2≥p1−pip1+pi, 2p_1^2p_i(p_1+p_i)-1 2p_1^2p_i(p_1+p_i)+1= (p_1-p_i)(2p_1+p_i)2p_1^2+p_1p_i+p_i^2≥ p_1-p_ip_1+p_i, where the last inequality is equivalent to (2p1+pi)(p1+pi)≥2p12+p1pi+pi2(2p_1+p_i)(p_1+p_i)≥ 2p_1^2+p_1p_i+p_i^2. Hence q1−qiQ≥p12+pi23‖p‖22⋅p1−pip1+pi≥(p1−pi)(p1+pi)6‖p‖22, q_1-q_iQ≥ p_1^2+p_i^23 p_2^2· p_1-p_ip_1+p_i≥ (p_1-p_i)(p_1+p_i)6 p_2^2, where the last step uses p12+pi2≥(p1+pi)2/2p_1^2+p_i^2≥(p_1+p_i)^2/2. Since we have [Cr′∣C]=nQqrQ+(1−Q)Cr, E[C_r C]=nQ q_rQ+(1-Q)C_r, we obtain that [Δi′∣C]−Δi=nQ(q1−qiQ−(p1−pi))≥nQ(p1−pi)(p1+pi6‖p‖22−1). E[ _i C]- _i=nQ ( q_1-q_iQ-(p_1-p_i) )≥ nQ(p_1-p_i) ( p_1+p_i6 p_2^2-1 ). Since by hypothesis ‖p‖22<(p1+pi)/24 p_2^2<(p_1+p_i)/24, we get [Δi′∣C]−Δi≥Q(p1−pi)(p1+pi)2‖p‖22. E[ _i C]- _i≥ Q(p_1-p_i)(p_1+p_i)2 p_2^2. Since by Lemma 9 Q≥2−11minh2‖p‖22,1Q≥ 2^-11 \h^2 p_2^2,1 \, we conclude the proof of Lemma 24. ∎ Lemma 25. Let α=α(C1,h)=minC1nh2,1α=α(C_1,h)= \ C_1nh^2,1 \. Let C be an ordered configuration such that nC1≥24‖C‖22nC_1≥ 24\|C\|_2^2. It holds [C1′∣C]≥C1(1+γα724nC1‖C‖22). E[C _1 C]≥ C_1 (1+γα 724 nC_1\|C\|_2^2 ). Proof. By 15 it holds that [C1′∣C]=(1−Q)C1+nQq1Q≥C1(1+Q(nC13‖C‖22−1)). E[C _1 C]=(1-Q)C_1+nQ q_1Q≥ C_1 (1+Q ( nC_13\|C\|_2^2-1 ) ). If we now apply Lemma 9, we obtain that [C1′∣C]≥C1(1+γα(724nC1‖C‖22+124nC1‖C‖22−1)), E[C _1 C]≥ C_1 (1+γα ( 724 nC_1\|C\|_2^2+ 124 nC_1\|C\|_2^2-1 ) ), and using the hypothesis nC1≥24‖C‖22nC_1≥ 24\|C\|_2^2 we conclude the proof of Lemma 25. ∎ 6.3 Amplification in concentration In this section, we will prove that the bias amplifies w.h.p. by demonstrating that it is concentrated around the expectation computed in Lemma 23. Furthermore, we demonstrate that, in the subsequent round, the bias and the counter of the largest opinion satisfy the minimum requirements necessary to enable the iteration of our amplification analysis. We start quantifying the deviation from the mean of each opinion count. The main tool we use is Bernstein’s inequality. Lemma 26. Let α=α(C1,h)=minC1nh2,1α=α(C_1,h)= \ C_1nh^2,1 \. Assume αC1≥lognα C_1≥ n, and C1≥CjC_1≥ C_j for all j∈[k]j∈[k]. Let ℰE be the event ℰ=⋂j∈[k]|Cj′−[Cj′∣C]|≤λ1αnC12logn‖C‖22,E= _j∈[k] \ |C_j - E[C _j C]|≤ _1 α nC_1^2 n\|C\|_2^2 \, for some constant λ1 _1 large enough. We have that Pr(ℰ∣C)≥1−n−100 E C≥ 1-n^-100. Proof. By Lemma 18, it holds for all j∈[k]j∈[k] Var[Cj′∣C] [C_j C] ≤Var[C1′∣C] [C_1 C] =O(nC12‖C‖22minh2‖C/n‖22,1) =O ( nC_1^2\|C\|_2^2 \h^2\|C/n\|^2_2,1 \) =O(nαC12‖C‖22), =O ( nα C_1^2\|C\|_2^2), where in the last inequality we used the fact that ‖C/n‖22≤C1/n\|C/n\|^2_2≤ C_1/n. By Lemma 52, we obtain that Pr(|Cj′−[Cj′∣C]|≥t)≤1n101, ( |C_j - E[C_j C]|≥ t )≤ 1n^101, for t=λ1maxlogn,nαC12logn‖C‖22t= _1 \ n, nα C_1^2 n\|C\|_2^2 \, for a constant λ1 _1 large enough. Since αC1≥lognα C_1≥ n and ‖C‖22≤nC1\|C\|^2_2≤ nC_1, we obtain t=λ1nαC12logn‖C‖22t= _1 nα C_1^2 n\|C\|_2^2, as nαC12logn‖C‖22≥logn. nα C_1^2 n\|C\|_2^2≥ n. The proof of Lemma 26 now follows by a union bound. ∎ We continue with the additive version of the bias amplification which holds with high probability. Lemma 27 (Bias amplification in concentration). Let ℰE be the event defined in Lemma 26. Suppose the current ordered configuration is C=(C1,…,Ck)C=(C_1,…,C_k). Also, assume αC1=ω(logn)α C_1=ω( n) and C1≤45nC_1≤ 45n. Furthermore, assume that for every opinion i∈2,…,ki∈\2,…,k\, we have Δi≥λmaxnh2,C1logn _i≥λ \ nh^2,C_1 \ n for a large enough constant λ>0λ>0. Then there exists an absolute constant cB>0c_B>0 such that Pr(∩i∈2,…,kΔi′≥Δi(1+cBminC1nh2,1)|C,ℰ)=1. ( _i∈ \2,…,k \ \ _i≥ _i (1+c_B \ C_1nh^2,1 \ ) \\, |\,C,E )=1. Proof. First, notice that the hypothesis on the bias implies that Δi≥λ(C1lognα). _i≥λ ( C_1 nα ). (9) Let t=λ1nαC12logn‖C‖22t= _1 nα C_1^2 n\|C\|_2^2. First consider the case ‖C‖22≤nC1≤24‖C‖22\|C\|_2^2≤ nC_1≤ 24\|C\|_2^2, and therefore t≤λ2αC1lognt≤ _2 α C_1 n, for λ2=λ124 _2= _1 24. Conditioning on ℰE, we have that by Lemma 23 (Equation 4) Δi′ _i ≥[Δi′∣C]−2t ≥ E[ _i C]-2t ≥Δi(1+γα(C1,h))−2t ≥ _i (1+γα(C_1,h) )-2t ≥Δi(1+γ2α(C1,h))+(λγ2−2λ2)α(C1,h)C1logn. ≥ _i (1+ γ2α(C_1,h) )+(λ γ2-2 _2) α(C_1,h)C_1 n. (by Equation 9) (by @crefcreftypecap~refnumeq:condition_on_bias_function_of_alpha ) By taking λ s.t. λ≥4λ2γ−1λ≥ 4 _2γ^-1, we proved the claim whenever ‖C‖22≤nC1≤24‖C‖22\|C\|_2^2≤ nC_1≤ 24\|C\|_2^2. Now consider the remaining case, nC1≥24‖C‖22nC_1≥ 24\|C\|_2^2. Conditioning on ℰE, we have that by Lemma 24 Δi′ _i ≥Δi(1+nC1minh2‖C/n‖22,1212‖C‖22)−2t ≥ _i (1+ nC_1 \h^2\|C/n\|^2_2,1 \2^12\|C\|^2_2 )-2t ≥Δi(1+2−12α)−2t ≥ _i (1+2^-12α )-2t (nC1≥‖C‖22) (nC_1≥\|C\|^2_2 ) ≥Δi(1+2−13α)+λ2−13αC1logn−2λ1nαC12logn‖C‖22 ≥ _i (1+2^-13α )+λ 2^-13 α C_1 n-2 _1 nα C_1^2 n\|C\|_2^2 ≥Δi(1+2−13α)+(λ2−13−2λ1)αC1logn, ≥ _i (1+2^-13α )+ (λ 2^-13-2 _1 ) α C_1 n, (‖C‖22≤nC1) (\|C\|^2_2≤ nC_1 ) which concludes the proof of Lemma 27 if we take λ≥214λ1λ≥ 2^14 _1. ∎ In the next lemma we show that, w.h.p., C1′≥C1C_1 ≥ C_1, which enforces the condition C1′=ω(logn)C_1 =ω( n) at the next round. Lemma 28 (Majority opinion does not decrease in concentration). Let ℰE be the event defined in Lemma 26. Suppose the current ordered configuration is C=(C1,…,Ck)C=(C_1,…,C_k). Also, assume αC1=ω(logn)α C_1=ω( n) and C1≤45nC_1≤ 45n. Then Pr(C1′≥C1∣ℰ,C)=1 (C_1 ≥ C_1 ,C )=1. Proof. Let α≔α(C1,h)=minC1nh2,1α α(C_1,h)= \ C_1nh^2,1 \. Let t=λ1nαC12logn‖C‖22t= _1 nα C_1^2 n\|C\|_2^2. First consider the case ‖C‖22≤nC1≤24‖C‖22\|C\|_2^2≤ nC_1≤ 24\|C\|_2^2, and therefore t≤λ2αC1lognt≤ _2 α C_1 n, for λ2=λ124 _2= _1 24. Conditioning on ℰE, we have that by Lemma 23 (Equation 7) C1′ C _1 ≥[C1′∣C]−t ≥ E[C _1 C]-t ≥C1(1+γ7α)−t ≥ C_1 (1+ γ7α )-t ≥C1+αC1(γ7−λ2lognαC1)≥C1. ≥ C_1+α C_1 ( γ7- _2 nα C_1 )≥ C_1. (αC1=ω(logn)) (α C_1=ω( n) ) Now consider the remaining case, nC1≥24‖C‖22nC_1≥ 24\|C\|_2^2. Conditioning on ℰE, we have that by Lemma 25 C1′ C _1 ≥C1(1+γα724nC1‖C‖22)−t ≥ C_1 (1+γα 724 nC_1\|C\|_2^2 )-t ≥C1+αC1nC1‖C‖22(7γ24nC1‖C‖22−λ1lognαC1) ≥ C_1+α C_1 nC_1\|C\|_2^2 ( 7γ24 nC_1\|C\|_2^2- _1 nα C_1 ) ≥C1, ≥ C_1, (nC1≥24‖C‖22,αC1=ω(logn)) (nC_1≥ 24\|C\|_2^2,α C_1=ω( n) ) which concludes the proof of Lemma 28. ∎ In Lemma 27, we showed that the bias at the next round increases by a multiplicative factor if the current bias satisfies Δi≥λmaxnh2,C1logn _i≥λ \ nh^2,C_1 \ n. However, showing that Δi′≥Δi _i ≥ _i is not enough to ensure that this condition holds at the next round, as the right hand side depends on C1C_1, which we know grows. Therefore, in the next lemma we show that w.h.p. the bias at the next round satisfies the condition. Lemma 29 (Condition on bias is preserved). Let ℰE be the event defined in Lemma 26. Suppose the current ordered configuration is C=(C1,…,Ck)C=(C_1,…,C_k), with αC1≥logn,C1≤45n.α C_1≥ n, C_1≤ 45n. Assume that for every opinion i∈2,…,ki∈ \2,…,k \ it holds Δi≥λmaxnh2,C1logn, _i≥λ \ nh^2,C_1 \ n, for a sufficiently large absolute constant λ>0λ>0, it holds that Pr(∩i∈2,…,kΔi′≥λmaxnh2,C1′logn|C,ℰ)=1. ( _i∈ \2,…,k \ \ _i ≥λ \ nh^2,C_1 \ n \\, |\,C,E )=1. Proof. Let α≔α(C1,h)=minC1nh2,1α α(C_1,h)= \ C_1nh^2,1 \. Fix an opinion i∈2,…,ki∈ \2,…,k \. Let t=λ1nαC12logn‖C‖22t= _1 nα C_1^2 n\|C\|_2^2. Conditioning on ℰE, we have that Δi′C1′ _i C_1 ≥[Δi′∣C]−2t[C1′∣C]+t ≥ E[ _i C]-2t E[C_1 C]+t ≥[Δi′∣C][C1′∣C]−t[Δi′∣C]+4[C1′∣C]2[C1′∣C][C1′∣C] ≥ E[ _i C] E[C_1 C]-t E[ _i C]+4 E[C_1 C]2 E[C_1 C] E[C_1 C] (Taylor expansion and convexity) (Taylor expansion and convexity ) =[Δi′∣C][C1′∣C]−t5[C1′∣C]−[Ci′∣C]2[C1′∣C][C1′∣C] = E[ _i C] E[C_1 C]-t 5 E[C_1 C]- E[C_i C]2 E[C_1 C] E[C_1 C] ≥[Δi′∣C][C1′∣C]−5t2[C1′∣C] ≥ E[ _i C] E[C_1 C]- 5t2 E[C_1 C] (10) =[Δi′∣C][C1′∣C](1−5t2[C1′−Ci′∣C]). = E[ _i C] E[C_1 C] (1- 5t2 E[C_1 -C_i C] ). (11) First consider the case ‖C‖22≤nC1≤24‖C‖22\|C\|_2^2≤ nC_1≤ 24\|C\|_2^2, and therefore t≤λ2αC1lognt≤ _2 α C_1 n, for λ2=λ124 _2= _1 24. By Lemma 23 (Equation 5), Equation 11 implies Δi′C1′ _i C_1 ≥Δ2C1(1+γα3)(1−5λ2αC1logn2Δi(1+γα)) ≥ _2 C_1 (1+ γα3 ) (1- 5 _2 α C_1 n2 _i (1+γα ) ) ≥Δ2C1(1+γα3)(1−5λ2αC1logn2λC1lognα(1+γα)) ≥ _2 C_1 (1+ γα3 ) (1- 5 _2 α C_1 n2λ C_1 nα (1+γα ) ) (By Equation 9) (By @crefcreftypecap~refnumeq:condition_on_bias_function_of_alpha ) =Δ2C1(1+γα3)(2λC1lognα+(2λγ−5λ2)αC1logn2λC1lognα(1+γα)) = _2 C_1 (1+ γα3 ) ( 2λ C_1 nα+ (2λγ-5 _2 ) α C_1 n2λ C_1 nα (1+γα ) ) ≥Δ2C1(1+γα3)(1+34γα1+γα) ≥ _2 C_1 (1+ γα3 ) ( 1+ 34γα1+γα ) (by taking λ large enough) (by taking $λ$ large enough ) ≥Δ2C1 ≥ _2 C_1 ≥λlognα. ≥λ nα. This proves the claim whenever ‖C‖22≤nC1≤24‖C‖22\|C\|_2^2≤ nC_1≤ 24\|C\|_2^2. Now consider the remaining case, nC1≥24‖C‖22nC_1≥ 24\|C\|_2^2. By Lemma 23 (Equation 6), Equation 11 implies Δi′C1′ _i C_1 ≥Δ2C1[C1′∣C]C1(1−5λ1nαC12logn‖C‖22Δi(1+γαnC1‖C‖22)) ≥ _2 C_1 E[C _1 C]C_1 (1- 5 _1 nα C_1^2 n\|C\|_2^2 _i (1+γα nC_1\|C\|_2^2 ) ) ≥Δ2C1[C1′∣C]C1(1−5λ1nαC12logn‖C‖222λC1lognα(1+γαnC1‖C‖22)) ≥ _2 C_1 E[C _1 C]C_1 (1- 5 _1 nα C_1^2 n\|C\|_2^22λ C_1 nα (1+γα nC_1\|C\|_2^2 ) ) (By Equation 9) (By @crefcreftypecap~refnumeq:condition_on_bias_function_of_alpha ) =Δ2C1[C1′∣C]C1(2λC1lognα+(2λγnC1‖C‖22−5λ1)nαC12logn‖C‖222λC1lognα(1+γαnC1‖C‖22)) = _2 C_1 E[C _1 C]C_1 ( 2λ C_1 nα+ (2λγ nC_1\|C\|^2_2-5 _1 ) nα C_1^2 n\|C\|_2^22λ C_1 nα (1+γα nC_1\|C\|_2^2 ) ) ≥Δ2C1[C1′∣C]C1(1+34γαnC1‖C‖221+γαnC1‖C‖22) ≥ _2 C_1 E[C _1 C]C_1 ( 1+ 34γα nC_1\|C\|_2^21+γα nC_1\|C\|_2^2 ) (for large λ) (for large $λ$ ) ≥Δ2C11+γα724nC1‖C‖22(1+34γαnC1‖C‖221+γαnC1‖C‖22) ≥ _2 C_1 1+γα 724 nC_1\|C\|^2_2 ( 1+ 34γα nC_1\|C\|_2^21+γα nC_1\|C\|_2^2 ) (by Lemma 25) (by @crefcreftypecap~refnumclaim:expectation_growth_C_1_unbalanced ) ≥Δ2C1, ≥ _2 C_1, ≥λlognα. ≥λ nα. where in the second-last inequality we used the fact that, if x≥24x≥ 24, then 1+724x(1+34x)1+x≥1 1+ 724x (1+ 34x )1+x≥ 1. Moreover, by Lemma 28, on the event ℰE we have C1′≥C1C_1 ≥ C_1. Therefore, 1α=maxnh2C1,1≥maxnh2C1′,1, 1α= \ nh^2C_1,1 \≥ \ nh^2C_1 ,1 \, and hence λlognα≥λmaxnh2C1′,1logn.λ nα≥λ \ nh^2C_1 ,1 \ n. Multiplying both sides by C1′ C_1 , we conclude that Δi′≥λmaxnh2,C1′logn, _i ≥λ \ nh^2,C_1 \ n, as claimed. ∎ 6.4 Convergence time of DéjàVu To prove Theorem 1, we need one last lemma to handle the case in which C1≥3n4C_1≥ 3n4. In this regime, we reduce the analysis to the better-understood binary case by merging all remaining opinions. Lemma 30 (Binary merging domination). Let C(0)=(C1(0),…,Ck(0))C^(0)=(C_1^(0),…,C_k^(0)) be an initial configuration, and let C¯(0)=(C1(0),n−C1(0)) C^(0)=(C_1^(0),n-C_1^(0)) be the binary configuration obtained by merging all opinions i≠1i≠ 1 into a single competing opinion. Let (C(t))t≥0 (C^(t) )_t≥ 0 be the DéjàVu process started from C(0)C^(0), and let (C¯(t))t≥0 ( C^(t) )_t≥ 0 be the binary DéjàVu process started from C¯(0) C^(0). Then there exists a coupling such that C¯1(t)≤C1(t) C_1^(t)≤ C_1^(t) for all t≥0t≥ 0. In particular, the consensus time on opinion 11 in the original process is stochastically dominated by the consensus time in the merged binary process. Proof. We realize the two processes on the same set of n agents. For each round t, let At≔u∈[n]:agent u has opinion 1 in the original process at time tA_t \u∈[n]:agent $u$ has opinion $1$ in the original process at time $t$ \ and Bt≔u∈[n]:agent u has opinion 1 in the binary process at time t.B_t \u∈[n]:agent $u$ has opinion $1$ in the binary process at time $t$ \. We construct the coupling so that Bt⊆AtB_t A_t for every t≥0t≥ 0. At time t=0t=0, choose B0=A0B_0=A_0, so that |B0|=C¯1(0)=C1(0)|B_0|= C_1^(0)=C_1^(0). Assume inductively that Bt⊆AtB_t A_t. For every agent u, reveal the same sampled agents v1,…,vhv_1,…,v_h in both processes during round t. In the original process, the sampled opinions are the actual opinions of v1,…,vhv_1,…,v_h. In the binary process, we declare that a sampled agent has opinion 11 if it belongs to BtB_t, and opinion 0 otherwise. Since |Bt|=C¯1(t)|B_t|= C_1^(t), this gives exactly the correct law for one round of the binary process started from C¯(t) C^(t). Fix an agent u. We claim that, under this coupling, u∈Bt+1≤u∈At+1.1 \u∈ B_t+1 \ 1 \u∈ A_t+1 \. If u∈Bt+1u∈ B_t+1, then either: 1. the binary process observes a repeated 11 before any repeated 0, or 2. no opinion is repeated within the first h samples and u∈Btu∈ B_t, so u keeps opinion 11. In the first case, before the second sampled agent from BtB_t appears, there is at most one sampled agent outside BtB_t. Since Bt⊆AtB_t A_t, this implies that before that same time there is at most one sampled agent outside AtA_t, hence in the original process no opinion different from 11 can appear twice. On the other hand, the two samples from BtB_t are also two samples of opinion 11 in the original process. Therefore the first repeated opinion in the original process is also 11, and u∈At+1u∈ A_t+1. In the second case, u∈Bt⊆Atu∈ B_t A_t, so u starts the round with opinion 11 also in the original process. Moreover, if no opinion is repeated in the binary process within the first h samples, then necessarily h=2h=2, with one sampled agent in BtB_t and one sampled agent outside BtB_t. Hence in the original process either the two samples have different opinions, in which case u keeps opinion 11, or the sampled agent outside BtB_t belongs to At∖BtA_t B_t, in which case the two original samples are both equal to 11 and u adopts opinion 11. Thus again u∈At+1u∈ A_t+1. Since this holds for every agent u, we obtain Bt+1⊆At+1B_t+1 A_t+1. By induction, Bt⊆AtB_t A_t for all t≥0t≥ 0, and therefore C¯1(t)=|Bt|≤|At|=C1(t) C_1^(t)=|B_t|≤|A_t|=C_1^(t) for all t≥0t≥ 0. Finally, if the merged binary process reaches consensus on opinion 11 at time t, then C¯1(t)=n C_1^(t)=n. Since C¯1(t)≤C1(t)≤n C_1^(t)≤ C_1^(t)≤ n, it follows that C1(t)=nC_1^(t)=n as well. ∎ We are now ready to prove Theorem 1, which we now restate for convenience. Theorem. Let h≥2h≥ 2 and C=(C1,…,Ck)C=(C_1,…,C_k) be an initial system configuration where each agent supports an opinion in 1,…,k\1,…,k\. Without loss of generality, let C1≥C2≥⋯≥CkC_1≥ C_2≥·s≥ C_k. Assume that C1=ω(logn)C_1=ω ( n ) and that, for a large enough constant λ>0λ>0, C1−C2≥λmaxnh2,C1logn.C_1-C_2≥λ \ nh^2,C_1 \ n. DéjàVu converges to consensus on the first opinion w.h.p. in O((nh2C1+1)logn)O (( nh^2C_1+1) n ) rounds. Proof of Theorem 1. If C1(0)>3n/4C_1^(0)>3n/4, let (C¯(t))t≥0 ( C^(t) )_t≥ 0 be the binary process obtained by merging all opinions i≠1i≠ 1 into a single competing opinion, as in Lemma 30. In the binary setting, DéjàVu coincides with 22-Choices if h=2h=2, and with 33-Majority if h>2h>2. Since C¯1(0)>3n/4 C_1^(0)>3n/4, the known high-probability bounds for these two binary dynamics imply that (C¯(t))t≥0 ( C^(t) )_t≥ 0 reaches consensus on opinion 11 within O(logn)O( n) rounds w.h.p. [S25]. By Lemma 30, the original process reaches consensus on opinion 11 no later than the merged binary process. Therefore the theorem follows in this case. We now consider the remaining case C1(0)≤3n/4C_1^(0)≤ 3n/4. For each round t≥0t≥ 0, define αt≔minC1(t)nh2,1. _t \ C_1^(t)nh^2,1 \. Also define the event ℰ(t)=⋂j∈[k]|Cj(t+1)−[Cj(t+1)∣C(t)]|≤λ1αtn(C1(t))2logn‖C(t)‖22.E^(t)= _j∈[k] \ |C_j^(t+1)- E[C_j^(t+1) C^(t)]|≤ _1 _t\,n(C_1^(t))^2 n\|C^(t)\|_2^2 \. For every round t such that C1(t)≤3n/4C_1^(t)≤ 3n/4, let ℱ(t) ^(t) =⋂i=2kΔi(t+1)≥Δi(t)(1+cBαt), = _i=2^k \ _i^(t+1)≥ _i^(t)(1+c_B _t) \, (t) ^(t) =⋂i=2kΔi(t+1)≥λmaxnh2,C1(t+1)logn, = _i=2^k \ _i^(t+1)≥λ \ nh^2,C_1^(t+1) \ n \, ℋ(t) ^(t) =C1(t+1)≥C1(t). = \C_1^(t+1)≥ C_1^(t) \. Assume that, at some round t, the current configuration satisfies ⋂i=2kΔi(t)≥λmaxnh2,C1(t)lognandC1(t)≤34n. _i=2^k \ _i^(t)≥λ \ nh^2,C_1^(t) \ n \ C_1^(t)≤ 34n. Then, by Lemma 26, Pr(ℰ(t)∣C(t))≥1−n−100. (E^(t) C^(t))≥ 1-n^-100. Moreover, by Lemmas 27, 29 and 28, Pr(ℱ(t)∩(t)∩ℋ(t)∣C(t),ℰ(t))=1. (F^(t) ^(t) ^(t) C^(t),E^(t))=1. Therefore, Pr(ℱ(t)∩(t)∩ℋ(t)∣C(t))≥1−n−100. (F^(t) ^(t) ^(t) C^(t))≥ 1-n^-100. Let τ≔mint≥0:C1(t)>3n/4.τ \t≥ 0:C_1^(t)>3n/4 \. As long as t<τt<τ, event (t)G^(t) implies that the bias condition needed to reapply the previous argument holds at round t+1t+1, while ℋ(t)H^(t) implies that C1(t)C_1^(t) is nondecreasing. Set β≔cBminC1(0)nh2,1.β c_B \ C_1^(0)nh^2,1 \. Since C1(t)≥C1(0)C_1^(t)≥ C_1^(0) for all t<τt<τ, we have αt≥minC1(0)nh2,1 _t≥ \ C_1^(0)nh^2,1 \, and hence on every event ℱ(t)F^(t) with t<τt<τ, Δ2(t+1)≥Δ2(t)(1+β). _2^(t+1)≥ _2^(t)(1+β). Iterating, we obtain Δ2(t)≥Δ2(0)(1+β)tfor every t<τ. _2^(t)≥ _2^(0)(1+β)^t every t<τ. Let τ2≔mint≥0:Δ2(t)>3n/4. _2 \t≥ 0: _2^(t)>3n/4 \. Since Δ2(t)≤C1(t) _2^(t)≤ C_1^(t) for every t, the event Δ2(t)>3n/4 \ _2^(t)>3n/4 \ implies C1(t)>3n/4 \C_1^(t)>3n/4 \, and hence τ≤τ2τ≤ _2. Also define T≔mint∈ℕ:Δ2(0)(1+β)t>3n/4.T \t∈ N: _2^(0)(1+β)^t>3n/4 \. By the previous growth estimate, on the event ⋂s=0T−1(ℱ(s)∩(s)∩ℋ(s)) _s=0^T-1(F^(s) ^(s) ^(s)) we have τ2≤T _2≤ T, and therefore τ≤Tτ≤ T. Moreover, by a union bound, Pr(⋂s=0T−1(ℱ(s)∩(s)∩ℋ(s)))≥1−Tn−100=1−n−Θ(1). \! ( _s=0^T-1(F^(s) ^(s) ^(s)) )≥ 1-Tn^-100=1-n^- (1). Since Δ2(0)≥λmaxn/h2,C1(0)logn≥1 _2^(0)≥λ \n/h^2,C_1^(0) \ n≥ 1, we obtain T=O(lognlog(1+β))=O((nh2C1(0)+1)logn).T=O ( n (1+β) )=O ( ( nh^2C_1^(0)+1) n ). Therefore, with high probability, the process reaches a configuration with C1(t)>3n/4C_1^(t)>3n/4 within O((nh2C1(0)+1)logn)O ( ( nh^2C_1^(0)+1) n ) rounds. We are now back to the case where the majority opinion has size larger than 3n/43n/4, and therefore we can apply the previous argument to conclude that consensus on opinion 11 is reached within an additional O(logn)O( n) rounds w.h.p. Hence the overall convergence time is O((nh2C1(0)+1)logn),O ( ( nh^2C_1^(0)+1) n ), concluding the proof of Theorem 1. ∎ 7 Lower bound for h-majority In this section, we prove Theorem 2, which we restate here for convenience. Theorem. Let ε>0 >0 be any arbitrarily small constant. Let C=(C1,…,Ck)C=(C_1,…,C_k) be the starting configuration of the system, with C1≥…≥CkC_1≥…≥ C_k, and C1≤n/100C_1≤ n/100. For any h≥n0.75+ε/C1h≥ n^0.75+ /C_1, the h-majority process converges in time Ω(n/(h2C1)+1) (n/(h^2C_1)+1) with high probability. To prove Theorem 2, we revisit the proof given by [BCN+17]. We will generally refer to the number of nodes supporting an opinion j at any given time t by CjC_j, and we denote by Cj′C_j the number of nodes supporting opinion j at time t+1t+1 conditional on the system configuration at time t. We rely on the following lemma, adapted from [BCN+17, Lemma 9]. Lemma 31. Let C=(C1,…,Ck)C=(C_1,…,C_k) be the starting configuration of the system, with C1≥…≥CkC_1≥…≥ C_k. If h≥n0.75+ε/C1h≥ n^0.75+ /C_1, then after one round of the h-majority protocol, Pr(Cj′≥(1+h2C1n)C1∣C)≤exp[−nΘ(ε)]. (C_j ≥ (1+ h^2C_1n )C_1 C )≤ [-n ( )]. Proof. Let u∈[n]u∈[n] be any specific node, and let NjN_j be the number of nodes with opinion j picked by u during the sampling stage of h-majority protocol. Let YuY_u be the indicator random variable of the event that node u adopts opinion j. We give an upper bound on the probability of the event Yu=1Y_u=1 by conditioning it on Nj=1N_j=1 and Nj>2N_j>2 (observe that if Nj=0N_j=0 node u cannot choose j as its opinion). Pr(Yu=1)≤Pr(Yu∣Nj=1)Pr(Nj=1)+Pr(Nj≥2). (Y_u=1)≤ (Y_u N_j=1) (N_j=1)+ (N_j≥ 2). (12) The term Pr(Yu=1∣Nj=1) (Y_u=1 N_j=1) is at most 1/h1/h since the only event in which u picks opinion j is that all the h sampled opinions are different. The term Pr(Nj=1) (N_j=1) can be upper bounded by the probability that at least 11 opinion among the sampled ones is 11, which is, by the union bound, at most hCj/nhC_j/n. Finally, the term Pr(Nj≥2) (N_j≥ 2) is at most (h2)Cj2/n2 h2C_j^2/n^2. Hence, Eq. 12 can be rewritten as Pr(Yu=1) (Y_u=1) ≤Cjn+(h2)Cj2n2 ≤ C_jn+ h2 C_j^2n^2 ≤Cjn+h2Cj22n2. ≤ C_jn+ h^2C_j^22n^2. Hence, it holds that [Cj′∣C] E[C_j C] ≤Cj+h2Cj22n ≤ C_j+ h^2C_j^22n =Cj(1+h2Cj2n) =C_j (1+ h^2C_j2n ) ≤Cj(1+h2C12n), ≤ C_j (1+ h^2C_12n ), where the latter inequality holds by the hypothesis on CjC_j. We now consider two cases. First, assume Cj≥C1/2C_j≥ C_1/2. By the Hoeffding bound (Lemma 51), we obtain that Pr(Cj′≥Cj(1+h2C1n)∣C) (C_j ≥ C_j (1+ h^2C_1n ) C ) ≤exp[−2(Cj⋅h2C12n)2n] ≤ [- 2 (C_j· h^2C_12n )^2n ] ≤exp[−h4C12Cj22n3] ≤ [- h^4C_1^2C_j^22n^3 ] ≤exp[−h4C148n3], ≤ [- h^4C_1^48n^3 ], where the latter inequality holds by the hypothesis on CjC_j. To conclude, observe that the hypothesis on h implies that hC1≥n0.75+εhC_1≥ n^0.75+ and, hence, exp[−h4C148n3]≤exp[−n4ε8]. [- h^4C_1^48n^3 ]≤ [- n^4 8 ]. In the second case, we assume Cj<C1/2C_j<C_1/2. Then, Pr(Cj′≥C1(1+h2C12n)∣C) (C_j ≥ C_1 (1+ h^2C_12n ) C ) = =\ Pr(Cj′≥Cj(1+h2C12n)+C1(1+h2C12n)−Cj(1+h2C12n)∣C) (C_j ≥ C_j (1+ h^2C_12n )+C_1 (1+ h^2C_12n )-C_j (1+ h^2C_12n ) C ) = =\ Pr(Cj′≥Cj(1+h2C12n)+(C1−Cj)(1+h2C12n)∣C) (C_j ≥ C_j (1+ h^2C_12n )+(C_1-C_j) (1+ h^2C_12n ) C ) ≤ ≤\ Pr(Cj′≥Cj(1+h2C12n)+C12(1+h2C12n)∣C), (C_j ≥ C_j (1+ h^2C_12n )+ C_12 (1+ h^2C_12n ) C ), where, in the latter inequality, we used that Cj<C1/2C_j<C_1/2. We can continue by observing that Pr(Cj′≥C1(1+h2C12n)∣C) (C_j ≥ C_1 (1+ h^2C_12n ) C ) ≤Pr(Cj′≥Cj(1+h2C12n)+C12(1+h2C12n)∣C) ≤ (C_j ≥ C_j (1+ h^2C_12n )+ C_12 (1+ h^2C_12n ) C ) ≤Pr(Cj′≥Cj(1+h2C12n)+h2C124n∣C). ≤ (C_j ≥ C_j (1+ h^2C_12n )+ h^2C_1^24n C ). By the Hoeffding bound (Lemma 51), we obtain that Pr(Cj′≥C1(1+h2C12n)∣C) (C_j ≥ C_1 (1+ h^2C_12n ) C ) ≤exp[−2(h2C124n)2n] ≤ [- 2 ( h^2C_1^24n )^2n ] =exp[−h4C148n3] = [- h^4C_1^48n^3 ] ≤exp[−n4ε8], ≤ [- n^4 8 ], where the latter inequality comes from the hypothesis on h. Hence, for any j∈[n]j∈[n], it holds that Pr(Cj′≥C1(1+h2C1n)∣C)≤exp[−nΘ(ε)]. (C_j ≥ C_1 (1+ h^2C_1n ) C )≤ [-n ( )]. ∎ We are now ready to prove Theorem 2. Proof of Theorem 2. It is sufficient to iteratively apply Lemma 31 and the union bound. More formally, for any i∈[k]i∈[k], let ci(t)c_i^(t) be the number of nodes supporting opinion i at the end of round t. Note that ci(0)=Cic_i^(0)=C_i for all i∈[k]i∈[k], and that C1≤n/100C_1≤ n/100. Let X(t)=maxj∈[k]cj(t)X^(t)= _j∈[k]\c_j^(t)\. We lower bound the convergence time of the h-majority process by the time τ any opinion reaches at least 100C1100C_1 supporting nodes. Note that, whenever X(t)<100C1X^(t)<100C_1, by the union bound and Lemma 31, it holds that X(t+1)≤X(t)(1+h2(100C1)n)X^(t+1)≤ X^(t) (1+ h^2(100C_1)n ) with probability 1−exp[−nΘ(ε)]1- [-n ( )]. Let T=⌊nln99/(100h2C1)⌋T= n 99/(100h^2C_1) , and denote by EtE_t the event X(t)≤C1(1+h2(100C1)/n)tX^(t)≤ C_1(1+h^2(100C_1)/n)^t. Note that ETE_T implies that X(T)<100C1X^(T)<100C_1, and, hence, ∩t=0TEt _t=0^TE_t implies that τ≥Tτ≥ T. It holds that Pr(τ≥T) (τ≥ T ) ≥Pr(∩t=0TEt) ≥ ( _t=0^TE_t) =∏t=0T−1Pr(Et+1∣∩j=0tEj) = _t=0^T-1 (E_t+1 _j=0^tE_j ) ≥∏t=0T−1Pr(X(t+1)≤X(t)(1+h2(100C1)n)∣∩j=0tEj) ≥ _t=0^T-1 (X^(t+1)≤ X^(t) (1+ h^2(100C_1)n ) _j=0^tE_j ) ≥∏t=0T−1[1−exp[−nΘ(ε)]] ≥ _t=0^T-1 [1- [-n ( )] ] ≥1−Texp[−nΘ(ε)] ≥ 1-T [-n ( )] ≥1−exp[−nΘ(ε)], ≥ 1- [-n ( )], where the third inequality follows because on the event ∩j=0tEj _j=0^tE_j we have X(t)≤C1(1+h2(100C1)n)t<100C1,X^(t)≤ C_1 (1+ h^2(100C_1)n )^t<100C_1, so Lemma 31 applies at round t, while the last two inequalities follow from Bernoulli’s inequality, that is, (1−x)m≥1−mx(1-x)^m≥ 1-mx for any x∈[0,1]x∈[0,1] and m≥1m≥ 1, together with the definition of T and the hypothesis on h and C1C_1. This concludes the proof. ∎ 8 Number of samples required by DéjàVu The goal of this section is to prove Theorem 3. To this end, we derive a lower bound on SmS_m, the number of samples required for convergence of h-Majority, and an upper bound on SdS_d, the number of samples required for convergence of DéjàVu. While SmS_m is simply h times the convergence time of h-Majority, the random variable SdS_d is considerably more intricate, as it depends on the configuration at every round prior to consensus. Consequently, the main technical effort of this section is devoted to proving the following theorem. Theorem 32. Let h≥2h≥ 2 and C=(C1,…,Ck)C=(C_1,…,C_k) be an initial system configuration where each agent supports an opinion in 1,…,k\1,…,k\. Without loss of generality, let C1≥C2≥⋯≥CkC_1≥ C_2≥·s≥ C_k. Assume that C1=ω(log2n)C_1=ω ( ^2n ) and that, for a large enough constant λ>0λ>0, C1−C2≥λmaxnh2,C1logn.C_1-C_2≥λ \ nh^2,C_1 \ n. Let SdS_d be the number of samples of DéjàVu in ℒℒPULL(h). Then, w.h.p., Sd=O(minh,n‖C‖2(nh2C1+1)logn)S_d=O ( \h, n C_2 \ ( nh^2C_1+1 ) n ) The key ingredient in proving this theorem is to show that the ℓ2 _2-norm of the configuration does not decrease by more than a constant multiplicative factor. More precisely, we prove that ‖C(t)‖≥c↓‖C(0)‖\|C^(t)\|≥ c \|C^(0)\| for some absolute constant c↓>0c >0 and for all t≤Tt≤ T, where T denotes the convergence time of DéjàVu. Indeed, by Lemma 9, once ‖p(t)‖\|p^(t)\| is bounded from below, an agent sees a repeated opinion within O(‖p(t)‖−1)O(\|p^(t)\|^-1) samples with constant probability. Therefore, once we establish a uniform lower bound on ‖p(t)‖\|p^(t)\|, we can conclude Theorem 32 by combining this per-round bound with the upper bound on the convergence time. Let us first define the stopping time we will bound. Definition 33 (Stopping times for basic quantities). For constants c↑,c↓>0c ,c >0 define τ↑=inft≥0:‖p(t)‖≥(1+c↑)‖p(0)‖, τ = \t≥ 0:\|p^(t)\|≥(1+c )\|p^(0)\|\, τ↓=inft≥0:‖p(t)‖≤(1−c↓)‖p(0)‖. τ = \t≥ 0:\|p^(t)\|≤(1-c )\|p^(0)\| \. Here is the aforementioned key lemma to prove Theorem 32. Lemma 34 (Bounded decrease of ‖C(t)‖\|C^(t)\|). Consider the stopping times τ↓τ defined in Definition 33. Then, for any T>0T>0, we have Pr[τ↓≤T]≤Texp(−Ω(nh2T+n‖C‖−1))if h‖C(0)‖≤nTexp(−Ω(‖C(0)‖2nT))if h‖C(0)‖>n [τ ≤ T]≤ casesT (- ( nh^2T+n\|C\|^-1)) &if h\|C^(0)\|≤ n\\ T (- ( \|C^(0)\|^2nT)) &if h\|C^(0)\|>n cases We follow the same drift analysis approach presented in [S25] used to analyze 3-majority and 2-choices. In that paper, the authors use a drift analysis based on the Bernstein condition. First, they prove that the euclidean norm of the configuration at round t, ‖Ct‖\|C_t\|, is a sub-martingale. Then they prove that the difference ‖Ct‖−‖Ct−1‖\|C_t\|-\|C_t-1\| conditioned on the (t−1)(t-1)-th configuration satisfies the Bernstein condition. Under these conditions, they show that, it holds that ‖Ct‖=Ω(‖C0‖)\|C_t\|= (\|C_0\| ) w.h.p. for all 0≤t≤n0≤ t≤ n. Our main contribution to adapt their analysis to DéjàVu is to show that the sub-martingale condition for ‖Ct‖\|C_t\| still holds for DéjàVu. More generally, the same argument applies to any Majority Boosting Protocol, i.e. any protocol such that for all opinions i<ji<j, (Ci′)(Cj′)≥CiCj. E(C_i ) E(C_j )≥ C_iC_j. Lemma 35. Suppose the protocol is Majority Boosting, namely that for all i<ji<j, (Ci′)(Cj′)≥CiCj, E (C _i ) E (C _j )≥ C_iC_j, Then (‖C′‖2∣C)≥‖C‖2. E (\|C \|^2 C )≥ C^2. 8.1 The configuration norm is a submartingale for Majority Boosting Protocols In this section we prove Lemma 35. To do so we first prove in Lemma 36 that (Ct,(Ct+1∣Ct))≥(Ct,Ct)(C_t, E(C_t+1 C_t))≥(C_t,C_t), where (⋅,⋅)(·,·) is the scalar product. Using the Cauchy-Schwarz inequality, we obtain that ‖(Ct+1∣Ct)‖2≥‖Ct‖2\| E (C_t+1 C_t )\|^2≥\|C_t\|^2. By the definition of variance, we finally obtain the sub-martingale condition in Lemma 35, i.e. (‖Ct+1‖2)≥‖Ct‖2 E (\|C_t+1\|^2 )≥\|C_t\|^2. We need some technical lemmas. Lemma 36. It holds ∑j∈[k]Cj2≤∑j∈[k]Cj⋅(Cj′). _j∈[k]C_j^2≤ _j∈[k]C_j· E (C _j ). Before proving Lemma 36, we need the following technical claims. Claim 37. For all opinions 1≤i<j≤k1≤ i<j≤ k, we have that (Ci′)−Ci≤0 E (C _i )-C_i≤ 0 implies that (Cj′)−Cj≤0 E (C _j )-C_j≤ 0. Proof. W.l.o.g. we can assume Ci,Cj>0C_i,C_j>0. By the Majority Boosting assumption, we have that (Ci′)(Cj′)≥CiCj. E (C _i ) E (C _j )≥ C_iC_j. This implies that (Cj′)Cj≤(Ci′)Ci≤1, E (C _j )C_j≤ E (C _i )C_i≤ 1, where the last inequality follows if we assume (Ci′)−Ci≤0 E (C _i )-C_i≤ 0. This concludes the proof of 37. ∎ Claim 38. For all opinions 1≤i≤k1≤ i≤ k, it holds ∑j=1i((Cj′)−Cj)≥0. _j=1^i ( E (C _j )-C_j )≥ 0. Proof. Let i∗=mini∈[k]:(Ci′)−Ci≤0i^*= \i∈[k]: E (C _i )-C_i≤ 0 \. The claim is trivially true for all i<i∗i<i^* or if the set is empty. By 37, for all i∗≤i≤ki^*≤ i≤ k, (Ci′)−Ci≤0 E (C _i )-C_i≤ 0. This implies that for i∗≤i≤ki^*≤ i≤ k, ∑j=1i((Cj′)−Cj) _j=1^i ( E (C _j )-C_j ) is a non-increasing function in i. Since for i=ki=k we have ∑j=1i((Cj′)−Cj)=n−n=0 _j=1^i ( E (C _j )-C_j )=n-n=0, we conclude the proof of 38. ∎ Proof of Lemma 36. Let dj≔(Cj′)−Cj,Si≔∑j=1idj(i∈[k]).d_j E (C _j )-C_j, S_i _j=1^id_j (i∈[k]). By 38, we have Si≥0S_i≥ 0 for every i∈[k]i∈[k], and since ∑j=1kCj′=n=∑j=1kCj _j=1^kC _j=n= _j=1^kC_j, we also have Sk=0S_k=0. Summation by parts yields ∑j=1kCjdj _j=1^kC_jd_j =∑i=1k−1(Ci−Ci+1)Si+CkSk = _i=1^k-1(C_i-C_i+1)S_i+C_kS_k =∑i=1k−1(Ci−Ci+1)Si = _i=1^k-1(C_i-C_i+1)S_i ≥0, ≥ 0, because C1≥⋯≥CkC_1≥·s≥ C_k and Si≥0S_i≥ 0 for all i≤k−1i≤ k-1. This concludes the proof of Lemma 36. ∎ The Cauchy-Schwarz inequality and Lemma 36 imply this corollary. Note that this is not yet the sub-martingale condition, since the expectation is inside the norm operator. Corollary 39. It holds ‖(C′)‖≥‖C‖\| E (C )\|≥\|C\|. Proof. By Lemma 36 and the Cauchy-Schwarz inequality, we have ‖C‖2=(C,C)≤(C,(C′))≤‖C‖‖(C′)‖.\|C\|^2=(C,C)≤(C, E (C ))≤\|C\|\| E (C )\|. By dividing both terms by ‖C‖\|C\|, we conclude the proof of Corollary 39. ∎ Now we have all the ingredients to show that ‖Ct‖\|C_t\| is a sub-martingale. Proof of Lemma 35. We have that (‖C′‖2∣C)−‖C‖2 E (\|C \|^2 C )-\|C\|^2 =∑j∈[k](Cj′2∣C)−‖C‖2 = _j∈[k] E (C_j ^2 C )-\|C\|^2 =∑j∈[k]((Cj′∣C)2+Var(Cj′∣C))−∥C∥2 = _j∈[k] ( E (C_j C )^2+Var (C_j C ) )-\|C\|^2 ≥∑j∈[k]((Cj′∣C)2)−∥C∥2 ≥ _j∈[k] ( E (C_j C )^2 )-\|C\|^2 =‖(C′∣C)‖2−‖C‖2 =\| E (C C )\|^2-\|C\|^2 ≥0. ≥ 0. (by Corollary 39) (by @crefcreftype~refnumcorollary:norm_2_expected_value_inequality ) By rearranging the last inequality, we conclude the proof of Lemma 35. ∎ 8.2 DéjàVu does not decrease the configuration norm In this section we follow the steps in [S25] to show that, for the DéjàVu protocol, ‖Ct‖=Ω(‖C0‖)\|C_t\|= (\|C_0\| ). Some of the lemmas are identical to those in [S25]; for this reason we omitted their proofs. The remaining lemmas needed to be adapted to the DéjàVu protocol. The following definition and lemmas are the primary mathematical tools used for the drift analysis of ‖Ct‖\|C_t\|. Definition 40 (Bernstein condition and one-sided Bernstein condition). Let D,s≥0D,s≥ 0 be parameters. A random variable X satisfies (D,s)(D,s)-Bernstein condition if, for any λ∈ℝλ such that |λ|D<3 λD<3, [expλX]≤exp(λ2s/21−(|λ|D)/3) E [ ^λ X]≤ ( λ^2s/21-( λD)/3). We say that X satisfies one-sided (D,s)(D,s)-Bernstein condition if, for any λ≥0λ≥ 0 such that λD<3λ D<3, [expλX]≤exp(λ2s/21−(λD)/3) E [ ^λ X]≤ ( λ^2s/21-(λ D)/3). Lemma 41 (Lemma 3.4 (Closure properties of one-sided Bernstein) from [S25] ). Let X,YX,Y be random variables. We have the following: (i) If [X]=0 E[X]=0 and |X|≤D X≤ D for some D, then X satisfies (D,Var[X]) (D,Var [X])-Bernstein condition. (i) If X satisfies (D,s) (D,s)-Bernstein condition, then X satisfies (D′,s′) (D ,s )-Bernstein condition for any D′≥D ≥ D and s′≥s ≥ s. Similarly, if X satisfies one-sided (D,s) (D,s)-Bernstein condition, then X satisfies one-sided (D′,s′) (D ,s )-Bernstein condition for any D′≥D ≥ D and s′≥s ≥ s. (i) If X satisfies (D,s) (D,s)-Bernstein condition, then aXaX satisfies (|a|D,a2s)( aD,a^2s)-Bernstein condition for any a∈ℝa∈ R. If X satisfies one-sided (D,s) (D,s)-Bernstein condition, then aXaX satisfies one-sided (aD,a2s)(aD,a^2s)-Bernstein condition for any a≥0a≥ 0. (iv) If X satisfies one-sided (D,s) (D,s)-Bernstein condition and Y⪯XY X, then Y satisfies one-sided (D,s) (D,s)-Bernstein condition. In particular, if X satisfies one-sided (D,s) (D,s)-Bernstein condition and Y≤XY≤ X, then Y satisfies one-sided (D,s) (D,s)-Bernstein condition. (v) If a sequence of n random variables X1,…,XnX_1,…,X_n are independent and XiX_i satisfies (D,si) (D,s_i)-Bernstein condition for i∈[n]i∈[n], then ∑i∈[n]Xi _i∈[n]X_i satisfies (D,∑i∈[n]si) (D, _i∈[n]s_i)-Bernstein condition. (vi) If a sequence of n random variables X1,…,XnX_1,…,X_n are negatively associated and XiX_i satisfies one-sided (D,si) (D,s_i)-Bernstein condition for i∈[n]i∈[n], then ∑i∈[n]Xi _i∈[n]X_i satisfies one-sided (D,∑i∈[n]si) (D, _i∈[n]s_i)-Bernstein condition. Lemma 42 (Lemma 3.5 (Additive drift under one-sided Bernstein) from [S25]). Let (Xt)t≥0(X_t)_t≥ 0 be an adapted process and τ a stopping time. Suppose there exist R∈ℝR , D,s>0D,s>0 such that for every t: (C1) τ>t−1(t−1[Xt]−Xt−1−R)≤01_\τ>t-1\ (E_t-1[X_t]-X_t-1-R )≤ 0. (C2) τ>t−1(Xt−Xt−1−R)1_\τ>t-1\ (X_t-X_t-1-R ) satisfies the (D,s)(D,s)-one-sided Bernstein condition . For a parameter h>0h>0, define stopping times τX+≔inft≥0:Xt≥X0+h τ^+_X \t≥ 0:X_t≥ X_0+h \ τX−≔inft≥0:Xt≤X0−h τ^-_X \t≥ 0:X_t≤ X_0-h \ Then, we have the following: 1. Suppose R≥0R≥ 0. Then, for any h,T>0h,T>0 such that z≔h−R⋅T>0z h-R· T>0, we have Pr[τX+≤minT,τ]≤exp(−z2/2sT+(zD)/3). \! [τ^+_X≤ \T,τ\ ]≤ \! (- z^2/2sT+(zD)/3 ). 2. Suppose R<0R<0. Then, for any h,T>0h,T>0 such that z≔(−R)⋅T−h>0z (-R)· T-h>0, we have Pr[minτX−,τ>T]≤exp(−z2/2sT+(zD)/3).. \! [ \τ^-_X,τ\>T ]≤ \! (- z^2/2sT+(zD)/3 ).. In the following lemma, we show that some fundamental quantities satisfy the Bernstein condition. We will use our notation p(t)=C(t)/np^(t)=C^(t)/n. Lemma 43 (Adapted from Lemma 4.2 (One-sided Bernstein for the basic quantities) from [S25]). We have the following for any t≥1t≥ 1: (i) For any opinion i∈[k]i∈[k], the random variable pi(t)−t−1(p(t)(i))p_i^(t)- E_t-1 (p^(t)(i) ) conditioned on round t−1t-1 satisfies the (1n,Vart−1[pi(t)]) ( 1n,Var_t-1 [p_i^(t)]) Bernstein condition. (i) If h‖p(t−1)‖≤1h\|p^(t-1)\|≤ 1, ‖p(t−1)‖2−‖p(t)‖2\|p^(t-1)\|^2-\|p^(t)\|^2 conditioned on round t−1t-1 satisfies one-sided (2‖p(t−1)‖n,ch2‖p(t−1)‖4n) ( 2\|p^(t-1)\|n, ch^2\|p^(t-1)\|^4n)-Bernstein condition. (i) If h‖p(t−1)‖>1h\|p^(t-1)\|>1, ‖p(t−1)‖2−‖p(t)‖2\|p^(t-1)\|^2-\|p^(t)\|^2 conditioned on round t−1t-1 satisfies one-sided (2‖p(t−1)‖n,c‖p(t−1)‖2n) ( 2\|p^(t-1)\|n, c\|p^(t-1)\|^2n)-Bernstein condition. Proof of Item 1. By definition, npi(t)=∑v∈Vopiniont(v)=i.np_i^(t)= _v∈ V1_opinion_t(v)=i. Hence pi(t)−t−1[pi(t)]=∑v∈VXt(v),p_i^(t)- E_t-1 [p_i^(t)]= _v∈ VX_t(v), where Xt(v)≔opiniont(v)=i−t−1[opiniont(v)=i]n.X_t(v) 1_opinion_t(v)=i- E_t-1 [1_opinion_t(v)=i]n. Since |Xt(v)|≤1/n X_t(v)≤ 1/n for all v∈Vv∈ V, Xt(v)X_t(v) conditioned on round t−1t-1 satisfies (1n,Vart−1[Xt(v)]) ( 1n,Var_t-1[X_t(v)])-Bernstein condition (Item 1 of Lemma 41). Furthermore, since (Xt(v))v∈V(X_t(v))_v∈ V conditioned on round t−1t-1 are n mean-zero independent random variables, pi(t)−t−1[pi(t)]=∑v∈VXt(v)p_i^(t)- E_t-1 [p_i^(t)]= _v∈ VX_t(v) satisfies (1n,∑v∈VVart−1[Xv]) ( 1n, _v∈ VVar_t-1[X_v])-Bernstein condition from Item 5 of Lemma 41. Since ∑v∈VVart−1[Xt(v)]=Vart−1[∑v∈VXt(v)]=Vart−1[pi(t)−t−1[pi(t)]]=Vart−1[pi(t)], _v∈ VVar_t-1[X_t(v)]=Var_t-1 [ _v∈ VX_t(v)]=Var_t-1 [p_i^(t)- E_t-1 [p_i^(t)]]=Var_t-1 [p_i^(t)], we obtain the claim. ∎ Proof of Items 2 and 3. We have ‖p(t−1)‖2−‖pt‖2 \|p^(t-1)\|^2-\|p_t\|^2 =∑i∈[k]pi(t−1)2−pi(t)2 = _i∈[k] \p^(t-1)_i^2-p^(t)_i^2 \ ≤∑i∈[k]2pi(t−1)pi(t−1)−pi(t) ≤ _i∈[k]2p^(t-1)_i \p^(t-1)_i-p^(t)_i \ (for all x,y∈ℝ, x2−y2≤2x(x−y)) (for all $x,y∈ R$, $x^2-y^2≤ 2x(x-y)$ ) ≤∑i∈[k]2pi(t−1)t−1(pi(t))−pi(t) ≤ _i∈[k]2p^(t-1)_i \ E_t-1 (p^(t)_i )-p^(t)_i \ (by Lemma 36) (by @crefcreftype~refnumlemma:norm_2_expected_value_inequality ) =∑i∈[k]Yt(i), = _i∈[k]Y_t(i), where Yt(i)≔2pi(t−1)t−1(pi(t))−pi(t)=∑v∈V2pi(t−1)n(t−1[ot(v)=i]−ot(v)=i).Y_t(i) 2p^(t-1)_i \ E_t-1 (p^(t)_i )-p^(t)_i \= _v∈ V 2p^(t-1)_in ( E_t-1[1_o_t(v)=i]-1_o_t(v)=i). Yt(i)Y_t(i) conditioned on round t−1t-1 satisfies (2pi(t−1)n,4pi(t−1)2Vart−1[p(t)(i)]) ( 2p^(t-1)_in,4p^(t-1)_i^2Var_t-1[p^(t)(i)])-Bernstein condition from Item 3 of Lemma 41 and Item 1 of Lemma 43. Furthermore, from pi(t−1)≤‖p(t−1)‖p^(t-1)_i≤\|p^(t-1)\|, Item 2 of Lemma 41 implies that Yt(i)Y_t(i) conditioned on round t−1t-1 satisfies (2‖p(t−1)‖n,4pi(t−1)2Vart−1[p(t)(i)]) ( 2\|p^(t-1)\|n,4p^(t-1)_i^2Var_t-1[p^(t)(i)])-Bernstein condition. From Lemma 48, the random variables (opiniont(v)=i)i∈[k](1_opinion_t(v)=i)_i∈[k] are negatively associated for each v∈Vv∈ V. From Proposition 49, ((opiniont(v)=i)i∈[k])v∈V ((1_opinion_t(v)=i)_i∈[k])_v∈ V, a sequence of knkn random variables, are also negatively associated. Since Yt(i)=hi((opiniont(v)=i)v∈V)Y_t(i)=h_i ((1_opinion_t(v)=i)_v∈ V), i.e., non-increasing functions of disjoint subsets of negatively associated random variables ((opiniont(v)=i)i∈[k])v∈V ((1_opinion_t(v)=i)_i∈[k])_v∈ V, (Yt(i))i∈[k](Y_t(i))_i∈[k] are negatively associated (Proposition 49). Thus, from Item 6 of Lemma 41, ∑i∈[k]Yt(i) _i∈[k]Y_t(i) conditioned on round t−1t-1 satisfies one-sided (2‖p(t−1)‖n,4∑i∈[k]pi(t−1)2Vart−1[pi(t)]) ( 2\|p^(t-1)\|n,4 _i∈[k]p^(t-1)_i^2Var_t-1[p^(t)_i])-Bernstein condition. From Item 4 of Lemma 41, ‖p(t−1)‖2−‖pt‖2≤∑i∈[k]Yt(i)\|p^(t-1)\|^2-\|p_t\|^2≤ _i∈[k]Y_t(i) conditioned round t−1t-1 also satisfies one-sided (2‖p(t−1)‖n,4∑i∈[k]pi(t−1)2Vart−1[pi(t)]) ( 2\|p^(t-1)\|n,4 _i∈[k]p^(t-1)_i^2Var_t-1[p^(t)_i])-Bernstein condition. Since by Lemma 18 we have that Vart−1(pi(t))≤pi(t−1)nminch2‖p(t−1)‖22,1(pi(t−1)‖p(t−1)‖2+1)Var_t-1 (p^(t)_i )≤ p^(t-1)_in \c\,h^2\|p^(t-1)\|_2^2,1 \ ( p^(t-1)_i\|p^(t-1)\|^2+1 ), applying Item 2 of Lemma 41 and that ‖p(t−1)‖33≤‖p(t−1)‖3\|p^(t-1)\|_3^3≤\|p^(t-1)\|^3, ‖p(t−1)‖44≤‖p(t−1)‖4\|p^(t-1)\|_4^4≤\|p^(t-1)\|^4, we obtain the claim. ∎ The following lemmas bound the stopping time until the Euclidean norm of the configuration decreases by a constant multiplicative factor. Lemma 44 (Adapted from Lemma 4.5 from [S25]). Consider stopping times defined in Definition 33. For any T>0T>0, we have Pr[τ↓≤minT,τ↑]≤exp(−Ω(nh2T+‖p(0)‖−1))if h‖p(0)‖≤1exp(−Ω(n‖p(0)‖2T))if h‖p(0)‖>1 [τ ≤ \T,τ \]≤ cases (- ( nh^2T+\|p^(0)\|^-1)) &if h\|p^(0)\|≤ 1\\ (- ( n\|p^(0)\|^2T)) &if h\|p^(0)\|>1 cases Proof of Lemma 44. Let τ=τ↑τ=τ , Xt=−‖p(t∧τ)‖2X_t=-\|p^(t τ)\|^2, and R=0R=0. From Lemma 35, τ>t−1(t−1[Xt]−Xt−1−R) 1_τ>t-1 ( E_t-1 [X_t]-X_t-1-R) =τ>t−1(‖p(t−1)‖2−t−1[‖p(t)‖2])≤0. =1_τ>t-1 (\|p^(t-1)\|^2- E_t-1 [\|p^(t)\|^2])≤ 0. Furthermore, from Item 2 of Lemma 43 and Item 2 of Lemma 41, the random variable τ>t−1(Xt−Xt−1−R) 1_τ>t-1 (X_t-X_t-1-R) =τ>t−1(‖p(t−1)‖2−‖p(t)‖2) =1_τ>t-1 (\|p^(t-1)\|^2-\|p^(t)\|^2) satisfies one-sided (O(‖p(0)‖n),O(minh2‖p(0)‖2,1‖p(0)‖2n)) (O ( \|p^(0)\|n),O ( \h^2\|p^(0)\|^2,1 \\|p^(0)\|^2n ))-Bernstein condition. Here, we used ‖p(t−1)‖≤(1+c↑)‖p(0)‖\|p^(t-1)\|≤(1+c )\|p^(0)\| for t−1<τt-1<τ. Set ε≔‖p(0)‖2−((1−c↓)‖p(0)‖)2=(2c↓−(c↓)2)‖p(0)‖2. \|p^(0)\|^2- ((1-c )\|p^(0)\| )^2= (2c -(c )^2 )\|p^(0)\|^2. Applying Lemma 42 with D=O(‖p(0)‖n)D=O ( \|p^(0)\|n) and threshold ε , Pr[τX↑≤minT,τ]≤exp(−Ω(‖p(0)‖4h2‖p(0)‖4T/n+‖p(0)‖3/n))if h‖p(0)‖≤1exp(−Ω(‖p(0)‖4‖p(0)‖2T/n+‖p(0)‖3/n))if h‖p(0)‖>1 [ _X ≤ \T,τ\]≤ cases (- ( \|p^(0)\|^4h^2\|p^(0)\|^4T/n+\|p^(0)\|^3/n)) &if h\|p^(0)\|≤ 1\\ (- ( \|p^(0)\|^4\|p^(0)\|^2T/n+\|p^(0)\|^3/n)) &if h\|p^(0)\|>1 cases holds. Moreover, if τ↓≤minT,τ ≤ \T,τ\, then for some t≤minT,τt≤ \T,τ\ we have ‖p(t)‖≤(1−c↓)‖p(0)‖,\|p^(t)\|≤(1-c )\|p^(0)\|, and therefore Xt−X0=‖p(0)‖2−‖p(t)‖2≥‖p(0)‖2−((1−c↓)‖p(0)‖)2=ε.X_t-X_0=\|p^(0)\|^2-\|p^(t)\|^2≥\|p^(0)\|^2- ((1-c )\|p^(0)\| )^2= . Hence τ↓≤minT,τ ≤ \T,τ\ implies τX↑≤minT,τ _X ≤ \T,τ\, and so Pr[τ↓≤minT,τ]≤Pr[τX↑≤minT,τ], [τ ≤ \T,τ\]≤ [ _X ≤ \T,τ\], which yields the claim. ∎ Proof of Lemma 34. For each 0≤s≤T0≤ s≤ T, let σs↓=inft≥s:‖p(t)‖≤(1−c↓)‖ps‖σ _s= \t≥ s \|p^(t)\|≤(1-c )\|p_s\|\, σs↑=inft≥s:‖p(t)‖≥2‖ps‖σ _s= \t≥ s \|p^(t)\|≥ 2\|p_s\|\, and let ℰ(s)E^(s) be the event that ‖ps‖≥‖p(0)‖\|p_s\|≥\|p^(0)\| and σs↓≤minT,σs↑σ _s≤ \T,σ _s\. Note that τ↓=σ0↓τ =σ _0 and τ↑=σ0↑τ =σ _0 (for c↑=1c =1). The key observation is that the partial process (p(t))t≥s(p^(t))_t≥ s is again a DéjàVu process and σt↑,σt↓ _t , _t can be seen as the stopping times of Definition 33 for the partial process. Moreover, the event ℰ(s)E^(s) depends only on the partial process (p(t))t≥s(p^(t))_t≥ s. Therefore, from Lemma 44, we have Pr(p(t))t≥s[ℰ(s)] _(p^(t))_t≥ s [E^(s)] ≤Pr(p(t))t≥s[σs↓≤minT,σs↑|∥p(s)∥≥∥p(0)∥] ≤ _(p^(t))_t≥ s [ _s ≤ \T,σ _s\ |\|p^(s)\|≥\|p^(0)\|] ≤exp(−Ω(nh2T+‖p(0)‖−1))if h‖p(0)‖≤1exp(−Ω(n‖p(0)‖2T))if h‖p(0)‖>1 ≤ cases (- ( nh^2T+\|p^(0)\|^-1)) &if h\|p^(0)\|≤ 1\\ (- ( n\|p^(0)\|^2T)) &if h\|p^(0)\|>1 cases If τ↓≤Tτ ≤ T occurs, then ℰ(s)E^(s) occurs for some 0≤s≤T0≤ s≤ T. For example, if s≤τ↓s≤τ is the round such that ‖ps‖=max0≤t≤τ↓‖p(t)‖\|p_s\|= _0≤ t≤τ \|p^(t)\|, then ℰ(s)E^(s) holds. Therefore, we have Pr[τ↓≤T] [τ ≤ T] ≤Pr[⋁0≤s≤Tℰ(s)] ≤ [ _0≤ s≤ TE^(s)] ≤∑0≤s≤TPr[ℰ(s)] ≤ _0≤ s≤ T [E^(s)] ≤Texp(−Ω(nh2T+‖p(0)‖−1))if h‖p(0)‖≤1Texp(−Ω(n‖p(0)‖2T))if h‖p(0)‖>1 ≤ casesT (- ( nh^2T+\|p^(0)\|^-1)) &if h\|p^(0)\|≤ 1\\ T (- ( n\|p^(0)\|^2T)) &if h\|p^(0)\|>1 cases ∎ In the following, we remark why Lemma 34 implies that ‖p(t)‖≥c↓‖p(0)‖\|p^(t)\|≥ c \|p^(0)\| w.h.p. In the regime h≤1p1h≤ 1 p_1, by Theorem 1, Td=O(lognh2p1)T_d=O ( nh^2p_1 ). Hence, whenever p1=ω(log2n/n)p_1=ω ( ^2n/n ), Lemma 34 implies that w.h.p. ‖p(t)‖≥c↓‖p(0)‖\|p^(t)\|≥ c \|p^(0)\| for all 0≤t≤Td0≤ t≤ T_d. In the regime 1p1≤h≤1‖p‖logn 1 p_1≤ h≤ 1\|p\| n (which exists only for initial unbalanced configurations), by Theorem 1, it holds Td=O(logn)T_d=O ( n ). Therefore, Lemma 34 implies that w.h.p. ‖p(t)‖≥c↓‖p(0)‖\|p^(t)\|≥ c \|p^(0)\|. In the regime h>1‖p‖logn,1p1h> 1\|p\| n, 1 p_1, by Theorem 1, it holds Td=O(logn)T_d=O ( n ), so we distinguish two cases. If ‖p(0)‖2=ω(log2n)\|p^(0)\|^2=ω ( ^2nn ), for some sufficiently large constant C>0C>0, Lemma 34 implies that w.h.p. ‖p(t)‖2=Ω(‖p(0)‖2)\|p^(t)\|^2= (\|p^(0)\|^2 ) for all 0≤t≤Td0≤ t≤ T_d. Instead, if ‖p(0)‖2≤Clog2n\|p^(0)\|^2≤ C ^2nn, we have that ‖p(t)‖2=Ω(‖p(0)‖2log2n)\|p^(t)\|^2= ( \|p^(0)\|^2 ^2n ) for all t≥0t≥ 0, as it always holds ‖p(t)‖≥1k≥1n\|p^(t)\|≥ 1k≥ 1n. 8.3 Comparing the number of samples required by DéjàVu and h-Majority We have all the ingredients to conclude the proof of Theorems 32 and 3, which we restate for convenience. Theorem. Let C=(C1,…,Ck)C=(C_1,…,C_k) be a system configuration such that C1≥⋯≥CkC_1≥·s≥ C_k, C1=ω(log2n)C_1=ω ( ^2n ), and that, for a large enough constant λ>0λ>0, C1−C2≥λmaxnh2,C1logn.C_1-C_2≥λ \ nh^2,C_1 \ n. Let SdS_d and SmS_m be the numbers of samples until consensus of, respectively, DéjàVu and h-Majority. Fix any arbitrarily small constant ε>0 >0. For h=Ω(minn3/4+ε/C1,n/C1)h= ( \n^3/4+ /C_1, n/C_1\), w.h.p. it holds Sd⋅O(max1,h‖C‖2n)log3n≤Sm if ‖C‖2=O(nlogn) and h‖C‖2≥nlogn,Sd⋅O(max1,h‖C‖2n)logn≤Sm otherwise. cases&S_d· O ( \1,h C_2n )\ ^3n≤ S_m if C_2=O( n n) and h C_2≥ n n,\\ &S_d· O ( \1,h C_2n )\ n≤ S_m otherwise. cases Proof of Theorem 32. Let TdT_d be the convergence time of DéjàVu. By Theorem 1, there exists an absolute constant cT>0c_T>0 such that Pr(Td≤cTmaxnh2C1,1logn)≥1−n−Θ(1). \! (T_d≤ c_T \ nh^2C_1,1 \ n )≥ 1-n^- (1). Define T∗≔cTmaxnh2C1,1logn.T_* c_T \ nh^2C_1,1 \ n. On the event Td≤T∗∩‖p(t)‖≥c↓‖p(0)‖ for all 0≤t≤T∗, \T_d≤ T_* \∩ \\|p^(t)\|≥ c \|p^(0)\| for all 0≤ t≤ T_* \, let m≔minh,⌈1/‖p(0)‖⌉.m \h, 1/\|p^(0)\| \. By Lemma 9, for every t≤T∗t≤ T_*, Pr(H≤m∣C(t))≥2−11minm2∥p(t)∥2,1≥2−11min(c↓)2,1=:κ>0. (H≤ m C^(t))≥ 2^-11 \m^2\|p^(t)\|^2,1 \≥ 2^-11 \(c )^2,1 \=:κ>0. Therefore, the number of samples performed by a fixed agent in round t is stochastically dominated by mGtmG_t, where Gt∼Geom(κ)G_t (κ): indeed, every fresh block of m samples contains an internal repeat with conditional probability at least κ, and such an internal repeat already stops the round. Consequently, on the same event, Sd⪯m∑t=1T∗Gt.S_d m _t=1^T_*G_t. Since κ is an absolute constant, Theorem 53 yields ∑t=1T∗Gt=O(T∗) _t=1^T_*G_t=O(T_*) w.h.p. Combining this estimate with the high-probability event Td≤T∗T_d≤ T_* and with the norm lower bound from Lemma 34 for T=T∗T=T_*, a union bound implies that, w.h.p., Sd=O(T∗⋅minh,1‖p(0)‖)=O(maxnh2C1,1logn⋅minh,n‖C‖)S_d=O\! (T_*· \h, 1\|p^(0)\| \ )=O\! ( \ nh^2C_1,1 \ n· \h, n\|C\| \ ) w.h.p., which is the claim. ∎ We restate Theorem 3 for convenience. Theorem. Let C=(C1,…,Ck)C=(C_1,…,C_k) be a system configuration such that C1≥⋯≥CkC_1≥·s≥ C_k, C1=ω(log2n)C_1=ω ( ^2n ), and bias C1−C2=Ω(maxnh2,C1logn).C_1-C_2= ( \ nh^2,C_1 \ n ). Let SdS_d and SmS_m be the numbers of samples until consensus of, respectively, DéjàVu and h-Majority. Fix any arbitrarily small constant ε>0 >0. For h=Ω(minn3/4+ε/C1,n/C1)h= ( \n^3/4+ /C_1, n/C_1\), w.h.p. it holds Sd⋅O(max1,h‖C‖2n)logn≤Sm.S_d· O ( \1,h C_2n )\ n≤ S_m~. Proof of Theorem 3. Let TmT_m be the convergence time of the h-Majority. By Theorem 2 and by the trivial lower bound Tm≥1T_m≥ 1, we obtain Sm=Tm⋅h=ΩmaxnhC1,hif h=Ω(n3/4+ε/C1)hotherwise S_m=T_m· h= cases \ nh\,C_1,h \&if h= (n^3/4+ /C_1 )\\ h&otherwise cases Let’s first assume that C1≤nC_1≤ n. Consequently, we have that minn3/4+εC1,nC1=nC1. \ n^3/4+ C_1, nC_1 \= nC_1. Then we assume that h≥n/C1h≥ n/C_1. To find the ratio SdSm S_dS_m, we analyze the two main regimes of h. Low sampling regime (h≤n‖C‖2) (h≤ n C_2 ). The ratio is: SdSm=O(logn⋅h)=O(logn). S_dS_m=O ( n· hh )=O( n). Large sampling regime (h>n‖C‖2) (h> n C_2 ). The ratio is: SdSm=O(lognn‖C‖2h). S_dS_m=O ( n n C_2h ). If instead, C1>nC_1> n, assuming h≥n3/4+ε/C1h≥ n^3/4+ /C_1, we obtain the same results similarly. ∎ 9 Conclusion and Open Questions We conclude by discussing some limitations of our work and several directions for future research. A complete analysis of the convergence time of h-Majority for arbitrary values of h and k remains a major open problem, since the regime h≤kh≤ k is still missing. Our analysis of DéjàVu provides several tools, in particular the Poisson race framework and the monotonicity of the probability ratio via Newton’s inequalities, that may be useful for attacking this question. As discussed in Section 1.1, our analysis requires an initial additive bias of Ω(maxn/h2,C1logn). \! ( \n/h^2,C_1 \ n ). For constant h, this is comparable to the ω(nlogn)ω( n n) bias required by the 33-Majority dynamics. We conjecture that this requirement can be significantly reduced for DéjàVu. More precisely, we believe that the minimum bias needed for plurality consensus is always ω(C1logn)ω( C_1 n), matching the optimal bias of the 22-Choices dynamics (see Section 2). The intuition is that DéjàVu can be viewed as a generalization of 22-Choices in which more samples are allowed, and we see no fundamental reason why its bias requirement should deteriorate as h grows. By contrast, we expect that h-Majority genuinely requires a larger bias in some regimes. Finally, we stress that DéjàVu(h) is specifically designed for plurality consensus: it amplifies and preserves the initial majority opinion. Without sufficient initial bias, the protocol can be slow to converge because of its conservative behavior: when no opinion is repeated within the first h samples of a round, the agent keeps its current opinion. This is analogous to the comparison between 22-Choices and 33-Majority in [BCE+17], where 33-Majority is shown to converge much faster than 22-Choices when the number of initial opinions approaches n. One can also consider a variant of DéjàVu(h) in which, when no opinion is repeated within the first h samples, the agent updates to one of the sampled opinions chosen uniformly at random. This variant may be more effective for achieving general consensus when the number of initial opinions is extremely large and there is no initial bias, and it appears to be an interesting direction for future work. Acknowledgments This work has been supported the French government National Research Agency (ANR) through the UCA JEDI (ANR-15-IDEX-01) and EUR DS4H (ANR-17-EURE-004), through the 3IA Cote d’Azur Investments in the project with the reference number ANR-23-IACL-0001, and by the AID INRIA-DGA project n°2023000872 “BioSwarm”. Support was received also by the MUR (Italy) Department of Excellence 2023 - 2027 for GSSI, and the Agence Nationale de la Recherche (ANR) under project ByBloS (ANR-20-CE25-0002). Francesco d’Amore is supported by the project Decreto MUR n. 47/2025, CUP: D13C25000750001. References [AAB+23] T. Amir, J. Aspnes, P. Berenbrink, F. Biermeier, C. Hahn, D. Kaaser, and J. Lazarsfeld (2023) Fast convergence of k-opinion undecided state dynamics in the population protocol model. In 2023 ACM Symposium on Principles of Distributed Computing, PODC, p. 13–23. External Links: Link, Document Cited by: §2. [AAE08] D. Angluin, J. Aspnes, and D. Eisenstat (2008) A simple population protocol for fast robust approximate majority. Distributed Comput. 21 (2), p. 87–102. External Links: Link, Document Cited by: §2. [AGG89] R. Arratia, L. Goldstein, and L. Gordon (1989) Two Moments Suffice for Poisson Approximations: The Chen-Stein Method. The Annals of Probability 17 (1), p. 9 – 25. External Links: Document, Link Cited by: §1.2, §5.1, §5.1. [B+22] G. Bankhamer, P. Berenbrink, F. Biermeier, R. Elsässer, H. Hosseinpour, D. Kaaser, and P. Kling (2022) Fast consensus via the unconstrained undecided state dynamics. In 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, p. 3417–3429. External Links: Link, Document Cited by: §2. [BCN+17] L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, and L. Trevisan (2017) Simple dynamics for plurality consensus. Distributed Computing 30 (4), p. 293–306. External Links: Document Cited by: §1.1, §1.2, §1, §2.1, §2, §2, §2, §7, Theorem 2. [BCN+15] L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and R. Silvestri (2015) Plurality consensus in the gossip model. In Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, p. 371–390. External Links: Link, Document Cited by: §2. [BCN+16] L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan (2016) Stabilizing consensus with many opinions. In Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, p. 620–635. External Links: Link, Document Cited by: §2. [BCN20] L. Becchetti, A. Clementi, and E. Natale (2020) Consensus Dynamics: An Overview. ACM SIGACT News 51 (1), p. 58–104. External Links: ISSN 0163-5700, Document Cited by: §1.2, §1, §2. [BBH24] P. Berenbrink, F. Biermeier, and C. Hahn (2024) Undecided state dynamics with stubborn agents. CoRR abs/2406.07335. External Links: Link, Document, 2406.07335 Cited by: §2. [BCE+17] P. Berenbrink, A. Clementi, R. Elsässer, P. Kling, F. Mallmann-Trenn, and E. Natale (2017) Ignore or comply?: on breaking symmetry in consensus. In ACM Symposium on Principles of Distributed Computing, PODC, p. 335–344. External Links: Link, Document Cited by: §2, §2, §2, §9. [BCG+22] P. Berenbrink, A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, D. Kaaser, and M. Rau (2022) On the hierarchy of distributed majority protocols. In 26th International Conference on Principles of Distributed Systems, OPODIS, p. 23:1–23:19. External Links: Link, Document Cited by: §2, §2, §2. [BLB03] S. Boucheron, G. Lugosi, and O. Bousquet (2003) Concentration inequalities. In Summer school on machine learning, p. 208–240. Cited by: Lemma 52. [CGG+18] A. Clementi, M. Ghaffari, L. Gualà, E. Natale, F. Pasquale, and G. Scornavacca (2018) A tight analysis of the parallel undecided-state dynamics with two colors. In 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS, p. 28:1–28:15. External Links: Link, Document Cited by: §2. [CMR+25] C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga (2025) Asynchronous 3-majority dynamics with many opinions. In 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, p. 4095–4131. External Links: Link, Document Cited by: §1, §2, §2. [CMQ+23] E. Cruciani, H. A. Mimun, M. Quattropani, and S. Rizzo (2023) Phase transition of the k-majority dynamics in biased communication models. Distributed Comput. 36 (2), p. 107–135. External Links: Link, Document Cited by: §2. [DCN20] F. D’Amore, A. Clementi, and E. Natale (2020) Phase transition of a non-linear opinion dynamics with noisy interactions. In Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO, p. 255–272. External Links: Link, Document Cited by: §2. [DCN22] F. D’Amore, A. Clementi, and E. Natale (2022) Phase transition of a nonlinear opinion dynamics with noisy interactions. Swarm Intell. 16 (4), p. 261–304. External Links: Link, Document Cited by: §2. [DDG+25] F. D’Amore, N. D’Archivio, G. Giakkoupis, and E. Natale (2025) On the h-majority dynamics with many opinions. In 39th International Symposium on Distributed Computing, DISC, p. 27:1–27:24. External Links: Link, Document Cited by: §1.1, §1, §2.1, §2, §2. [DZ22] F. D’Amore and I. Ziccardi (2022) Phase transition of the 3-majority dynamics with uniform communication noise. In Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO, p. 98–115. External Links: Link, Document Cited by: §2. [DZ25] F. D’Amore and I. Ziccardi (2025) Phase transition of the 3-majority opinion dynamics with noisy interactions. Theor. Comput. Sci. 1028, p. 115030. External Links: Link, Document Cited by: §2. [DHN22] S. Dasgupta, D. Hattori, and S. Navlakha (2022) A neural theory for counting memories. Nature Communications 13 (1), p. 5961. External Links: ISSN 2041-1723, Document Cited by: §1. [DGH+87] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry (1987) Epidemic algorithms for replicated database maintenance. In 6th ACM Symposium on Principles of Distributed Computing, PODC, External Links: Document Cited by: §1. [DP09] D. P. Dubhashi and A. Panconesi (2009) Concentration of measure for the analysis of randomized algorithms. Cambridge University Press. External Links: Link, ISBN 978-0-521-88427-3 Cited by: Lemma 50. [DR98] D. Dubhashi and D. Ranjan (1998) Balls and bins: a study in negative dependence. Random Struct. Algorithms 13 (2), p. 99–124 (en). External Links: Document, ISSN 1042-9832,1098-2418 Cited by: Lemma 47, Lemma 48, Proposition 49. [EES25] A. El-Hayek, R. Elsässer, and S. Schmid (2025) An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. In ACM Symposium on Principles of Distributed Computing, PODC, p. 532–540. External Links: Link, Document Cited by: §2. [FHK17] O. Feinerman, B. Haeupler, and A. Korman (2017) Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. Distributed Computing 30 (5), p. 339–355. External Links: ISSN 0178-2770, 1432-0452, Document Cited by: §1. [FN19] P. Fraigniaud and E. Natale (2019) Noisy rumor spreading and plurality consensus. Distributed Computing 32 (4), p. 257–276. External Links: Link, Document Cited by: §1. [FNR24] M. Függer, T. Nowak, and J. Rybicki (2024) Majority consensus thresholds in competitive lotka-volterra populations. In 43rd ACM Symposium on Principles of Distributed Computing, PODC, p. 76–86. External Links: Link, Document Cited by: §1. [GH12] S. D. Galbraith and M. Holmes (2012) A non-uniform birthday problem with applications to discrete logarithms. Discret. Appl. Math. 160, p. 1547–1560. External Links: Link Cited by: §1.2. [GL18] M. Ghaffari and J. Lengler (2018) Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In 2018 ACM Symposium on Principles of Distributed Computing, PODC, p. 305–313. External Links: Link Cited by: §2, §2. [JAN18] S. Janson (2018) Tail bounds for sums of geometric and exponential variables. Statistics and Probability Letters 135, p. 1–6. External Links: ISSN 0167-7152, Document, Link Cited by: Theorem 53. [LGP22] H. Lesfari, F. Giroire, and S. Pérennes (2022) Biased Majority Opinion Dynamics: Exploiting Graph k-domination. In Thirty-First International Joint Conference on Artificial Intelligence, Vienna, Austria, p. 377–383. External Links: Document, ISBN 978-1-956792-00-3 Cited by: §2. [MU05] M. Mitzenmacher and E. Upfal (2005) Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press. External Links: Link, Document, ISBN 978-0-521-83540-4 Cited by: §1.2, Lemma 51. [MT17] E. Mossel and O. Tamuz (2017) Opinion exchange dynamics. Probability Surveys 14, p. 155–204. External Links: ISSN 1549-5787, Document Cited by: §2. [PVV09] E. Perron, D. Vasudevan, and M. Vojnovic (2009) Using three states for binary consensus on complete graphs. In 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, INFOCOM, p. 2527–2535. External Links: Link, Document Cited by: §2. [RUA07] S. Ruan (2007) Poisson race models: theory and application in conjoint choice analysis. Ph.D. Thesis, The Ohio State University. Cited by: §1.2. [SHA07] D. Shah (2007) Gossip Algorithms. Foundations and Trends® in Networking 3 (1), p. 1–125. External Links: ISSN 1554-057X, 1554-0588, Document Cited by: §1. [S25] N. Shimizu and T. Shiraga (2025) 3-Majority and 2-Choices with Many Opinions. In ACM Symposium on Principles of Distributed Computing, PODC, p. 207–217. External Links: Document, ISBN 979-8-4007-1885-4 Cited by: §1.2, §2.1.1, §2.1, §2, §2, §6.4, §8.2, §8, Lemma 41, Lemma 42, Lemma 43, Lemma 44. [TOW83] J. T. Townsend (1983) The stochastic modeling of elementary psychological processes. Cambridge University Press. External Links: ISBN 978-0-521-24181-6, LCCN BF 39 T748s 1983 Cited by: §1. [WIK26a] Wikipedia contributors (2026) Newton’s inequalities — Wikipedia, the free encyclopedia. Note: https://en.wikipedia.org/w/index.php?title=Newton%27s_inequalities&oldid=1334087247[Online; accessed 17-February-2026] Cited by: Lemma 54. [WIK26b] Wikipedia contributors (2026) Poisson distribution — Wikipedia, the free encyclopedia. Note: https://en.wikipedia.org/w/index.php?title=Poisson_distribution&oldid=1337666560[Online; accessed 17-February-2026] Cited by: Theorem 45. APPENDIX Appendix A Tools Theorem 45 (Also in [WIK26b]). Let Xii∈[n] \X_i \_i∈[n] be n mutually independent Poisson(λi)Poisson( _i) random variables. Conditioning on the sum S=∑i∈[n]Xi=sS= _i∈[n]X_i=s, we have ((Xi)i∈[n]∣S=s)∼Multinomial(p,s) ( (X_i )_i∈[n] S=s ) (p,s) where p=(λi∑j∈[n]λj)i∈[n]p= ( _i _j∈[n] _j )_i∈[n]. Definition 46 (Negative association). Random variables X1,…,XnX_1,…,X_n are negatively associated if for every two disjoint index sets I,J⊆[n]I,J [n], [f(Xi,i∈I)g(Xj,j∈J)]≤[f(Xi,i∈I)][g(Xj,j∈J)] E [f(X_i,i∈ I)g(X_j,j∈ J)]≤ E [f(X_i,i∈ I)] E [g(X_j,j∈ J)] for all functions f:ℝI→ℝf:R^I and g:ℝJ→ℝg:R^J that are both non-decreasing. Lemma 47 (Lemma 2 of [DR98]). Let X1,…,XnX_1,…,X_n be a sequence of negatively associated random variables. Then for any non-decreasing functions fif_i, i∈[n]i∈[n], [∏i∈[n]fi(Xi)]≤∏i∈[n][fi(Xi)]. E [ _i∈[n]f_i(X_i)]≤ _i∈[n] E [f_i(X_i)]. Lemma 48 (Lemma 8 of [DR98]). Let X1,…,XnX_1,…,X_n be random variables taking values in 0,1 \0,1 \ such that ∑i∈[n]Xi=1 _i∈[n]X_i=1. Then X1,…,XnX_1,…,X_n are negatively associated. Proposition 49 (Proposition 7 of [DR98]). We have the following: 1. Let X1,…,XnX_1,…,X_n and Y1,…,YnY_1,…,Y_n be two sequences of negatively associated random variables that are mutually independent. Then X1,…,Xn,Y1,…,YnX_1,…,X_n,Y_1,…,Y_n are negatively associated. 2. Let X1,…,XnX_1,…,X_n be a sequence of negatively associated random variables. Let I1,…,IkI_1,…,I_k be disjoint index sets for some k. For j∈[k]j∈[k], let hj:ℝIj→ℝh_j:R^I_j be functions that are all non-decreasing or all non-increasing, and define Yj:=hj(Xi,i∈Ij)Y_j:=h_j(X_i,i∈ I_j). Then, Y1,…,YkY_1,…,Y_k are negatively associated. That is, non-decreasing (or non-increasing) functions of disjoint subsets of negatively associated random variables are also negatively associated. Lemma 50 (Multiplicative forms of Chernoff bounds [DP09]). Let X1,…,XnX_1,…,X_n be independent binary random variables. Let X=∑i=1nXiX= _i=1^nX_i and μ=[X]μ= E[X]. Then: 1. For any δ∈(0,1)δ∈(0,1) and any μ≤μ+≤nμ≤ _+≤ n, it holds that Pr(X≥(1+δ)μ+)≤exp(−δ2μ+/3). (X≥(1+δ) _+)≤ (-δ^2 _+/3). 2. For any δ∈(0,1)δ∈(0,1) and any 0≤μ−≤μ0≤ _-≤μ, it holds that Pr(X≤(1−δ)μ−)≤exp(−δ2μ−/2). (X≤(1-δ) _-)≤ (-δ^2 _-/2). Lemma 51 (Hoeffding bounds [MU05]). Let a<ba<b be two constants, and X1,…,XnX_1,…,X_n be independent random variables such that Pr(a≤Xi≤b)=1 (a≤ X_i≤ b)=1 for all i∈[n]i∈[n]. Let X=∑i=1nXiX= _i=1^nX_i and μ=[X]μ= E[X]. Then: 1. For any t>0t>0 and any μ≤μ+μ≤ _+, it holds that Pr(X≥μ++t)≤exp(−2t2n(b−a)2). (X≥ _++t)≤ (- 2t^2n(b-a)^2). 2. For any t>0t>0 and any 0≤μ−≤μ0≤ _-≤μ, it holds that Pr(X≤μ−t)≤exp(−2t2n(b−a)2). (X≤ _--t)≤ (- 2t^2n(b-a)^2). Lemma 52 (Bernstein inequality for independent bounded variables [BLB03]). Let X1,…,XnX_1,…,X_n be independent random variables such that [Xi]=0E[X_i]=0 and |Xi|≤bi|X_i|≤ b_i Denote Sn=∑i=1nXi,V=∑i=1nVar(Xi),B=max1≤i≤nbi.S_n= _i=1^nX_i, V= _i=1^nVar(X_i), B= _1≤ i≤ nb_i. Then for every t>0t>0, ℙ(Sn≥t)≤exp(−t22V+23Bt).P(S_n≥ t)≤ \! (- t^22V+ 23Bt ). The same bound holds for ℙ(Sn≤−t)P(S_n≤-t). Theorem 53 (From [JAN18]). Let X=∑i=1nXiX= _i=1^nX_i be a sum of independent geometric random variables Xi∼Geom(pi)X_i (p_i) with 0<pi≤10<p_i≤ 1. Let μ:=X=∑i=1n1/piμ:=EX= _i=1^n1/p_i and let p∗:=minipip_*:= _ip_i. For any λ≥1λ≥ 1, Pr(X≥λμ)≤exp(−p∗μ(λ−1−lnλ)). (X≥λμ )≤ (-p_*μ(λ-1- λ) ). Lemma 54 (Newton’s inequality for elementary symmetric polynomials [WIK26a]). Let x1,x2,…,xnx_1,x_2,…,x_n be non-negative real numbers. For k∈1,…,n−1k∈\1,…,n-1\, let ek()e_k(x) denote the k-th elementary symmetric polynomial: ek()=∑1≤i1<i2<⋯<ik≤nxi1xi2…xik.e_k(x)= _1≤ i_1<i_2<…<i_k≤ nx_i_1x_i_2… x_i_k. The normalized elementary symmetric means Sk=ek/(nk)S_k=e_k/ nk satisfy Sk2≥Sk−1Sk+1.S_k^2≥ S_k-1S_k+1. Corollary 55. The following inequality holds: ek()2≥ek−1()⋅ek+1().e_k(x)^2≥ e_k-1(x)· e_k+1(x). Proof. By Lemma 54, (ek(nk))2≥ek−1(nk−1)⋅ek+1(nk+1). ( e_k nk )^2≥ e_k-1 nk-1· e_k+1 nk+1. Rearranging gives ek2≥(nk)2(nk−1)(nk+1)ek−1ek+1.e_k^2≥ nk^2 nk-1 nk+1\,e_k-1e_k+1. For every 1≤k<n1≤ k<n, (nk)2(nk−1)(nk+1)=(k+1)(n−k+1)k(n−k)>1. nk^2 nk-1 nk+1= (k+1)(n-k+1)k(n-k)>1. Therefore ek2≥ek−1ek+1e_k^2≥ e_k-1e_k+1, as claimed. ∎