On the h-Majority Dynamics with Many Opinions

d'Amore, Francesco; D'Archivio, Niccolò; Giakkoupis, George; Natale, Emanuele

doi:10.4230/LIPIcs.DISC.2025.27

On the $𝒉$ -Majority Dynamics with Many Opinions

Francesco d’Amore

Gran Sasso Science Institute, L’Aquila, Italy Niccolò D’Archivio

INRIA, COATI, Université Côte d’Azur, Nice, France George Giakkoupis

INRIA Rennes, France Emanuele Natale

CNRS, I3S, COATI, Université Côte d’Azur, Nice, France

Abstract

We present the first upper bound on the convergence time to consensus of the well-known $h$ -majority dynamics with $k$ opinions, in the synchronous setting, for $h$ and $k$ that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by $x$ nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is $\omega(\sqrt{x})$ and the initial plurality opinion is supported by at least $x=\omega(\log n)$ nodes, then the process converges to plurality consensus in $O(\log n)$ rounds whenever $h=\omega(n\log n/x)$ . A main corollary is the following: if $k=o(n/\log n)$ and the process starts from an almost-balanced configuration with an initial bias of magnitude $\omega(\sqrt{n/k})$ towards the initial plurality opinion, then any function $h=\omega(k\log n)$ suffices to guarantee convergence to consensus in $O(\log n)$ rounds, with high probability. Our upper bound shows that the lower bound of $\Omega(k/h^{2})$ rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than $\widetilde{\Omega}(k/h)$ . Moreover, the bias we require is asymptotically smaller than the $\Omega(\sqrt{n\log n})$ bias that guarantees plurality consensus in the $3$ -majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in $\omega(\sqrt{x})$ for any value of $k\geq 2$ .

Keywords and phrases:

Distributed Algorithms, Randomized Algorithms, Markov Chains, Consensus Problem, Opinion dynamics, Plurality Consensus

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed algorithms ; Mathematics of computing

\rightarrow

Probabilistic algorithms ; Mathematics of computing

\rightarrow

Markov processes ; Applied computing

\rightarrow

Systems biology ; Networks

\rightarrow

Network protocols

Related Version:

Full Version: https://arxiv.org/abs/2506.20218 [17]

Acknowledgements:

The authors are grateful to Frédéric Giroire for helpful discussions regarding this project.

Funding:

This work was partially supported by the MUR (Italy) Department of Excellence 2023 - 2027 for GSSI, the AID INRIA-DGA project n°2023000872 “BioSwarm”, and the 3IA Côte d’Azur Investments in the Future project ANR-19P3IA-0002.

DOI:

10.4230/LIPIcs.DISC.2025.27

Event:

39th International Symposium on Distributed Computing (DISC 2025)

Editor:

Dariusz R. Kowalski

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In this paper, we study the convergence time of the well-known $h$ -majority dynamics. In brief, the setting is the following: We are given a network of $n$ agents that interact with each other in synchronous rounds. At round 0, each agent supports one out of $k$ possible opinions in the set $[k]$ : At round $i>0$ , each agent $v$ samples uniformly at random $h$ neighbors $u_{1},\ldots,u_{h}$ (with repetition) which, in turn, send their opinions $x_{1},\ldots,x_{h}$ to $v$ . Then, $v$ adopts as its own opinion the mode of $\{x_{1},\ldots,x_{h}\}$ , breaking ties uniformly at random. Let $\mathbf{c}_{t}(i)$ count the number of agents supporting opinion $i$ after round number $t$ . The $h$ -majority dynamics gives rise to a random process on the system graph, which we call the $h$ -majority process. The question is to determine the number of communication rounds that the process needs to reach consensus, i.e., a configuration where all agents agree on some opinion $i\in[k]$ . Furthermore, we are interested in plurality consensus: Suppose that at the beginning of the process there is a plurality opinion, that is, an opinion $i^{\star}$ such that $\mathbf{c}_{0}(i^{\star})>\mathbf{c}_{0}(j)$ for all $j\neq i^{\star}$ . Plurality consensus is consensus on the opinion $i^{\star}$ , and one wishes to quantify the size of the initial bias that guarantees to obtain plurality consensus with high probability.¹¹1The expression with high probability (in short, w.h.p.) refers to an event that holds with probability at least $1-n^{-c}$ , where $c>0$ is any constant that is independent of the size $n$ of the distributed system.

1.1 Our contribution

We give the first non-trivial upper bound to the consensus time of the $h$ -majority process with $k$ opinions for non-constant $h$ and $k$ . Let us denote the difference $\max_{i}\min_{j\neq i}\{\mathbf{c}_{t}(i)-\mathbf{c}_{t}(j)\}$ by $\mathrm{B}_{t}$ and refer to it as the bias of the configuration $\mathbf{c}_{t}$ at time $t$ . In a nutshell, our main result is the following.

Theorem 1.

Consider the $h$ -majority dynamics with $k$ opinions in the complete graph of $n$ nodes with self-loops ²²2Assuming self-loops is standard in the literature, as it simplifies the analysis without affecting the possible outcomes.. Let $\lambda_{1},\lambda_{2},\lambda_{3}$ be large enough positive constants. Assume that opinion 1 is the initial plurality opinion with $\mathrm{B}_{0}\geq\lambda_{1}\sqrt{\mathbf{c}_{0}(1)}$ and $\mathbf{c}_{0}(1)\geq\lambda_{2}\log n$ . If $h\geq\lambda_{3}n\log n/\mathbf{c}_{0}(1)$ , then, with high probability, the $h$ -majority process reaches plurality consensus within $O(\log n)$ rounds.

Let us discuss Theorem 1 a bit more in details. First, notice that it always holds $\mathbf{c}_{0}(1)\geq n/k$ since $k\geq n/\mathbf{c}_{0}(1)$ . In the following, we say that a configuration is almost-balanced if there exists a subset $I\subseteq[k]$ , with $\absolutevalue{I}=O(1)$ , such that $\mathbf{c}_{0}(i)=\Theta(\mathbf{c}_{0}(1))$ for all $i\in[k]\setminus I$ , assuming that opinion $1$ is the plurality opinion. Notice that, in this case, it must hold that $\mathbf{c}_{0}(1)=\Theta(n/k)$ and $\mathbf{c}_{0}(i)=\Theta(n/k)$ for all $i\in[k]\setminus I$ .

Case 1: $k=O(n/\log n)$ .

Here we have two sub-cases depending on how we fix $\mathbf{c}_{0}(1)$ . In the first sub-case, we fix $\mathbf{c}_{0}(1)=\Theta(n/k)$ such that $\mathbf{c}_{0}(1)\geq\lambda_{2}\log n$ (which is always possible). Here, we must select some large enough $h=\Theta(n\log n/c_{0}(1))=\Theta(k\log n)$ in order to apply Theorem 1, with the required bias that is minimum, that is, $\mathrm{B}_{0}=\Theta(\sqrt{n/k})$ : observe that the configuration is necessarily almost-balanced. If, instead, $\mathbf{c}_{0}(1)=\omega(n/k)$ , it is guaranteed that $\mathbf{c}_{0}(1)=\omega(\log n)$ . In this case, the configuration cannot be almost-balanced because the required bias is $\mathrm{B}_{0}=\Theta(\sqrt{\mathbf{c}_{0}(1)})=\omega(\sqrt{n/k})$ . Here, we can pick $h=\Theta(n\log n/\mathbf{c}_{0}(1))=o(k\log n)$ .

Case 2: $k=\omega(n/\log n)$ .

Since $k=\omega(n/\log n)$ and $\mathbf{c}_{0}(1)=\Omega(\log n)$ by hypothesis, we cannot have almost balanced configurations: we can always choose some $h=o(k\log n)$ and we will have that the minimum bias is $\mathrm{B}_{0}=\omega(\sqrt{n/k})$ . Note that in this setting, $h$ may be larger than $n$ , which we do not exclude as the samples can contain repetitions.

Observations

Despite the assumption $h\geq\lambda_{3}n\log n/\mathbf{c}_{0}(1)$ is undoubtedly a strong one (that is, $h$ needs to be at least roughly $k\log n$ for almost-balanced configurations), in Section 3 we show how the analysis for such regime of $h$ is already quite involved and we discuss what the main difficulties to reduce such assumption are. Also, in Section 3 we will highlight why we believe that $h\sim n/\mathbf{c}_{0}(1)$ is a “threshold” value, since the two settings $h\ll n/\mathbf{c}_{0}(1)$ and $h\gg n/\mathbf{c}_{0}(1)$ seem to need complementary approaches, which is also why our analysis cannot be adapted to the case $h\ll n/\mathbf{c}_{0}(1)$ . However, since $h$ is a “static” parameter of the $h$ -majority dynamics, in order to approach the case $h<\lambda_{3}n\log n/\mathbf{c}_{0}(1)$ , one has to show only that there is a time $t>0$ such that $\mathbf{c}_{t}(1)\geq\lambda_{3}n\log n/h$ and that opinion $1$ is still the plurality opinion with $B_{t}$ that meets the hypothesis of Theorem 1, which implies that our analysis applies.

Prior to this work, the only result for the $h$ -majority dynamics with non-constant $h$ and $k$ was a lower bound of $\Omega(k/h^{2})$ rounds to reach consensus given by [5] that holds with high probability whenever $\max_{i\in[k]}\{\mathbf{c}_{0}(i)\}\leq 3n/(2k)$ . Hence, Theorem 1 shows that the lower bound cannot be pushed to $\widetilde{\Omega}(k/h)$ (where the notation $\widetilde{\Omega}$ hides $\text{polylog}(n)$ factors), at least as long as $\max_{i\in[k]}\{\mathbf{c}_{0}(i)\}\leq 3n/(2k)$ is satisfied, e.g., when $(n-\mathrm{B}_{0})/(\mathbf{c}_{0}(1)-\mathrm{B}_{0})\leq k\leq 3n/(2\mathbf{c% }_{0}(1))$ , which is always realized when $\max\{(n+(k-1)\mathrm{B}_{0})/k,\lambda_{2}\log n\}\leq\mathbf{c}_{0}(1)\leq 3% n/(2k)$ and $k\leq 3n/(2\lambda_{2}\log n)$ for any value of $\mathrm{B}_{0}$ meeting the hypothesis of Theorem 1.

Furthermore, as we will discuss in the related works, in the context of opinion dynamics, the minimum required bias in any other opinion dynamics is always asymptotically larger than our minimum required bias. Interestingly, the $h$ -majority dynamics can amplify a very small bias even when $h=O(k\log n)$ (this is easy to prove for very large $h$ as we argue in Section 3, but it is not at all trivial for our parameters).

A final remark that we stress is about the message complexity. According to Theorem 1, the message complexity required to reach consensus is $O(hn\log n)$ , which can be as high as $O(kn\log^{2}n)$ in almost-balanced configurations. By recent work on the $3$ -majority dynamics (see Section 1.2), the message complexity of the $3$ -majority dynamics is $O(kn\log n)$ . We believe that the gap between these two quantities is due to the fact that the analysis of the $h$ -majority dynamics is not yet tight.

1.2 Previous results

There is a vast body of research that investigated the $h$ -majority dynamics when either $h$ or $k$ are constant values, both in the synchronous and in the asynchronous settings [5, 9, 10, 27, 13, 34]. Before exploring the results in the two settings, let us discuss the work [10]. The authors compared the power of the $h$ -majority dynamics and that of the $(h+1)$ -majority dynamics with $k=2$ opinions. They proved that, starting from the same configuration, the consensus time $T_{h+1}$ of the $(h+1)$ -majority dynamics is stochastically dominated by the consensus time $T_{h}$ of the $h$ -majority dynamics in the following sense: for each $t>0$ , $\Pr(T_{h+1}\leq t)\geq\Pr(T_{h}\leq t)$ in both the synchronous and the asynchronous settings. However, to date no such extension to the case of $k>2$ opinions is known.

Synchronous setting

Let us specify that all the results we mention in this subsection and the next two ones hold in the complete graph of $n$ nodes with self-loops. The work [6] proved an upper bound of $O\left((k^{2}\sqrt{\log n}+k\log n)(k+\log n)\right)$ rounds to reach consensus that holds w.h.p., provided that $k\leq n^{\alpha}$ for a suitable positive constant $\alpha<1$ .

In [5], the authors showed that the synchronous $3$ -majority dynamics with $k$ opinions converges in $O(\min\{k,(n/\log n)^{\frac{1}{3}}\}\log n)$ with high probability, provided that the bias of the initial configuration is at least $c\sqrt{\min\{2k,(n/\log n)^{\frac{1}{3}}\}n\log n}$ for some constant $c>0$ . Moreover, the authors provided a lower bound of $\Omega(k\log n)$ on the convergence time to consensus, w.h.p., whenever the initial configuration is sufficiently balanced, that is, $\max_{i\in[k]}\{\mathbf{c}_{0}(i)\}\leq n/k+(n/k)^{1-\varepsilon}$ for some $\varepsilon>0$ and $k\leq(n/\log n)^{1/4}$ .

The work [9] compared the synchronous $3$ -majority dynamics with the synchronous $2$ -choices dynamics. The $2$ -choices dynamics works as follows: At each round, each agent picks two neighbors (with repetition) u.a.r. If the two sampled neighbors support the same opinion, the agent adopts that opinion. Otherwise, the agent keeps its own opinion. The authors first proved a generic lower bound of $\Omega(\min\{k,n/\log n\})$ rounds to reach consensus starting from the initial perfectly balanced configuration, w.h.p. Furthermore, they proved that the $3$ -majority dynamics works better in symmetric configurations (i.e., with no initial bias) when, e.g., $\max_{i\in[k]}\{\mathbf{c}_{0}(i)\}=O(\log n)$ . In particular, w.h.p., the $3$ -majority takes time at most $O(n^{3/4}\log^{7/8}n)$ to reach consensus w.h.p., regardless of any other hypothesis on the initial configuration, while the $2$ -choices needs time $\Omega(n/\log n)$ whenever $\max_{i\in[k]}\{\mathbf{c}_{0}(i)\}=O(\log n)$ . This was the first work to notice that, for a large number of opinions, the $3$ -majority dynamics is polynomially (in $k$ ) faster than the $2$ -choices dynamics.

