1 Introduction

As illustrated by the popular Axelrod model [1], opinion and cultural dynamics are driven by two key components: social influence, the tendency of individuals to become more similar when they interact, and homophily, the tendency to interact more frequently with individuals who are more similar [4]. Another important component in the context of social dynamics is the topology of the social network whose connections indicate who interacts with whom, an aspect that is well captured by stochastic models known as interacting particle systems [27, 29].

The voter model The simplest example of interacting particle system modeling the dynamics of opinions is the voter model introduced independently in [5, 15]. Individuals located on the vertices of a connected graph (interpreted as a social network) are characterized by one of two competing opinions, and update their opinion independently at rate one by mimicking one of their neighbors chosen uniformly at random. In particular, this model accounts for the topology of the social network as well as social influence, but not homophily. Most of the results about the voter model rely on a duality relationship with a system of coalescing random walks. When the individuals are located on the d-dimensional integer lattice, the system clusters, and so a local consensus is reached, in dimensions \(d \le 2\), whereas the process converges to a nontrivial stationary distribution, and so the two opinions coexist at equilibrium, in higher dimensions [15]. The asymptotic behavior of the cluster size for the one- and the two-dimensional voter models is studied in [3, 7]. In higher dimensions, even though the two opinions coexist at equilibrium, as time evolves, spatial correlations build up due to the presence of local interactions. The spatial correlations in the infinite time limit are studied in [2, 31]. On finite connected graphs, the voter model always reaches a consensus, and the time to consensus on the large d-dimensional torus is studied in [6].

Threshold voter models Natural variants of the voter model that also describe the dynamics of opinions on social networks are the threshold voter models. In this case, individuals switch their opinion at rate one if and only if they disagree with at least \(\theta \) of their neighbors. Looking again at the process on the d-dimensional integer lattice, when the threshold is equal to one, coexistence occurs except in one dimension [28]. While increasing the threshold \(\theta \), the process exhibits two phase transitions, from coexistence to clustering, and then from clustering to fixation where both opinions again coexist, but coexistence is now due to the system becoming frozen locally as opposed to convergence to a unique nontrivial stationary distribution. Fixation occurs in particular when the individuals switch their opinion if and only if they disagree with a strict majority of their neighbors [9], a particular case referred to as the majority vote model.

The majority rule model Another process related to the majority vote model that includes the simultaneous updates of multiple individuals is the majority rule model [10]. In the original version of this model, the population is finite, individuals are again characterized by one of two competing opinions, and a single update consists in choosing a random number of individuals uniformly (referred to as a discussion group), which results in all the individuals in the group adopting the majority opinion within the group before the interaction. In case of a tie, all the individuals adopt a preferred opinion representing the status quo. A spatial version of the majority rule model where individuals are located on the integer lattice is introduced in [19]. The discussion groups consist of all the \(n \times \cdots \times n\) hypercubes and are chosen to be updated independently at rate one. In this case, the behavior depends on the parity of n: the system clusters with the density of each opinion being preserved when n is odd whereas the status quo wins when n is even.

The Axelrod model The classical and threshold voter models and the majority rule model account for social influence but not homophily, the tendency to interact more frequently with individuals who are more similar. The most popular interacting particle system that includes both social influence and homophily is the Axelrod model [1]. Individuals are now characterized by one of q possible opinions about F different issues, which results in \(q^F\) possible vectors of opinions representing cultural profiles. Homophily is modeled by assuming that neighbors interact at a rate equal to the fraction of opinions or cultural features they have in common while social influence is modeled by matching one of the opinions the two neighbors do not share, if any. Depending on the values of F and q, the system either clusters so that a local consensus is reached or fixates in a fragmented configuration where disagreements persist. Intuitively, increasing the value of F promotes consensus while increasing the value of q promotes discordance. For the one-dimensional model where the individuals are located on the integers, consensus is studied in [16, 23] while discordance is studied in [20]. See also [26] for a study of the two-dimensional process.

Constrained voter models Homophily in the Axelrod model is incorporated by assuming that the rate at which individuals interact is proportional to the amount of agreement between neighbors. In many other models, this component is modeled instead through the inclusion of a so-called confidence threshold: neighbors either interact at a constant rate or do not interact at all depending on whether their level of disagreement is within a reasonable threshold or not. The simplest such model is the constrained voter model [30] where individuals are either leftist, centrist or rightist, and mimic a randomly chosen neighbor unless one of the individuals is leftist and the other one rightist. This model has been generalized in [22] where the set of opinions is represented by the vertices of a general finite connected graph and where the level of disagreement is measured using the geodesic distance on the opinion graph: neighbors interact at rate one, which results in one neighbor mimicking the other neighbor if and only if the geodesic distance (or graph distance) between their opinions does not exceed some confidence threshold \(\tau \). It is proved in [22] that the one-dimensional process clusters when the confidence threshold exceeds the radius of the opinion graph while sufficient conditions for fixation in a fragmented configuration are also given. A lower bound for the probability of consensus for the process where individuals are located on a finite connected graph is derived in [12]. The constrained voter model [30] corresponds to the particular case where the opinion graph consists of the path with three vertices and two edges and where \(\tau = 1\) while the particular case where the opinion graph consists of the hypercube with \(2^n\) vertices is referred to as the vectorial Deffuant model introduced in [8] and studied in [21].

