# On the h-majority dynamics with many opinions

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

► To cite this version:

Francesco d'Amore, Niccolò d'Archivio, George Giakkoupis, Emanuele Natale. On the h-majority dynamics with many opinions. 39th International Symposium on Distributed Computing (DISC 2025), European Association for Theoretical Computer Science (EATCS), Oct 2025, Berlin, Germany. 10.4230/LIPIcs.DISC.2025.27 . hal-05198643

HAL Id: hal-05198643

https://hal.science/hal-05198643v1

Submitted on 20 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
On the $h$-majority dynamics with many opinions

Francesco d'Amore<fnref n="1" />, Niccolò D'Archivio<fnref n="2" />, George Giakkoupis³, and Emanuele Natale<fnref n="2" />

¹Gran Sasso Science Institute, Italy

²INRIA, COATI, Université Côte d'Azur, France

³INRIA Rennes

**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 $\tilde{\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 \ge 2$.

# 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, \dots, u_h$ (with repetition) which, in turn, send their opinions $x_1, \dots, x_h$ to $v$. Then, $v$ adopts as its own opinion the mode of $\{x_1, \dots, x_h\}$, breaking ties uniformly at random. Let $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^*$ such that $c_0(i^*) > c_0(j)$ for all $j \neq i^*$. Plurality consensus is consensus on the opinion $i^*$, and one wishes to quantify the size of the initial bias that guarantees to obtain plurality consensus with high probability.<fnref n="1" />

## 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} \{c_t(i) - c_t(j)\}$ by $B_t$ and refer to it as the *bias* of the configuration $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<fnref n="2" />. Let $\lambda_1, \lambda_2, \lambda_3$ be large enough positive constants. Assume that opinion 1 is the initial

<footnote n="1">¹The 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.</footnote>

<footnote n="2">²Assuming self-loops is standard in the literature, as it simplifies the analysis without affecting the possible outcomes.</footnote>
plurality opinion with $B_0 \ge \lambda_1 \sqrt{c_0(1)}$ and $c_0(1) \ge \lambda_2 \log n$. If $h \ge \lambda_3 n \log n / 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 $c_0(1) \ge n/k$ since $k \ge n/c_0(1)$. In the following, we say that a configuration is almost-balanced if there exists a subset $I \subseteq [k]$, with $|I| = O(1)$, such that $c_0(i) = \Theta(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 $c_0(1) = \Theta(n/k)$ and $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 $c_0(1)$. In the first sub-case, we fix $c_0(1) = \Theta(n/k)$ such that $c_0(1) \ge \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, $B_0 = \Theta(\sqrt{n/k})$: observe that the configuration is necessarily almost-balanced. If, instead, $c_0(1) = \omega(n/k)$, it is guaranteed that $c_0(1) = \omega(\log n)$. In this case, the configuration cannot be almost-balanced because the required bias is $B_0 = \Theta(\sqrt{c_0(1)}) = \omega(\sqrt{n/k})$. Here, we can pick $h = \Theta(n \log n / c_0(1)) = o(k \log n)$.

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

Since $k = \omega(n/\log n)$ and $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 $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 \ge \lambda_3 n \log n / 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/c_0(1)$ is a “threshold” value, since the two settings $h \ll n/c_0(1)$ and $h \gg n/c_0(1)$ seem to need complementary approaches, which is also why our analysis cannot be adapted to the case $h \ll n/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 / c_0(1)$, one has to show only that there is a time $t > 0$ such that $c_t(1) \ge \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]} \{c_0(i)\} \le 3n/(2k)$. Hence, Theorem 1 shows that the lower bound cannot be pushed to $\tilde{\Omega}(k/h)$ (where the notation $\tilde{\Omega}$ hides polylog($n$) factors), at least as long as $\max_{i \in [k]} \{c_0(i)\} \le 3n/(2k)$ is satisfied, e.g., when $(n - B_0)/(c_0(1) - B_0) \le k \le 3n/(2c_0(1))$, which is always realized when $\max\{(n + (k-1)B_0)/k, \lambda_2 \log n\} \le c_0(1) \le 3n/(2k)$ and $k \le 3n/(2\lambda_2 \log n)$ for any value of $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, 13, 26, 33]. 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*<sub>*h*+1</sub> of the (*h* + 1)-majority dynamics is stochastically dominated by the consensus time *T*<sub>*h*</sub> of the *h*-majority dynamics in the following sense: for each *t* > 0, Pr(*T*<sub>*h*+1</sub> ≤ *t*) ≥ Pr(*T*<sub>*h*</sub> ≤ *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((k^2\sqrt{\log n} + k \log n)(k + \log n))$ rounds to reach consensus that holds w.h.p., provided that $k \le 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)^{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)^{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]} \{c_0(i)\} \le n/k + (n/k)^{1-\epsilon}$ for some $\epsilon > 0$ and $k \le (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]} \{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]} \{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 [26] 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 \le (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, [33] 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, [33] proved that plurality consensus is ensured w.h.p. as long as the initial bias is $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 $B_0 = \omega(\sqrt{c_0(1) \log n})$.<fnref n="3" /> 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 [10, 13]. In [10], the authors consider the binary opinion case and show that the convergence time of the

<footnote n="3">³This 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.</footnote>
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 [33]) 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 $h$-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 asynchronous 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. [33] put the $h$-majority dynamics in the “Open Question” section of their recent work, and wondered whether the techniques developed in [33] 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 $c_{t+1}(i)$ conditional on the whole configuration $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 [5, 6, 13, 26, 33]. 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 $\mathbb{E}[c_{t+1}(1) - c_{t+1}(2) | 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 [17, 18], 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, 31].

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) [1–4, 8, 12, 15, 16] 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 than 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) [11, 19, 21–23, 25, 27, 28, 30, 34].

A special mention goes to [24]. 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 com-
munication. 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.<fnref n="4" /> The protocol designed
by [24] 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 [24] 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), \dots, \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, \dots, y_t \in [n]^k$, it holds that $\Pr(\mathbf{c}_t = y_t | \cap_{i=1}^{t-1}\{\mathbf{c}_i = y_i\}) = \Pr(\mathbf{c}_t = y_t | \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) \ge \mathbf{c}_0(2) \ge \dots \mathbf{c}_0(k)$. At any time $t$, we call plurality opinion at time $t$ the opinion $i$ such that $\mathbf{c}_t(i) \ge \mathbf{c}_t(j)$ for all $j \in [k]$. At any time $t$, the bias of a configuration $\mathbf{c}_t$ is the quantity $B_t = \max_{i \in [k]} \min_{j \ne 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 $B_t = 0$ if there are multiple plurality opinions, while $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), \dots, 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)}, \dots, 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 \ne i} \{p_i^{(t)} - p_j^{(t)}\}$, which is equal to $B_t/n$. When the round we are referring to is clear from the context, we only write $p_1, \dots, p_k$, $\delta$, $\mathbf{X}(v) = (X_1(v), \dots, X_k(v))$, and $\mathcal{W}_i(v)$, omitting the dependency on $t$, to refer to $p_1^{(t)}, \dots, p_k^{(t)}$, $\delta_t$, $\mathbf{X}^{(t)}(v) = (X_1^{(t)}(v), \dots, 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, \dots, 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 $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 \ge \lambda_1\sqrt{p_1/n}$ and $p_1 \ge \lambda_2 \log n/n$. If $hp_1 \ge \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 \ge p_2 \ge \dots \ge p_k$), and use it to get a lower bound on the expect round-by-round growth of the bias

<footnote n="4">⁴Information 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.</footnote>
δ. Notice that, for any given configuration $\mathbf{c}_t$ at time $t$, it holds that

$$ 
\begin{aligned}
\mathbb{E}[\delta_{t+1} | \mathbf{c}_t] &\ge \mathbb{E} \left[ \max_{i \in [k]} \min_{j \ne i} \left\{ \Pr(W_i^{(t+1)}) - \Pr(W_j^{(t+1)}) \right\} \middle| \mathbf{c}_t \right] \\
&\ge \mathbb{E} \left[ \min_{j \ne 1} \left\{ \Pr(W_1^{(t+1)}) - \Pr(W_j^{(t+1)}) \right\} \middle| \mathbf{c}_t \right] \\
&\ge \mathbb{E} \left[ \Pr(W_1^{(t+1)}) - \Pr(W_2^{(t+1)}) \middle| \mathbf{c}_t \right].
\end{aligned} 
\quad (1) $$

Suppose that $p_1^{(t)} = p_2^{(t)} + \delta_t > p_2^{(t)} \ge \dots \ge p_k^{(t)}$. This implies that $\Pr(W_1^{(t+1)} | \mathbf{c}_t) - \Pr(W_i^{(t+1)} | \mathbf{c}_t) \ge \Pr(W_1^{(t+1)} | \mathbf{c}_t) - \Pr(W_2^{(t+1)} | \mathbf{c}_t)$ for all $i \ge 3$ since $p_2^{(t)} \ge p_i^{(t)}$ for $i \ge 3$. If we proved that $\Pr(W_1^{(t+1)} | \mathbf{c}_t) - \Pr(W_2^{(t+1)} | \mathbf{c}_t) \ge \delta_t(1+x)$ for some constant $x > 0$, then we would get $\mathbb{E}[\delta_{t+1} | \mathbf{c}_t] \ge \delta_t(1+x)$, which allows us to concentrate and establish that $\delta_{t+1} \ge \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 28).

Notice that, in general, the probability of $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

$$ \Pr(W_i) = \sum_{m=1}^{k} \frac{1}{m} \sum_{\substack{1 \le i_1 < \dots < i_m \le k: \\ i_j \ne i \forall j \in [m]}} \Pr \left( \bigcap_{j \in [m]} \{X_i = X_{i_j}\} \cap \left( \bigcap_{j \notin \{i, i_1, \dots, i_m\}} \{X_i > X_j\} \right) \right). \quad (2) $$

Using directly Equation (2) to bound $\Pr(W_1) - \Pr(W_2)$ is difficult, and we did not find general estimations in the literature.