The work [27] improved upon [5] and showed that, for the $2$ -choices with $k=O(\sqrt{n/\log n})$ and for the $3$ -majority with $k=O(n^{1/3}/\sqrt{\log n})$ , the convergence time to consensus is $O(k\log n)$ , with high probability. Notice that this upper bound is tight according to the lower bound by [5], at least as long as $k\leq(n/\log n)^{1/4}$ . Furthermore, the authors showed that the convergence time on the $3$ -majority dynamics is $O(n^{2/3}\log^{3/2}n)$ with high probability, regardless of the number of opinions.

Very recently, [34] settled almost tightly the complexity of both the $3$ -majority and the $2$ -choices dynamics. The authors proved that, w.h.p., the $3$ -majority dynamics reaches consensus in $O(k\log n)$ rounds whenever $k=o(\sqrt{n}/\log n)$ , while it takes time $O(\sqrt{n}\log^{2}n)$ for other values of $k$ . Furthermore, [34] proved that plurality consensus is ensured w.h.p. as long as the initial bias is $\mathrm{B}_{0}=\omega(\sqrt{n\log n})$ . As for the $2$ -choices, they showed that, w.h.p., the dynamics reaches consensus in $O(k\log n)$ rounds whenever $k=o(n/\log^{2}n)$ , while it takes time $O(n\log^{3}n)$ otherwise. In this case, plurality consensus is ensured w.h.p. as long as the initial bias is $\mathrm{B}_{0}=\omega(\sqrt{\mathbf{c}_{0}(1)\log n})$ .³³3This is the only example of initial bias that gets “close enough” to what we require in Theorem 1, but with an exceeding $\sqrt{\log n}$ factor. These results almost match the generic lower bound given by [9], up to logarithmic factors.

Asynchronous setting

The only works that analyzed the $3$ -majority dynamics in the asynchronous setting are [13, 10]. In [10], the authors consider the binary opinion case and show that the convergence time of the asynchronous $3$ -majority dynamics is $O(n\log n)$ rounds, w.h.p., and that a bias of $\Theta(\sqrt{n\log n})$ is sufficient to ensure plurality consensus, w.h.p. The authors of [13] showed that the convergence time is $O(\min\{kn\log^{2}n,n^{3/2}\log^{3/2}n\})$ , w.h.p., no matter the number of initial opinions. They also provided a generic lower bound of $\Omega(\min\{kn,n^{3/2}/\sqrt{\log n}\})$ rounds to reach consensus (starting from balanced configurations), w.h.p. The work [13] (which came before [34]) was the first to establish exactly how the linear-in- $k$ dependence in the consensus time of the $3$ -majority dynamics breaks when the number of opinions grows over $\sqrt{n}$ , in which case the consensus time is sublinear in the number of opinions. The reader may observe that the asynchronous setting has exactly the same convergence time as the synchronous model, but for a multiplicative factor $n$ . This is to be expected: In the asynchronous setting, in a round only one agent (sampled u.a.r.) updates its state, and hence we need roughly $n$ rounds to activate all agents at least once (up to polylogarithmic factors). For processes with small variance (smaller w.r.t. the voter model), convergence times from the synchronous to the asynchronous setting usually scale with such a factor. Note that this is not true for processes with large variance [7].

On the $𝒉$ -majority dynamics

As previously discussed, [10] established the “hierarchy” of the $h$ -majority dynamics when the number of opinions is $k=2$ , by showing that the $(h+1)$ -majority is “faster” than the $h$ -majority (both in the synchronous and asynchronou settings), and [5] exhibited the lower bound of $\Omega(k/h^{2})$ rounds to reach consensus (that holds w.h.p.). Apart for the two aforementioned works, there is no theoretical result on the $h$ -majority dynamics for $h\gg 1$ , which makes it one of the open problems in consensus dynamics. [34] put the $h$ -majority dynamics in the “Open Question” section of their recent work, and wondered whether the techniques developed in [34] applied to the $h$ -majority dynamics as well. We do not know the answer to this question: As we will discuss in Section 3, in the $h$ -majority the main difficulty is to compute the expectation of $\mathbf{c}_{t+1}(i)$ conditional on the whole configuration $\mathbf{c}_{t}$ at the previous rounds, while this is straightforward when $h=3$ and is at the core of every paper analyzing the $3$ -majority dynamics [6, 5, 27, 34, 13]. More in general, there is no non-trivial upper bound to the consensus time of the $h$ -majority dynamics with $k\gg 1$ opinions. In this paper, we take a first step into the analysis of the $h$ -majority dynamics. As we will show, our main effort basically is providing a lower bound to $\operatorname*{\mathbb{E}}[\mathbf{c}_{t+1}(1)-\mathbf{c}_{t+1}(2)\mid\mathbf{% c}_{t}]$ , supposing that opinion 1 is the plurality opinion at round $t$ , and opinion $2$ is the opinion supported by the second-largest community.

Other related works

The $3$ -majority, the $h$ -majority, and other majority-based dynamics have been investigated also in other settings. For example, in presence of communication noise (which corrupts the exchanged messages) or in presence of stubborn agents [18, 19], or when some opinion is preferred among the others, that is, there is some probability that an agent, instead of running the protocol, spontaneously switches to the preferred opinion with some fixed probability [14, 32].

Other opinion dynamics for the (plurality) consensus problem have been investigated both in the synchronous and asynchronous settings. One of the most prominent is the undecided-state dynamics. In the undecided-state dynamics there is an extra opinion, the undecided opinion. The update rule works as follows: A node samples one neighbor u.a.r. and pulls its opinion. If the received opinion is different from the supported one, the node becomes undecided. If the node is undecided, it just copies whatever opinion receives. The undecided-state dynamics has been studied both in the synchronous setting and in the population protocol model (asynchronous setting) [2, 12, 4, 15, 16, 1, 8, 3] and performs roughly the same as the $3$ -majority dynamics for a small number of opinions (while its analysis for the unconstrained general case is still open). More in general, work on opinion dynamics fits into the recent trend in the distributed computing community of drawing inspiration from social and biological systems. Other then the consensus problem, researchers have analyzed distributed search problems but also more generic problems (MIS, leader election, etc.) in extremely weak computational models (such as the beeping model or the stone-age model) [31, 23, 11, 29, 28, 20, 26, 35, 24, 22].

A special mention goes to [25]. Here, the authors considered noisy distributed systems, i.e., systems in which exchanged messages can be corrupted and changed with some positive probability, a setting that takes inspiration by biological societies, where environmental factors can disturb communication. They characterized the type of noise for which the tasks of information spreading and plurality consensus can be solved, when the number of opinions is constant.⁴⁴4Information spreading is defined as follows: In the distributed system there is only one node that is informed about one out $k$ opinions, while all other nodes are not informed. The task is to design a protocol that informs all nodes as fast as possible. The protocol designed by [25] to solve plurality consensus relies on some majority-based rule, and proves a technical result that is at the heart of our analysis. We will discuss this in more details in Section 3. We nevertheless stress the fact that [25] only considers the case where the number of opinions $k$ is a constant.

2 Preliminaries

We work on a complete graph of $n$ nodes with self-loops. Initially, each node supports one out of $k$ opinions in the set $[k]$ . Time is synchronous and controlled by some global clock. At each round, in parallel, every node $v$ samples $h$ neighbors u.a.r. with repetition and pulls their opinions. Then, $v$ adopts the unique majority opinion, if any, breaking ties u.a.r. among the opinions that are in the majority. For each opinion $i\in[k]$ , we denote by $\mathbf{c}_{t}(i)$ the number of nodes supporting opinion $i$ at time after performing the update-rule at time $t$ . Let $\mathbf{c}_{t}=(\mathbf{c}_{t}(1),\ldots,\mathbf{c}_{t}(k))$ denote the configuration of the system at time $t$ . Notice that the random variable $\mathbf{c}_{t}$ defines a Markov chain: for any sequence of configurations $y_{1},\ldots,y_{t}\in[n]^{k}$ , it holds that $\Pr(\mathbf{c}_{t}=y_{t}\mid\cap_{i=1}^{t-1}\{\mathbf{c}_{i}=y_{i}\})=\Pr(% \mathbf{c}_{t}=y_{t}\mid\mathbf{c}_{t-1}=y_{t-1})$ .

Without loss of generality, we assume that at the beginning of the process we have $\mathbf{c}_{0}(1)\geq\mathbf{c}_{0}(2)\geq\ldots\mathbf{c}_{0}(k)$ . At any time $t$ , we call plurality opinion at time $t$ the opinion $i$ such that $\mathbf{c}_{t}(i)\geq\mathbf{c}_{t}(j)$ for all $j\in[k]$ . At any time $t$ , the bias of a configuration $\mathbf{c}_{t}$ is the quantity $\mathrm{B}_{t}=\max_{i\in[k]}\min_{j\neq i}\{\mathbf{c}_{t}(i)-\mathbf{c}_{t}(% j)\}$ , that is, of how many nodes the community supporting the plurality opinion exceeds the community supporting the second largest one. Note that $\mathrm{B}_{t}=0$ if there are multiple plurality opinions, while $\mathrm{B}_{t}>0$ the plurality opinion is unique.

We work from the perspective of a single node. When a node $v$ samples $h$ neighbors u.a.r., we are drawing from a multinomial distribution. In particular, given a configuration $\mathbf{c}_{t}$ at time $t$ and a node $v$ , let $\mathbf{X}^{(t)}(v)=(X_{1}^{(t)}(v),\ldots,X_{k}^{(t)}(v))$ be a multinomial random variable where $X_{i}^{(t)}(v)\sim\text{Bin}(n,p_{i}^{(t)})$ , with $p_{i}^{(t)}=\mathbf{c}_{t}(i)/n$ , counts the number of neighbors supporting opinion $i$ that $v$ samples at time $t$ : it must hold that $\sum_{i=1}^{k}X_{i}^{(t)}(v)=n$ , so the variables are negatively correlated. Let us denote the event that $v$ supports opinion $i$ at the end of round $t$ by $\mathcal{W}_{i}^{(t)}(v)$ .

For the rest of the paper, we will use only $p_{1}^{(t)},\ldots,p_{k}^{(t)}$ , since these are the probabilities defining the multinomial distribution of interest. We define the normalized bias to be $\delta_{t}=\max_{i\in[k]}\min_{j\neq i}\{p_{i}^{(t)}-p_{j}^{(t)}\}$ , which is equal to $\mathrm{B}_{t}/n$ . When the round we are referring to is clear from the context, we only write $p_{1},\ldots,p_{k}$ , $\delta$ , $\mathbf{X}(v)=(X_{1}(v),\ldots,X_{k}(v))$ , and $\mathcal{W}_{i}(v)$ , omitting the dependency on $t$ , to refer to $p_{1}^{(t)},\ldots,p_{k}^{(t)}$ , $\delta_{t}$ , $\mathbf{X}^{(t)}(v)=(X_{1}^{(t)}(v),\ldots,X_{k}^{(t)}(v))$ , and $\mathcal{W}_{i}^{(t)}(v)$ . Also, since in any given round $t$ the random variables $\{\mathbf{X}(v)\}_{v\in V}$ are i.i.d., and the events $\{\mathcal{W}_{i}(v)\}_{v\in V}$ are mutually independent, when analyzing the distribution of some $\mathbf{X}(v)$ or the probabilities of some $\mathcal{W}_{i}(v)$ , we omit the dependency on $v$ and only write $\mathbf{X}=(X_{1},\ldots,X_{k})$ and $\mathcal{W}_{i}$ .

From now on, we will refer to the normalized bias $\delta_{t}$ simply as the bias of the configuration, as we will not make use of $\mathrm{B}_{t}$ anymore. With this notation, our main theorem can be rewritten as follows:

Theorem 2.

Let $\lambda_{1},\lambda_{2},\lambda_{3}$ be large enough positive constants. Assume that opinion 1 is the initial plurality opinion with $\delta_{0}\geq\lambda_{1}\sqrt{p_{1}/n}$ and $p_{1}\geq\lambda_{2}\log n/n$ . If $hp_{1}\geq\lambda_{3}\log n$ , then, with high probability, the $h$ -majority process reaches plurality consensus within $O(\log n)$ rounds.

3 Overview of our analysis and technical challenges

The whole analysis is an effort to estimate the quantity $\Pr(\mathcal{W}_{1})-\Pr(\mathcal{W}_{2})$ from below (assuming that $p_{1}\geq p_{2}\geq\ldots\geq p_{k}$ ), and use it to get a lower bound on the expect round-by-round growth of the bias $\delta$ . Notice that, for any given configuration $\mathbf{c}_{t}$ at time $t$ , it holds that

$\displaystyle\operatorname*{\mathbb{E}}[\delta_{t+1}\mid\mathbf{c}_{t}]$	$\displaystyle\geq\operatorname*{\mathbb{E}}\left[\max_{i\in[k]}\min_{j\neq i}% \left\{\Pr(\mathcal{W}_{i}^{(t+1)})-\Pr(\mathcal{W}_{j}^{(t+1)})\right\}\ % \middle\|\ \mathbf{c}_{t}\right]$
	$\displaystyle\geq\operatorname*{\mathbb{E}}\left[\min_{j\neq 1}\left\{\Pr(% \mathcal{W}_{1}^{(t+1)})-\Pr(\mathcal{W}_{j}^{(t+1)})\right\}\ \middle\|\ % \mathbf{c}_{t}\right]$
	$\displaystyle\geq\operatorname*{\mathbb{E}}\left[\Pr(\mathcal{W}_{1}^{(t+1)})-% \Pr(\mathcal{W}_{2}^{(t+1)})\ \middle\|\ \mathbf{c}_{t}\right].$	(1)