The Deffuant model In another (more popular) version of the Deffuant model [8], the opinion space is uncountable and consists of the unit interval. Edges become active independently at rate one and the two individuals connected by that edge interact if and only if the distance between their opinions does not exceed some confidence threshold \(\tau \), which results in the two neighbors’ opinions getting closer to each other. If the opinions are initially independent and uniform, it is conjectured that the system on infinite graphs converges to a consensus when \(\tau > 1/2\) whereas disagreements persist when \(\tau < 1/2\). This conjecture was first established in [17] for the one-dimensional process while [11] gave an alternative simpler proof. Multivariate versions of the model where the opinion space consists of a bounded convex subset of a normed vector space are also studied in [14] for the one-dimensional system and in [18] for the process on general finite connected graphs.

The Hegselmann–Krause model The Hegselmann–Krause (HK) model [13] is a general interacting particle system. The opinion space again consists of the unit interval but, in contrast with the Deffuant model which evolves via pairwise interactions, the new opinion at a vertex x is now replaced by a weighted average of all the opinions in the population that are within some confidence threshold \(\tau \) of the opinion at x. General conditions under which certain initial configurations and certain sets of parameters can lead to asymptotic stability and/or consensus are discussed in [24, 25]. In the version of the HK-model considered in [4], the matrix of the weights between individuals is chosen to be the adjacency matrix of a graph (the weight is one if the two individuals are connected by an edge and zero otherwise) thus inducing an opinion dynamics on a social network: Individuals are located on the vertices of a graph representing a social network, and each update at vertex x results in the new opinion at x to be the average of the opinions of the neighbors that are compatible with x (at opinion distance less than \(\tau \)). The objective of this paper is to derive a lower bound for the probability of consensus for a multivariate version of this model.

2 Model Description and Results

To define the model rigorously, let \(\mathscr {G}= (\mathscr {V}, \mathscr {E})\) be a finite connected graph representing a social network: each vertex is occupied by an individual and any two individuals are connected by an edge if and only if they are socially connected or acquainted. Individuals are characterized by their opinion, and we assume that the opinions are initially independent and distributed across a bounded convex subset \(\Delta \subset \mathbb {R}^n\), thus extending the opinion space [0, 1] of the original HK-model. To measure the disagreements between two neighbors, meaning from now on two individuals who are acquainted, and define the dynamics of the process, we also assume that \(\mathbb {R}^n\) is equipped with an arbitrary norm \(|\!|\cdot |\!|\). The state of the process at time t is a configuration of opinions

$$\begin{aligned} \xi _t : \mathscr {V}\rightarrow \Delta \quad \hbox {where} \quad \xi _t (x) = \hbox {opinion at vertex}~x~\hbox { at time}~t. \end{aligned}$$

Having a confidence threshold \(\tau > 0\), two neighbors are said to be compatible at time t if the distance (induced by the norm) between their opinions does not exceed this threshold, and we denote by \(N_t (x)\) the set of neighbors of x that are compatible with x, i.e.,

$$\begin{aligned} N_t (x) = \{y \in \mathscr {V}: (x, y) \in \mathscr {E}\ \hbox {and} \ |\!|\xi _t (x) - \xi _t (x)|\!| \le \tau \}. \end{aligned}$$
(1)

The process we study evolves as follows: Individuals update their opinion independently at a rate equal to the number of their compatible neighbors, the new opinion being equal to the average opinion of their compatible neighbors. More precisely, letting \(\mathscr {F}_t\) be the natural filtration of the process, we assume that

$$\begin{aligned} \lim _{\epsilon \rightarrow 0} \ \frac{1}{\epsilon } \ P \bigg (\xi _{t + \epsilon } (x) = \frac{1}{|N_t (x)|} \sum _{y \in N_t (x)} \xi _t (y) \ \Big | \ \mathscr {F}_t \bigg ) = |N_t (x)| \end{aligned}$$
(2)

when \(N_t (x) \ne \varnothing \) whereas the transition rate is zero when x has no compatible neighbors. These transitions indicate that the individuals are open-minded in the sense that the new opinion only depends on the opinions of the compatible neighbors. Following [24, 25], we can include more realistically a degree of stubbornness by assuming that the new opinion is given by

$$\begin{aligned} \alpha \,\xi _t (x) + \frac{1 - \alpha }{|N_t (x)|} \sum _{y \in N_t (x)} \xi _t (y) \quad \hbox {where} \quad 0 \le \alpha < 1. \end{aligned}$$

The parameter \(\alpha \) represents the degree of stubbornness of the individuals. To simplify the algebra, we assume from now on that \(\alpha = 0\), which corresponds to model (2), but we point out that all our proofs and our main result easily extend to the model with stubbornness. Indeed, when \(0< \alpha < 1\), each update results in an individual’s opinion moving closer to the average opinion of its compatible neighbors, and only this aspect of the dynamics is used throughout our proofs.

The main objective is to study the probability of consensus, i.e., the probability that all the opinions converge to the same limit, when starting from a configuration where the opinions are independent, identically distributed with values in the opinion space \(\Delta \). Because the opinion space is uncountable, it is also natural to assume that the initial distribution is continuous. Under this assumption, replacing the large inequality in (1) by a strict inequality, i.e., assuming that neighbors at exactly opinion distance \(\tau \) from each other are incompatible, does not change the behavior of the process. Indeed, for any given opinion \(c \in \Delta \), because the initial opinions are independent continuous random variables, the probability that an individual has initially or at any time exactly opinion c is equal to zero. It follows that the probability of two neighbors being exactly at opinion distance \(\tau \) (or any given positive real number) of each other is equal to zero so our model and the model with a strict inequality are equal with probability one. There is however a positive probability that two neighbors have the exact same opinion (opinion distance zero), which occurs when there is an update at a vertex that has exactly one compatible neighbor. To state our result, let