**Trivial case: very large h.** If, e.g., h is very large compared to δ, in one round all nodes would adopt the plurality opinion with high probability. The reason follows.

Suppose $p_1 = p_2 + \delta > p_2 \ge \dots \ge p_k$. Then, by the multiplicative Chernoff bound (Lemma 27 in Appendix B) we get that

$$ \Pr(X_1 \ge hp_1(1-x)) \ge 1 - \exp(-\Theta(x^2hp_1)). $$

Similarly,

$$ \Pr(X_i \le hp_2(1+x)) \ge 1 - \exp(-\Theta(x^2hp_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 \ge hp_1(1-x)$ and $X_i \le hp_2(1+x)$ for all $i \ge 2$ hold w.h.p. as long as $h \ge C \log n/(p_1x^2)$ for a large enough constant $C > 0$. If $hp_1(1-x) > hp_2(1+x)$, then $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 \ge C \log n/(p_1x^2)$ and $x < \delta/(p_1 + p_2)$ must hold at the same time, it is sufficient to choose $h \ge C'p_1 \log n/\delta^2$ for a large enough constant $C' > C$. Notice that, since our bias can be such that $\delta \sim \sqrt{p_1/n}$, we must have that $hp_1 > (C'/\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 \ge 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 \ge \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, $\mathbb{E}[X_2] = hp_2 = hp_1 - o(hp_1) = \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 [24, 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, [24, Lemma 9] provides a tight lower bound on the expected bias after one round, i.e., on Pr($W_1$) - Pr($W_2$). Notice that, when k = 2, Pr($W_1$) - Pr($W_2$) = 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 [24]). For any integer $h > 0$, let $X_1 \sim \text{Binomial}(h, p)$ and $X_2 = h - X_1 \sim \text{Binomial}(h, 1-p)$, with $p > 1/2$. Let $\delta = 2p - 1$ be the bias. Then, we have that

$$ \Pr(X_1 > X_2) - \Pr(X_2 > X_1) \geq \sqrt{\frac{2h}{\pi}} \cdot g(\delta, h), $$

where

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

We show how to adapt the proof of [24, Lemma 9] to get Lemma 3 in Appendix A.1. 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}} (1 - \delta^2)^{\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 $W_{i,ties}$ to be the event in which opinion "i" is the most sampled opinion, including possible ties. Formally,

$$ W_{i,ties} = \cap_{j \in [k] \setminus \{i\}} \{X_i \geq X_j\}. \qquad (3) $$

Similarly, we define $W_{i,strict}$ to be the event in which opinion "i" is the most sampled opinion, without ties. Formally,

$$ W_{i,strict} = \cap_{j \in [k] \setminus \{i\}} \{X_i > X_j\}. \qquad (4) $$

Finally, for $i \neq j \in [k]$, we define $W_{i,j} = W_i \cup W_j$, $W_{i,j,strict} = W_{i,strict} \cup W_{j,strict}$, and $W_{i,j,ties} = W_{i,ties} \cup W_{j,ties}$.

Clearly, $W_{i,strict} \subseteq W_i \subseteq W_{i,ties}$ and $W_{i,j,strict} \subseteq W_{i,j} \subseteq W_{i,j,ties}$. The idea is to perform a conditional analysis: if we condition on $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 | W_{1,2})$ is a binomial one. At the same time, it is not true that $(X_2 | W_{1,2})$ counts the number of failures of $(X_1 | 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 $W_{1,2,strict}$. The reason being that (as we show in Lemma 7)

$$ \begin{aligned} & \Pr(W_1 | W_{1,2,strict}) - \Pr(W_2 | W_{1,2,strict}) \\ &= \Pr(X_1 > X_2 | W_{1,2,strict}) - \Pr(X_2 > X_1 | W_{1,2,strict}), \end{aligned} \qquad (5) $$

while the equality is not true if instead of $W_{1,2,strict}$ we use $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 $W_{1,2,strict}$ with respect to $W_{1,2}$ and $W_{1,2,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 $W_1 = \Omega(p_1)$. The main result that we obtain in Section 4.2 is that, basically, under the hypothesis that $hp_1 \ge C \log n$ for some large enough constant $C > 0$, $p_1/8 \le \Pr(W_{1,ties})/8 \le \Pr(W_{1,strict}) \le \Pr(W_1) \le \Pr(W_{1,ties})$, 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(W_{1,strict}) \ge p_1/8$ implies that $\Pr(W_{1,2,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

$$ 
\begin{align} 
& \Pr(W_1) - \Pr(W_2) \tag{6} \\ 
& \ge \Pr(W_{1,2,strict}) [\Pr(W_1 | W_{1,2,strict}) - \Pr(W_2 | W_{1,2,strict})] \nonumber \\ 
& = \Pr(W_{1,2,strict}) [\Pr(X_1 > X_2 | W_{1,2,strict}) - \Pr(X_2 > X_1 | W_{1,2,strict})], \tag{7}
\end{align} 
$$

and then use Equation (1). Given the expected growth of the bias, we make use of the Bernstein's inequality (Lemma 29 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 \ge C \log n$ for a large enough constant $C$. Interestingly, Theorem 2 answers (partially) a long-standing open question on mathoverflow [29] which basically asks how to estimate $\Pr(W_1) - \Pr(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 \ge C \log n$, and we also show that the bias increases w.h.p. each round as long as $C'\sqrt{p_1/n} \le \delta = o(\sqrt{p_1/\log n})$ for some large enough constant $C' > 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, \dots, X_k)$ where each $X_i \sim \text{Binomial}(h, p_i)$, with $p_1 \ge \dots \ge p_k$. If $hp_1 \ge C \log n$ for a large enough constant $C > 0$, then $\Pr(\bigcap_{i=2}^k \{X_1 > X_i\}) \ge 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 = \dots = p_k$, what is the probability that there exists $i \in [k]$ such that $X_i > 1$? In fact, if $hp_1^2 = \Theta(1)$, we are in the standard birthday paradox: with constant probability, we have that $\max_{i \in [k]} \{X_i\} = 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(W_{1,strict}) = o(p_1)$, implying that our approach, that entirely builds around the fact that $\Pr(W_{1,strict}) \sim \Pr(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 \ge \dots \ge 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 are deferred to Appendix A.

## 4.1 Conditional analysis of the expected behavior of the process

Due to space limitations, we defer all the proofs in this section to Appendix A.2.

**Lemma 3** shows a good lower bound of $\Pr(W_1) - \Pr(W_2)$ 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 \ge 3} \{X_i\}$ the mode of the sample among the opinions $\{3, \dots, k\}$. This event can be written as $\max\{X_1, X_2\} > 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 \text{Binomial}(m, q)$ and $Y_2 = m - Y_1 \sim \text{Binomial}(m, 1 - q)$, with $q > 1/2$. We have, for any $m/2 < x \le m$,

$$ \Pr(Y_1 > Y_2 | \max(Y_1, Y_2) > x) - \Pr(Y_2 > Y_1 | \max(Y_1, Y_2) > x) \ge 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(W_1) - \Pr(W_2)$, is equal to $\Pr(X_1 > X_2) - \Pr(X_2 > X_1)$, 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 $W_{1,2,strict}$. We have

$$ \Pr(W_1 | W_{1,2,strict}) - \Pr(W_2 | W_{1,2,strict}) = \Pr(X_1 > X_2 | W_{1,2,strict}) - \Pr(X_2 > X_1 | W_{1,2,strict}) $$

We remark that the statement of Lemma 7 does not hold if we condition on the event $W_{1,2}$, which includes possible ties. In fact, the event $\{W_1, W_{1,2}\}$ 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 \ge \log n$, we can
apply the Chernoff bound (Lemma 27 in Appendix B) to show that $X_1 + X_2 \ge (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(X_1 + X_2 \ge h \cdot (p_1 + p_2)/2 | W_{1,2,\text{strict}}) \ge \Pr(X_1 + X_2 \ge h \cdot (p_1 + p_2)/2). $$

## 4.2 Estimating the probability of the conditional event

In this section our goal is to estimate a lower bound for $\Pr(W_{1,2,\text{strict}})$. More specifically, we show that $\Pr(W_{1,2,\text{strict}}) \ge 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 := \{i \in [k] : p_i \le x \cdot p_1\}$ be the set of the x-rare opinions, for $0 < x < 1$.

**Definition 10 (Strong opinions).** Denote with $\mathcal{S} := \{i \in [k] : p_i > \frac{1}{2}p_1\}$ 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 27 in Appendix B) and we defer it to Appendix A.3.

**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 = (3C_3\frac{1}{1-C_2})^2$, then

$$ \Pr(\cap_{i \in \mathcal{R}_{C_2}} \{X_1 > X_i\}) \ge 1 - \frac{1}{n^{C_3-2}}. $$

To bound $\Pr(W_{1,\text{strict}})$, we plan to first show that there exists a constant $C$ s.t. $W_{1,\text{ties}} \ge Cp_1$, and, therefore, show that $\Pr(W_{1,\text{strict}}) \ge C\Pr(W_{1,\text{ties}})$, for some other constant $C$. Hence, in the next lemma we show that $\Pr(W_1) \ge Cp_1$ which, in turn, implies that $\Pr(W_{1,\text{ties}}) \ge 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(W_i) \ge 1$. Again, the proof is deferred to Appendix A.3.

**Lemma 12.** Let $C_4 = (18)^2$. If $p_1h \ge C_4 \log n$, then

$$ \Pr(W_1) \ge \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 Appendix A.3 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(W_{1,\text{strict}}) \ge \frac{1}{6} \Pr(W_{1,\text{ties}}) \ge \frac{1}{18}p_1. $$

The goal of this section was to show that $\Pr(W_{1,2,\text{strict}}) \ge C(p_1 + p_2)$ for some constant $C > 0$. This can be easily obtained by applying Lemma 13, because $p_1 + p_2 \le 2p_1$ and $W_{1,\text{strict}} \subseteq W_{1,2,\text{strict}}$.

**Corollary 14.** Let $hp_1 > C_4 \log n$ for $C_4 = 18^2$. It holds that

$$ \Pr(W_{1,2,\text{strict}}) \ge \frac{1}{36}(p_1 + p_2). $$
## 4.3 Putting everything together

In this section we can finally put together all the results to give a lower bound to $\Pr(W_1) - \Pr(W_j)$ 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 $W_{1,2,strict}$. Its proof involves a mix of the previous results and is quite intricate.

**Lemma 15.** Let $p_1 h \ge C_4 \log n$, with $C_4 = 18^2$. We have

$$ \Pr(W_1 | W_{1,2,strict}) - \Pr(W_2 | W_{1,2,strict}) \ge 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(X_1 + X_2 = m | W_{1,2,strict}) > 0\} \cap \{m \ge h \cdot (p_1 + p_2)/2\} $$

and

$$ L_m = \{x \in \mathbb{N} : \Pr \left( \max_{j \ge 3} X_j = x \mid X_1 + X_2 = m, W_{1,2,strict} \right) > 0 \}. $$

We have

$$
\begin{align*}
& \Pr(W_1 | W_{1,2,strict}) - \Pr(W_2 | W_{1,2,strict}) \\
&= \Pr(X_1 > X_2 | W_{1,2,strict}) - \Pr(X_2 > X_1 | W_{1,2,strict}) \\
&\overset{(i)}{\ge} \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict}) [\Pr(X_1 > X_2 | W_{1,2,strict}, X_1 + X_2 = m) \\
&\phantom{\overset{(i)}{\ge} \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict}) [} - \Pr(X_2 > X_1 | W_{1,2,strict}, X_1 + X_2 = m)] \\
&= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict}) \\
&\phantom{= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict})} \cdot \sum_{x \in L_m} \Pr \left( \max_{j \ge 3} X_j = x \mid X_1 + X_2 = m, W_{1,2,strict} \right) \\
&\phantom{= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict})} \cdot \left[ \Pr \left( X_1 > X_2 \mid W_{1,2,strict}, X_1 + X_2 = m, \max_{j \ge 3} X_j = x \right) \right. \\
&\phantom{= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict})} \phantom{\cdot \left[} \left. - \Pr \left( X_2 > X_1 \mid W_{1,2,strict}, X_1 + X_2 = m, \max_{j \ge 3} X_j = x \right) \right] \\
&= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict}) \\
&\phantom{= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict})} \cdot \sum_{x \in L_m} \Pr \left( \max_{j \ge 3} X_j = x \mid X_1 + X_2 = m, W_{1,2,strict} \right) \\
&\phantom{= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict})} \cdot \left[ \Pr \left( X_1 > X_2 \mid \max\{X_1, X_2\} > x, X_1 + X_2 = m, \max_{j \ge 3} X_j = x \right) \right. \\
&\phantom{= \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,strict})} \phantom{\cdot \left[} \left. - \Pr \left( X_2 > X_1 \mid \max\{X_1, X_2\} > x, X_1 + X_2 = m, \max_{j \ge 3} X_j = x \right) \right] \tag{8}
\end{align*}
$$

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,