Suppose that $p_{1}^{(t)}=p_{2}^{(t)}+\delta_{t}>p_{2}^{(t)}\geq\ldots\geq p_{k}^{(t)}$ . This implies that $\Pr\mspace{2.0mu}(\mathcal{W}_{1}^{(t+1)}\mid\mathbf{c}_{t})-\Pr\mspace{2.0mu}% (\mathcal{W}_{i}^{(t+1)}\mid\mathbf{c}_{t})\geq\Pr\mspace{2.0mu}(\mathcal{W}_{% 1}^{(t+1)}\mid\mathbf{c}_{t})-\Pr\mspace{2.0mu}(\mathcal{W}_{2}^{(t+1)}\mid% \mathbf{c}_{t})$ for all $i\geq 3$ since $p_{2}^{(t)}\geq p_{i}^{(t)}$ for $i\geq 3$ . If we proved that $\Pr\mspace{2.0mu}(\mathcal{W}_{1}^{(t+1)}\mid\mathbf{c}_{t})-\Pr\mspace{2.0mu}% (\mathcal{W}_{2}^{(t+1)}\mid\mathbf{c}_{t})\geq\delta_{t}(1+x)$ for some constant $x>0$ , then we would get $\operatorname*{\mathbb{E}}[\delta_{t+1}\mid\mathbf{c}_{t}]\geq\delta_{t}(1+x)$ , which allows us to concentrate and establish that $\delta_{t+1}\geq\delta_{t}(1+x/2)$ w.h.p. (conditional on $\mathbf{c}_{t}$ ), for a suitable choice of $x>0$ and for a large enough $\delta_{t}$ , thanks to the Hoeffding bound (Lemma 23).

Notice that, in general, the probability of $\mathcal{W}_{i}$ is the probability that $X_{i}$ is either the unique maximum or, if it is a maximum and is not unique, it must win the tie broken u.a.r. In formulas, the probability is

\displaystyle\Pr(\mathcal{W}_{i})=\sum_{m=1}^{k}\frac{1}{m}\sum_{\begin{% subarray}{c}1\leq i_{1}<\ldots<i_{m}\leq k:\\ i_{j}\neq i\,\forall j\in[m]\end{subarray}}\Pr(\bigcap_{j\in[m]}\{X_{i}=X_{i_{% j}}\}\cap(\bigcap_{j\notin\{i,i_{1},\ldots,i_{m}\}}\{X_{i}>X_{j}\})).

(2)

Using directly Equation 2 to bound $\Pr(\mathcal{W}_{1})-\Pr(\mathcal{W}_{2})$ is difficult, and we did not find general estimations in the literature.

Trivial case: very large $𝒉$

If, e.g., $h$ is very large compared to $\delta$ , in one round all nodes would adopt the plurality opinion with high probability. The reason follows.

Suppose $p_{1}=p_{2}+\delta>p_{2}\geq\ldots\geq p_{k}$ . Then, by the multiplicative Chernoff bound (Lemma 22 in Appendix B) we get that

\Pr(X_{1}\geq hp_{1}(1-x))\geq 1-\exp(-\Theta(x^{2}hp_{1})).

Similarly,

\Pr(X_{i}\leq hp_{2}(1+x))\geq 1-\exp(-\Theta(x^{2}hp_{2})).

Suppose $p_{1}$ and $p_{2}$ are comparable, that is, $p_{1}=\Theta(p_{2})$ (anyway the bias we require is always an $o(p_{1})$ ). Then, $X_{1}\geq hp_{1}(1-x)$ and $X_{i}\leq hp_{2}(1+x)$ for all $i\geq 2$ hold w.h.p. as long as $h\geq C\log n/(p_{1}x^{2})$ for a large enough constant $C>0$ . If $hp_{1}(1-x)>hp_{2}(1+x)$ , then $\mathcal{W}_{1}$ holds w.h.p., that is, a node would adopt opinion 1 in just 1 round w.h.p. Playing with constants, by the union bound, one would obtain plurality consensus w.h.p. in just 1 round. The condition is satisfied whenever $\delta>x(p_{1}+p_{2})$ , that is, for $x<\delta/(p_{1}+p_{2})$ . Since $h\geq C\log n/(p_{1}x^{2})$ and $x<\delta/(p_{1}+p_{2})$ must hold at the same time, it is sufficient to choose $h\geq C^{\prime}p_{1}\log n/\delta^{2}$ for a large enough constant $C^{\prime}>C$ . Notice that, since our bias can be such that $\delta\sim\sqrt{p_{1}/n}$ , we must have that $hp_{1}>(C^{\prime}/\lambda_{1}^{2})p_{1}\cdot n\log n\gg\log n$ for any choice of $p_{1}=\Omega(\log n/n)$ . The minimum that $h$ can be with this approach is $\Theta(\log^{2}n/p_{1})$ and can be as large as $h=\Omega(n^{2/3}/p_{1})$ if $p_{1}\geq 1/n^{1/3}$ . Our Theorem 2 guarantees us that we can always set $h=\Theta(\log n/p_{1})$ as long as $p_{1}\geq\lambda_{2}\log n/n$ for a large enough constant $\lambda_{2}>0$ . For the minimum bias $\delta=\lambda_{1}\sqrt{p_{1}/n}$ , we have that $p_{2}=p_{1}-o(p_{1})$ . Hence, $\operatorname*{\mathbb{E}}[X_{2}]=hp_{2}=hp_{1}-o(hp_{1})=\operatorname*{% \mathbb{E}}[X_{1}]-o(\log n)$ . Unfortunately, we cannot capture such a deviation from the average of $X_{1}$ using concentration bounds, so we need to adopt a different approach.

3.1 Our approach

At the heart of our analysis, there is a technical lemma that was proved in [25, Lemma 9].

The lemma can be reformulated as follows. Suppose we are performing the $h$ -majority when in the system there are only $k=2$ opinions. Then, [25, Lemma 9] provides a tight lower bound on the expected bias after one round, i.e., on $\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)$ . Notice that, when $k=2$ , $\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)=\Pr(X_{1}>X_{2% })+\Pr(X_{1}=X_{2})/2-\Pr(X_{2}>X_{1})-\Pr(X_{1}=X_{2})/2$ , which is equal to $\Pr(X_{1}>X_{2})-\Pr(X_{2}>X_{1})$ .

Lemma 3 (Lemma 9 in [25]).

For any integer $h>0$ , let $X_{1}\sim\mathrm{Binomial}(h,p)$ and $X_{2}=h-X_{1}\sim\mathrm{Binomial}(h,1-p)$ , with $p>1/2$ . Let $\delta=2p-1$ be the bias. Then, we have that

\displaystyle\Pr\left(X_{1}>X_{2}\right)-\Pr\left(X_{2}>X_{1}\right)\geq\sqrt{% \frac{2h}{\pi}}\cdot g(\delta,h),

where

g(\delta,h)=\begin{cases}\delta\,\left(1-\delta^{2}\right)^{\frac{h-1}{2}}&% \text{if }\delta<\frac{1}{\sqrt{h}},\\ \frac{1}{\sqrt{h}}\,\left(1-\frac{1}{h}\right)^{\frac{h-1}{2}}&\text{if }% \delta\geq\frac{1}{\sqrt{h}}.\end{cases}

We show how to adapt the proof of [25, Lemma 9] to get Lemma 3 in the full version of the paper [17]. Basically, Lemma 3 makes explicit the minimum sample size required by the expectation of the bias in the next round to increase by a constant multiplicative factor relative to the current bias, to which we refer here as $\delta$ . More specifically, it is sufficient that the number of samples $h$ satisfies $\sqrt{\frac{2h}{\pi}}\left(1-\delta^{2}\right)^{\frac{h-1}{2}}\geq\sqrt{\frac{% 2h}{\pi\,e}}\geq c$ for some positive constant $c>0$ as long as $\delta<\frac{1}{\sqrt{h}}$ . If, instead, $\delta\geq\frac{1}{\sqrt{h}}$ , the lemma states that the new expected value of the bias is more than a constant, which allows us to show that the bias increases just by standard concentration arguments around the averages of $X_{1}$ and $X_{2}$ (through Berry-Esseen’s inequality or Chernoff bounds depending on how large $\delta$ is w.r.t. $h$ ).

We would like to exploit something that is similar, in spirit, to Lemma 3 when $k\gg 1$ , in order to get that the bias increases each round. However, $X_{1}\sim\text{Binomial}(h,p_{1})$ and $X_{2}\sim\text{Binomial}(h,p_{2})$ but $p_{1}+p_{2}<1$ and $X_{2}\neq h-X_{1}$ . In order to overcome this issue, let us define few events.

Definition 4 (Winning events).

Let $i\in[k]$ . We define $\mathcal{W}_{i,\mathrm{ties}}$ to be the event in which opinion “ $i$ ” is the most sampled opinion, including possible ties. Formally,

\mathcal{W}_{i,\mathrm{ties}}=\cap_{j\in[k]\setminus\{i\}}\left\{X_{i}\geq X_{% j}\right\}.

(3)

Similarly, we define $\mathcal{W}_{i,\mathrm{strict}}$ to be the event in which opinion “ $i$ ” is the most sampled opinion, without ties. Formally,

\mathcal{W}_{i,\mathrm{strict}}=\cap_{j\in[k]\setminus\{i\}}\left\{X_{i}>X_{j}% \right\}.

(4)

Finally, for $i\neq j\in[k]$ , we define $\mathcal{W}_{i,j}=\mathcal{W}_{i}\cup\mathcal{W}_{j}$ , $\mathcal{W}_{i,j,\mathrm{strict}}=\mathcal{W}_{i,\mathrm{strict}}\cup\mathcal{% W}_{j,\text{strict}}$ , and $\mathcal{W}_{i,j,\mathrm{ties}}=\mathcal{W}_{i,\mathrm{ties}}\cup\mathcal{W}_{% j,\text{ties}}$ .

Clearly, $\mathcal{W}_{i,\mathrm{strict}}\subseteq\mathcal{W}_{i}\subseteq\mathcal{W}_{i% ,\mathrm{ties}}$ and $\mathcal{W}_{i,j,\mathrm{strict}}\subseteq\mathcal{W}_{i,j}\subseteq\mathcal{W% }_{i,j,\mathrm{ties}}$ . The idea is to perform a conditional analysis: if we condition on $\mathcal{W}_{1,2}$ , then we already know that either $X_{1}$ or $X_{2}$ win at the next round. However, we do not quite get that the conditional random variable $(X_{1}\mid\mathcal{W}_{1,2})$ is a binomial one. At the same time, it is not true that $(X_{2}\mid\mathcal{W}_{1,2})$ counts the number of failures of $(X_{1}\mid\mathcal{W}_{1,2})$ . The whole Section 4.1 presents the analytical effort to demonstrate that, in practice, we can get some result that is similar to Lemma 3. The section is quite technical and involved, with ad-hoc results that are needed for this adaptation. We stress that we actually use, as conditional event, the event $\mathcal{W}_{1,2,\mathrm{strict}}$ . The reason being that (as we show in Lemma 7)

		$\displaystyle\Pr\left(\mathcal{W}_{1}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{% strict}}\right)-\Pr\left(\mathcal{W}_{2}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{% strict}}\right)$
	$\displaystyle=\$	$\displaystyle\Pr\left(X_{1}>X_{2}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{strict}}% \right)-\Pr\left(X_{2}>X_{1}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{strict}}% \right),$		(5)

while the equality is not true if instead of $\mathcal{W}_{1,2,\mathrm{strict}}$ we use $\mathcal{W}_{1,2}$ , because we need to take ties into account. Observe that Equation 5 gives a formula that resembles the one that is estimated in Lemma 3.

In Section 4.2, we estimate the probability of $\mathcal{W}_{1,2,\mathrm{strict}}$ with respect to $\mathcal{W}_{1,2}$ and $\mathcal{W}_{1,2,\mathrm{ties}}$ . In order to do that, we classify the $k$ opinions in two classes: the strong and the rare opinions. The strong ones are opinions whose probabilities are comparable to $p_{1}$ , say, $p_{i}>p_{1}/2$ . The rare ones are all the others. Through concentration arguments, we can show that rare opinions disappear in one round w.h.p., and it is easy to see, by symmetry arguments, that $\mathcal{W}_{1}=\Omega(p_{1})$ . The main result that we obtain in Section 4.2 is that, basically, under the hypothesis that $hp_{1}\geq C\log n$ for some large enough constant $C>0$ , $p_{1}/8\leq\Pr\left(\mathcal{W}_{1,\mathrm{ties}}\right)/8\leq\Pr(\mathcal{W}_% {1,\mathrm{strict}})\leq\Pr\left(\mathcal{W}_{1}\right)\leq\Pr\left(\mathcal{W% }_{1,\mathrm{ties}}\right)$ , that is, ties do not matter that much. Notice that the latter fact is, again, trivial if $hp_{1}=\Omega(\max\{p_{1}^{2}n,\log^{2}n\}\gg O(\log n)$ , while we require a smaller (and, possibly, much smaller) $h$ . Also, observe that $\Pr(\mathcal{W}_{1,\mathrm{strict}})\geq p_{1}/8$ implies that $\Pr(\mathcal{W}_{1,2,\mathrm{strict}})=\Omega(p_{1}+p_{2})$ . Computing directly the probability of ties in the multinomial is hard, but we resolve this issue mapping injectively events in which opinion 1 wins with a tie to an event in which opinion 1 wins without a tie. We show that this mapping preserves probabilities up to small constants, therefore we can conclude that events with ties (where opinion 1 wins) have probability weights that are comparable to events without ties (where opinion 1 wins). See Lemma 13 for more details (and note that no initial bias is required for the result of Lemma 13 to hold).

Finally, in Section 4.3 we show how to combine all the ingredients that we have proved in Sections 4.1 and 4.2 to obtain the round-by-round expected growth of the bias and the final statement on plurality consensus. As for the round-by-round expected growth of the bias, we just use the law of total probability which implies that

	$\displaystyle\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)$	(6)
$\displaystyle\geq\$	$\displaystyle\Pr\left(\mathcal{W}_{1,2,\mathrm{strict}}\right)\left[\Pr\left(% \mathcal{W}_{1}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{strict}}\right)-\Pr\left(% \mathcal{W}_{2}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{strict}}\right)\right]$
$\displaystyle=\$	$\displaystyle\Pr\left(\mathcal{W}_{1,2,\mathrm{strict}}\right)\left[\Pr\left(X% _{1}>X_{2}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{strict}}\right)-\Pr\left(X_{2}>% X_{1}\ \middle\|\ \mathcal{W}_{1,2,\mathrm{strict}}\right)\right],$	(7)