$$\begin{aligned} \begin{array}{l} \mathscr {C}= \Big \{\lim _{t \rightarrow \infty } \max _{x, y \in \mathscr {V}} |\!|\xi _t (x) - \xi _t (y)|\!| = 0 \Big \} \end{array} \end{aligned}$$

be the consensus event. We also define

$$\begin{aligned} \begin{array}{rcl} \mathbf {r}&{} = &{} \inf \{r> 0 : \Delta \subset B (c, r) \ \hbox {for some} \ c \in \Delta \} \\ &{} = &{} \inf \{r > 0 : \sup _{a \in \Delta } |\!|a - c|\!| \le r \ \hbox {for some} \ c \in \Delta \}, \end{array} \end{aligned}$$

which can be viewed as the radius of the opinion space, and

$$\begin{aligned} \mathbf {c}\in \Delta \quad \hbox {such that} \quad \Delta \subset B (\mathbf {c}, \mathbf {r}), \end{aligned}$$

which can be viewed as the center of the opinion space. Throughout this paper, we also assume that the opinions across the social network are initially independent and identically distributed, and we let X be the \(\Delta \)-valued random variable describing the initial opinions:

$$\begin{aligned} P (\xi _0 (x) \in B) = P (X \in B) \quad \hbox {for all} \quad x \in \mathscr {V}\ \hbox {and} \ \hbox {Borel set} \ B \subset \Delta . \end{aligned}$$

Then, we have the following universal lower bound that holds uniformly over all possible finite connected graphs (social networks).

Theorem 1

(probability of consensus) For all \(\tau > \mathbf {r}\), \(P (\mathscr {C}) \ge 1 - E \,|\!|X - \mathbf {c}|\!| / (\tau - \mathbf {r})\).

This result is identical to [18, Theorem 2.1] which applies to the Deffuant model. However, because the HK dynamics is significantly different from the Deffuant dynamics, our proof is quite different from the proof in [18].

To begin with, we prove that, for all \(c \in \mathbb {R}^n\), the process \(X_t (c)\) that keeps track of the total disagreement between a virtual external agent with opinion c and the vertices of the graph is a supermartingale (Lemma 1). Looking at \(2^n\) of these processes for values of c that surround the opinion space and applying the martingale convergence theorem, we deduce that the opinion model converges almost surely to a random configuration \(\xi _{\infty }\) (Lemma 2). The evolution rules of the HK-model imply that, in the configuration \(\xi _{\infty }\), any two neighbors on the social network either completely agree or disagree by more than the confidence threshold \(\tau \) (Lemma 3). Using this characterization, we deduce that, for all \(\epsilon > 0\), the first time \(T_{\epsilon }\) at which any two neighbors disagree by at most \(\epsilon \) or at least \(\tau \) is almost surely finite (Lemma 4). Note that the assumption \(\tau > \mathbf {r}\) means that, regardless of their opinion, all the individuals are compatible with the center of the opinion space. In particular, a stubborn individual with that opinion would lead the system to a consensus. Using this idea, we prove that the event \(\mathscr {A}\) that the opinion at a vertex is at distance less than \(\tau - \mathbf {r}\) from the center \(\mathbf {c}\) of the opinion space at time \(T_{\epsilon }\) for some \(\epsilon \) small always drives the process to a global consensus (Lemma 5). Applying the optional stopping theorem to the bounded supermartingale \(X_t (\mathbf {c})\) stopped at time \(T_{\epsilon }\) gives a lower bound for the probability of \(\mathscr {A}\) (Lemma 6) which, together with Lemma 5, implies the theorem.

Numerical example Before going into the details of the proof, we give a numerical example to show how our result applies to the original HK-model. Assume that the opinion space is

$$\begin{aligned} \Delta = B (a, r) = \{c \in \mathbb {R}^n : |\!|a - c|\!| < r \}, \end{aligned}$$

the ball with center a and radius r, and that the opinions are initially independent and uniformly distributed: \(X = {{\,\mathrm{Uniform}\,}}(\Delta )\). Then, \(\mathbf {c}= a\) and \(\mathbf {r}= r\). In addition, for all \(s \le r\),

$$\begin{aligned} P (|\!|X - a|\!| \le s) = P (X \in B (a, s)) = \frac{\lambda (B (0, s))}{\lambda (B (0, r))} = \frac{s^n \,\lambda (B (0, 1))}{r^n \,\lambda (B (0, 1))} = \bigg (\frac{s}{r} \bigg )^n \end{aligned}$$

where \(\lambda (B)\) refers to the Lebesgue measure of set \(B \subset \mathbb {R}^n\). It follows that

$$\begin{aligned} E \,|\!|X - a|\!| = \int _0^{\infty } P (|\!|X - a|\!| > s) \,ds = \int _0^r \bigg (1 - \bigg (\frac{s}{r} \bigg )^n \bigg ) \,ds = \frac{nr}{n + 1}. \end{aligned}$$

Therefore, the theorem implies that

$$\begin{aligned} P (\mathscr {C}) \ge 1 - \frac{E \,|\!|X - \mathbf {c}|\!|}{\tau - \mathbf {r}} = 1 - \frac{E \,|\!|X - a|\!|}{\tau - r} = 1 - \frac{nr}{(n + 1)(\tau - r)} \quad \hbox {when} \quad \Delta = B (a, r). \end{aligned}$$