$$
\begin{align*}
& \left( W_{1,2,strict}, X_1 + X_2 = m, \max_{j \ge 3} X_j = x \right) \\
&= \left( \max\{X_1, X_2\} > x, X_1 + X_2 = m, \max_{j \ge 3} X_j = x \right).
\end{align*}
$$
Conditioning on {$X_1 + X_2 = m$}, makes $X_1, X_2$ independent from $X_3, \dots, X_k$, and distributed as $Y_1, Y_2$, where $Y_1 \sim \text{Binomial}(m, q_1)$ with $q_1 = \frac{p_1}{p_1+p_2}$ and $Y_2 = m - Y_1$. We obtain, by Equation (8)

$$
\begin{align*}
& \Pr(W_1 | W_{1,2,\text{strict}}) - \Pr(W_2 | W_{1,2,\text{strict}}) \\
\ge & \sum_{m \in M} \Pr(X_1 + X_2 = m | W_{1,2,\text{strict}}) \\
& \cdot \sum_{x \in L_m} \Pr \left( \max_{j \ge 3} X_j = x \mid X_1 + X_2 = m, W_{1,2,\text{strict}} \right) \\
& \cdot [\Pr(Y_1 > Y_2 | \max\{Y_1, Y_2\} \ge x) - \Pr(Y_2 > Y_1 | \max\{Y_1, Y_2\} \ge x)] \\
\ge & \sum_{(i) m \in M} \Pr(X_1 + X_2 = m | W_{1,2,\text{strict}}) \\
& \cdot \sum_{x \in L_m} \Pr \left( \max_{j \ge 3} X_j = x \mid X_1 + X_2 = m, W_{1,2,\text{strict}} \right) \\
& \cdot C_1 \cdot \min \left( \sqrt{m} \left( \frac{\delta_2}{p_1 + p_2} \right), 1 \right) \\
= & \sum_{(ii) m \in M} \Pr(X_1 + X_2 = m | W_{1,2,\text{strict}}) \cdot C_1 \cdot \min \left( \sqrt{m} \left( \frac{\delta_2}{p_1 + p_2} \right), 1 \right) \\
\ge & \Pr(X_1 + X_2 \ge h \cdot (p_1 + p_2)/2 | W_{1,2,\text{strict}}) \cdot C_1 \cdot \min \left( \left( \frac{\delta_2 \sqrt{h}}{\sqrt{2(p_1 + p_2)}} \right), 1 \right) \\
\ge & 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) \\
\ge & 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) \\
\ge & C \min \left( \left( \frac{\delta_2 \sqrt{h}}{\sqrt{2(p_1 + p_2)}} \right), 1 \right),
\end{align*}
$$

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 \ge h(p_1 + p_2)/2$, in (iv) we used Lemma 8 and the multiplicative Chernoff bound (Lemma 27 in Appendix B), and in (v) we used that $hp_1 \ge 16 \log n$. This concludes the proof of Lemma 15. □

In the next lemma, we finally remove the conditional event $W_{1,2,\text{strict}}$ and bound $\Pr(W_1) - \Pr(W_2)$ 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 Appendix A.4. From now on, we denote the difference $p_1 - p_j$ by $\delta(j)$.

**Lemma 16.** Let $p_1 h \ge C_4 \log n$, with $C_4 = 18^2$. If $\delta(j) \le \sqrt{\frac{2(p_1+p_2)}{h}}$, then there exists a constant $C_5 > 0$ s.t.

$$ \Pr(W_1) - \Pr(W_j) \ge C_5 \left( \delta(j) \sqrt{\frac{h}{p_1 + p_2}} \right) \Pr(W_1). $$

Instead, if $\delta(j) \ge \sqrt{\frac{2(p_1+p_2)}{h}}$, there exists a constant $0 < C_6 < 1$ s.t.

$$ \Pr(W_1) \ge \frac{1}{1-C_6} \Pr(W_j). $$

Given a configuration $(p_1, \dots, p_k)$, we denote by $p'_j$ the probability associated to opinion $j$ at the next round. Fix an opinion $j \ne 1$. Let $\delta(j)'$ be the bias between opinion 1 and opinion $j$ at the next round, i.e. $p'_1 - p'_j$.
Before proceeding in the analysis presentation, let us comment **Lemma 16**. Note that $\Pr(W_j)$ is the expected value of $p'_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'_1 \ge (1+C)p'_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(p_1 \log n)$ and $\Pr(W_1) = \Omega(p_1 + p_2)$, **Lemma 16** implies that at the next round the expected bias grows of a $\Omega(\log n)$ 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 $(p_1, \dots, p_k)$ s.t. $p_1 \ge C_7 \frac{\log n}{n}$, and $p_1 - p_j \ge C_8 \sqrt{\frac{p_1}{n}}$ for all $j \ge 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 Appendix A.4). 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 \ge (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 \ge C_4 \log n$. If $\delta(j) \ge (1 - \frac{1}{1+C_6}) 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(\sqrt{p_1/h})$, 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 \ge C_4 \log n$. If $p_1 \ge C_7 \frac{\log n}{n}$ and $\sqrt{\frac{2(p_1+p_2)}{h}} \le \delta(j) \le (1 - \frac{1}{1+C_6}) 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)' \ge \left(1 - \frac{1}{1+C_6}\right) p_1' \right) \ge 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 \ge C_4 \log n$. If $p_1 \ge C_7 \frac{\log n}{n}$ and $C_8 \sqrt{\frac{p_1}{n}} \le \delta(j) \le \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(\delta(j)' \ge e \delta(j)) \ge 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) \ge \sqrt{\frac{p_1}{n}}$, and a constant $C_8 > 0$. For $n$ large enough we have

$$ \Pr \left( \delta(j)' \ge C \sqrt{\frac{p_1}{n}} \right) \ge 1 - \frac{2}{n^4}. $$
# Acknowledgments

This work was partially supported by the MUR (Italy) Department of Excellence 2023 - 2027 for GSSI, and the AID INRIA-DGA project n°2023000872 "BioSwarm". The authors are grateful to thank Frédéric Giroire for helpful discussions regarding this project.

# 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. URL: https://doi.org/10.1007/s00446-008-0059-z, 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. URL: https://doi.org/10.1137/1.9781611974331.ch46, 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 stub-born agents. *CoRR*, abs/2406.07335, 2024. URL: https://doi.org/10.48550/arXiv.2406.07335, arXiv:2406.07335, 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. URL: https://doi.org/10.4230/LIPIcs.OPODIS.2022.23, 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 $Z^2$. 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. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.28, doi:10.4230/LIPICS.MFCS.2018.28.

[13] Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraaga. 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. URL: https://doi.org/10.1007/s00446-023-00444-2, 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. URL: https://doi.org/10.1007/s11721-022-00217-w, doi:10.1007/S11721-022-00217-W.

[17] 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.

[18] Francesco D'Amore and Isabella Ziccardi. Phase transition of the 3-majority opinion dynamics with noisy interactions. *Theor. Comput. Sci.*, 1028:115030, 2025. URL: https://doi.org/10.1016/j.tcs.2024.115030, doi:10.1016/J.TCS.2024.115030.

[19] 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. URL: https://doi.org/10.4230/LIPIcs.DISC.2024.18, doi:10.4230/LIPICS.DISC.2024.18.
[20] 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/.

[21] 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.

[22] Ofer Feinerman and Amos Korman. The ANTS problem. *Distributed Comput.*, 30(3):149–168, 2017. URL: https://doi.org/10.1007/s00446-016-0285-8, doi:10.1007/S00446-016-0285-8.

[23] 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.

[24] Pierre Fraigniaud and Emanuele Natale. Noisy rumor spreading and plurality consensus. *Distributed Computing*, 32(4):257–276, 2019. URL: https://doi.org/10.1007/s00446-018-0335-5, doi:10.1007/S00446-018-0335-5.

[25] 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.

[26] 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.

[27] 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. URL: https://doi.org/10.4230/LIPIcs.DISC.2024.28, doi:10.4230/LIPICS.DISC.2024.28.

[28] 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.

[29] 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). URL: https://mathoverflow.net/q/210018, arXiv:https://mathoverflow.net/q/210018.