and then use Equation 1. Given the expected growth of the bias, we make use of the Bernstein’s inequality (Lemma 24 in Appendix B) to show its round-by-round increase in high probability, and we need to make sure that all other surrounding conditions of the growth are still satisfied in order to iterate in high probability each round.

3.2 Final discussion and open questions

In this paper we present an analysis of the $h$ -majority dynamics when $hp_{1}\geq C\log n$ for a large enough constant $C$ . Interestingly, Theorem 2 answers (partially) a long-standing open question on mathoverflow [30] which basically asks how to estimate $\Pr(\mathcal{W}_{1})-\Pr(\mathcal{W}_{2})$ when $h=o(1/\delta^{2})$ , that is, when $\delta=o(\sqrt{1/h})$ . With Lemma 16 we answer to this question under the hypothesis that $hp_{1}\geq C\log n$ , and we also show that the bias increases w.h.p. each round as long as $C^{\prime}\sqrt{p_{1}/n}\leq\delta=o(\sqrt{p_{1}/\log n})$ for some large enough constant $C^{\prime}>0$ .

We also remark that $\delta\sim\sqrt{p_{1}/n}$ is the smallest bias that was ever required in the literature on opinion dynamics (see Section 1.2). Indeed, in the proof of Theorem 17, we show that the standard deviation of the bias at the next round is no smaller than some function $\Theta(\sqrt{p_{1}/n})$ , while its expected growth is at least a multiplicative factor $\sim\sqrt{\log n}$ . It remains open to understand whether the bias can be reduced for $h\sim k\log n$ , which would imply that the growth of the bias is higher than a multiplicative factor $\sim\sqrt{\log n}$ : however, we conjecture that this growth is optimal in the regime $h\sim k\log n$ .

The main open question here is whether the lower bound $\Omega(k/h^{2})$ given by [5] is tight or not. To understand this, one has to improve the assumption on $hp_{1}$ and analyze especially the case where $hp_{1}\ll 1$ . We argue more in the next subsection.

We remark that our work does not deal with perfectly-balanced configurations: one simply has to show that in short time the system reaches a configuration with the bias specified in the hypotheses of Theorem 2. We leave the analysis of the symmetry-breaking phase for future research.

On the multinomial distribution

Our analysis offers a corollary for the multinomial distribution that is interesting per-se, and is just a reformulation of Lemma 13.

Corollary 5.

Consider a multinomial random variable $(X_{1},\ldots,X_{k})$ where each $X_{i}\sim\mathrm{Binomial}(h,p_{i})$ , with $p_{1}\geq\ldots\geq p_{k}$ . If $hp_{1}\geq C\log n$ for a large enough constant $C>0$ , then $\Pr(\cap_{i=2}^{k}\{X_{1}>X_{i}\})\geq cp_{1}$ for some small enough constant $c>0$ .

We do not know how the statement of Corollary 5 changes when $hp_{1}$ decreases, which remains an open question. This is linked to the generalized birthday paradox, which asks as follows: If $p_{1}=\ldots=p_{k}$ , what is the probability that there exists $i\in[k]$ such that $X_{i}>1$ ? In fact, if $hp^{2}_{1}=\Theta(1)$ , we are in the standard birthday paradox: with constant probability, we have that $\max_{i\in[k]}\left\{X_{i}\right\}=1$ , which means that whenever opinion 1 is the maximum, the number of ties is $h$ with constant probability. In contrast, Corollary 5 suggests that when $hp_{1}=\Omega(\log n)$ the number of ties that involve opinion 1 when it is the maximum is small.

Since the number of ties among the maxima increases when $hp_{1}$ gets smaller, we conjecture that, for $hp_{1}\ll 1$ , $\Pr(\mathcal{W}_{1,\mathrm{strict}})=o(p_{1})$ , implying that our approach, that entirely builds around the fact that $\Pr(\mathcal{W}_{1,\mathrm{strict}})\sim\Pr(\mathcal{W}_{1})$ , cannot apply, and new ideas are required.

Another open question is to quantify the number of ties among the maxima, in general, and especially when opinion $1$ is in the maxima for a generic configuration where $p_{1}\geq\ldots\geq p_{k}$ . This would help bridging the two cases $hp_{1}\ll 1$ and $hp_{1}\gg 1$ .

4 Analysis

In this section we present the proof of Theorem 2, following the overview presented in Section 3. Most of the technical proofs either are deferred to Appendix A or can be found in the full version [17].

4.1 Conditional analysis of the expected behavior of the process

Due to space limitations, the interested reader can find the proofs in the full version [17].

Lemma 3 shows a good lower bound of $\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)$ for the $h$ -majority when the number of opinion is 2. In order to use this result for $k$ opinions, our plan is to condition on the event that either opinion 1 or 2 wins, without ties. Let $x=\max_{i\geq 3}\left\{X_{i}\right\}$ the mode of the sample among the opinions $\left\{3,\ldots,k\right\}$ . This event can be written as $\max\left\{X_{1},X_{2}\right\}>x$ . In the following lemma, we adapt the result of Lemma 3 to work under the additional conditioning event that opinion 1 or 2 is sampled more than $x$ times.

Lemma 6.

For any integer $m>0$ , let $Y_{1}\sim\mathrm{Binomial}(m,q)$ and $Y_{2}=m-Y_{1}\sim\mathrm{Binomial}(m,1-q)$ , with $q>1/2$ . We have, for any $m/2<x\leq m$ ,

\Pr\left(Y_{1}>Y_{2}\mid\max(Y_{1},Y_{2})>x\right)-\Pr\left(Y_{2}>Y_{1}\mid% \max(Y_{1},Y_{2})>x\right)\geq C_{1}\cdot\min(\sqrt{m}\cdot(2q-1),1),

for some constant $C_{1}>0$ .

The next lemma shows that the expected bias at the next round, i.e. $\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)$ , is equal to $\Pr\left(X_{1}>X_{2}\right)-\Pr\left(X_{2}>X_{1}\right)$ , conditioning on the event either opinion 1 or 2 wins, without ties. The last quantity is easier to estimate, because we don’t have to handle possible ties. This is to get a formula that resembles that of Lemma 3.

Lemma 7.

Recall the Definition 4 of the event $\mathcal{W}_{1,2,\mathrm{strict}}$ . We have

		$\displaystyle\ \Pr\left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}% \right)-\Pr\left(\mathcal{W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)$
	$\displaystyle=$	$\displaystyle\ \Pr\left(X_{1}>X_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right% )-\Pr\left(X_{2}>X_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)$

We remark that the statement of Lemma 7 does not hold if we condition on the event $\mathcal{W}_{1,2}$ , which includes possible ties. In fact, the event $\left\{\mathcal{W}_{1},\mathcal{W}_{1,2}\right\}$ contains sub-events for which opinion 1 ties with many other opinions, and we could not find a simple close expression for the probability of these sub-events.

To use Lemma 6 after conditioning on the fact either opinion 1 or 2 wins, we need to estimate the number of total samples of opinion 1 and 2. Since, at the end, we assume $hp_{1}\geq\log n$ , we can apply the Chernoff bound (Lemma 22 in Appendix B) to show that $X_{1}+X_{2}\geq(p_{1}+p_{2})/2$ w.h.p., but we must ensure that this remains true under the aforementioned conditioning. The following lemma shows this is indeed the case. Despite the intuitive nature of the statement (the fact either opinion 1 or 2 wins is positively correlated with the absolute value of $X_{1}$ and $X_{2}$ ) we need to use an involved coupling argument to formally prove it.

Lemma 8.

It holds that

\Pr\left(X_{1}+X_{2}\geq h\cdot(p_{1}+p_{2})/2\mid\mathcal{W}_{1,2,\mathrm{% strict}}\right)\geq\Pr\left(X_{1}+X_{2}\geq h\cdot(p_{1}+p_{2})/2\right).

4.2 Estimating the probability of the conditional event

In this section our goal is to estimate a lower bound for $\Pr\left(\mathcal{W}_{1,2,\mathrm{strict}}\right)$ . More specifically, we show that $\Pr\left(\mathcal{W}_{1,2,\mathrm{strict}}\right)\geq C(p_{1}+p_{2})$ for some constant $C>0$ . As we already argued after Lemma 7, it is important to exclude ties in the event we condition on.

The next definitions introduce terms to refer to opinions that will disappear w.h.p. at the next round, the weak opinions, and their counter part, the strong opinions.

Definition 9 (Rare opinions).

Denote with $\mathcal{R}_{x}:=\left\{i\in[k]:p_{i}\leq x\cdot p_{1}\right\}$ be the set of the $x$ -rare opinions, for $0<x<1$ .

Definition 10 (Strong opinions).

Denote with $\mathcal{S}:=\left\{i\in[k]:p_{i}>\frac{1}{2}p_{1}\right\}$ be the set of the strong opinions, for $0<x<1$ .

Note that the set of the strong opinions and the set of $1/2$ -rare opinions are complementary.

In the next lemma we show that w.h.p. all weak opinions will be sampled less than the opinion 1, and therefore, they will disappear at the next round. The proof is just an application of Chernoff bounds (Lemma 22 in Appendix B) and we defer it to Section A.1.

Lemma 11.

Let $C_{2},C_{3}$ be two constants s.t. $0<C_{2}<1$ and $C_{3}>2$ . If $hp_{1}>C_{4}\log n$ , with $C_{4}=\left(3\,C_{3}\frac{1}{1-C_{2}}\right)^{2}$ , then

\Pr\left(\cap_{i\in\mathcal{R}_{C_{2}}}\left\{X_{1}>X_{i}\right\}\right)\geq 1% -\frac{1}{n^{C_{3}-2}}.

To bound $\Pr\left(\mathcal{W}_{1,\text{strict}}\right)$ , we plan to first show that there exists a constant $C$ s.t. $\mathcal{W}_{1,\mathrm{ties}}\geq Cp_{1}$ , and, therefore, show that $\Pr\left(\mathcal{W}_{1,\text{strict}}\right)\geq C\Pr(\mathcal{W}_{1,\mathrm{% ties}})$ , for some other constant $C$ . Hence, in the next lemma we show that $\Pr(\mathcal{W}_{1})\geq Cp_{1}$ which, in turn, implies that $\Pr(\mathcal{W}_{1,\mathrm{ties}})\geq Cp_{1}$ . The idea is to use Lemma 11 to show that only strong opinion compete for the win and in the worst case they have all same probability to win without ties. The thesis follows after showing that the number of strong opinions is at most $2/p_{1}$ , and that $\sum_{i\in\mathcal{S}}\Pr\left(\mathcal{W}_{i}\right)\geq 1$ . Again, the proof is deferred to Section A.1.

Lemma 12.

Let $C_{4}=\left(18\right)^{2}$ . If $p_{1}h\geq C_{4}\log n$ , then

\Pr(\mathcal{W}_{1})\geq\frac{1}{3}p_{1}.

The next Lemma plays a key role in avoiding the computation of the probability of ties. Assuming that $hp_{1}=O(\log n)$ , we can map each realization of the multinomial in which opinion 1 wins with ties to a realization in which opinion 1 wins without ties. We will show that these two realizations have the same probability up to a constant. Therefore, we can conclude that tie events have a comparable weight to events without ties. We present its proof in Section A.1 as we believe this is an interesting result per-se, which also proves Corollary 5 in Section 3.2.

Lemma 13.

Let $hp_{1}>C_{4}\log n$ for $C_{4}=18^{2}$ . It holds that

\Pr\left(\mathcal{W}_{1,\text{strict}}\right)\geq\frac{1}{6}\Pr\left(\mathcal{% W}_{1,\mathrm{ties}}\right)\geq\frac{1}{18}p_{1}.

The goal of this section was to show that $\Pr\left(\mathcal{W}_{1,2,\text{strict}}\right)\geq C\left(p_{1}+p_{2}\right)$ for some constant $C>0$ . This can be easily obtained by applying Lemma 13, because $p_{1}+p_{2}\leq 2p_{1}$ and $\mathcal{W}_{1,\text{strict}}\subseteq\mathcal{W}_{1,2,\text{strict}}$ .

Corollary 14.

Let $hp_{1}>C_{4}\log n$ for $C_{4}=18^{2}$ . It holds that

\Pr\left(\mathcal{W}_{1,2,\text{strict}}\right)\geq\frac{1}{36}\left(p_{1}+p_{% 2}\right).

4.3 Putting everything together

In this section we can finally put together all the results to give a lower bound to $\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{j}\right)$ and to use it to prove Theorem 2. Next lemma is the statement that is “equivalent in spirit” to Lemma 3 but for many opinions, conditional on $\mathcal{W}_{1,2,\mathrm{strict}}$ . Its proof involves a mix of the previous results and is quite intricate.

Lemma 15.

Let $p_{1}\,h\geq C_{4}\,\log n$ , with $C_{4}=18^{2}$ . We have

\Pr\left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\text{strict}}\right)-\Pr\left(% \mathcal{W}_{2}\mid\mathcal{W}_{1,2,\text{strict}}\right)\geq C\min\left\{% \frac{(p_{1}-p_{2})\sqrt{h}}{\sqrt{2(p_{1}+p_{2})}},1\right\},

for some constant $C>0$ .

Proof of Lemma 15.

Let

M=\{m\in\mathbb{N}:\Pr\left(X_{1}+X_{2}=m\mid\mathcal{W}_{1,2,\mathrm{strict}}% \right)>0\}\cap\{m\geq h\cdot(p_{1}+p_{2})/2\}

and

L_{m}=\{x\in\mathbb{N}:\Pr\left(\max_{j\geq 3}X_{j}=x\mid X_{1}+X_{2}=m,% \mathcal{W}_{1,2,\mathrm{strict}}\right)>0\}.