In particular, for the original HK-model (\(n = 1\) and \(a = r = 1/2\)),

$$\begin{aligned} P (\mathscr {C}) \ge \frac{4 \tau - 3}{4 \tau - 2}> 0 \quad \hbox {for all} \quad \tau > 3/4 \quad \hbox {when} \quad \Delta = [0, 1]. \end{aligned}$$

3 Underlying Supermartingales

In this section, we prove that the processes that keep track of the total disagreement between a fixed point c and the model’s opinions, i.e.,

$$\begin{aligned} X_t (c) = \sum _{x \in \mathscr {V}} \,|\!|\xi _t (x) - c \,|\!| \quad \hbox {for all} \quad c \in \mathbb {R}^n, \end{aligned}$$

are supermartingales. Applying the martingale convergence theorem to these supermartingales will show almost sure convergence of the HK-model to a limiting configuration \(\xi _{\infty }\). This result will also be used later in combination with the optional stopping theorem to derive the lower bound for the probability of consensus in the theorem.

Lemma 1

The processes \(X_t (c)\) are supermartingales for the filtration \(\mathscr {F}_t\).

Proof

Let \(\mathscr {V}_t\) be the set of vertices with at least one compatible neighbor, i.e., at least one neighbor at opinion distance at most \(\tau \) of the vertex. To simplify the notation, we let

$$\begin{aligned} {{\bar{\xi }}}_t (x) = \frac{1}{|N_t (x)|} \sum _{y \in N_t (x)} \xi _t (y) \quad \hbox {for all} \quad x \in \mathscr {V}_t. \end{aligned}$$

By the absolute homogeneity of the norm and the triangle inequality, for all \(x \in \mathscr {V}_t\),

$$\begin{aligned} \begin{array}{l} \displaystyle |N_t (x)| \cdot |\!|{\bar{\xi }}_t (x) - c \,|\!| = \displaystyle |N_t (x)| \cdot \bigg |\!\bigg |\frac{1}{|N_t (x)|} \sum _{y \in N_t (x)} \xi _t (y) - c \, \,\bigg |\!\bigg | \\ = \displaystyle \bigg |\!\bigg |\sum _{y \in N_t (x)} \xi _t (y) - |N_t (x)| \cdot c \, \,\bigg |\!\bigg | = \displaystyle \bigg |\!\bigg |\sum _{y \in N_t (x)} (\xi _t (y) - c) \, \,\bigg |\!\bigg | \le \sum _{y \in N_t (x)} |\!|\xi _t (y) - c \,|\!|. \end{array} \end{aligned}$$

In particular, recalling the transition rates of the HK-model, we get

$$\begin{aligned} \begin{array}{rcl} \displaystyle \lim _{\epsilon \rightarrow 0} \,E \bigg (\frac{X_{t + \epsilon } (c) - X_t (c)}{\epsilon } \ \Big | \ \mathscr {F}_t \bigg ) &{} = &{} \displaystyle \sum _{x \in \mathscr {V}_t} \,|N_t (x)| \cdot \Big (|\!|{\bar{\xi }}_t (x) - c \,|\!| - |\!|\xi _t (x) - c \,|\!| \Big ) \\ &{} = &{} \displaystyle \sum _{x \in \mathscr {V}_t} \left( \left( \sum _{y \in N_t (x)} |\!|\xi _t (y) - c \,|\!| \right) - |N_t (x)| \cdot |\!|\xi _t (x) - c \,|\!| \right) . \end{array} \end{aligned}$$

To conclude, observe that

$$\begin{aligned} \begin{array}{rcl} |\{x \in \mathscr {V}_t : y \in N_t (x) \}| &{} = &{} |\{x : (x, y) \in \mathscr {E}\ \hbox {and} \ |\!|\xi _t (x) - \xi _t (y)|\!| \le \tau \}| \\ &{} = &{} |\{x : (y, x) \in \mathscr {E}\ \hbox {and} \ |\!|\xi _t (y) - \xi _t (x)|\!| \le \tau \}| = |N_t (y)|. \end{array} \end{aligned}$$

In other words, the number of vertices x such that y is in the neighborhood of x and compatible with x at time t is equal to the number of vertices that are in the neighborhood of y and compatible with y at that time. It follows that

$$\begin{aligned} \displaystyle \lim _{\epsilon \rightarrow 0} \,E \bigg (\frac{X_{t + \epsilon } (c) - X_t (c)}{\epsilon } \ \Big | \ \mathscr {F}_t \bigg )\le & {} \displaystyle \sum _{x \in \mathscr {V}_t} \left( \sum _{y \in N_t (x)} |\!|\xi _t (y) - c \,|\!| \right) \\&- \sum _{x \in \mathscr {V}_t} \,|N_t (x)| \cdot |\!|\xi _t (x) - c \,|\!| \\= & {} \displaystyle \sum _{y \in \mathscr {V}_t} |N_t (y)| \cdot |\!|\xi _t (y) - c \,|\!| \\&- \sum _{x \in \mathscr {V}_t} \,|N_t (x)| \cdot |\!|\xi _t (x) - c \,|\!| = 0, \end{aligned}$$

which proves that \(X_t (c)\) is a supermartingale. \(\square \)

Using Lemma 1, we now prove almost sure convergence of the HK-model.

Lemma 2