[30] 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.

[31] 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. URL: https://doi.org/10.24963/ijcai.2022/54, doi:10.24963/IJCAI.2022/54.
[32] Michael Mitzenmacher and Eli Upfal. *Probability and Computing: Randomized Algorithms and Probabilistic Analysis*. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603.

[33] Nobutaka Shimizu and Takeharu Shiraga. 3-majority and 2-choices with many opinions. *CoRR*, abs/2503.02426, 2025. To appear at PODC 2025. URL: https://doi.org/10.48550/arXiv.2503.02426, arXiv:2503.02426, doi:10.48550/ARXIV.2503.02426.

[34] Robin Vacus and Isabella Ziccardi. Minimal leader election under weak communication. *CoRR*, abs/2502.12697, 2025. To appear at PODC 2025. URL: https://doi.org/10.48550/arXiv.2502.12697, arXiv:2502.12697, doi:10.48550/ARXIV.2502.12697.

# A Missing proofs

## A.1 Omitted proofs from Section 3

*Proof of Lemma 3.* We note that

$$ 
\begin{aligned}
& \Pr(X_1 > X_2) - \Pr(X_2 > X_1) \\
&= \Pr(X_1 \ge X_2) - \Pr(X_1 = X_2) - (\Pr(X_2 \ge X_1) - \Pr(X_1 = X_2)) \\
&= \Pr(X_1 \ge X_2) - \Pr(X_2 \ge X_1) \\
&= \sum_{k=\lceil h/2 \rceil}^{h} \binom{h}{k} p^k (1-p)^{h-k} - \sum_{k=\lceil h/2 \rceil}^{h} \binom{h}{k} p^{h-k} (1-p)^k.
\end{aligned}
$$

Then the proof continues exactly as in [24, Lemma 9]. Please note that in [24, Lemma 9], the definition of $g$ contains a typographical error, i.e., it is defined so that $g(\delta, h) = \frac{1}{\sqrt{h}} \left(1 - \frac{1}{\sqrt{h}}\right)^{\frac{h-1}{2}}$ if $\delta \ge \frac{1}{\sqrt{h}}$; the correct definition is the one provided here and is the one actually used in the proof of [24, Lemma 9]. □

## A.2 Omitted proofs from Section 4.1

*Proof of Lemma 6.* The proof of Lemma 6 requires some minor technical result, which we express through the following claim.

**Claim 22.** For any integer $m > 0$, let $Y_1 \sim \text{Binomial}(m, q)$ and $Y_2 = m - Y_1 \sim \text{Binomial}(m, 1 - q)$, with $q > 1/2$. For any $m/2 \le i' \le i \le m$, it holds that

$$ 
\begin{aligned}
& \Pr(Y_1 > Y_2 | M \ge i) - \Pr(Y_2 > Y_1 | M \ge i) \\
&\ge \Pr(Y_1 > Y_2 | M \ge i') - \Pr(Y_2 > Y_1 | M \ge i').
\end{aligned}
$$

By Claim 22, we have

$$ 
\begin{aligned}
& \Pr(Y_1 > Y_2 | \max(Y_1, Y_2) > x) - \Pr(Y_2 > Y_1 | \max(Y_1, Y_2) > x) \\
&= \Pr(Y_1 > Y_2 | \max(Y_1, Y_2) \ge x - 1) \\
&\quad - \Pr(Y_2 > Y_1 | \max(Y_1, Y_2) \ge x - 1) \\
&\ge \Pr(Y_1 > Y_2 | \max(Y_1, Y_2) \ge m/2) \\
&\quad - \Pr(Y_2 > Y_1 | \max(Y_1, Y_2) \ge m/2) \qquad \text{(by Claim 22)} \\
&= \Pr(Y_1 > Y_2) - \Pr(Y_2 > Y_1) \\
&\ge C_1 \cdot \min(\sqrt{m} \cdot (2q - 1), 1), \qquad \text{(by Lemma 3)}
\end{aligned}
$$

for some constant $C_1 > 0$. □

*Proof of Claim 22.* In order to prove Claim 22, let us first state the following result.
**Claim 23.** For any integer $m > 1$, let $Y_1 \sim \text{Binomial}(m, q)$ and $Y_2 = m - Y_1 \sim \text{Binomial}(m, 1-q)$, with $q > 1/2$. Furthermore, let $M = \max\{Y_1, Y_2\}$. For all integers $i, i'$ such that $\lceil m/2 \rceil \le i' \le i \le m$, it holds that

$$ \Pr(Y_1 > Y_2 | M = i) - \Pr(Y_2 > Y_1 | M = i) \\ \ge \Pr(Y_1 > Y_2 | M = i') - \Pr(Y_2 > Y_1 | M = i'). $$

Now we are ready to prove Claim 22. For the sake of brevity, we will denote

$$ b_j = \Pr(Y_1 > Y_2 | M = j) - \Pr(Y_2 > Y_1 | M = j). $$

By Claim 23, we have