We have

	$\displaystyle\Pr\left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}% \right)-\Pr\left(\mathcal{W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)$
$\displaystyle\underset{(i)}{=}\$	$\displaystyle\Pr\left(X_{1}>X_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)-% \Pr\left(X_{2}>X_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)$
$\displaystyle\underset{(ii)}{\geq}\$	$\displaystyle\sum_{m\in M}\Pr\left(X_{1}+X_{2}=m\mid\mathcal{W}_{1,2,\mathrm{% strict}}\right)\left[\Pr\left(X_{1}>X_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}% ,X_{1}+X_{2}=m\right)\right.$
	$\displaystyle-\left.\Pr\left(X_{2}>X_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}},% X_{1}+X_{2}=m\right)\right]$
$\displaystyle\underset{(iii)}{=}\$	$\displaystyle\sum_{m\in M}\Pr\left(X_{1}+X_{2}=m\mid\mathcal{W}_{1,2,\mathrm{% strict}}\right)$
	$\displaystyle\cdot\sum_{x\in L_{m}}\Pr\left(\max_{j\geq 3}X_{j}=x\mid X_{1}+X_% {2}=m,\mathcal{W}_{1,2,\mathrm{strict}}\right)$
	$\displaystyle\cdot\left[\Pr\left(X_{1}>X_{2}\mid\mathcal{W}_{1,2,\mathrm{% strict}},X_{1}+X_{2}=m,\max_{j\geq 3}X_{j}=x\right)\right.$
	$\displaystyle-\left.\Pr\left(X_{2}>X_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}},% X_{1}+X_{2}=m,\max_{j\geq 3}X_{j}=x\right)\right]$
$\displaystyle\underset{(iv)}{=}\$	$\displaystyle\sum_{m\in M}\Pr\left(X_{1}+X_{2}=m\mid\mathcal{W}_{1,2,\mathrm{% strict}}\right)$
	$\displaystyle\cdot\sum_{x\in L_{m}}\Pr\left(\max_{j\geq 3}X_{j}=x\mid X_{1}+X_% {2}=m,\mathcal{W}_{1,2,\mathrm{strict}}\right)$
	$\displaystyle\cdot\left[\Pr\left(X_{1}>X_{2}\mid\max\{X_{1},X_{2}\}>x,X_{1}+X_% {2}=m,\max_{j\geq 3}X_{j}=x\right)\right.$
	$\displaystyle-\left.\Pr\left(X_{2}>X_{1}\mid\max\{X_{1},X_{2}\}>x,X_{1}+X_{2}=% m,\max_{j\geq 3}X_{j}=x\right)\right],$	(8)

where in $(i)$ we used Lemma 7, in $(ii),(iii)$ we used the law of total probabilities, and in $(iv)$ we used that, by Definition 4,

		$\displaystyle\ \left(\mathcal{W}_{1,2,\mathrm{strict}},X_{1}+X_{2}=m,\max_{j% \geq 3}X_{j}=x\right)$
	$\displaystyle=$	$\displaystyle\ \left(\max\{X_{1},X_{2}\}>x,X_{1}+X_{2}=m,\max_{j\geq 3}X_{j}=x% \right).$

Conditioning on $\{X_{1}+X_{2}=m\}$ , makes $X_{1},X_{2}$ independent from $X_{3},\ldots,X_{k}$ , and distributed as $Y_{1},Y_{2}$ , where $Y_{1}\sim\mathrm{Binomial}(m,q_{1})$ with $q_{1}=\frac{p_{1}}{p_{1}+p_{2}}$ and $Y_{2}=m-Y_{1}$ . We obtain, by Section 4.3

		$\displaystyle\Pr\left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}% \right)-\Pr\left(\mathcal{W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)$
	$\displaystyle\geq\$	$\displaystyle\sum_{m\in M}\Pr\left(X_{1}+X_{2}=m\mid\mathcal{W}_{1,2,\mathrm{% strict}}\right)$
		$\displaystyle\cdot\sum_{x\in L_{m}}\Pr\left(\max_{j\geq 3}X_{j}=x\mid X_{1}+X_% {2}=m,\mathcal{W}_{1,2,\mathrm{strict}}\right)$
		$\displaystyle\cdot\left[\Pr\left(Y_{1}>Y_{2}\mid\max\{Y_{1},Y_{2}\}\geq x% \right)-\Pr\left(Y_{2}>Y_{1}\mid\max\{Y_{1},Y_{2}\}\geq x\right)\right]$
	$\displaystyle\underset{(i)}{\geq}\$	$\displaystyle\sum_{m\in M}\Pr\left(X_{1}+X_{2}=m\mid\mathcal{W}_{1,2,\mathrm{% strict}}\right)$
		$\displaystyle\cdot\sum_{x\in L_{m}}\Pr\left(\max_{j\geq 3}X_{j}=x\mid X_{1}+X_% {2}=m,\mathcal{W}_{1,2,\mathrm{strict}}\right)$
		$\displaystyle\cdot C_{1}\cdot\min\left(\sqrt{m}\left(\frac{\delta_{2}}{p_{1}+p% _{2}}\right),1\right)$
	$\displaystyle\underset{(ii)}{=}\$	$\displaystyle\sum_{m\in M}\Pr\left(X_{1}+X_{2}=m\mid\mathcal{W}_{1,2,\mathrm{% strict}}\right)\cdot C_{1}\cdot\min\left(\sqrt{m}\left(\frac{\delta_{2}}{p_{1}% +p_{2}}\right),1\right)$
	$\displaystyle\underset{(iii)}{\geq}\$	$\displaystyle\Pr\left(X_{1}+X_{2}\geq h\cdot(p_{1}+p_{2})/2\mid\mathcal{W}_{1,% 2,\mathrm{strict}}\right)\cdot C_{1}\cdot\min\left(\left(\frac{\delta_{2}\sqrt% {h}}{\sqrt{2(p_{1}+p_{2})}}\right),1\right)$
	$\displaystyle\underset{(iv)}{\geq}\$	$\displaystyle C_{1}\left(1-\exp\left(-\frac{1}{8}h(p_{1}+p_{2})\right)\right)% \cdot\min\left(\left(\frac{\delta_{2}\sqrt{h}}{\sqrt{2(p_{1}+p_{2})}}\right),1\right)$
	$\displaystyle\underset{(v)}{\geq}\$	$\displaystyle C_{1}\left(1-\frac{1}{n^{2}}\right)\cdot\min\left(\left(\frac{% \delta_{2}\sqrt{h}}{\sqrt{2(p_{1}+p_{2})}}\right),1\right)$
	$\displaystyle\geq\$	$\displaystyle C\min\left(\left(\frac{\delta_{2}\sqrt{h}}{\sqrt{2(p_{1}+p_{2})}% }\right),1\right),$

where in $(i)$ we used Lemma 6, in $(ii)$ we used the law of total probabilities, in $(iii)$ we used that by definition of $M$ , $m\geq h(p_{1}+p_{2})/2$ , in $(iv)$ we used Lemma 8 and the multiplicative Chernoff bound (Lemma 22 in Appendix B), and in $(v)$ we used that $hp_{1}\geq 16\log n$ . This concludes the proof of Lemma 15. $\hfill\blacktriangleleft$

In the next lemma, we finally remove the conditional event $\mathcal{W}_{1,2,\mathrm{strict}}$ and bound $\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)$ from below. We need to use Lemmas 13 and 15, but its proof consists in just mixing in the “right way” previous results, hence we defer it to Section A.2. From now on, we denote the difference $p_{1}-p_{j}$ by $\delta(j)$ .

Lemma 16.

Let $p_{1}\,h\geq C_{4}\,\log n$ , with $C_{4}=18^{2}$ . If $\delta(j)\leq\sqrt{\frac{2(p_{1}+p_{2})}{h}}$ , then there exists a constant $C_{5}>0$ s.t.

\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{j}\right)\geq C_{5}\left% (\delta(j)\sqrt{\frac{h}{p_{1}+p_{2}}}\right)\Pr\left(\mathcal{W}_{1}\right).

Instead, if $\delta(j)\geq\sqrt{\frac{2(p_{1}+p_{2})}{h}}$ , there exists a constant $0<C_{6}<1$ s.t.

\Pr\left(\mathcal{W}_{1}\right)\geq\frac{1}{1-C_{6}}\Pr\left(\mathcal{W}_{j}% \right).

Given a configuration $\left(p_{1},\dots,p_{k}\right)$ , we denote by $p_{j}^{\prime}$ the probability associated to opinion $j$ at the next round. Fix an opinion $j\neq 1$ . Let $\delta(j)^{\prime}$ be the bias between opinion 1 and opinion j at the next round, i.e. $p_{1}^{\prime}-p_{j}^{\prime}$ .

Before proceeding in the analysis presentation, let us comment Lemma 16. Note that $\Pr\left(\mathcal{W}_{j}\right)$ is the expected value of $p^{\prime}_{j}$ . In the case the bias between opinion 1 and opinion $j$ is more than $\sqrt{\frac{2(p_{1}+p_{2})}{h}}$ , at the next round we have $p^{\prime}_{1}\geq(1+C)p^{\prime}_{j}$ in expectation, for some constant $C>0$ . In the case the bias is smaller than $\sqrt{\frac{2(p_{1}+p_{2})}{h}}$ , by the fact $h=\Omega\left(p_{1}\log n\right)$ and $\Pr\left(\mathcal{W}_{1}\right)=\Omega\left(p_{1}+p_{2}\right)$ , Lemma 16 implies that at the next round the expected bias grows of a $\Omega\left(\log n\right)$ factor. Thanks to standard concentration bounds (Chernoff Bound and Bernstein Inequality) we show that w.h.p. the new bias is sufficiently close to its expectation.

Now we all have all ingredients to prove Theorem 2. Next theorem is just a reformulation of Theorem 2.

Theorem 17.

Consider an initial configuration $\left(p_{1},\dots,p_{k}\right)$ s.t. $p_{1}\geq C_{7}\frac{\log n}{n}$ , and $p_{1}-p_{j}\geq C_{8}\sqrt{\frac{p_{1}}{n}}$ for all $j\geq 2$ . Then the $h$ -majority dynamics with $hp_{1}>C_{4}\log n$ converges in time $O(\log n)$ to opinion 1, w.h.p., for some constants $C_{4},C_{7},C_{8}>0$ .

The proof relies on first quantifying the increase in the bias between the first opinion and other opinions after one round. Then it iterates the same reasoning until consensus (for the complete proof, see the full version [17]). For the first point, we use concentration bounds on the results obtained in Lemma 16. In particular, we distinguish three sub-cases based on the size of the bias between two opinions. For the second point, we need to show that the initial hypotheses are still satisfied after one round to ensure that we can iterate.

In the next lemma, we show that if $p_{1}\geq(1+C)p_{j}$ for some constant $C>0$ , opinion $j$ disappears at the next round, by simply applying the Chernoff bound.

Lemma 18 (Opinion $j$ -disappear at the next round).

Let $hp_{1}\geq C_{4}\log n$ . If $\delta(j)\geq\left(1-\frac{1}{1+C_{6}}\right)p_{1}$ for the constant $C_{6}$ defined in Lemma 16, with probability at least $1-\frac{1}{n^{4}}$ opinion $j$ will disappear at the next round

The next Lemma shows that if the bias is $\Omega\left(\sqrt{p_{1}/h}\right)$ , then the new bias will fall within the hypothesis of Lemma 18 in one step. Therefore, we conclude that, in two steps, opinion $j$ will disappear if the bias is large enough. The proof relies on the results obtained in Lemma 16, combined with the Chernoff bound.

Lemma 19 (Opinion $j$ -disappear in two rounds).

Let $hp_{1}\geq C_{4}\log n$ . If $p_{1}\geq C_{7}\frac{\log n}{n}$ and $\sqrt{\frac{2(p_{1}+p_{2})}{h}}\leq\delta(j)\leq\left(1-\frac{1}{1+C_{6}}% \right)p_{1}$ for the constant $C_{6}>0$ defined in Lemma 16 and for a constant $C_{7}>0$ , we have that

\Pr\left(\delta(j)^{\prime}\geq\left(1-\frac{1}{1+C_{6}}\right)p_{1}^{\prime}% \right)\geq 1-\frac{2}{n^{4}}.

The next Lemma addresses the minimum possible bias. We show that, until we fall back into the hypotheses of Lemmas 18 and 19, the bias grows exponentially. The proof is more complex than the previous two lemmas because it requires bounding the second moment of the bias to apply the Bernstein inequality.

Lemma 20 (Bias exponential growth).

Let $hp_{1}\geq C_{4}\log n$ . If $p_{1}\geq C_{7}\frac{\log n}{n}$ and $C_{8}\sqrt{\frac{p_{1}}{n}}\leq\delta(j)\leq\sqrt{\frac{2(p_{1}+p_{2})}{h}}$ for the constant $C_{6}>0$ defined in Lemma 16 and for some constants $C_{7},C_{8}>0$ , we have that

\Pr\left(\delta(j)^{\prime}\geq e\,\delta(j)\right)\geq 1-\frac{1}{n^{4}}

The next Lemma ensures that the hypothesis of Theorem 2 on the bias is always satisfied so that we can iterate Lemma 20.

Lemma 21 (The new bias satisfies the initial hypothesis).

Let $\delta(j)\geq\sqrt{\frac{p_{1}}{n}}$ , and a constant $C_{8}>0$ . For $n$ large enough we have

\Pr\left(\delta(j)^{\prime}\geq C\sqrt{\frac{p_{1}^{\prime}}{n}}\right)\geq 1-% \frac{2}{n^{4}}.

References