There is a random configuration \(\xi _{\infty } : \mathscr {V}\rightarrow \Delta \) such that

$$\begin{aligned} \lim _{t \rightarrow \infty } \xi _t (x) = \xi _{\infty } (x) \quad \hbox {almost surely} \quad \hbox {for all} \ x \in \mathscr {V}. \end{aligned}$$

Proof

Let \(r > 0\) be sufficiently large that \(\Delta \subset \Lambda = [- r, r]^n\) (see Figure 1). Assuming that the configuration \(\xi _t\) does not converge, there exists \(\epsilon > 0\) such that

$$\begin{aligned} \max _{x \in \mathscr {V}} |\!|\xi _t (x) - \xi _{t-} (x)|\!|_1 = \max _{x \in \mathscr {V}} \ \sum _{i = 1}^n \,|\langle \xi _t (x) - \xi _{t-} (x), e_i \rangle | > \epsilon \quad \hbox {at arbitrary large times}\nonumber \\ \end{aligned}$$
(3)

where \(e_i = (0, \ldots , 0, 1, 0, \ldots , 0)\) denotes the ith unit vector in \(\mathbb {R}^n\) and where \(\xi _{t-} (x)\) refers to the opinion at vertex x just before time t. By the choice of r and by the equivalence of the norms in finite dimension, there exists \(m_1 > 0\) such that, for at least one of the corners of the n-dimensional cube \(\Lambda \), say corner c,

$$\begin{aligned} \begin{array}{rcl} |X_t (c) - X_{t-} (c)| &{} \ge &{} m_1 \,\max _{x \in \mathscr {V}} ||\!|\xi _t (x) - c \,|\!|_1 - |\!|\xi _{t-} (x) - c \,|\!|_1| \\ &{} = &{} m_1 \,\max _{x \in \mathscr {V}} |\!|\xi _t (x) - \xi _{t-} (x)|\!|_1> \epsilon m_1 > 0. \end{array} \end{aligned}$$

In particular, for at least one corner c,

$$\begin{aligned} |X_t (c) - X_{t-} (c)| > \epsilon m_1 \quad \hbox {at arbitrary large times}, \end{aligned}$$
(4)

showing that \(X_t (c)\) does not converge. Now, using again the equivalence of the norms, there exists \(m_2 < \infty \) such that the process is bounded by

$$\begin{aligned} |X_t (c)| \le \max _{a \in \Delta } |\!|a - c \,|\!| {{\,\mathrm{card}\,}}(\mathscr {V}) \le m_2 \,\max _{a, b \in \Lambda } |\!|a - b|\!|_1 {{\,\mathrm{card}\,}}(\mathscr {V}) = 2nr m_2 {{\,\mathrm{card}\,}}(\mathscr {V}) < \infty . \end{aligned}$$

Because the process \(X_t (c)\) is also a supermartingale according to Lemma 1, it follows from the martingale convergence theorem that it converges almost surely. In particular, the events in (3) and (4) and the divergence of \(\xi _t\) occur with probability zero, which proves the lemma. \(\square \)

To study the limiting configuration \(\xi _{\infty }\), we now let \(\mathscr {G}_{\infty } = (\mathscr {V}, \mathscr {E}_{\infty })\) be the random subgraph of the social network \(\mathscr {G}\) induced by the edges that are compatible in the limit:

$$\begin{aligned} (x, y) \in \mathscr {E}_{\infty } \quad \hbox {if and only if} \quad (x, y) \in \mathscr {E}\quad \hbox {and} \quad |\!|\xi _{\infty } (x) - \xi _{\infty } (y)|\!| \le \tau . \end{aligned}$$
(5)

The next lemma shows that, in the limiting configuration, individuals on the same connected component of the graph \(\mathscr {G}_{\infty }\) share the same opinion.

Fig. 1
figure 1

Picture related to the proof of Lemmas 2 and 3

Full size image

Lemma 3

Configuration \(\xi _{\infty }\) is constant on each of the connected components of \(\mathscr {G}_{\infty }\).

Proof