$$ b_j \ge b_{j'}, \quad \text{for all } m \ge j \ge j' \ge \lceil m/2 \rceil. \tag{9} $$

We have

$$ \begin{align*} & \Pr(Y_1 > Y_2 | M \ge i) - \Pr(Y_2 > Y_1 | M \ge i) - \Pr(Y_1 > Y_2 | M \ge i') \\ & + \Pr(Y_2 > Y_1 | M \ge i') \\ &= \sum_{(i)}^{m} \left[ \Pr(M = j | M \ge i) - \Pr(M = j | M \ge i') \right] b_j - \sum_{(j=i')}^{i-1} \Pr(M = j | M \ge i') b_j \\ &\ge \sum_{(ii)}^{m} \left[ \Pr(M = j | M \ge i) - \Pr(M = j | M \ge i') \right] b_j \\ &\quad - b_{i-1} \sum_{j=i'}^{i-1} \Pr(M = j | M \ge i') \\ &= \sum_{(iii)}^{m} \left[ \Pr(M = j | M \ge i) - \Pr(M = j | M \ge i') \right] b_j \\ &\quad - b_{i-1} \left( 1 - \sum_{j=i}^{m} \Pr(M = j | M \ge i') \right) \\ &= \sum_{j=i}^{m} \Pr(M = j | M \ge i) b_j - b_{i-1} + \sum_{j=i}^{m} \Pr(M = j | M \ge i') (b_{i-1} - b_j) \\ &= \sum_{(iv)}^{m} \Pr(M = j | M \ge i) (b_j - b_{i-1}) + \sum_{j=i}^{m} \Pr(M = j | M \ge i') (b_{i-1} - b_j) \\ &= \sum_{j=i}^{m} \left[ \Pr(M = j | M \ge i) - \Pr(M = j | M \ge i') \right] (b_j - b_{i-1}) \\ &\ge 0, \tag{v} \end{align*} $$

where in (i) we used the law of total probabilities, in (ii) we used Equation (9), in (iii) and (iv) we used that $\sum_{j=i}^{m} \Pr(M = j | M \ge i) = 1$, and in (v) we used Equation (9) and that

$$ \begin{align*} \Pr(M = j | M \ge i) &= \frac{\Pr(M = j)}{\Pr(M \ge i)} \\ &\ge \frac{\Pr(M = j)}{\Pr(M \ge i')} \\ &= \Pr(M = j | M \ge i'). \end{align*} $$

This concludes the proof of Claim 22.

□
Proof of Claim 23. Let $q_1 = q$ and $q_2 = 1 - q$. For all integers $i > m/2$, we have $\{M = i\} = \{Y_1 = i\} \cup \{Y_2 = i\}$, with $\{Y_1 = i\} \cap \{Y_2 = i\} = \emptyset$. Hence, we obtain

$$
\begin{align*}
\Pr(Y_1 > Y_2 | M = i) &= \frac{\Pr(Y_1 > Y_2, M = i)}{\Pr(M = i)} \\
&= \frac{\Pr(Y_1 = i, M = i)}{\Pr(M = i)} \\
&= \frac{\binom{m}{i} q_1^i q_2^{m-i}}{\binom{m}{i} q_1^i q_2^{m-i} + \binom{m}{i} q_2^i q_1^{m-i}} \\
&= \frac{q_1^{2i-m}}{q_1^{2i-m} + q_2^{2i-m}},
\end{align*}
$$

where, in the second inequality, we used that $\{Y_1 > Y_2, M = i\} = \{Y_1 = i, M = i\}$. In the symmetrical way, we obtain

$$
\Pr(Y_2 > Y_1 | M = i) = \frac{q_2^{2i-m}}{q_1^{2i-m} + q_2^{2i-m}}.
$$

Then, for all integers $m/2 < i' \le i \le m$, we have

$$
\begin{align*}
& \Pr(Y_1 > Y_2 | M = i) - \Pr(Y_2 > Y_1 | M = i) \\
&= \frac{q_1^{2i-m} - q_2^{2i-m}}{q_1^{2i-m} + q_2^{2i-m}} \\
&= \frac{(q_1/q_2)^{2i-m} - 1}{(q_1/q_2)^{2i-m} + 1} \\
&> \frac{(q_1/q_2)^{2i'-m} - 1}{(q_1/q_2)^{2i'-m} + 1} \tag{10} \\
&= \Pr(Y_1 > Y_2 | M = i') - \Pr(Y_2 > Y_1 | M = i'), \tag{11}
\end{align*}
$$

where the inequality holds because the function $\frac{x-1}{x+1}$ is increasing in $x$, and $q_1/q_2 > 1$ ($q_1 > 1/2$).

It remains to prove the inequality in the case $i' = m/2$, for $m$ even. By Equation (10), we deduce
that for $i > m/2$,

$$
\Pr(Y_1 > Y_2 | M = i) - \Pr(Y_2 > Y_1 | M = i) > 0,
$$

because $\frac{x-1}{x+1} > 0$ for all $x > 1$. If $m$ is even, we have that $\{M = m/2\} = \{Y_1 = Y_2\}$. This implies that
$\Pr(Y_1 > Y_2 | M = m/2) = \Pr(Y_2 > Y_1 | M = m/2) = 0$, and, therefore,

$$
\Pr(Y_1 > Y_2 | M = m/2) - \Pr(Y_2 > Y_1 | M = m/2) = 0.
$$

This implies that for all $i > m/2$,

$$
\Pr(Y_1 > Y_2 | M = i) - \Pr(Y_2 > Y_1 | M = i) \\
> \Pr(Y_1 > Y_2 | M = m/2) - \Pr(Y_2 > Y_1 | M = m/2),
$$

which, together with Equation (11), concludes the proof of Claim 23.

Proof of Lemma 7. Our claim is equivalent to proving that

$$
\Pr(\mathcal{W}_1, \mathcal{W}_{1,2,\text{strict}}) - \Pr(\mathcal{W}_2, \mathcal{W}_{1,2,\text{strict}}) \\
= \Pr(X_1 > X_2, \mathcal{W}_{1,2,\text{strict}}) - \Pr(X_2 > X_1, \mathcal{W}_{1,2,\text{strict}}).
$$

By definition (Definition 4), we have that the event $\{\mathcal{W}_1, \mathcal{W}_{1,2,\text{strict}}\}$ is disjoint union of the events
$\{X_1 > X_2, \mathcal{W}_{1,2,\text{strict}}\}$ and the event

$$
\{X_1 = X_2, W_{1,2,\text{strict}}, \text{``opinion 1 gets chosen among the ties''}\}.
$$
It holds similarly for the event {$W_2, W_{1,2,strict}$}. Therefore, we can write

$$
\begin{align*}
& \Pr(W_1, W_{1,2,strict}) - \Pr(W_2, W_{1,2,strict}) \\
&= \Pr(X_1 > X_2, W_{1,2,strict}) + \frac{1}{2} \Pr(X_1 = X_2, W_{1,2,strict}) \\
&\quad - \Pr(X_2 > X_1, W_{1,2,strict}) - \frac{1}{2} \Pr(X_1 = X_2, W_{1,2,strict}) \\
&= \Pr(X_1 > X_2 | W_{1,2,strict}) - \Pr(X_2 > X_1 | W_{1,2,strict}). \quad \square
\end{align*}
$$

Proof of Lemma 8. We found it more convenient to swap the conditioning event with the event whose probability we are computing, and then apply Bayes’ theorem. Hence, we first state the following claim.

**Claim 24.** For any $0 \le x < h$,

$$
\Pr(W_{1,2,\text{strict}} | X_1 + X_2 \ge x) \ge \Pr(W_{1,2,\text{strict}} | X_1 + X_2 \ge x - 1).
$$

Now, by Bayes theorem and by Claim 24, we have

$$
\begin{align*}
& \Pr(X_1 + X_2 \ge h \cdot (p_1 + p_2)/2 \mid W_{1,2,\text{strict}}) \\
&= \frac{\Pr(X_1 + X_2 \ge h \cdot (p_1 + p_2)/2) \cdot \Pr(W_{1,2,\text{strict}} \mid X_1 + X_2 \ge h \cdot (p_1 + p_2)/2)}{\Pr(W_{1,2,\text{strict}})} \\
&\ge \frac{\Pr(X_1 + X_2 \ge h \cdot (p_1 + p_2)/2) \cdot \Pr(W_{1,2,\text{strict}} \mid X_1 + X_2 \ge 0)}{\Pr(W_{1,2,\text{strict}})} \\
&= \Pr(X_1 + X_2 \ge h \cdot (p_1 + p_2)/2),
\end{align*}
$$

concluding the proof of Lemma 8.

*Proof of Claim 24.* We want to use a coupling argument. The idea is that

$$
\Pr(W_{1,2,\text{strict}} | X_1 + X_2 \ge x)
$$

is the probability that we have $W_{1,2,strict}$ after $x$ extractions among $\{1,2\}$ only, and the rest of them are among all opinions. More specifically we consider two families of r.v. representing $h$ extractions among balls with $k$ opinions. For both families, the first $x-1$ extractions are identical and only among the first two opinions, and from the $x+1$ to the end are identical and among all opinions. They instead differ on the $x$-th extraction. For first family the $x$-th extraction is simply among the first two opinions. For the second family, we need to flip first an unbalanced coin: in case of head, the extraction is identical to the first family, in case of tail, the extraction is on all opinions except the first twos. The coin is unbalanced in such a way the marginal distribution of the $x$-th extraction of the second family is like the one of an extraction among all opinions. Let $\{Y_j\}_{j \in \{1, \dots, h\}}$ family of independent r.v. with the following distributions: For $0 \le j \le x$:

$$
\Pr(Y_j = 1) = \frac{p_1}{p_1 + p_2};
$$

$$
\Pr(Y_j = 2) = \frac{p_2}{p_1 + p_2}.
$$

For $x + 1 \le j \le h$ and $i \in \{1, \dots, k\}$:

$$
\Pr(Y_j = i) = p_i.
$$

Now let $\{\bar{Y}_j\}_{j \in \{1, \dots, h\}}$ be the r.v. family s.t. $\bar{Y}_j = Y_j$ for all $j \neq x$, and $\bar{Y}_x$ with the following distribution. Let $C$ a random coin, independent of $\{Y_j\}_{j \in \{1, \dots, h\}}$, with distribution $\Pr(C = 1) = p_1 + p_2$ and $\Pr(C = 0) = 1 - (p_1 + p_2)$. $\bar{Y}_x$ is distributed in such a way we obtain

$$
\Pr(C = 1, \bar{Y}_x = Y_x) = 1
$$
For $i \in \{3, \dots, k\}$,

$$ \mathrm{Pr}(C = 0, \bar{Y}_x = i) = \frac{p_i}{\sum_{j \ge 3} p_i}. $$

Overall, we have, for $i \in \{1, \dots, k\}$

$$ \mathrm{Pr}(\bar{Y}_x = i) = p_i. $$

Now define $\{Z_i\}_{i \in \{1, \dots, k\}}$ and $\{\bar{Z}_i\}_{i \in \{1, \dots, k\}}$ as follows: for all $i \in \{1, \dots, k\}$

$$ Z_i = |\{j \in \{1, \dots, h\} : Y_j = i\}| $$

$$ \bar{Z}_i = |\{j \in \{1, \dots, h\} : \bar{Y}_j = i\}|. $$

In this way, we have that $(X_i | X_1 + X_2 \ge x) \sim Z_i$ and $(X_i | X_1 + X_2 \ge x - 1) \sim \bar{Z}_i$ and then

$$ \mathrm{Pr}(W_{1,2,\mathrm{strict}} | X_1 + X_2 \ge x) = \mathrm{Pr}(\cap_{i \ge 3} \{\max(Z_1, Z_2) > Z_i\}) \text{ and} $$

$$ \mathrm{Pr}(W_{1,2,\mathrm{strict}} | X_1 + X_2 \ge x - 1) = \mathrm{Pr}(\cap_{i \ge 3} \{\max(\bar{Z}_1, \bar{Z}_2) > \bar{Z}_i\}). $$

For our construction, we have for all $i \in \{1, \dots, k\}$

$$ \{C = 1\} \implies \{Z_i = \bar{Z}_i\} $$

and for $i = 1, 2$

$$ \{C = 0\} \implies \{Z_i \ge \bar{Z}_i\} $$

while for $i \ge 3$

$$ \{C = 0\} \implies \{Z_i \le \bar{Z}_i\}, $$

These facts imply, regardless the realization of $C$,

$$ \{\cap_{i \ge 3} \{\max(\bar{Z}_1, \bar{Z}_2) > \bar{Z}_i\}\} \subset \{\cap_{i \ge 3} \{\max(Z_1, Z_2) > Z_i\}\}. $$

We conclude

$$ \begin{aligned} \mathrm{Pr}(W_{1,2,\mathrm{strict}} | X_1 + X_2 \ge x) &= \mathrm{Pr}(\cap_{i \ge 3} \{\max(Z_1, Z_2) > Z_i\}) \\ &\ge \mathrm{Pr}(\cap_{i \ge 3} \{\max(\bar{Z}_1, \bar{Z}_2) > \bar{Z}_i\}) \\ &= \mathrm{Pr}(W_{1,2,\mathrm{strict}} | X_1 + X_2 \ge x - 1). \end{aligned} $$

This concludes the proof of Claim 24.

<figure><img src="image_2.png" /></figure>

## A.3 Omitted proofs from Section 4.2

*Proof of Lemma 11.* Define the event $C_j = \{|X_j - hp_j| < \sqrt{3C_3 hp_j \log n}\}$ and $C = \cap_{j=1}^k C_j$. The event $C_j$ can be rewritten as

$$ 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\}. \quad (12) $$

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

$$ \begin{aligned} & hp_1 - \sqrt{3C_3 hp_1 \log n} - (hp_i + \sqrt{3C_3 hp_i \log n}) \\ & \ge (1 - C_2) hp_1 - \sqrt{3C_3 hp_1 \log n} \\ & > 0, \end{aligned} \quad (i \in \mathcal{R} \implies hp_i \le hC_2 \cdot p_1) $$
by taking $hp_1 > C_4 \log n$, with $C_4 = (3C_3 \frac{1}{1-C_2})^2$. This fact, together with Equation (12), implies that $\mathcal{C} \subset \{\cap_{i \in \mathcal{R}_{C_2}} \{X_1 > X_i\}\}$, and therefore $\Pr(\cap_{i \in \mathcal{R}_{C_2}} \{X_1 > X_i\}) \ge \Pr(\mathcal{C})$. By the multiplicative Chernoff bound we have

$$
\begin{align*}
\Pr(C_j) &= \Pr(|X_j - hp_j| < \sqrt{3C_3 hp_j \log n}) \\
&= 1 - \Pr(|X_j - hp_j| \ge \sqrt{3C_3 hp_j \log n}) \\
&\ge 1 - 2 \exp\left(-\frac{3C_3 \log n}{3}\right) \\
&= 1 - \frac{2}{n^{C_3}},
\end{align*}
$$

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

$$
\Pr(\cap_{i \in \mathcal{R}} \{X_1 > X_i\}) \geq \Pr(\mathcal{C}) \geq 1 - \frac{2k}{n^{C_3}} \geq 1 - \frac{1}{n^{C_3-2}},
$$

concluding the proof of Lemma 11.

Proof of Lemma 12. Recall $\mathcal{S} := \{i \in [k] : p_i > \frac{1}{2}p_1\}$ be the set of the strong opinions. By definition of $\mathcal{S}$ we have

$$
1 \geq \sum_{j \in \mathcal{S}} p_j > \frac{|\mathcal{S}| p_1}{2},
$$

and therefore we have

$$
|S| \le \frac{2}{p_1}. \tag{13}
$$

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

$$
\Pr(W_i | \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}) = 0.
$$

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

$$
1 = \Pr \left( \bigcup_{j \in S} W_j \mid \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\} \right) \le \sum_{j \in S} \Pr \left( W_j \mid \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\} \right). \quad (14)
$$

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