[1] Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. Fast convergence of k-opinion undecided state dynamics in the population protocol model. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 13–23. ACM, 2023. doi:10.1145/3583668.3594589.
[2] Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Comput., 21(2):87–102, 2008. doi:10.1007/S00446-008-0059-Z.
[3] Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. Fast consensus via the unconstrained undecided state dynamics. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 3417–3429. SIAM, 2022. doi:10.1137/1.9781611977073.135.
[4] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. Plurality consensus in the gossip model. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 371–390. SIAM, 2015. doi:10.1137/1.9781611973730.27.
[5] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293–306, August 2017. doi:10.1007/s00446-016-0289-4.
[6] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 620–635. SIAM, 2016. doi:10.1137/1.9781611974331.CH46.
[7] Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. The minority dynamics and the power of synchronicity. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4155–4176. SIAM, 2024. doi:10.1137/1.9781611977912.144.
[8] Petra Berenbrink, Felix Biermeier, and Christopher Hahn. Undecided state dynamics with stubborn agents. CoRR, abs/2406.07335, 2024. doi:10.48550/arXiv.2406.07335.
[9] Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or comply?: On breaking symmetry in consensus. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 335–344. ACM, 2017. doi:10.1145/3087801.3087817.
[10] Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the hierarchy of distributed majority protocols. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors, 26th International Conference on Principles of Distributed Systems, OPODIS 2022, December 13-15, 2022, Brussels, Belgium, volume 253 of LIPIcs, pages 23:1–23:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.OPODIS.2022.23.
[11] Andrea Clementi, Francesco D’Amore, George Giakkoupis, and Emanuele Natale. Search via Parallel Lévy Walks on Z2. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 81–91. ACM, 2021. doi:10.1145/3465084.3467921.
[12] Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A tight analysis of the parallel undecided-state dynamics with two colors. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 28:1–28:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPICS.MFCS.2018.28.
[13] Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Asynchronous 3-majority dynamics with many opinions. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4095–4131. SIAM, 2025. doi:10.1137/1.9781611978322.140.
[14] Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Phase transition of the k-majority dynamics in biased communication models. Distributed Comput., 36(2):107–135, 2023. doi:10.1007/S00446-023-00444-2.
[15] Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a non-linear opinion dynamics with noisy interactions - (extended abstract). In Andréa Werneck Richa and Christian Scheideler, editors, Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings, volume 12156 of Lecture Notes in Computer Science, pages 255–272. Springer, 2020. doi:10.1007/978-3-030-54921-3_15.
[16] Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a nonlinear opinion dynamics with noisy interactions. Swarm Intell., 16(4):261–304, 2022. doi:10.1007/S11721-022-00217-W.
[17] Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, and Emanuele Natale. On the $h$ -majority dynamics with many opinions, 2025. doi:10.48550/arXiv.2506.20218.
[18] Francesco D’Amore and Isabella Ziccardi. Phase transition of the 3-majority dynamics with uniform communication noise. In Merav Parter, editor, Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27-29, 2022, Proceedings, volume 13298 of Lecture Notes in Computer Science, pages 98–115. Springer, 2022. doi:10.1007/978-3-031-09993-9_6.
[19] Francesco D’Amore and Isabella Ziccardi. Phase transition of the 3-majority opinion dynamics with noisy interactions. Theor. Comput. Sci., 1028:115030, 2025. doi:10.1016/J.TCS.2024.115030.
[20] Niccolò D’Archivio and Robin Vacus. On the limits of information spread by memory-less agents. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing, DISC 2024, October 28 to November 1, 2024, Madrid, Spain, volume 319 of LIPIcs, pages 18:1–18:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.DISC.2024.18.
[21] Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. URL: http://www.cambridge.org/gb/knowledge/isbn/item2327542/.
[22] Ofer Feinerman, Bernhard Haeupler, and Amos Korman. Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014, pages 114–123. ACM, 2014. doi:10.1145/2611462.2611469.
[23] Ofer Feinerman and Amos Korman. The ANTS problem. Distributed Comput., 30(3):149–168, 2017. doi:10.1007/S00446-016-0285-8.
[24] Pierre Fraigniaud, Amos Korman, and Yoav Rodeh. Parallel exhaustive search without coordination. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 312–323. ACM, 2016. doi:10.1145/2897518.2897541.
[25] Pierre Fraigniaud and Emanuele Natale. Noisy rumor spreading and plurality consensus. Distributed Computing, 32(4):257–276, 2019. doi:10.1007/S00446-018-0335-5.
[26] Matthias Függer, Thomas Nowak, and Joel Rybicki. Majority consensus thresholds in competitive lotka-volterra populations. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024, pages 76–86. ACM, 2024. doi:10.1145/3662158.3662823.
[27] Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 305–313. ACM, 2018. URL: https://dl.acm.org/citation.cfm?id=3212738.
[28] George Giakkoupis, Volker Turau, and Isabella Ziccardi. Self-stabilizing MIS computation in the beeping model. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing, DISC 2024, October 28 to November 1, 2024, Madrid, Spain, volume 319 of LIPIcs, pages 28:1–28:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.DISC.2024.28.
[29] George Giakkoupis and Isabella Ziccardi. Distributed self-stabilizing MIS with few states and weak communication. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 310–320. ACM, 2023. doi:10.1145/3583668.3594581.
[30] Immanuel Weihnachten (https://mathoverflow.net/users/23351/immanuel weihnachten). Lower bound on the probability of guessing the mode in a small multinomial sample. MathOverflow. URL:https://mathoverflow.net/q/210018 (version: 2015-06-24). arXiv:https://mathoverflow.net/q/210018.
[31] Amos Korman and Robin Vacus. Distributed alignment processes with samples of group average. IEEE Trans. Control. Netw. Syst., 10(2):960–971, 2023. doi:10.1109/TCNS.2022.3212640.
[32] Hicham Lesfari, Frédéric Giroire, and Stéphane Pérennes. Biased majority opinion dynamics: Exploiting graph k-domination. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 377–383. ijcai.org, 2022. doi:10.24963/IJCAI.2022/54.
[33] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603.
[34] Nobutaka Shimizu and Takeharu Shiraga. 3-majority and 2-choices with many opinions. CoRR, abs/2503.02426, 2025. To appear at PODC 2025. doi:10.48550/arXiv.2503.02426.
[35] Robin Vacus and Isabella Ziccardi. Minimalist Leader Election Under Weak Communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 406–416, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733559.

Appendix A Missing proofs

A.1 Omitted proofs from Section 4.2

Proof of Lemma 11.

Define the event $\mathcal{C}_{j}=\left\{\absolutevalue{X_{j}-hp_{j}}<\sqrt{3C_{3}\,hp_{j}\log n% }\right\}$ and $\mathcal{C}=\cap_{j=1}^{k}\mathcal{C}_{j}$ . The event $\mathcal{C}_{j}$ can be rewritten as

\mathcal{C}_{j}=\left\{X_{j}\in\left(hp_{j}-\sqrt{3C_{3}\,hp_{j}\log n},hp_{j}% +\sqrt{3C_{3}\,hp_{j}\log n}\right)\right\}.

(9)

For $i\in\mathcal{R}$ , we have

	$\displaystyle\ hp_{1}-\sqrt{3\,C_{3}\,hp_{1}\log n}-\left(hp_{i}+\sqrt{3\,C_{3% }\,hp_{i}\log n}\right)$
$\displaystyle\geq$	$\displaystyle\ \left(1-C_{2}\right)hp_{1}-\sqrt{3\,C_{3}\,hp_{1}\log n}$	$\displaystyle\left(i\in\mathcal{R}\implies hp_{i}\leq hC_{2}\cdot p_{1}\right)$
$\displaystyle>$	$\displaystyle\ 0,$

by taking $hp_{1}>C_{4}\log n$ , with $C_{4}=\left(3\,C_{3}\frac{1}{1-C_{2}}\right)^{2}$ . This fact, together with Equation 9, implies that $\mathcal{C}\subset\left\{\cap_{i\in\mathcal{R}_{C_{2}}}\left\{X_{1}>X_{i}% \right\}\right\}$ , and therefore $\Pr\left(\cap_{i\in\mathcal{R}_{C_{2}}}\left\{X_{1}>X_{i}\right\}\right)\geq% \Pr\left(\mathcal{C}\right)$ . By the multiplicative Chernoff bound we have

	$\displaystyle\Pr\left(C_{j}\right)$	$\displaystyle=\Pr\left(\absolutevalue{X_{j}-hp_{j}}<\sqrt{3C_{3}\,hp_{j}\log n% }\right)$
		$\displaystyle=1-\Pr\left(\absolutevalue{X_{j}-hp_{j}}\geq\sqrt{3C_{3}\,hp_{j}% \log n}\right)$
		$\displaystyle\geq 1-2\exp\left(-\frac{3C_{3}\log n}{3}\right)$
		$\displaystyle=1-\frac{2}{n^{C_{3}}},$

and by the union bound and by the fact the number of opinion $k\leq n$ , we obtain

\Pr\left(\cap_{i\in\mathcal{R}}\left\{X_{1}>X_{i}\right\}\right)\geq\Pr\left(% \mathcal{C}\right)\geq 1-\frac{2k}{n^{C_{3}}}\geq 1-\frac{1}{n^{C_{3}-2}},

concluding the proof of Lemma 11. $\hfill\blacktriangleleft$

Proof of Lemma 12.

Recall $\mathcal{S}:=\left\{i\in[k]:p_{i}>\frac{1}{2}p_{1}\right\}$ be the set of the strong opinions. By definition of $\mathcal{S}$ we have

\displaystyle 1\geq\sum_{j\in\mathcal{S}}p_{j}>\frac{\absolutevalue{\mathcal{S% }}\,p_{1}}{2},

and therefore we have

\absolutevalue{\mathcal{S}}\leq\frac{2}{p_{1}}.

(10)

Recall that $\mathcal{R}_{1/2}:=\left\{i\in[k]:p_{i}\leq\frac{1}{2}p_{1}\right\}$ is the set of the $1/2$ -rare opinions. If $i\in\mathcal{R}_{1/2}$ , we have that

\Pr\left(\mathcal{W}_{i}\mid\cap_{\ell\in\mathcal{R}_{1/2}}\left\{X_{1}>X_{% \ell}\right\}\right)=0.

By this fact, and by noticing that an opinion is either strong or $1/2$ -rare,

1=\Pr\left(\bigcup_{j\in\mathcal{S}}\mathcal{W}_{j}\mid\cap_{\ell\in\mathcal{R% }_{1/2}}\left\{X_{1}>X_{\ell}\right\}\right)\leq\sum_{j\in\mathcal{S}}\Pr\left% (\mathcal{W}_{j}\mid\cap_{\ell\in\mathcal{R}_{1/2}}\left\{X_{1}>X_{\ell}\right% \}\right).

(11)

Since $X_{j}\sim\mathrm{Binomial}(p_{j},h)$ and $p_{1}\geq p_{j}$ , for all $j\in[k]$ , we have that $X_{1}$ stochastically dominates $X_{j}$ for all $j\geq 2$ . This fact remains true also conditioning on the event $\left\{\cap_{\ell\in\mathcal{R}_{1/2}}\left\{X_{1}>X_{\ell}\right\}\right\}$ . Therefore, we have

\Pr\left(\mathcal{W}_{1}\mid\cap_{\ell\in\mathcal{R}_{1/2}}\left\{X_{1}>X_{% \ell}\right\}\right)\geq\Pr\left(\mathcal{W}_{j}\mid\cap_{\ell\in\mathcal{R}_{% 1/2}}\left\{X_{1}>X_{\ell}\right\}\right),

for all $j\in\mathcal{S},j\geq 2$ . This fact, together with Equation 11, implies

\absolutevalue{\mathcal{S}}\cdot\Pr\left(\mathcal{W}_{1}\mid\cap_{\ell\in% \mathcal{R}_{1/2}}\left\{X_{1}>X_{\ell}\right\}\right)\geq\sum_{j\in\mathcal{S% }}\Pr\left(\mathcal{W}_{j}\mid\cap_{\ell\in\mathcal{R}_{1/2}}\left\{X_{1}>X_{% \ell}\right\}\right)\geq 1,

and, by using Equation 10, we obtain

\Pr\left(\mathcal{W}_{1}\mid\cap_{\ell\in\mathcal{R}_{1/2}}\left\{X_{1}>X_{% \ell}\right\}\right)\geq\frac{1}{\absolutevalue{\mathcal{S}}}\geq\frac{p_{1}}{% 2}.

We can conclude the proof of Lemma 12 noticing that, by Lemma 11 with $C_{3}=3$ and $C_{2}=1/2$ (which implies $C_{4}=(18)^{2}$ , we have

\Pr(\mathcal{W}_{1})\geq\Pr\left(\cap_{\ell\in\mathcal{R}_{1/2}}\left\{X_{1}>X% _{\ell}\right\}\right)\cdot\Pr\left(\mathcal{W}_{1}\mid\cap_{\ell\in\mathcal{R% }_{1/2}}\left\{X_{1}>X_{\ell}\right\}\right)\geq\left(1-\frac{1}{n}\right)% \frac{p_{1}}{2}\geq\frac{p_{1}}{3},

for $n$ large enough. $\hfill\blacktriangleleft$

Proof of Lemma 13.

Define the event $\mathcal{C}_{j}=\left\{\absolutevalue{X_{j}-hp_{j}}<\sqrt{9hp_{j}\log n}\right\}$ and $\mathcal{C}=\cap_{j\geq 1}\mathcal{C}_{j}$ . By the multiplicative Chernoff bound (Lemma 22 in Appendix B), we obtain

	$\displaystyle\Pr\left(\mathcal{C}_{j}\right)$	$\displaystyle=\Pr\left(\absolutevalue{X_{j}-hp_{j}}<\sqrt{9\,hp_{j}\log n}\right)$
		$\displaystyle=1-\Pr\left(\absolutevalue{X_{j}-hp_{j}}\geq\sqrt{9\,hp_{j}\log n% }\right)$
		$\displaystyle\geq 1-2\exp\left(-\frac{9\log n}{3}\right)$
		$\displaystyle=1-\frac{2}{n^{3}}.$

Moreover, by the union bound and by the fact $k\leq n$ , we have, for $n$ large enough,

\Pr\left(\mathcal{C}\right)\geq 1-\frac{2k}{n^{3}}\geq 1-\frac{1}{n}.

(12)

Recall $\mathcal{S}:=\left\{i\in[k]:p_{i}>\frac{1}{2}p_{1}\right\}$ be the set of the strong opinions. We first note that

$\displaystyle\mathcal{C}$	$\displaystyle\subseteq\bigcap_{j\in\mathcal{S}}\left\{X_{j}>hp_{j}-\sqrt{9hp_{% j}\log n}\right\}$
	$\displaystyle\subseteq\bigcap_{j\in\mathcal{S}}\left\{X_{j}>\frac{1}{2}hp_{1}-% \sqrt{9hp_{1}\log n}\right\}$	$\displaystyle\left(p_{i}>\frac{1}{2}p_{1},p_{i}\leq p_{1},\text{ for all }i\in% \mathcal{S}\right)$
	$\displaystyle\subseteq\cap_{j\in\mathcal{S}}\left\{X_{j}>0\right\}.$	$\displaystyle\left(hp_{1}>36\log n\right)$	(13)

Let us denote a particular realization of a multinomial in the following way.

\mathcal{X}(x_{1},\dots,x_{k})=\left\{X_{1}=x_{1},\dots,X_{k}=x_{k}\right\}.

We define the event $\mathcal{X}(x_{1},\dots,x_{k})$ a 1-tie if $x_{1}\geq x_{i}$ for all $i\geq 1$ and there exists a $j\neq 1$ s.t. $x_{j}=x_{1}$ . In other words, opinion 1 is the most sampled, together with at least another opinion. We denote the set of 1-tie as $\mathcal{T}_{1}$ .

We map a 1-tie to an event in which the opinion 1 gets one extra sample which is stolen from the least scoring strong opinion. Formally, if $\mathcal{X}(x_{1},\dots,x_{k})\in\mathcal{T}_{1}$ and $j=\max\left\{i:X_{i}=\min_{r\in\mathcal{S}}\left\{X_{r}\right\}\right\}$ , we define:

f:\,\mathcal{X}(x_{1},\dots,x_{k})\mapsto\mathcal{X}(x_{1}+1,\dots,x_{j-1},x_{% j}-1,x_{j+1},\dots,x_{k}).

The map is well-defined if and only if $x_{j}>0$ . If $\mathcal{X}(x_{1},\dots,x_{k})\in\mathcal{C}$ , by Equation 13, we have $\mathcal{X}(x_{1},\dots,x_{k})\in\cap_{j\in\mathcal{S}}\left\{X_{j}>0\right\}$ , and, since $j\in\mathcal{S}$ by definition, we obtain that $x_{j}>0$ . Therefore, $f$ is well-defined on $\mathcal{C}$ .

Moreover, the map is injective. Using the probability mass function of the multinomial distribution, we compute the following:

\frac{\Pr\left(f\left(\mathcal{X}(x_{1},\dots,x_{k})\right)\right)}{\Pr\left(% \mathcal{X}(x_{1},\dots,x_{k})\right)}=\frac{x_{j}}{x_{1}+1}\cdot\frac{p_{1}}{% p_{j}}\geq\frac{x_{j}}{x_{1}+1},

where we used that $p_{1}\geq p_{j}$ . Therefore we obtain

	$\displaystyle\sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T}_{1},\mathcal{X% }\in\mathcal{C}\end{subarray}}\Pr\left(f\left(\mathcal{X}(x_{1},\dots,x_{k})% \right)\right)$