Let \(\mathscr {G}' = (\mathscr {V}', \mathscr {E}')\) be a connected component of the graph \(\mathscr {G}_{\infty }\), and observe that, because \(\xi _{\infty }\) is an absorbing state for the HK-model, it follows from the evolution rules that

$$\begin{aligned} N_{\infty } (x) = \lim _{t \rightarrow \infty } N_t (x) = \varnothing \quad \hbox {or} \quad \xi _{\infty } (x) = \frac{1}{{{\,\mathrm{card}\,}}(N_{\infty } (x))} \sum _{y \in N_{\infty } (x)} \xi _{\infty } (y) \end{aligned}$$

for all \(x \in \mathscr {V}\). When \(\mathscr {V}'\) reduces to one vertex, \(\xi _{\infty }\) is trivially constant on \(\mathscr {V}'\). Otherwise, because the subgraph \(\mathscr {G}'\) is connected and all its edges are compatible in the limit, we have

$$\begin{aligned} N_{\infty } (x) \ne \varnothing \quad \hbox {so} \quad \xi _{\infty } (x) = \frac{1}{{{\,\mathrm{card}\,}}(N_{\infty } (x))} \sum _{y \in N_{\infty } (x)} \xi _{\infty } (y) \quad \hbox {for all} \quad x \in \mathscr {V}'. \end{aligned}$$
(6)

In this case, let K be the convex envelope of the limiting opinions in \(\mathscr {V}'\),

$$\begin{aligned} K = {{\,\mathrm{Conv}\,}}\{\xi _{\infty } (z) : z \in \mathscr {V}' \} \subset \Delta , \end{aligned}$$

and let \(\xi _{\infty } (x) \in K\), \(x \in \mathscr {V}'\), be an extreme point of K, i.e., a point which is not an inner point of segments of the convex envelope (see Fig. 1). Now, assume by contradiction that

$$\begin{aligned} \xi _{\infty } (y) \ne \xi _{\infty } (x) \quad \hbox {for some} \quad y \in N_{\infty } (x). \end{aligned}$$
(7)

Then, it follows from (6) that

$$\begin{aligned} \xi _{\infty } (x) \in {{\,\mathrm{Int}\,}}(K') \quad \hbox {where} \quad K' = {{\,\mathrm{Conv}\,}}\{\xi _{\infty } (y) : y \in N_{\infty } (x) \}. \end{aligned}$$
(8)

Here, \({{\,\mathrm{Int}\,}}(K')\) refers to the interior of the set \(K'\). Because

$$\begin{aligned} N_{\infty } (x) \subset \mathscr {V}' \quad \hbox {and so} \quad K' \subset K, \end{aligned}$$

we deduce from (8) that \(\xi _{\infty } (x) \in {{\,\mathrm{Int}\,}}(K)\), contradicting the fact that \(\xi _{\infty } (x)\) is an extreme point of the convex set K. This shows that the statement in (7) is false therefore all the neighbors of x on the connected component must share the same opinion as x in the limit. This also implies that the neighbors’ opinions are (identical) extreme points of K so, by the same reasoning, the neighbors of the neighbors of x must share the same opinion as x, and using a simple induction, we deduce that the convex envelope reduces to one point: \(K = \{\xi _{\infty } (x) \}\), which proves the lemma. \(\square \)

Note that the proof of the lemma can be simplified when dealing with the original HK-model, where \(\Lambda = (0, 1)\) and \(|\!|\cdot |\!|\) refers to the Euclidean norm, using that, according to (6), the restriction of the limiting configuration to each of the connected components of \(\mathscr {G}_{\infty }\) is harmonic. Indeed, in this case, let \(x \in \mathscr {V}'\) be a vertex where \(\xi _{\infty }\) reaches its maximum:

$$\begin{aligned} \xi _{\infty } (x) = \max \{\xi _{\infty } (z) : z \in \mathscr {V}' \}. \end{aligned}$$

Then, because \(\xi _{\infty } (x) \ge \xi _{\infty } (y)\) for all \(y \in N_{\infty } (x) \subset \mathscr {V}'\) and

$$\begin{aligned} \frac{1}{{{\,\mathrm{card}\,}}(N_{\infty } (x))} \sum _{y \in N_{\infty } (x)} (\xi _{\infty } (x) - \xi _{\infty } (y)) = \xi _{\infty } (x) - \frac{1}{{{\,\mathrm{card}\,}}(N_{\infty } (x))} \sum _{y \in N_{\infty } (x)} \xi _{\infty } (y) = 0, \end{aligned}$$

we must have \(\xi _{\infty } (x) = \xi _{\infty } (y)\) for all \(y \in N_{\infty } (x)\).

4 Optional Stopping and Consensus

As previously mentioned, the next step to prove the theorem is to apply the optional stopping theorem to the supermartingale \(X_t (\mathbf {c})\). In order to apply the optional stopping theorem, we also define the collection of stopping times

$$\begin{aligned} T_{\epsilon } = \inf \,\{t : |\!|\xi _t (x) - \xi _t (y)|\!| \not \in [\epsilon , \tau ] \ \hbox {for all} \ (x, y) \in \mathscr {E}\} \quad \hbox {for all} \quad \epsilon \in (0, \tau ). \end{aligned}$$

The next lemma shows that these stopping times are almost surely finite, which is one of the required assumptions to apply the optional stopping theorem.

Lemma 4

For all \(\epsilon \in (0, \tau )\), time \(T_{\epsilon }\) is almost surely finite.

Proof

On the event that \(T_{\epsilon } = \infty \), there exists \((x, y) \in \mathscr {E}\) such that

$$\begin{aligned} |\!|\xi _t (x) - \xi _t (y)|\!| \in [\epsilon , \tau ] \quad \hbox {at arbitrary large times}. \end{aligned}$$
(9)

This, together with Lemma 2, implies that

$$\begin{aligned} |\!|\xi _{\infty } (x) - \xi _{\infty } (y)|\!| = \lim _{t \rightarrow \infty } |\!|\xi _t (x) - \xi _t (y)|\!| \in [\epsilon , \tau ]. \end{aligned}$$
(10)

Observing also that, by the definition of \(\mathscr {E}_{\infty }\) in (5),

$$\begin{aligned} \begin{array}{rcl} (x, y) \in \mathscr {E}\ \hbox {and} \ |\!|\xi _{\infty } (x) - \xi _{\infty } (y)|\!| \le \tau &{} \Longrightarrow &{} (x, y) \in \mathscr {E}_{\infty } \\ |\!|\xi _{\infty } (x) - \xi _{\infty } (y)|\!| \ge \epsilon &{} \Longrightarrow &{} \xi _{\infty } (x) \ne \xi _{\infty } (y), \end{array} \end{aligned}$$

we deduce that the limiting configuration \(\xi _{\infty }\) is not constant on the connected components of the random graph \(\mathscr {G}_{\infty }\) which, according to Lemma 3, is an event with probability zero. In conclusion, the events in (9) and (10) and the event that \(T_{\epsilon } = \infty \) all have probability zero. \(\square \)

Next, we prove that if, at time \(T_{\epsilon }\) for \(\epsilon \) small, the opinion of at least one vertex is close enough to the center \(\mathbf {c}\) of the opinion space, an event that we call \(\mathscr {A}\), then all the opinions across the network should be close to that opinion. This, together with a convexity argument and Lemma 3, implies consensus. In particular, the probability of consensus is larger than the probability of \(\mathscr {A}\), which will be used later to deduce the theorem.

Lemma 5

For all \(\epsilon ' \in (0, \tau / 2)\) and \(\tau > \mathbf {r}+ \epsilon '\), there is \(\epsilon > 0\) such that

$$\begin{aligned} \mathscr {A}= \mathscr {A}(\epsilon , \epsilon ') = \Big \{|\!|\xi _{T_{\epsilon }} (x) - \mathbf {c}|\!| < \tau - \mathbf {r}- \epsilon ' \ \hbox {for some} \ x \in \mathscr {V}\Big \} \subset \mathscr {C}. \end{aligned}$$

Proof

First, we observe that, on the event \(\mathscr {A}\), for all \(y \in \mathscr {V}\),

$$\begin{aligned} |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (y)|\!| \le |\!|\xi _{T_{\epsilon }} (x) - \mathbf {c}|\!| + |\!|\xi _{T_{\epsilon }} (y) - \mathbf {c}|\!| < \tau - \mathbf {r}- \epsilon ' + \mathbf {r}= \tau - \epsilon '. \end{aligned}$$
(11)

Now, we prove by induction that, on the event \(\mathscr {A}\),

$$\begin{aligned} |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (y)|\!| \le d (x, y) \,\epsilon \quad \hbox {for all} \quad y \in \mathscr {V}\quad \hbox {when} \quad \epsilon = \epsilon ' / {{\,\mathrm{card}\,}}(\mathscr {V}). \end{aligned}$$
(12)

Here, d(x, y) refers to the graph distance between vertex x and vertex y.

Base case Assume that \(d (x, y) = 0\). Then,

$$\begin{aligned} y = x \quad \hbox {and} \quad |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (y)|\!| = 0 = 0 \times \epsilon . \end{aligned}$$

Induction step: Let \(y \ne x\) and \(d = d (x, y)\) and assume that (12) holds for all vertices at graph distance \(d - 1\) from vertex x. Letting z be a neighbor of y at distance \(d - 1\) from x,

$$\begin{aligned} |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (z)|\!| \le (d - 1) \,\epsilon . \end{aligned}$$
(13)

Because the longest self-avoiding path on the social network contains less than \({{\,\mathrm{card}\,}}(\mathscr {V})\) edges, we must have \(d < {{\,\mathrm{card}\,}}(\mathscr {V})\). Assuming by contradiction that \(|\!|\xi _{T_{\epsilon }} (y) - \xi _{T_{\epsilon }} (z)|\!| > \epsilon \). By definition of the stopping time \(T_{\epsilon }\), the two neighbors y and z must be incompatible at that time:

$$\begin{aligned} |\!|\xi _{T_{\epsilon }} (y) - \xi _{T_{\epsilon }} (z)|\!| > \tau . \end{aligned}$$
(14)

Using the triangle inequality, then (11) and (14), we deduce that

$$\begin{aligned} \begin{array}{rcl} |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (z)|\!| &{} \ge &{} |\!|\xi _{T_{\epsilon }} (z) - \xi _{T_{\epsilon }} (y)|\!| - |\!|\xi _{T_{\epsilon }} (y) - \xi _{T_{\epsilon }} (x)|\!| \\ &{} \ge &{} \tau - (\tau - \epsilon ') = \epsilon ' = \epsilon {{\,\mathrm{card}\,}}(\mathscr {V}) > (d - 1) \,\epsilon , \end{array} \end{aligned}$$

which contradicts (13), therefore \(|\!|\xi _{T_{\epsilon }} (y) - \xi _{T_{\epsilon }} (z)|\!| \le \epsilon \) and

$$\begin{aligned} |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (y)|\!| \le |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (z)|\!| + |\!|\xi _{T_{\epsilon }} (y) - \xi _{T_{\epsilon }} (z)|\!| \le (d - 1) \,\epsilon + \epsilon = d \epsilon . \end{aligned}$$

This completes the proof of (12).

Recalling that \(d (x, y) < {{\,\mathrm{card}\,}}(\mathscr {V})\) for all \(y \in \mathscr {V}\), we deduce that, on the event \(\mathscr {A}\),

$$\begin{aligned} |\!|\xi _{T_{\epsilon }} (x) - \xi _{T_{\epsilon }} (y)|\!| < \epsilon {{\,\mathrm{card}\,}}(\mathscr {V}) = \epsilon ' \quad \hbox {and so} \quad \xi _{T_{\epsilon }} (y) \in B (\xi _{T_{\epsilon }} (x), \epsilon ') \quad \hbox {for all} \quad y \in \mathscr {V}. \end{aligned}$$

Since at each update of the process the new opinion is contained in the convex envelope of the other opinions, we deduce that, on the event \(\mathscr {A}\),

$$\begin{aligned} \xi _{\infty } (y) \in {{\,\mathrm{Conv}\,}}\{\xi _{T_{\epsilon }} (z) : z \in \mathscr {V}\} \subset B (\xi _{T_{\epsilon }} (x), \epsilon ') \quad \hbox {and so} \quad |\!|\xi _{\infty } (y) - \xi _{\infty } (z)|\!|< 2 \epsilon ' < \tau \end{aligned}$$

for all \(y, z \in \mathscr {V}\). In conclusion, \(\mathscr {G}_{\infty }\) is connected and \(\mathscr {C}\) occurs by Lemma 3. \(\square \)

The last step to prove the theorem is to apply the optional stopping theorem to the supermartingale \(X_t (\mathbf {c})\) stopped at time \(T_{\epsilon }\) to get a lower bound for the probability of the sub-event \(\mathscr {A}\).

Lemma 6

The event \(\mathscr {A}= \mathscr {A}(\epsilon , \epsilon ')\) defined in Lemma 5 has probability

$$\begin{aligned} P (\mathscr {A}) \ge 1 - E \,|\!|X - \mathbf {c}|\!| / (\tau - \mathbf {r}- \epsilon '). \end{aligned}$$

Proof

Observing that, on the complement of \(\mathscr {A}\),

$$\begin{aligned} |\!|\xi _{T_{\epsilon }} (x) - \mathbf {c}|\!| \ge \tau - \mathbf {r}- \epsilon ' \quad \hbox {for all} \quad x \in \mathscr {V}, \end{aligned}$$

we deduce that the conditional expectation of \(X_{T_{\epsilon }} (\mathbf {c})\) is bounded from below by

$$\begin{aligned} E \left( X_{T_{\epsilon }} (\mathbf {c}) \,| \,\mathscr {A}^c\right) = E \bigg (\sum _{x \in \mathscr {V}} \,|\!|\xi _{T_{\epsilon }} (x) - \mathbf {c}\,|\!| \,\Big | \,\mathscr {A}^c \bigg ) \ge (\tau - \mathbf {r}- \epsilon ') \cdot {{\,\mathrm{card}\,}}(\mathscr {V}). \end{aligned}$$

In particular, conditioning on the partition \(\{\mathscr {A}, \mathscr {A}^c \}\), we get

$$\begin{aligned} \begin{array}{rcl} E (X_{T_{\epsilon }} (\mathbf {c})) &{} = &{} E (X_{T_{\epsilon }} (\mathbf {c}) \,| \,\mathscr {A}) P (\mathscr {A}) + E (X_{T_{\epsilon }} (\mathbf {c}) \,| \,\mathscr {A}^c) P (\mathscr {A}^c) \\ &{} \ge &{} E (X_{T_{\epsilon }} (\mathbf {c}) \,| \,\mathscr {A}^c) P (\mathscr {A}^c) \ge (\tau - \mathbf {r}- \epsilon ') {{\,\mathrm{card}\,}}(\mathscr {V}) P (\mathscr {A}^c). \end{array} \end{aligned}$$
(15)

Because the process \(X_t (\mathbf {c})\) is a (bounded) supermartingale according to Lemma 1 and because \(T_{\epsilon }\) is an almost surely finite stopping time according to Lemma 4, we may apply the optional stopping theorem. This, together with the previous inequality (15), gives

$$\begin{aligned} P (\mathscr {A}) = 1 - P (\mathscr {A}^c) \ge 1 - \frac{E (X_{T_{\epsilon }} (\mathbf {c}))}{(\tau - \mathbf {r}- \epsilon ') {{\,\mathrm{card}\,}}(\mathscr {V})} \ge 1 - \frac{E (X_0 (\mathbf {c}))}{(\tau - \mathbf {r}- \epsilon ') {{\,\mathrm{card}\,}}(\mathscr {V})}. \end{aligned}$$
(16)

Recalling that the opinions across the social network \(\mathscr {G}\) are initially independent and identically distributed with values in the opinion space \(\Delta \), we also have

$$\begin{aligned} E (X_0 (\mathbf {c})) = E \bigg (\sum _{x \in \mathscr {V}} \,|\!|\xi _0 (x) - \mathbf {c}\,|\!| \bigg ) = \sum _{x \in \mathscr {V}} \,E \,|\!|\xi _0 (x) - \mathbf {c}\,|\!| \!=\! E \,|\!|X - \mathbf {c}|\!| \cdot {{\,\mathrm{card}\,}}(\mathscr {V}).\qquad \end{aligned}$$
(17)

The result follows from (16) and (17). \(\square \)

To deduce the theorem, let \(\tau > \mathbf {r}\). Then, for all \(\epsilon ' \in (0, \tau - \mathbf {r})\), we have \(\tau > \mathbf {r}+ \epsilon '\). Therefore, according to Lemmas 5 and 6 , there exists \(\epsilon > 0\) such that

$$\begin{aligned} P (\mathscr {C}) \ge P (\mathscr {A}(\epsilon , \epsilon ')) \ge 1 - E \,|\!|X - \mathbf {c}|\!| / (\tau - \mathbf {r}- \epsilon '). \end{aligned}$$

Because this holds for all \(\epsilon ' > 0\) arbitrary small,

$$\begin{aligned} P (\mathscr {C}) \ge 1 - \lim _{\epsilon ' \rightarrow 0} E \,|\!|X - \mathbf {c}|\!| / (\tau - \mathbf {r}- \epsilon ') = 1 - E \,|\!|X - \mathbf {c}|\!| / (\tau - \mathbf {r}). \end{aligned}$$

This completes the proof of Theorem 1.