$$
\Pr(W_1 | \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}) \ge \Pr(W_j | \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}),
$$

for all $j \in S, j \ge 2$. This fact, together with Equation (14), implies

$$
|S| \cdot \Pr(W_1 | \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}) \ge \sum_{j \in S} \Pr(W_j | \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}) \ge 1,
$$

and, by using Equation (13), we obtain

$$
\Pr(W_1 | \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}) \ge \frac{1}{|S|} \ge \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(W_1) \ge \Pr(\cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}) \cdot \Pr(W_1 | \cap_{\ell \in \mathcal{R}_{1/2}} \{X_1 > X_\ell\}) \ge \left(1 - \frac{1}{n}\right) \frac{p_1}{2} \ge \frac{p_1}{3},
$$

for *n* large enough.
Proof of Lemma 13. Define the event $C_j = \{|X_j - hp_j| < \sqrt{9hp_j \log n}\}$ and $C = \cap_{j \ge 1} C_j$. By the multiplicative Chernoff bound (Lemma 27 in Appendix B), we obtain

$$
\begin{align*}
\Pr(C_j) &= \Pr(|X_j - hp_j| < \sqrt{9hp_j \log n}) \\
&= 1 - \Pr(|X_j - hp_j| \ge \sqrt{9hp_j \log n}) \\
&\ge 1 - 2 \exp\left(-\frac{9 \log n}{3}\right) \\
&= 1 - \frac{2}{n^3}.
\end{align*}
$$

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

$$
\Pr(C) \geq 1 - \frac{2k}{n^3} \geq 1 - \frac{1}{n}. \qquad (15)
$$

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

$$
\begin{align*}
\mathcal{C} &\subseteq \bigcap_{j \in \mathcal{S}} \{X_j > hp_j - \sqrt{9hp_j \log n}\} \\
&\subseteq \bigcap_{j \in \mathcal{S}} \left\{X_j > \frac{1}{2}hp_1 - \sqrt{9hp_1 \log n}\right\} \quad \left(p_i > \frac{1}{2}p_1, p_i \le p_1, \text{ for all } i \in \mathcal{S}\right) \\
&\subseteq \bigcap_{j \in \mathcal{S}} \{X_j > 0\}. \tag{hp$_1$ > 36 log $n$} \tag{16}
\end{align*}
$$

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

$$
\mathcal{X}(x_1, \dots, x_k) = \{X_1 = x_1, \dots, X_k = x_k\}.
$$

We define the event $\mathcal{X}(x_1, \dots, x_k)$ a **1-tie** if $x_1 \ge x_i$ for all $i \ge 1$ and there exists a $j \ne 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\{i: X_i = \min_{r \in \mathcal{S}}\{X_r\}\}$, 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 (16), we have
$\mathcal{X}(x_1, \dots, x_k) \in \cap_{j \in \mathcal{S}} \{X_j > 0\}$, 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(f(\mathcal{X}(x_1, \dots, x_k)))}{\Pr(\mathcal{X}(x_1, \dots, x_k))} = \frac{x_j}{x_1+1} \cdot \frac{p_1}{p_j} \ge \frac{x_j}{x_1+1},
$$

where we used that $p_1 \ge p_j$. Therefore we obtain

$$
\begin{align*}
& \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(f(\mathcal{X}(x_1, \dots, x_k))) \\
\ge & \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \frac{x_j}{x_1+1} \Pr((\mathcal{X}(x_1, \dots, x_k))) \\
\ge & \frac{hp_j - \sqrt{9hp_j \log n}}{1 + hp_1 + \sqrt{9hp_1 \log n}} \cdot \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(\mathcal{X}(x_1, \dots, x_k)) \quad \text{(by definition of } \mathcal{C}) \\
\ge & \frac{\frac{1}{2}hp_1 - \sqrt{9hp_1 \log n}}{1 + hp_1 + \sqrt{9hp_1 \log n}} \cdot \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(\mathcal{X}(x_1, \dots, x_k)) \quad \left( p_i > \frac{1}{2}p_1, p_i \le p_1, \text{ for } i \in \mathcal{S} \right)
\end{align*}
$$
$$ 
\begin{aligned}
&= \frac{\frac{1}{2}\sqrt{\frac{hp_1}{9\log n}} - 1}{\sqrt{\frac{hp_1}{9\log n}} + 2} \cdot \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(\mathcal{X}(x_1, \dots, x_k)) \\
&\geq \frac{1}{4} \cdot \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(\mathcal{X}(x_1, \dots, x_k)),
\end{aligned} 
\quad (17) $$

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

$$ 
\begin{aligned}
& \Pr(\mathcal{W}_{1,ties}, \mathcal{C}) \\
&= \Pr(\mathcal{W}_{1,strict}, \mathcal{C}) + \Pr(\mathcal{W}_{1,ties} \setminus \mathcal{W}_{1,strict}, \mathcal{C}) \\
&\geq \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(f(\mathcal{X}(x_1, \dots, x_k))) + \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(\mathcal{X}(x_1, \dots, x_k)) \\
&\geq \left(1 + \frac{1}{4}\right) \sum_{\mathcal{X} \in \mathcal{T}_1, \mathcal{X} \in \mathcal{C}} \Pr(\mathcal{X}(x_1, \dots, x_k)) \quad \text{(by Equation (17))} \\
&= \left(1 + \frac{1}{4}\right) \Pr(\mathcal{W}_{1,ties} \setminus \mathcal{W}_{1,strict}, \mathcal{C}).
\end{aligned} 
$$

Hence,

$$ \Pr(\mathcal{W}_{1,ties} \setminus \mathcal{W}_{1,strict}, \mathcal{C}) \le \frac{4}{5} \cdot \Pr(\mathcal{W}_{1,ties}, \mathcal{C}), $$

and

$$ 
\begin{aligned}
\Pr(\mathcal{W}_{1,strict}) &\ge \Pr(\mathcal{W}_{1,strict}, \mathcal{C}) = \Pr(\mathcal{W}_{1,ties}, \mathcal{C}) - \Pr(\mathcal{W}_{1,ties} \setminus \mathcal{W}_{1,strict}, \mathcal{C}) \\
&\ge \frac{1}{5} \cdot \Pr(\mathcal{W}_{1,ties}, \mathcal{C}) \\
&= \frac{1}{5} (\mathcal{W}_{1,ties} + \Pr(\mathcal{C}) - \Pr(\mathcal{W}_{1,ties} \cup \mathcal{C})) \quad \text{(by the inclusion-exclusion princ.)} \\
&\ge \frac{1}{5} (\mathcal{W}_{1,ties} + \Pr(\mathcal{C}) - 1) \quad \text{(Pr}(\mathcal{W}_{1,ties} \cup \mathcal{C}) \le 1) \\
&\ge \frac{1}{5} \left(\mathcal{W}_{1,ties} - \frac{1}{n}\right) \quad \text{(by Equation (15))} \\
&\ge \frac{1}{6} \mathcal{W}_{1,ties} \ge \frac{1}{18} p_1
\end{aligned} 
$$

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

Proof of Corollary 14. By Lemmas 12 and 13, we obtain

$$ \Pr(\mathcal{W}_{1,2,strict}) \ge \Pr(\mathcal{W}_{1,strict}) \ge \frac{1}{6} \Pr(\mathcal{W}_{1,ties}) \ge \frac{1}{18} p_1 = \frac{1}{36} (p_1 + p_1) \ge \frac{1}{36}(p_1 + p_2). $$

This concludes the proof of Corollary 14. $\square$

## A.4 Omitted proofs from Section 4.3

Proof of Lemma 16. Since $p_2 \ge p_j$ for all $j \ge 2$, we have that $\Pr(\mathcal{W}_j) \le \Pr(\mathcal{W}_2)$, and, therefore,

$$ \Pr(\mathcal{W}_1) - \Pr(\mathcal{W}_2) \implies \Pr(\mathcal{W}_1) - \Pr(\mathcal{W}_j), $$

and,