$\displaystyle\geq\$	$\displaystyle\sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T}_{1},\mathcal{X% }\in\mathcal{C}\end{subarray}}\frac{x_{j}}{x_{1}+1}\Pr\left(\left(\mathcal{X}(% x_{1},\dots,x_{k})\right)\right)$
$\displaystyle\geq\$	$\displaystyle\frac{hp_{j}-\sqrt{9hp_{j}\log n}}{1+hp_{1}+\sqrt{9hp_{1}\log n}}% \cdot\sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T}_{1},\mathcal{X}\in% \mathcal{C}\end{subarray}}\Pr\left(\mathcal{X}(x_{1},\dots,x_{k})\right)$	$\displaystyle\left(\text{by definition of }\mathcal{C}\right)$
$\displaystyle\geq\$	$\displaystyle\frac{\frac{1}{2}hp_{1}-\sqrt{9hp_{1}\log n}}{1+hp_{1}+\sqrt{9hp_% {1}\log n}}\cdot\sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T}_{1},% \mathcal{X}\in\mathcal{C}\end{subarray}}\Pr\left(\mathcal{X}(x_{1},\dots,x_{k}% )\right)$	$\displaystyle\left(p_{i}>\frac{1}{2}p_{1},p_{i}\leq p_{1},\text{ for }i\in% \mathcal{S}\right)$
$\displaystyle=\$	$\displaystyle\frac{\frac{1}{2}\sqrt{\frac{hp_{1}}{9\log n}}-1}{\sqrt{\frac{hp_% {1}}{9\log n}}+2}\cdot\sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T}_{1},% \mathcal{X}\in\mathcal{C}\end{subarray}}\Pr\left(\mathcal{X}(x_{1},\dots,x_{k}% )\right)$
$\displaystyle\geq\$	$\displaystyle\frac{1}{4}\cdot\sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T% }_{1},\mathcal{X}\in\mathcal{C}\end{subarray}}\Pr\left(\mathcal{X}(x_{1},\dots% ,x_{k})\right),$		(14)

where the last inequality holds because $x\mapsto\frac{\frac{1}{2}x-1}{x+2}\text{ is increasing and }hp_{1}\geq 18^{2}\log n$ . Recall Definition 4. Since $\mathcal{T}_{1}=\mathcal{W}_{1,\text{ties}}\setminus\mathcal{W}_{1,\text{% strict}}$ and $f\left(\mathcal{T}_{1}\cap\mathcal{C}\right)\subseteq\mathcal{W}_{1}$ , we can write

	$\displaystyle\ \Pr\left(\mathcal{W}_{1,\text{ties}},\mathcal{C}\right)$
$\displaystyle=$	$\displaystyle\ \Pr\left(\mathcal{W}_{1,\text{strict}},\mathcal{C}\right)+\Pr% \left(\mathcal{W}_{1,\text{ties}}\setminus\mathcal{W}_{1,\text{strict}},% \mathcal{C}\right)$
$\displaystyle\geq$	$\displaystyle\ \sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T}_{1},\mathcal% {X}\in\mathcal{C}\end{subarray}}\Pr\left(f\left(\mathcal{X}(x_{1},\dots,x_{k})% \right)\right)+\sum_{\begin{subarray}{c}\mathcal{X}\in\mathcal{T}_{1},\mathcal% {X}\in\mathcal{C}\end{subarray}}\Pr\left(\mathcal{X}(x_{1},\dots,x_{k})\right)$
$\displaystyle\geq$	$\displaystyle\ \left(1+\frac{1}{4}\right)\sum_{\begin{subarray}{c}\mathcal{X}% \in\mathcal{T}_{1},\mathcal{X}\in\mathcal{C}\end{subarray}}\Pr\left(\mathcal{X% }(x_{1},\dots,x_{k})\right)$	$\displaystyle\left(\text{by \lx@cref{creftypecap~refnum}{eq:relationship_proba% bilities_1_ties}}\right)$
$\displaystyle=$	$\displaystyle\ \left(1+\frac{1}{4}\right)\Pr\left(\mathcal{W}_{1,\text{ties}}% \setminus\mathcal{W}_{1,\text{strict}},\mathcal{C}\right).$

Hence,

\Pr\left(\mathcal{W}_{1,\text{ties}}\setminus\mathcal{W}_{1,\text{strict}},% \mathcal{C}\right)\leq\frac{4}{5}\cdot\Pr\left(\mathcal{W}_{1,\text{ties}},% \mathcal{C}\right),

and

		$\displaystyle\ \Pr\left(\mathcal{W}_{1,\text{strict}}\right)\geq\Pr\left(% \mathcal{W}_{1,\text{strict}},\mathcal{C}\right)=\Pr\left(\mathcal{W}_{1,\text% {ties}},\mathcal{C}\right)-\Pr\left(\mathcal{W}_{1,\text{ties}}\setminus% \mathcal{W}_{1,\text{strict}},\mathcal{C}\right)$
	$\displaystyle\geq$	$\displaystyle\ \frac{1}{5}\cdot\Pr\left(\mathcal{W}_{1,\text{ties}},\mathcal{C% }\right)$
	$\displaystyle=$	$\displaystyle\ \frac{1}{5}\left(\mathcal{W}_{1,\mathrm{ties}}+\Pr\left(% \mathcal{C}\right)-\Pr\left(\mathcal{W}_{1,\text{ties}}\cup\mathcal{C}\right)% \right)\qquad\left(\text{by the inclusion\textendash exclusion princ.}\right)$
	$\displaystyle\geq$	$\displaystyle\ \frac{1}{5}\left(\mathcal{W}_{1,\mathrm{ties}}+\Pr\left(% \mathcal{C}\right)-1\right)\qquad\qquad\qquad\qquad\,\left(\Pr\left(\mathcal{W% }_{1,\text{ties}}\cup\mathcal{C}\right)\leq 1\right)$
	$\displaystyle\geq$	$\displaystyle\ \frac{1}{5}\left(\mathcal{W}_{1,\mathrm{ties}}-\frac{1}{n}% \right)\qquad\qquad\qquad\qquad\qquad\quad\left(\text{by \lx@cref{% creftypecap~refnum}{eq:concentration_strong_opinions}}\right)$
	$\displaystyle\geq$	$\displaystyle\ \frac{1}{6}\mathcal{W}_{1,\mathrm{ties}}\geq\frac{1}{18}p_{1}$

for $n$ large enough. This concludes the proof of Lemma 13. $\hfill\blacktriangleleft$

Proof of Corollary 14.

By Lemmas 13 and 12, we obtain

\Pr\left(\mathcal{W}_{1,2,\mathrm{strict}}\right)\geq\Pr\left(\mathcal{W}_{1,% \text{strict}}\right)\geq\frac{1}{6}\Pr(\mathcal{W}_{1,\mathrm{ties}})\geq% \frac{1}{18}\,p_{1}=\frac{1}{36}\left(p_{1}+p_{1}\right)\geq\frac{1}{36}(p_{1}% +p_{2}).

This concludes the proof of Corollary 14. $\hfill\blacktriangleleft$

A.2 Omitted proofs from Section 4.3

Proof of Lemma 16.

Since $p_{2}\geq p_{j}$ for all $j\geq 2$ , we have that $\Pr\left(\mathcal{W}_{j}\right)\leq\Pr\left(\mathcal{W}_{2}\right)$ , and, therefore,

\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)\implies\Pr% \left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{j}\right),

and,

\Pr\left(\mathcal{W}_{1}\right)\geq\frac{1}{1-C_{6}}\Pr\left(\mathcal{W}_{2}% \right)\implies\Pr\left(\mathcal{W}_{1}\right)\geq\frac{1}{1-C_{6}}\Pr\left(% \mathcal{W}_{j}\right).

Hence, we will focus on the proof statement for $j=2$ .

Consider the case $\delta(2)\leq\sqrt{\frac{2(p_{1}+p_{2})}{h}}$ , that, in particular, implies that

\min\left(\left(\frac{\delta(2)\sqrt{h}}{\sqrt{2(p_{1}+p_{2})}}\right),1\right% )=\left(\frac{\delta(2)\sqrt{h}}{\sqrt{2(p_{1}+p_{2})}}\right).

We have

	$\displaystyle\Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)$
$\displaystyle\geq$	$\displaystyle\ \Pr\left(\mathcal{W}_{1,2,\mathrm{strict}}\right)\cdot\left[\Pr% \left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)-\Pr\left(% \mathcal{W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)\right]$
$\displaystyle\geq$	$\displaystyle\ \Pr\left(\mathcal{W}_{1,\mathrm{strict}}\right)\cdot\left[\Pr% \left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)-\Pr\left(% \mathcal{W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)\right]$	$\displaystyle\left(\mathcal{W}_{1,\mathrm{strict}}\subseteq\mathcal{W}_{1,2,% \mathrm{strict}}\right)$
$\displaystyle\geq$	$\displaystyle\ \frac{1}{6}\Pr\left(\mathcal{W}_{1,\mathrm{ties}}\right)\cdot% \left[\Pr\left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)-\Pr% \left(\mathcal{W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)\right]$	$\displaystyle\left(\text{by \lx@cref{creftypecap~refnum}{lemma:relationship_ti% es_without_ties}}\right)$
$\displaystyle\geq$	$\displaystyle\ \frac{1}{6}\Pr\left(\mathcal{W}_{1}\right)\cdot\left[\Pr\left(% \mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)-\Pr\left(\mathcal{% W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)\right]$	$\displaystyle\left(\mathcal{W}_{1}\subseteq\mathcal{W}_{1,\mathrm{ties}}\right)$
$\displaystyle\geq$	$\displaystyle\ \frac{C}{6}\,\Pr\left(\mathcal{W}_{1}\right)\delta(2)\sqrt{% \frac{h}{p_{1}+p_{2}}}$	$\displaystyle\left(\text{by \lx@cref{creftypecap~refnum}{lemma:lemma_ema_with_% conditioning}}\right)$

Setting $C_{5}=\frac{C}{6}$ , we conclude the proof of the first statement of Lemma 16. Now consider the case $\delta\geq\sqrt{\frac{2(p_{1}+p_{2})}{h}}$ , that implies that $\left(\frac{\delta\sqrt{h}}{\sqrt{2(p_{1}+p_{2})}}\right)=1$ .

	$\displaystyle\ \Pr\left(\mathcal{W}_{1}\right)-\Pr\left(\mathcal{W}_{2}\right)$
$\displaystyle\geq$	$\displaystyle\ \Pr\left(\mathcal{W}_{1,2,\mathrm{strict}}\right)\cdot\left[\Pr% \left(\mathcal{W}_{1}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)-\Pr\left(% \mathcal{W}_{2}\mid\mathcal{W}_{1,2,\mathrm{strict}}\right)\right]$
$\displaystyle\geq$	$\displaystyle\ \Pr\left(\mathcal{W}_{1,2,\text{strict}}\right)\cdot C$	(by Lemma 15)
$\displaystyle\geq$	$\displaystyle\ \Pr\left(\mathcal{W}_{1,\text{strict}}\right)\cdot C$	$\displaystyle\left(\mathcal{W}_{1,\mathrm{strict}}\subseteq\mathcal{W}_{1,% \mathrm{strict}}\right)$
$\displaystyle\geq$	$\displaystyle\ \frac{C}{6}\Pr\left(\mathcal{W}_{1,\mathrm{ties}}\right)$	(by Lemma 13)
$\displaystyle\geq$	$\displaystyle\ \frac{C}{6}\Pr\left(\mathcal{W}_{1}\right)$	$\displaystyle\left(\mathcal{W}_{1}\subseteq\mathcal{W}_{1,\mathrm{ties}}\right)$
$\displaystyle\geq$	$\displaystyle\ C_{6}\Pr\left(\mathcal{W}_{1}\right),$

if we set $0<C_{6}=\min\left(\frac{1}{2},\frac{C}{6}\right)<1$ . This concludes the proof of Lemma 16. $\hfill\blacktriangleleft$

Appendix B Tools

Lemma 22 (Multiplicative forms of Chernoff bounds [21]).

Let $X_{1},\ldots,X_{n}$ be independent binary random variables. Let $X=\sum_{i=1}^{n}X_{i}$ and $\mu=\operatorname*{\mathbb{E}}[X]$ . Then:

1.

For any $\delta\in(0,1)$ and any $\mu\leq\mu_{+}\leq n$ , it holds that

$\Pr(X\geq(1+\delta)\mu_{+})\leq\exp(-\delta^{2}\mu_{+}/3).$
2.

For any $\delta\in(0,1)$ and any $0\leq\mu_{-}\leq\mu$ , it holds that

$\Pr(X\leq(1-\delta)\mu_{-})\leq\exp(-\delta^{2}\mu_{-}/2).$

Lemma 23 (Hoeffding bounds [33]).

Let $a<b)$ be two constants, and $X_{1},\ldots,X_{n}$ be independent binary random variables such that $\Pr(a\leq X_{i}\leq b)=1$ for all $i\in[n]$ . Let $X=\sum_{i=1}^{n}X_{i}$ and $\mu=\operatorname*{\mathbb{E}}[X]$ . Then:

1.

For any $t>0$ and any $\mu\leq\mu_{+}$ , it holds that

$\Pr(X\geq\mu_{+}+t)\leq\exp(-\frac{2t^{2}}{n(b-a)^{2}}).$
2.

For any $t>0$ and any $0\leq\mu_{-}\leq\mu$ , it holds that

$\Pr(X\leq\mu_{-}-t)\leq\exp(-\frac{2t^{2}}{n(b-a)^{2}}).$

Lemma 24 (Bernstein Inequality [21]).

Let $X_{1},X_{2},\dots,X_{n}$ be i.i.d. random variables such that $\absolutevalue{X_{i}-\mathbb{E}[X_{i}]}\leq C$ and $\absolutevalue{\operatorname*{\mathbb{E}}[X_{i}]}\leq C$ for some $C>0$ . Define the sum of centered variables $S_{n}=\sum_{i=1}^{n}(X_{i}-\mathbb{E}[X_{i}]).$ Then, for all $t>0$ ,

\Pr(\absolutevalue{S_{n}}\geq t)\leq 2\exp\left(-\frac{t^{2}}{2n\mathrm{Var}(X% _{1})+\frac{2Ct}{3}}\right).

[bib.bib1] [1] Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. Fast convergence of k-opinion undecided state dynamics in the population protocol model. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 13–23. ACM, 2023. doi:10.1145/3583668.3594589.

[bib.bib2] [2] Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Comput., 21(2):87–102, 2008. doi:10.1007/S00446-008-0059-Z.

[bib.bib3] [3] Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. Fast consensus via the unconstrained undecided state dynamics. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 3417–3429. SIAM, 2022. doi:10.1137/1.9781611977073.135.

[bib.bib4] [4] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. Plurality consensus in the gossip model. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 371–390. SIAM, 2015. doi:10.1137/1.9781611973730.27.

[bib.bib5] [5] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293–306, August 2017. doi:10.1007/s00446-016-0289-4.

[bib.bib6] [6] Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 620–635. SIAM, 2016. doi:10.1137/1.9781611974331.CH46.

[bib.bib7] [7] Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. The minority dynamics and the power of synchronicity. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4155–4176. SIAM, 2024. doi:10.1137/1.9781611977912.144.

[bib.bib8] [8] Petra Berenbrink, Felix Biermeier, and Christopher Hahn. Undecided state dynamics with stubborn agents. CoRR, abs/2406.07335, 2024. doi:10.48550/arXiv.2406.07335.

[bib.bib9] [9] Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or comply?: On breaking symmetry in consensus. In Elad Michael Schiller and Alexander A. Schwarzmann, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages 335–344. ACM, 2017. doi:10.1145/3087801.3087817.

[bib.bib10] [10] Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the hierarchy of distributed majority protocols. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors, 26th International Conference on Principles of Distributed Systems, OPODIS 2022, December 13-15, 2022, Brussels, Belgium, volume 253 of LIPIcs, pages 23:1–23:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPICS.OPODIS.2022.23.

[bib.bib11] [11] Andrea Clementi, Francesco D’Amore, George Giakkoupis, and Emanuele Natale. Search via Parallel Lévy Walks on Z2. In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 81–91. ACM, 2021. doi:10.1145/3465084.3467921.

[bib.bib12] [12] Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A tight analysis of the parallel undecided-state dynamics with two colors. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 28:1–28:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPICS.MFCS.2018.28.

[bib.bib13] [13] Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Asynchronous 3-majority dynamics with many opinions. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4095–4131. SIAM, 2025. doi:10.1137/1.9781611978322.140.

[bib.bib14] [14] Emilio Cruciani, Hlafo Alfie Mimun, Matteo Quattropani, and Sara Rizzo. Phase transition of the k-majority dynamics in biased communication models. Distributed Comput., 36(2):107–135, 2023. doi:10.1007/S00446-023-00444-2.

[bib.bib15] [15] Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a non-linear opinion dynamics with noisy interactions - (extended abstract). In Andréa Werneck Richa and Christian Scheideler, editors, Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Proceedings, volume 12156 of Lecture Notes in Computer Science, pages 255–272. Springer, 2020. doi:10.1007/978-3-030-54921-3_15.

[bib.bib16] [16] Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a nonlinear opinion dynamics with noisy interactions. Swarm Intell., 16(4):261–304, 2022. doi:10.1007/S11721-022-00217-W.

[bib.bib17] [17] Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, and Emanuele Natale. On the $h$ -majority dynamics with many opinions, 2025. doi:10.48550/arXiv.2506.20218.

[bib.bib18] [18] Francesco D’Amore and Isabella Ziccardi. Phase transition of the 3-majority dynamics with uniform communication noise. In Merav Parter, editor, Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Paderborn, Germany, June 27-29, 2022, Proceedings, volume 13298 of Lecture Notes in Computer Science, pages 98–115. Springer, 2022. doi:10.1007/978-3-031-09993-9_6.

[bib.bib19] [19] Francesco D’Amore and Isabella Ziccardi. Phase transition of the 3-majority opinion dynamics with noisy interactions. Theor. Comput. Sci., 1028:115030, 2025. doi:10.1016/J.TCS.2024.115030.

[bib.bib20] [20] Niccolò D’Archivio and Robin Vacus. On the limits of information spread by memory-less agents. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing, DISC 2024, October 28 to November 1, 2024, Madrid, Spain, volume 319 of LIPIcs, pages 18:1–18:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.DISC.2024.18.

[bib.bib21] [21] Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009. URL: http://www.cambridge.org/gb/knowledge/isbn/item2327542/.

[bib.bib22] [22] Ofer Feinerman, Bernhard Haeupler, and Amos Korman. Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication. In Magnús M. Halldórsson and Shlomi Dolev, editors, ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014, pages 114–123. ACM, 2014. doi:10.1145/2611462.2611469.

[bib.bib23] [23] Ofer Feinerman and Amos Korman. The ANTS problem. Distributed Comput., 30(3):149–168, 2017. doi:10.1007/S00446-016-0285-8.

[bib.bib24] [24] Pierre Fraigniaud, Amos Korman, and Yoav Rodeh. Parallel exhaustive search without coordination. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 312–323. ACM, 2016. doi:10.1145/2897518.2897541.

[bib.bib25] [25] Pierre Fraigniaud and Emanuele Natale. Noisy rumor spreading and plurality consensus. Distributed Computing, 32(4):257–276, 2019. doi:10.1007/S00446-018-0335-5.

[bib.bib26] [26] Matthias Függer, Thomas Nowak, and Joel Rybicki. Majority consensus thresholds in competitive lotka-volterra populations. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024, pages 76–86. ACM, 2024. doi:10.1145/3662158.3662823.

[bib.bib27] [27] Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dynamics. In Calvin Newport and Idit Keidar, editors, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, July 23-27, 2018, pages 305–313. ACM, 2018. URL: https://dl.acm.org/citation.cfm?id=3212738.

[bib.bib28] [28] George Giakkoupis, Volker Turau, and Isabella Ziccardi. Self-stabilizing MIS computation in the beeping model. In Dan Alistarh, editor, 38th International Symposium on Distributed Computing, DISC 2024, October 28 to November 1, 2024, Madrid, Spain, volume 319 of LIPIcs, pages 28:1–28:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.DISC.2024.28.

[bib.bib29] [29] George Giakkoupis and Isabella Ziccardi. Distributed self-stabilizing MIS with few states and weak communication. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 310–320. ACM, 2023. doi:10.1145/3583668.3594581.

[bib.bib30] [30] Immanuel Weihnachten (https://mathoverflow.net/users/23351/immanuel weihnachten). Lower bound on the probability of guessing the mode in a small multinomial sample. MathOverflow. URL:https://mathoverflow.net/q/210018 (version: 2015-06-24). arXiv:https://mathoverflow.net/q/210018.

[bib.bib31] [31] Amos Korman and Robin Vacus. Distributed alignment processes with samples of group average. IEEE Trans. Control. Netw. Syst., 10(2):960–971, 2023. doi:10.1109/TCNS.2022.3212640.

[bib.bib32] [32] Hicham Lesfari, Frédéric Giroire, and Stéphane Pérennes. Biased majority opinion dynamics: Exploiting graph k-domination. In Luc De Raedt, editor, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 377–383. ijcai.org, 2022. doi:10.24963/IJCAI.2022/54.

[bib.bib33] [33] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603.

[bib.bib34] [34] Nobutaka Shimizu and Takeharu Shiraga. 3-majority and 2-choices with many opinions. CoRR, abs/2503.02426, 2025. To appear at PODC 2025. doi:10.48550/arXiv.2503.02426.

[bib.bib35] [35] Robin Vacus and Isabella Ziccardi. Minimalist Leader Election Under Weak Communication. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 406–416, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733559.

$\displaystyle\operatorname*{\mathbb{E}}[\delta_{t+1}\mid\mathbf{c}_{t}]$	$\displaystyle\geq\operatorname*{\mathbb{E}}\left[\max_{i\in[k]}\min_{j\neq i}% \left\{\Pr(\mathcal{W}_{i}^{(t+1)})-\Pr(\mathcal{W}_{j}^{(t+1)})\right\}\ % \middle\|\ \mathbf{c}_{t}\right]$
	$\displaystyle\geq\operatorname*{\mathbb{E}}\left[\min_{j\neq 1}\left\{\Pr(% \mathcal{W}_{1}^{(t+1)})-\Pr(\mathcal{W}_{j}^{(t+1)})\right\}\ \middle\|\ % \mathbf{c}_{t}\right]$
	$\displaystyle\geq\operatorname*{\mathbb{E}}\left[\Pr(\mathcal{W}_{1}^{(t+1)})-% \Pr(\mathcal{W}_{2}^{(t+1)})\ \middle\|\ \mathbf{c}_{t}\right].$	(1)

On the 𝒉-Majority Dynamics with Many Opinions

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

1.1 Our contribution

Theorem 1.

Case 1: 𝒌=𝑶⁢(𝒏/𝐥𝐨𝐠⁡𝒏).

Case 2: 𝒌=𝝎⁢(𝒏/𝐥𝐨𝐠⁡𝒏).

Observations

1.2 Previous results

Synchronous setting

Asynchronous setting

On the 𝒉-majority dynamics

Other related works

2 Preliminaries

Theorem 2.

3 Overview of our analysis and technical challenges

Trivial case: very large 𝒉

3.1 Our approach

Lemma 3 (Lemma 9 in [25]).

Definition 4 (Winning events).

3.2 Final discussion and open questions

On the multinomial distribution

Corollary 5.

4 Analysis

4.1 Conditional analysis of the expected behavior of the process

Lemma 6.

Lemma 7.

Lemma 8.

4.2 Estimating the probability of the conditional event

Definition 9 (Rare opinions).

Definition 10 (Strong opinions).

Lemma 11.

Lemma 12.

Lemma 13.

Corollary 14.

4.3 Putting everything together

Lemma 15.

Proof of Lemma 15.

Lemma 16.

Theorem 17.

Lemma 18 (Opinion j-disappear at the next round).

Lemma 19 (Opinion j-disappear in two rounds).

Lemma 20 (Bias exponential growth).

Lemma 21 (The new bias satisfies the initial hypothesis).

References

Appendix A Missing proofs

A.1 Omitted proofs from Section 4.2

Proof of Lemma 11.

Proof of Lemma 12.

Proof of Lemma 13.

Proof of Corollary 14.

A.2 Omitted proofs from Section 4.3

Proof of Lemma 16.

Appendix B Tools

Lemma 22 (Multiplicative forms of Chernoff bounds [21]).

Lemma 23 (Hoeffding bounds [33]).

Lemma 24 (Bernstein Inequality [21]).

On the $𝒉$ -Majority Dynamics with Many Opinions

Case 1: $k=O(n/\log n)$ .

Case 2: $k=\omega(n/\log n)$ .

On the $𝒉$ -majority dynamics

Trivial case: very large $𝒉$

Lemma 18 (Opinion $j$ -disappear at the next round).

Lemma 19 (Opinion $j$ -disappear in two rounds).