$$ \Pr(\mathcal{W}_1) \ge \frac{1}{1 - C_6} \Pr(\mathcal{W}_2) \implies \Pr(\mathcal{W}_1) \ge \frac{1}{1 - C_6} \Pr(\mathcal{W}_j). $$

Hence, we will focus on the proof statement for $j = 2$.
Consider the case $\delta(2) \le \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

$$
\begin{align*}
& \Pr(W_1) - \Pr(W_2) \\
\ge & \Pr(W_{1,2,\text{strict}}) \cdot [\Pr(W_1 | W_{1,2,\text{strict}}) - \Pr(W_2 | W_{1,2,\text{strict}})] \\
\ge & \Pr(W_{1,\text{strict}}) \cdot [\Pr(W_1 | W_{1,2,\text{strict}}) - \Pr(W_2 | W_{1,2,\text{strict}})] \quad (W_{1,\text{strict}} \subseteq W_{1,2,\text{strict}}) \\
\ge & \frac{1}{6} \Pr(W_{1,\text{ties}}) \cdot [\Pr(W_1 | W_{1,2,\text{strict}}) - \Pr(W_2 | W_{1,2,\text{strict}})] \quad \text{(by Lemma 13)} \\
\ge & \frac{1}{6} \Pr(W_1) \cdot [\Pr(W_1 | W_{1,2,\text{strict}}) - \Pr(W_2 | W_{1,2,\text{strict}})] \quad (W_1 \subseteq W_{1,\text{ties}}) \\
\ge & \frac{C}{6} \Pr(W_1) \delta(2) \sqrt{\frac{h}{p_1 + p_2}} \quad \text{(by Lemma 15)}
\end{align*}
$$

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

$$
\begin{align*}
& \Pr(W_1) - \Pr(W_2) \\
\ge & \Pr(W_{1,2,\text{strict}}) \cdot [\Pr(W_1 | W_{1,2,\text{strict}}) - \Pr(W_2 | W_{1,2,\text{strict}})] \\
\ge & \Pr(W_{1,2,\text{strict}}) \cdot C \quad \text{(by Lemma 15)} \\
\ge & \Pr(W_{1,\text{strict}}) \cdot C \quad (W_{1,\text{strict}} \subseteq W_{1,\text{strict}}) \\
\ge & \frac{C}{6} \Pr(W_{1,\text{ties}}) \quad \text{(by Lemma 13)} \\
\ge & \frac{C}{6} \Pr(W_1) \quad (W_1 \subseteq W_{1,\text{ties}}) \\
\ge & C_6 \Pr(W_1),
\end{align*}
$$

if we set $0 < C_6 = \min(\frac{1}{2}, \frac{C}{6}) < 1$. This concludes the proof of Lemma 16. $\square$

*Proof of Theorem 17.* By using the union bound and by Lemmas 18 to 20, we have that either $\delta(j)' \ge e\delta(j)$, or $\frac{p'_j}{p'_1} < \frac{p_j}{p_1}$, or opinion j disappear and $p_j = 0$, for all $j \ne 1$ with probability $1 - \frac{1}{n^4}$. This means that, conditioning on this event, we can apply, the following claim (whose proof is deferred to Appendix A.4) to obtain $p'_1 \ge p_1$, with probability $1 - \frac{1}{n^4}$.

**Claim 25.** Let a partition of $[k] = \{1\} \cup I \cup J \cup K$ s.t. for $j \in I$, $\delta(j)' > \delta(j)$, for $j \in J$, $\frac{p'_j}{p_1} < \frac{p_j}{p_1}$, and for $j \in K$, $p'_j = 0$. Then $p'_1 > p_1$.

This fact, together with Lemma 21 and the union bound on all opinions, implies that with probability $1 - \frac{2}{n^3}$, after one round of h-majority, the new configuration still satisfies the initial hypothesis of the theorem, and we can iterate our calculations. By the union bound on several rounds, we can iterate this calculations up to n number of rounds to obtain all the events hold w.h.p.

By Lemma 20, at every round, with probability $1 - 1/n^4$, $\delta(j)' \ge e\delta(j)$ for n large enough, until we obtain a bias $\delta(j) \ge \sqrt{\frac{2(p_1+p_2)}{h}}$. Then, even starting with the minimal initial bias of $\delta(j) = \sqrt{\log n}/n$, we reach a configuration with $\delta(j) \ge \sqrt{\frac{2(p_1+p_2)}{h}}$ after

$$ \log \left( n \sqrt{\frac{2(p_1 + p_2)}{h \log n}} \right) \le \log \left( \frac{2\sqrt{C_4 n}}{\log n} \right) \le \log(n) $$
number of rounds, with probability $1 - 1/n^3$, where we used that $h \ge C_4 \log n/p_1$, that $p_2 \le p_1 \le 1$ and we took $n$ large enough. Once we have $\sqrt{\frac{2(p_1+p_2)}{h}} \le \delta(j) \le (1 - \frac{1}{1+C_6}) p_1$, by Equation (21) we have that at the next round with probability $1 - \frac{2}{n^4}$ we are in the last case $\delta(j) \ge (1 - \frac{1}{1+C_6}) p_1$, and, as computed before, in the following round opinion $j$ will disappear with probability $1 - \frac{1}{n^4}$.

Overall we have that all opinions $j \ne 1$ disappear with probability $1 - \frac{1}{n^3}$ in at most $\log(n) + 2$ number of rounds, and by applying the union bound, we obtain that w.h.p. after $\log n$ rounds the only opinion left is opinion 1 with probability $1 - \frac{1}{n^2}$, concluding the proof of Theorem 17. $\square$

*Proof of Lemma 18.* Recalling $\mathcal{R}_x := \{i \in [k] : p_i \le xp_1\}$, we have that $j \in \mathcal{R}_x$, and therefore, by Lemma 11, with probability $1 - \frac{1}{n^4}$ opinion $j$ will score less than opinion 1, and then will disappear in the next round and therefore $\delta(j)' = p_1'$.
$\square$

*Proof of Lemma 19.* We have that

$$ \begin{aligned} \Pr(W_1) &\ge \frac{1}{3}p_1 & \text{(by Lemma 12)} \\ &\ge \frac{C_7 \log(n)}{3n}. & \left( p_1 \ge \frac{C_7 \log n}{n} \right) \end{aligned} \quad (18) $$

Denote with $Y_{\ell}^{(i)}$ the indicator function of the event "the agent $i$ adopts opinion $\ell$". In this way, we have that $\sum_{i \in [n]} Y_{\ell}^{(i)}$ counts the number of agents supporting opinion $\ell$ during the next round, and $\mathbb{E}(\sum_{i \in [n]} Y_{\ell}^{(i)}) = n \Pr(W_{\ell})$. By the multiplicative Chernoff bound (Lemma 27 in Appendix B), we obtain

$$ \begin{aligned} & \Pr\left(\left|\sum_{i \in [n]} Y_1^{(i)} - n \Pr(W_1)\right| \le \frac{C_6^2}{2} n \Pr(W_1)\right) \\ & \le 2 \exp\left(-\frac{\left(\frac{C_6^2}{2}\right)^2}{2} n \Pr(W_1)\right) \\ & \le \frac{1}{n^4}. \end{aligned} \quad \text{(by Equation (18))} \quad (19) $$

By Lemma 16, we know that $\Pr(W_j) \le (1 - C_6) \Pr(W_1)$ for some constant $0 < C_6 < 1$. Let $\{Z_i\}_{i \in [n]}$ be i.i.d. random variables with Bernoulli distribution of parameter $(1 - C_6) \Pr(W_1)$. We obtain that $\sum_{i \in [n]} Y_j^{(i)}$ is stochastically dominated by $\sum_{i \in [n]} Z^{(i)}$. Hence,

$$ \begin{aligned} & \Pr\left(\sum_{i \in [n]} Y_j^{(i)} \ge \left(1 + \frac{C_6^2}{2(1-C_6^2)}\right) n(1-C_6) \Pr(W_1)\right) \\ & \le \Pr\left(\sum_{i \in [n]} Z^{(i)} \ge \left(1 + \frac{C_6^2}{2(1-C_6^2)}\right) n(1-C_6) \Pr(W_1)\right) \\ & \le \exp\left(-\frac{\left(\frac{C_6^2}{2(1-C_6^2)}\right)^2 n(1-C_6) \Pr(W_1)}{3}\right) \\ & \le \frac{1}{n^4}. \end{aligned} \quad \text{(by Equation (18))} $$

Since $1 - \frac{C_6^2}{2} \ge \left(1 + \frac{C_6^2}{2(1-C_6^2)}\right) (1 - C_6)(1 + C_6)$, by applying the union bound, we obtain that

$$ \Pr\left(\sum_{i \in [n]} Y_1^{(i)} \ge (1 + C_6) \sum_{i \in [n]} Y_j^{(i)}\right) \ge 1 - \frac{2}{n^4}, $$
which implies that $p'_j \le xp'_1$, with $0 < x = \frac{1}{1+C_6} < 1$. Therefore, we obtain that with probability $1 - \frac{2}{n^4}$,

$$ \frac{p'_j}{p'_1} \le \frac{1}{1+C_6} < \frac{p_j}{p_1} \qquad (20) $$

whenever $\sqrt{\frac{2(p_1+p_2)}{h}} \le \delta(j) < \left(1 - \frac{1}{1+C_6}\right) p_1$. Moreover, we obtain from the previous equation that

$$ \Pr\left(\delta(j)' \ge \left(1 - \frac{1}{1+C_6}\right) p'_1\right) \ge 1 - \frac{2}{n^4}. \qquad (21) $$

□

Before proving Lemma 20, we present a claim in which we apply the Bernstein inequality, which will be useful not only in proving the last lemma, but also later on.

**Claim 26.** Let $hp_1 \ge C_4 \log n$. If $p_1 \ge C_7 \frac{\log n}{n}$

$$ \Pr\left(\delta(j)' \le C_9\delta(j) \frac{\Pr(W_1)}{p_1} \sqrt{\log n}\right) \le \frac{1}{n^4}, $$

for some constant $C_9 > 0$.

*Proof of Claim 26.* By Lemma 16 and by the fact $hp_1 \ge C_4 \log n$, we obtain that

$$ \mathbb{E}(\delta(j)') \ge C_5\delta(j) \Pr(W_1) \sqrt{\frac{h}{p_1}} \ge C_5\delta(j) \frac{\Pr(W_1)}{p_1} \sqrt{C_4 \log n}. \qquad (22) $$

Let $X^{(i)}$ be a r.v. that take value 1 if at the next round the agent $i$ adopts opinion 1, value -1 if the agent $i$ adopts opinion $j$ and value 0 otherwise. Notice that $\{X_i\}_{i \in [n]}$ are i.i.d., that $n\delta(j)' = \sum_{i \in [n]} X^{(i)}$, and that

$$ \begin{aligned} \mathrm{Var}(X^{(1)}) &\le \mathbb{E}\left(\left(X^{(1)}\right)^2\right) \\ &= (\mathrm{Pr}(W_1) + \mathrm{Pr}(W_j)) \\ &\le 2 \mathrm{Pr}(W_1). \end{aligned} \qquad (\mathrm{Pr}(W_j) \le \mathrm{Pr}(W_1)) \qquad (23) $$

By the Bernstein inequality we obtain

$$ \begin{aligned} & \Pr\left(n\delta(j)' \le \frac{1}{2}C_5n\delta(j)\frac{\Pr(W_1)}{p_1}\sqrt{C_4\log n}\right) && \text{(by Lemma 13)} \\ & \le \Pr\left(n\delta(j)' \le \mathbb{E}(n\delta(j)') - \frac{C_5}{2}n\delta(j)\frac{\Pr(W_1)}{p_1}\sqrt{C_4\log n}\right) && \text{(by Equation (22))} \\ & \le \exp\left(-\frac{\left(\frac{1}{2}C_5n\delta(j)\frac{\Pr(W_1)}{p_1}\sqrt{C_4\log n}\right)^2}{2n\mathrm{Var}\{\delta(j)\} + \frac{2}{3}C_5\delta(j)\frac{\Pr(W_1)}{p_1}\sqrt{C_4\log n}}\right) && \text{(by Bernstein Inequality [20])} \\ & \le \exp\left(-\frac{\left(\frac{1}{2}C_5n\delta(j)\frac{\Pr(W_1)}{p_1}\sqrt{C_4\log n}\right)^2}{4n\Pr(W_1) + \frac{2}{3}C_5n\delta(j)\frac{\Pr(W_1)}{p_1}\sqrt{C_4\log n}}\right) && \text{(by Equation (23))} \\ & = \exp\left(-\frac{n\Pr(W_1)\left(\frac{1}{2}C_5\delta(j)\frac{1}{p_1}\sqrt{C_4\log n}\right)^2}{4 + \frac{2}{3}C_5\delta(j)\frac{1}{p_1}\sqrt{C_4\log n}}\right) \\ & \le \exp\left(-\frac{\frac{n}{3p_1}\left(\frac{1}{2}C_5\delta(j)\sqrt{C_4\log n}\right)^2}{4 + \frac{2}{3}C_5\delta(j)\frac{1}{p_1}\sqrt{C_4\log n}}\right) && \text{(by Lemma 12)} \end{aligned} $$
$$ \leq \exp \left( -\min \left\{ \frac{n}{24p_1} \left( \frac{1}{2} C_5 \delta(j) \sqrt{C_4 \log n} \right)^2, \frac{C_5}{4} n \delta(j) \sqrt{C_4 \log n} \right\} \right) \quad (24) $$

$$ \leq \frac{1}{n^C}, \quad (25) $$

where the latter holds because $\delta(j) \geq C_8 \sqrt{\frac{p_1}{n}} \geq \frac{C_8 \sqrt{C_7 \log n}}{n}$, with $C = \frac{C_4 C_5^2}{24} \geq 4$ for $C_4$ large enough. By dividing both sides by $n$ in the event we are computing the probability, we conclude the proof of Claim 26. $\square$

*Proof of Lemma 20.* By Lemma 13 we have $\frac{\Pr(W_1)}{p_1} \geq \frac{1}{18}$, and therefore, by Claim 26, we obtain

$$ \Pr \left( \delta(j)' \leq \frac{C_9}{18} \delta(j) \sqrt{\log n} \right) \leq \Pr \left( \delta(j)' \leq C_9 \delta(j) \frac{\Pr(W_1)}{p_1} \sqrt{\log n} \right) \leq \frac{1}{n^4}. $$

For $n$ large enough, we have $\sqrt{\log n} \geq \frac{18 \cdot e}{C_9}$, and therefore, we obtain

$$ \Pr(\delta(j)' \geq e \delta(j)) \geq 1 - \frac{1}{n^4}. \quad (26) $$

*Proof of Lemma 21.* Firstly, consider the case $\delta(j) \leq \sqrt{\frac{2(p_1+p_2)}{h}}$. By Claim 26, we have with probability $1 - \frac{1}{n^4}$,

$$ \begin{align*} \delta(j)' &\geq C_9 \delta(j) \frac{\Pr(W_1)}{p_1} \sqrt{\log n} \\ &\geq C_9 \frac{\Pr(W_1) \sqrt{\log n}}{\sqrt{p_1 n}} \quad \left( \delta(j) \geq \sqrt{\frac{p_1}{n}} \right) \\ &\geq C_9 \sqrt{\frac{\Pr(W_1) \log n}{18n}} \quad \text{(by Lemma 13)} \\ &\geq C_9 \sqrt{\frac{(1-C_6^2/2)p_1' \log n}{n}} \quad \text{(by Equation (19))} \\ &\geq C_8 \sqrt{\frac{p_1'}{n}}. \quad \text{(for $n$ large enough)} \end{align*} $$

Now consider the case $\delta(j) \geq \sqrt{\frac{2(p_1+p_2)}{h}}$. By Lemmas 18 and 19, we have that, whenever $\delta(j) \geq \sqrt{\frac{2(p_1+p_2)}{h}}$,

$$ \begin{align*} \delta(j)' &\geq \min \left\{ \left(1 - \frac{1}{1+C_6}\right) p_1', p_1' \right\} \\ &\geq \left(1 - \frac{1}{1+C_6}\right) \sqrt{p_1' \frac{C_7 \log n}{n}} \quad \left( p_1' \geq C_7 \frac{\log n}{n} \right) \\ &\geq C_8 \sqrt{\frac{p_1'}{n}}, \quad \text{(for $n$ large enough)} \end{align*} $$

with probability $1 - \frac{2}{n^4}$. These conclude the proof of Lemma 21. $\square$

*Proof of Claim 25.* Let $P_X = \sum_{j \in X} p_j$, and $P'_X = \sum_{j \in X} p'_j$, for $X = I, J, K$. For $j \in I$, by the hypothesis, we have that

$$ p'_{j} < p'_{1} - (p_{1} - p_{j}). $$
Hence,

$$P'_{I} = \sum_{j \in I} p'_{j} < \sum_{j \in I} p'_{1} - (p_{1} - p_{j}) < |I|(p'_{1} - p_{1}) + P_{I}. \quad (27)$$

For $j \in J$, by the hypothesis, we have that

$$p'_{j} < p'_{1} \cdot \frac{p_{j}}{p_{1}}.$$

Hence,

$$P'_{J} = \sum_{j \in J} p'_{j} < \sum_{j \in I} p'_{1} \cdot \frac{p_{j}}{p_{1}} < p'_{1} \frac{P_{J}}{p_{1}}. \quad (28)$$

By the fact the probabilities sum to 1, and by Equations (27) and (28), we have

$$1 = p'_{1} + P'_{I} + P'_{J} < p'_{1} + |I|(p'_{1} - p_{1}) + P_{I} + p'_{1} \frac{P_{J}}{p_{1}} = p'_{1}(1 + |I| + \frac{P_{J}}{p_{1}}) - |I|p_{1} + P_{I}.$$

Since $P_J = 1 - p_1 - P_I - P_K > 1 - p_1 - P_I$, this implies that

$$1 + |I|p_{1} - P_{I} < p'_{1} \left( 1 + |I| + \frac{1 - p_{1} - P_{I}}{p_{1}} \right) = p'_{1} \left( |I| + \frac{1 - P_{I}}{p_{1}} \right),$$

which implies that

$$p'_{1} > \frac{1 + |I|p_{1} - P_{I}}{|I| + \frac{1 - P_{I}}{p_{1}}} = p_{1}.$$

This concludes the proof of Claim 25. □

## B Tools

**Lemma 27** (Multiplicative forms of Chernoff bounds [20]). Let $X_1, \dots, X_n$ be independent binary random variables. Let $X = \sum_{i=1}^{n} X_i$ and $\mu = \mathbb{E}[X]$. Then:

1. For any $\delta \in (0, 1)$ and any $\mu \le \mu_+ \le n$, it holds that

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

2. For any $\delta \in (0, 1)$ and any $0 \le \mu_- \le \mu$, it holds that

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

**Lemma 28** (Hoeffding bounds [32]). Let $a < b$ be two constants, and $X_1, \dots, X_n$ be independent binary random variables such that $\Pr(a \le X_i \le b) = 1$ for all $i \in [n]$. Let $X = \sum_{i=1}^{n} X_i$ and $\mu = \mathbb{E}[X]$. Then:

1. For any $t > 0$ and any $\mu \le \mu_+$, it holds that

$$\Pr(X \ge \mu_{+} + t) \le \exp\left(-\frac{2t^2}{n(b-a)^2}\right).$$

2. For any $t > 0$ and any $0 \le \mu_- \le \mu$, it holds that

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

**Lemma 29** (Bernstein Inequality [20]). Let $X_1, X_2, \dots, X_n$ be i.i.d. random variables such that $|X_i - \mathbb{E}[X_i]| \le C$ and $|\mathbb{E}[X_i]| \le 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(|S_n| \ge t) \le 2 \exp \left( - \frac{t^2}{2n\mathrm{Var}(X_1) + \frac{2Ct}{3}} \right).$$