# Opinion dynamics on non-sparse networks
with community structure

Panagiotis Andreou  University of North Carolina at Chapel Hill
<EMAIL_ADDRESS>and  Mariana Olvera-Cravioto  University of North
Carolina at Chapel Hill<EMAIL_ADDRESS>
###### Abstract.

We study the evolution of opinions on a directed network with community
structure. Individuals update their opinions synchronously based on a weighted
average of their neighbors’ opinions, their own previous opinions, and
external media signals. Our model is akin to the popular Friedkin-Johnsen
model, and is able to incorporate factors such as stubbornness, confirmation
bias, selective exposure, and multiple topics, which are believed to play an
important role in the formation of opinions. Our main result shows that, in
the large graph limit, the opinion process concentrates around its mean-field
approximation for any level of edge density, provided the average degree grows
to infinity. Moreover, we show that the opinion process exhibits propagation
of chaos. We also give results for the trajectories of individual vertices and
the stationary version of the opinion process, and prove that the limits in
time and in the size of the network commute. The mean-field approximation is
explicit and can be used to quantify consensus and polarization.

###### Key words and phrases:

opinion dynamics, inhomogeneous random graphs, interacting particle systems,
mean-field approximation, propagation of chaos, strong couplings

###### 2020 Mathematics Subject Classification:

60G10, 05C80, 60G17, 60J20, 60J85, 60K35

##  1\. Introduction

As the consumption of information through virtual social networks has grown,
the number of news outlets has multiplied, and individuals increasingly find
ways to disseminate their opinions through online forums and video sharing
platforms, populations around the world have become heavily polarized on a
number of cultural and political issues [51, 9, 47, 49]. The asymmetry of the
information from one source to another has solidified positions into
ideological bubbles with little in common with each other. The formation of
such bubbles occurs through a combination of cognitive biases that allow
individuals to choose to listen only to opinions that conform to their
preconceptions, as well as reject people who espouse views contrary to their
own.

Our collective need to understand the mechanisms behind polarization and
propose ideas to reduce its negative effects has inspired much of the current
literature in the social sciences [51, 9, 47, 49, 1, 30, 32]. Simultaneously,
researchers in the mathematical and physical sciences have proposed models
that can capture and explain phenomena such as consensus and polarization,
often focusing on one or two modeling features at a time. In this work, we
analyze a model based on the classical DeGroot [20] and Friedkin-Johnsen [26]
models, that can simultaneously capture features such as:

  1. a.)

Confirmation bias: the tendency to search for, interpret, favor, and recall
information in a way that confirms or supports one’s prior beliefs or values;

  2. b.)

Selective exposure: individuals’ tendency to favor information which
reinforces their pre-existing views while avoiding contradictory information;

  3. c.)

Community structure: when a network divides naturally into groups of nodes
with dense connections internally and sparser connections between groups;

  4. d.)

Bots: software applications that run automated tasks over the Internet on a
large scale, usually with the intent of imitating human activity;

  5. e.)

Multiple topics: the analysis of the evolution of opinions on multiple
(possibly correlated) topics at a time.

A single-topic version of this model was recently analyzed in [24] on general
complex networks without community structure. This work focused on sparse
(i.e., bounded degree) graphs, where the graph’s local behavior determines the
evolution of the opinion process. Its main results show the power that the
media has in framing people’s opinions, and how selective exposure alone can
explain much of the polarization that we observe in many societies today. One
of the main features of the model in [24], as well as of the model studied
here, is that, due to its linearity, it produces computable formulas that can
be used to quantify the effect of various model parameters on the evolution of
opinions, and potentially, of any intervention one may want to propose.

The current work studies a more general opinion model than the one analyzed in
[24] on sparse graphs, but rather than focus on its explanatory/predictive
power, it computes its limiting behavior on denser graphs with community
structure. From a modeling point of view, it is often hard to decide whether a
real-world network is sparse with a large average degree, or, say, semi-
sparse, with an average degree that grows slowly with the size of the graph.
Given the lack of precise boundaries, we believe it is interesting to
understand the difference between sparse approximations and dense, or mean-
field, approximations. At a high level, sparse approximations are determined
by the entire local neighborhood of each vertex, while mean-field
approximations are obtained by replacing the individual contribution of each
neighbor with their average behavior, which is justified only when vertices in
the graph have a sufficiently large number of neighbors.

Our main interest in this paper is to show that there is a single mean-field
approximation for our opinion model that works for graphs with any density
level other than sparse. However, the precision level of this approximation
does exhibit a phase transition when the average degree crosses the familiar
connectivity threshold $\log n$ (with $n$ the number of vertices in the
graph), and seamlessly explains how the model’s behavior transitions into the
sparse regime, where local approximations such as those found in [24] take
over. In fact, our analysis of the semi-sparse regime is based on the same
local approximation that is used for sparse graphs, which when the average
degree grows with $n$ further simplifies to the mean-field approximation
obtained in the dense case. The transition into the sparse regime can also be
seen from the point of view of the trajectories for different individuals,
which in the setting of this paper exhibit propagation of chaos (i.e.,
asymptotically independent trajectories). In contrast, on sparse graphs, only
a weaker form of propagation of chaos holds, which states that only finite
sets of uniformly chosen trajectories are asymptotically independent. The in-
depth analysis of the model’s explanatory and predictive power will be covered
in a separate set of work.

This paper is organized as follows. In Section 2 we introduce our model for
the evolution of opinions on a large complex network with community structure,
as well as the random graph family used in our analysis. In Section 3 we
present our main results, which give an approximation for the stationary
opinion process that is valid for any density level of the underlying graph
other than sparse. In Section 4 we discuss related models for opinion
dynamics, as well as the technical aspects of our work, such as mean-field
approximations and local approximations for random graphs. Finally, in Section
5 we give all the proofs for the theorems in Section 3.

##  2\. The Model

Our opinion model consists of two parts: 1) the opinion process defined on a
fixed directed graph, and 2) the random graph model used to represent the
underlying social network.

###  2.1. The opinion process on a fixed graph

Consider a directed graph $G=(V,E)$, where individuals in the social network
are represented by vertices in the set $V$, and a directed edge $(i,j)\in E$
means that individual $j$ listens to the opinion of individual $i$; $|V|$
denotes the cardinality of the set. Each individual in the set $V$ is assumed
to belong to one of $K$ communities, and has a set of attributes that will
remain fixed throughout the evolution of the opinion process. We assume we
have $\ell$ topics, with $\ell$ a finite number, and individuals’ opinions on
each topic take values on the interval $[-1,1]$. The main object of study is
the opinion process $\\{R^{(k)}:k\geq 0\\}$, taking values on
$[-1,1]^{|V|\times\ell}$, where $R_{ij}^{(k)}$ denotes the expressed opinion
of individual $i\in V$ on topic $j\in\\{1,\dots,\ell\\}$ at time
$k\in\mathbb{N}=\\{0,1,2,\dots\\}$. We will use $\mathbf{R}_{i}^{(k)}$ to
denote the $i$th row of $R^{(k)}$, which corresponds to the multi-topic
opinion vector of individual $i$ at time $k$.

Before we describe the updating rule for the process $\\{R^{(k)}:k\geq 0\\}$,
we need to describe the vertex attributes that determine how each individual
engages with its neighbors and incorporates their own prejudices. To start,
each individual $i\in V$ has an attribute vector and an extended attribute
vector of the form:

$\mathbf{a}_{i}=(J_{i},\mathbf{q}_{i})\in\\{1,\dots,K\\}\times[-1,1]^{\ell}\quad\text{and}\quad\mathbf{y}_{i}=(J_{i},\mathbf{q}_{i},\mathbf{b}_{i})\in\\{1,\dots,K\\}\times[-1,1]^{\ell}\times\mathbb{R}_{+}^{|V|},$

where $J_{i}$ denotes the community to which individual $i$ belongs,
$\mathbf{q}_{i}=(q_{i1},\dots q_{i\ell})$ is a row vector of pre-conceived
ideas or internal beliefs on each of the $\ell$ topics, and
$\mathbf{b}_{i}=(b_{i1},\dots,b_{i|V|})$ is a nonnegative row vector of
“unnormalized” weights, where $b_{ij}$ is the weight that individual $i$ gives
to individual $j$’s expressed opinions (these weights will later be normalized
to add up to one). The extended attribute vectors $\\{\mathbf{y}_{i}:i\in
V\\}$ do not change throughout the evolution of the process, reflecting the
reasonable modeling assumption that they change at a much longer time-scale
than the expressed opinions process. To make them easy to identify, all
vectors are written in boldface.

Given the set of edges $E$, we now construct the (normalized) weights
according to:

$c_{ij}=\frac{b_{ij}1(j\to i)}{\sum_{l\in V}b_{il}1(l\to i)}1\left(\sum_{l\in
V}b_{il}1(l\to i)>0,\,i\neq j\right),\qquad i,j\in V,$ (2.1)

where $j\to i$ indicates that $(j,i)\in E$. The model also requires two
parameters, $c,d\in[0,1]$, such that $0<c+d\leq 1$ and $d>0$. The parameter
$c$ controls the amount of value that individuals give to the social network,
and $d$ controls the amount of weight they give to external influences, e.g.,
media and political leaders. Although one can easily make the parameters $c$
and $d$ depend on each individual, for simplicity we interpret them as average
weights and keep them the same across all individuals. Our assumption that
$d>0$ is important both to the explanatory/predictive power of the model, and
to its mathematical properties, as we will see later.

Having described the attributes of each individual, we can now describe the
evolution of the opinion process. At time zero, we initialize the process with
a matrix $R^{(0)}\in[-1,1]^{|V|\times\ell}$ chosen according to some initial
distribution $\mu_{0}$ such that $\\{\mathbf{R}_{i}^{(0)}:J_{i}=r\\}$ are
identically distributed for each $1\leq r\leq K$. At each time step $k$, each
individual $i$ listens to an external signal
$\mathbf{W}_{i}^{(k)}\in[-1,1]^{\ell}$ (row vector), and updates their opinion
according to:

$\mathbf{R}_{i}^{(k+1)}=c\sum_{j\in
V}c_{ij}\mathbf{R}_{j}^{(k)}+\mathbf{W}_{i}^{(k+1)}+(1-c-d)\mathbf{R}_{i}^{(k)},\qquad
k\geq 0,\,i\in V.$ (2.2)

The external signals $\\{\mathbf{W}_{i}^{(k)}:i\in V,k\geq 0\\}$ are assumed
to be independent of each other, and of the initial opinion matrix $R^{(0)}$.
In order to include the possibility of having vertices with no inbound
neighbors, it is convenient to assume that the external signals take the form:

$\mathbf{W}_{i}^{(k)}=d\mathbf{Z}_{i}^{(k)}+c\mathbf{q}_{i}1\left(d_{i}^{-}=0\right),$
(2.3)

where $d_{i}^{-}=\sum_{j\in V}1(j\to i)$ is the number of inbound neighbors of
vertex $i$ and $\\{\mathbf{Z}_{i}^{(k)}:k\geq 0\\}$ can be interpreted as
media signals. This form of the external signals replaces the contribution of
the neighbors with the vertex’s internal belief when it has no inbound
neighbors. For a vertex $i\in V$ having attribute vector $\mathbf{a}_{i}$, the
media signals $\\{\mathbf{Z}_{i}^{(k)}:k\geq 0\\}$ are assumed to be i.i.d.
with some distribution $\nu(\mathbf{a}_{i})$. If needed, one could make $\nu$
depend on the extended attribute vector of each vertex, and even add more
vertex properties to the extended attribute vector, but for simplicity we omit
this extension here. We use $W^{(k)}$ to denote the $|V|\times\ell$ matrix
whose $i$th row is $\mathbf{W}_{i}^{(k)}$.

Under the assumption that $d>0$, we will see that the process
$\\{R^{(k)}:k\geq 0\\}$ has a stationary distribution, i.e.,
$R^{(k)}\Rightarrow R$ as $k\to\infty$, where $\Rightarrow$ denotes weak
convergence on $[-1,1]^{|V|\times\ell}$. This paper focuses on the behavior of
both the trajectories $\\{\mathbf{R}_{i}^{(k)}:k\geq 0\\}$ and the stationary
opinion matrix $R$.

###  2.2. The network

Although the opinion process itself is defined on a fixed directed graph, our
results are based on analyzing the process on a random graph sequence
$\\{G_{n}:n\geq 1\\}$, where $G_{n}=(V_{n},E_{n})$. From a modeling point of
view, one can think of the fixed social network of interest as simply one
realization from the random graph model being used. For simplicity, we assume
$|V_{n}|=n$.

In order to model the community structure and individual-level confirmation
bias, we use as the basis for our model a directed stochastic block model
(dSBM) with $K$ communities. Each individual in $i\in V_{n}$ has a community
label $J_{i}$, and given the community labels $\mathscr{J}_{n}=\\{J_{i}:i\in
V_{n}\\}$, edge $(i,j)$ is present in the graph with probability:

$p_{ij}^{(n)}=\frac{\kappa(J_{i},J_{j})\theta_{n}}{n}\wedge 1,\qquad i,j\in
V_{n},$ (2.4)

independently of everything else, where $\kappa$ is a nonnegative kernel
(equivalently, a nonnegative matrix in $\mathbb{R}^{K\times K}$), and
$\theta_{n}$ is a density parameter.

Since our interest in this paper is to obtain approximations for semi-sparse
to dense graphs, it is not important to incorporate degree-corrections into
our model other than those produced by the kernel $\kappa$. In the sparse
setting, where one can closely model the inhomogeneity of the network (e.g.,
scale-free degree distributions), using a degree-corrected dSBM would be more
appropriate.

The proportion of vertices belonging to each community is controlled by the
probability vector $(\pi_{1}^{(n)},\dots,\pi_{K}^{(n)})$, so that a proportion
$\pi_{r}^{(n)}$ of the vertices in $V_{n}$ belong to community $r$. The main
assumption on the distribution of the community labels is given below.

######  Assumption A.

There exists a probability vector $\boldsymbol{\pi}=(\pi_{1},\dots,\pi_{K})$
with $\pi_{r}>0$ for all $1\leq r\leq K$, such that

$\pi_{r}^{(n)}=\frac{1}{n}\sum_{i=1}^{n}1(J_{i}=r)\xrightarrow{P}\pi_{r},$

as $n\to\infty$, for each $r\in\\{1,\dots,K\\}$.

Next, for each $r\in\\{1,\dots,K\\}$ let $F_{r}$ be a distribution on
$[-1,1]^{\ell}$. For each vertex $i\in V_{n}$ sample its internal belief
vector $\mathbf{Q}_{i}$ according to $F_{J_{i}}$, where $J_{i}$ is the
community label of vertex $i$.

Finally, to complete the description of the model on a random graph, we sample
each of the unnormalized weights $\\{B_{ij}:i,j\in V_{n}\\}$ conditionally
independent of each other given the community labels $\\{J_{i}:i\in V_{n}\\}$,
with $B_{ij}$ sampled from a distribution $G_{J_{i},J_{j}}$ on the interval
$[0,H]$, with $H$ a finite constant. Note that the distribution of the
unnormalized weights is allowed to depend on the communities to which each
vertex belongs, which means one can give less weight to opinions coming from
members of a different community. This is a form of confirmation bias [41, 42,
21], applied to the individual rather than the opinion itself.

######  Remarks 2.1.

We end this section by explaining how one can choose the various parameters to
model many of the features that social scientists believe influence the
evolution of opinions. Since the full explanatory and predictive power of the
model will be discussed in a future companion paper, we give here only a high-
level description of what our model can be used for.

  1. a.)

The kernel $\kappa$ and the unnormalized weights $\\{B_{ij}:i,j\in V_{n}\\}$
can be used to model a form of confirmation bias that affects the individuals
directly, i.e., by both controlling the number of neighbors that an individual
has who belong to communities different from their own, and by discounting
their opinions. Note that this form of confirmation bias depends on neither
the topic nor the specific expressed opinions being shared at any point. Other
ways of modeling confirmation bias directly applied to the expressed opinions
being shared are discussed in Section 4.

  2. b.)

A direct way in which our model incorporates selective exposure is through the
choice of the distribution $\nu(\mathbf{A}_{i})$ for the media signals, where
$\mathbf{A}_{i}=(J_{i},\mathbf{Q}_{i})$. For example, if we believe that each
community has its own preferred media outlets, e.g., news and political
commentators, then we can choose the distribution $\nu$ to depend on the
community label $J_{i}$. Moreover, if we want to model the human tendency to
reject information that contradicts our internal beliefs or pre-existing
views, we can do so by allowing $\nu$ to depend on the internal belief vector
$\mathbf{Q}_{i}$ (e.g., a person who listens to an outlet that has extreme
views on topics 1 and 2, but only agrees with the outlet on topic 1, may
choose to ignore the media signal for topic 2).

  3. c.)

The dSBM can also be used to model the presence of bots, targeted or not, by
creating additional communities. A targeted bot chooses who to send its
messages to based on their community label. Since bots are not real people,
they are not influenced by what they hear from their inbound neighbors, so we
can model them to have no inbound neighbors by adjusting the kernel $\kappa$
accordingly.

##  3\. Main Results

We are now ready to present the main results of the paper. We assume from here
onwards that we are working on a probability space $(\Omega,\mathcal{F},P)$
where we can construct the entire random graph sequence $\\{G_{n}:n\geq 1\\}$
along with their vertex marks, as well as all the external signals needed to
define the opinion process on each of the graphs in the sequence. We use
$E[\cdot]$ to denote the corresponding expectation. The opinion process
$\\{R^{(k)}:k\geq 0\\}$ is constructed on a fixed random graph
$G_{n}=(V_{n},E_{n})$ from the sequence, but for simplicity the dependence on
$n$ is not explicit in the notation.

As mentioned earlier, our work shows that there is a unique approximation for
the opinion process $\\{R^{(k)}:k\geq 0\\}$ under the large graph limit
$n\to\infty$, that works for all choices of the density parameter
$\theta_{n}$. The phase transition occurs only in the precision level of the
approximation, around the threshold $\theta_{n}=\log n$. Interestingly, the
proof technique is also significantly different above and below the threshold
$\log n$, reflecting the fact that as the density parameter $\theta_{n}$ drops
below the threshold, a vertex’s entire neighborhood becomes increasingly
important. To be able to drop the minimum in (2.4) and simplify our results,
we assume throughout the paper that

$\limsup_{n\to\infty}\max_{1\leq r,s\leq K}\frac{\kappa(r,s)\theta_{n}}{n}\leq
1.$

The process $\\{R^{(k)}:k\geq 0\\}$ will be approximated by another process
$\\{\mathcal{R}^{(k)}:k\geq 0\\}$ whose main characteristic is that its rows
$\\{\boldsymbol{\mathcal{R}}_{i}^{(k)}:k\geq 0,i\in V_{n}\\}$ are
conditionally independent of each other given the community labels. We will
now describe the approximating process, leaving an intuitive derivation of how
this process is obtained to Section 5.

To start, define the matrix $M\in[0,1]^{K\times K}$ whose $(r,s)$th component
is given by

$m_{rs}=\dfrac{\pi_{s}\beta_{r,s}\kappa(s,r)}{\pi_{1}\beta_{r,1}\kappa(1,r)+\dots+\pi_{K}\beta_{r,K}\kappa(K,r)}\cdot
1\left(\pi_{1}\beta_{r,1}\kappa(1,r)+\dots+\pi_{K}\beta_{r,K}\kappa(K,r)>0\right),$
(3.1)

where $\beta_{r,s}=E[B_{ij}|J_{i}=r,J_{j}=s]$. Note that since one may want
bot communities to have no inbound neighbors, $M$ may have zero rows. Define
also $v_{r,s}=E[B_{ij}^{2}|J_{i}=r,J_{j}=s]$. Recall that the media signals,
given by $\\{\mathbf{Z}_{i}^{(k)}:k\geq 0,i\in V_{n}\\}$, are independent of
each other, with $\\{\mathbf{Z}_{i}^{(k)}:k\geq 0\\}$ conditionally i.i.d.
given $\mathbf{A}_{i}$, with distribution $\nu(\mathbf{A}_{i})$. The external
signals $\\{\mathbf{W}_{i}^{(k)}:k\geq 0,i\in V_{n}\\}$ follow the form in
(2.3). We will use $\bar{W}\in[-1,1]^{K\times\ell}$ to denote the matrix whose
$r$th row is $E[\mathbf{W}_{i}^{(0)}|J_{i}=r]$, and
$\bar{R}\in[-1,1]^{K\times\ell}$ to denote the matrix whose $r$th row is
$E[\mathbf{R}_{i}^{(0)}|J_{i}=r]$.

The approximating process $\\{\mathcal{R}^{(k)}:k\geq 0\\}$ is given by:
$\mathcal{R}^{(0)}=R^{(0)}$ and

$\boldsymbol{\mathcal{R}}_{i}^{(k)}=\sum_{t=0}^{k-1}(1-c-d)^{t}\mathbf{W}_{i}^{(k-t)}+1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}(M^{s}\bar{W})_{J_{i}\bullet}+\sum_{s=1}^{k}a_{s,k}(M^{s}\bar{R})_{J_{i}\bullet}+(1-c-d)^{k}\mathbf{R}_{i}^{(0)},$
(3.2)

for $k\geq 1$ and $i\in V_{n}$, where $a_{s,t}=\binom{t}{s}(1-c-d)^{t-s}c^{s}$
and $H_{j\bullet}$ denotes the $j$th row of matrix $H$ ($H_{\bullet j}$
denotes the $j$th column). Note that conditionally on the vertex attributes
$\\{\mathbf{A}_{i}:i\in V_{n}\\}$, (3.2) takes the form of an autoregressive
process of order one, without any interactions among different vertices.
Before stating the main theorems, we will need a few additional definitions.

For a vector $\mathbf{x}\in\mathbb{R}^{n}$, we use the standard $l_{p}$-norm
$\|\cdot\|_{p}$, $p\geq 1$, namely,

$\|\mathbf{x}\|_{p}:=\left(\sum_{i=1}^{n}|x_{i}|^{p}\right)^{1/p}\quad\text{and}\quad\|\mathbf{x}\|_{\infty}:=\max_{1\leq
i\leq n}|x_{i}|.$

Applied to a matrix $A\in\mathbb{R}^{n\times\ell}$, $\|\cdot\|_{p}$ is the
induced norm

$\|A\|_{p}:=\sup_{\|\mathbf{x}\|\neq
0}\frac{\|A\mathbf{x}\|_{p}}{\|\mathbf{x}\|_{p}}.$

We will also use the notation

$\mu_{r}^{(n)}=\sum_{s=1}^{K}\beta_{r,s}\pi_{s}^{(n)}\kappa(s,r)\qquad\text{and}\qquad\nu_{r}^{(n)}=\sum_{s=1}^{K}v_{r,s}\pi_{s}^{(n)}\kappa(s,r),$

as well as

$\Delta_{n}=\max_{r\in\mathcal{I}}\frac{\nu_{r}^{(n)}}{(\mu_{r}^{(n)})^{2}}\qquad\text{and}\qquad\Lambda_{n}=\max_{r\in\mathcal{I}}\frac{\mu_{r}^{(n)}}{\nu_{r}^{(n)}},$

where $\mathcal{I}=\\{r\in\\{1,\dots,K\\}:\sum_{s=1}^{K}m_{rs}>0\\}$ is the
set of non-zero rows of $M$. Note that both $\Delta_{n}$ and $\Lambda_{n}$
converge to positive constants as $n\to\infty$ under Assumption Assumption A.
We use $\mathbb{E}_{n}[\cdot]=E[\cdot|\mathscr{J}_{n}]$ to denote the
conditional expectation given the community labels, and $\mathbb{P}_{n}$ to
denote its corresponding conditional probability. The first main result of the
paper is given below.

######  Theorem 3.1.

Define the process $\\{\mathcal{R}^{(k)}:k\geq 0\\}$ according to (3.2).
Suppose $\theta_{n}\geq(6H\Lambda_{n})^{2}\Delta_{n}\log n$. Then, there
exists a constant $\Gamma<\infty$ such that

$\sup\limits_{k\geq
0}\,\mathbb{E}_{n}\left[\left\|R^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right]\leq\Gamma\left(\sqrt{\frac{\log
n}{\theta_{n}}}+\mathcal{E}_{n}\right),$ (3.3)

where $\mathcal{E}_{n}:=\max_{1\leq r,s\leq
K}\left|\frac{\pi_{s}^{(n)}\pi_{r}-\pi_{s}\pi_{r}^{(n)}}{\pi_{r}^{(n)}\pi_{s}}\right|$.
Moreover, for any sequence $\theta_{n}$ satisfying
$\theta_{n}\rightarrow\infty$ as $n\rightarrow\infty$,

$\sup_{k\geq 0}\,\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]\xrightarrow{P}0,$
(3.4)

as $n\to\infty$.

######  Remarks 3.1.

  1. a.)

Since $\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]\leq\mathbb{E}_{n}\left[\left\|R^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right]$,
Theorem 3.1 shows that the approximation is stronger when $\theta_{n}/\log
n\to\infty$, and it gradually weakens as the rate at which $\theta_{n}$ grows
drops below the critical rate $\log n$. Intuitively, this can be explained by
noting that the average number of neighbors that any vertex has grows with the
density parameter $\theta_{n}$. The larger the number of neighbors, the more
their aggregate contributions behave as the average opinion. The weakest
result is valid for any $\theta_{n}\to\infty$, regardless of how slow the
growth is. However, it is worth pointing out that when $\theta_{n}$ is
bounded, the approximation fails, and the correct approximation is the sparse
approximation, which is determined by the local neighborhood of each vertex
(see Theorem 2 in [24]). The threshold $\log n$ determining the strength of
the approximation also appears in [11, 10] and [3], where the authors study
other processes on graphs with various edge density levels.

  2. b.)

For each $i\in V_{n}$, the sequence $\\{\textbf{R}_{i}^{(k)}:k\geq 0\\}$ is
called the trajectory of vertex $i$. Since the rows in the limiting process
$\\{\mathcal{R}^{(k)}:k\geq 1\\}$ are independent of each other, Theorem 3.1
yields that the trajectories of the process $\\{R^{(k)}:k\geq 0\\}$ are
asymptotically independent; in other words, the process exhibits propagation
of chaos (note that only particles in the same community are exchangeable).
Since

$\frac{1}{n}\sum_{i=1}^{n}\sup_{k\geq
0}\,\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}^{(k)}_{i}\right\|_{1}\right]\leq\sup_{k\geq
0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]\xrightarrow{P}0,\qquad
n\to\infty,$

the second statement in Theorem 3.1 implies pointwise propagation of chaos in
the sense of Definition 4.1 in [13], throughout the entire range of $k$. We
point out that this is not the case in the sparse regime, where the local
approximation given by Theorem 2 in [24] corresponds to a process whose
trajectories are not independent of each other, and the trajectories of
vertices close to each other may in fact have significant dependence.

  3. c.)

Note that since $\left\|R^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}$ is
bounded, Theorem 3.1 implies that for $\log n/\theta_{n}\to 0$, we have that
for each $k\geq 0$,

$\left\|R^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\xrightarrow{P}0,\qquad
n\to\infty.$

An alternative way of understanding the approximation is to look at the
empirical measure

$\frac{1}{n}\sum_{i=1}^{n}1(\textbf{R}_{i}^{(0)},\dots,\textbf{R}_{i}^{(k)})\in
A),$

for any measurable set $A\subseteq([-1,1]^{\ell})^{k+1}$. Written in this way,
one can identify this measure as the conditional law of a typical opinion,
understood as the trajectory of a uniformly chosen vertex $I_{n}\in V_{n}$,
given the underlying graph $G_{n}=(V_{n},E_{n})$ and the entire process
$\\{\mathcal{R}^{(t)}:0\leq t\leq k\\}$. In our model, the distribution of the
typical trajectory converges as $n\to\infty$ to a law that depends only on the
community label. Since in the random graph literature the typical vertex
converges to the distribution of the root of a rooted graph (usually a
branching tree), the notation we use in the following theorem is consistent
with that used in the sparse regime, where $\emptyset$ denotes the root of the
limiting graph. We point out that in this paper, the limiting graph is not
locally finite, so the notion of local weak convergence (see [52]) does not
apply.

######  Theorem 3.2.

Fix $k\geq 0$ and define the random variables
$(\\{\boldsymbol{\mathcal{R}}_{\emptyset}^{(m)}:0\leq m\leq
k\\},\mathcal{J}_{\emptyset})$ according to:

$\displaystyle P(\mathcal{J}_{\emptyset}=s)$ $\displaystyle=\pi_{s},\qquad
1\leq s\leq K,$ $\displaystyle
P\left(\left.(\boldsymbol{\mathcal{R}}_{\emptyset}^{(0)},\boldsymbol{\mathcal{R}}_{\emptyset}^{(1)},\dots,\boldsymbol{\mathcal{R}}_{\emptyset}^{(k)})\in
A\right|\mathcal{J}_{\emptyset}=s\right)$
$\displaystyle=\mathbb{P}_{n}\left((\boldsymbol{\mathcal{R}}_{i}^{(0)},\boldsymbol{\mathcal{R}}_{i}^{(1)},\dots,\boldsymbol{\mathcal{R}}_{i}^{(k)})\in
A\right),\qquad A\subseteq([-1,1]^{\ell})^{k+1},$

where $\\{\boldsymbol{\mathcal{R}}_{i}^{(k)}:k\geq 0\\}$ is given by (3.2) and
$i$ is any vertex belonging to community $s$. Define
$V_{k,i}\in[-1,1]^{\ell\times(k+1)}$ to be the matrix having $j$th column
$(V_{k,i})_{\bullet j}=(\mathbf{R}_{i}^{(j-1)})^{\top}$, and let
$\mathcal{V}_{k}\in[-1,1]^{\ell\times(k+1)}$ be the matrix having $j$th column
$(\mathcal{V}_{k})_{\bullet
j}=(\boldsymbol{\mathcal{R}}_{\emptyset}^{(j-1)})^{\top}$. Then, for any
$1\leq r\leq K$ and any bounded and continuous (with respect to the
$\|\cdot\|_{1}$ operator norm) function
$f:[-1,1]^{\ell\times(k+1)}\to\mathbb{R}$, we have

$\dfrac{1}{n}\sum_{i=1}^{n}f\left(V_{k,i}\right)1(J_{i}=r)\stackrel{{\scriptstyle
P}}{{\rightarrow}}E\left[f\left(\mathcal{V}_{k}\right)1(\mathcal{J}_{\emptyset}=r)\right]$

as $n\rightarrow\infty$. Furthermore, for any arbitrary collection of vertices
$\\{i_{1},\dots,i_{m}\\}\subseteq V_{n}$ having community labels
$\\{r_{1},\dots,r_{m}\\}$, $m\geq 1$, and any set of continuous (with respect
to $\|\cdot\|_{1}$) bounded functions $\\{f_{1},\dots,f_{m}\\}$ on
$[-1,1]^{\ell\times(k+1)}$, $k\geq 0$, we have

$\mathbb{E}_{n}\left[\prod\limits_{j=1}^{m}f_{j}\left(V_{k,i_{j}}\right)\right]\xrightarrow{P}\prod\limits_{j=1}^{m}E\left[\left.f_{j}\left(\mathcal{V}_{k}\right)\right|\mathcal{J}_{\emptyset}=r_{j}\right],\qquad
n\to\infty.$

######  Remark 3.1.

The last statement in Theorem 3.2 is closely related to Theorem 2.6.B in [23],
which states that trajectories of a finite set of vertices uniformly chosen at
random are asymptotically independent of each other, a limited form of
propagation of chaos that holds only for vertices that are likely to be far
from each other. However, the last statement in Theorem 3.2 allows the
vertices to be chosen arbitrarily.

The last set of results in the paper refers to the stationary behavior of the
Markov chain $\\{R^{(k)}:k\geq 0\\}$. Recall that $R$ denotes a matrix in
$[-1,1]^{n\times\ell}$ having the stationary distribution of the chain, and
$\mathbf{R}_{I_{n}}$ denotes a uniformly chosen row of the matrix $R$. Note
that $\textbf{R}_{I_{n}}$ represents the typical stationary opinion on the
graph, across all $\ell$ topics. Our last theorem provides a characterization
for $\textbf{R}_{I_{n}}$ when $n$ is large, by establishing the existence of a
random variable $\boldsymbol{\mathcal{R}}_{\emptyset}\in[-1,1]^{\ell}$ such
that

$\textbf{R}_{I_{n}}\Rightarrow\boldsymbol{\mathcal{R}}_{\emptyset},\qquad
n\to\infty,$

where $\Rightarrow$ denotes weak convergence on $[-1,1]^{\ell}$. Since
$\boldsymbol{\mathcal{R}}_{\emptyset}$ also turns out to be the weak limit of
$\\{\boldsymbol{\mathcal{R}}_{\emptyset}^{(k)}:k\geq 0\\}$ as $k\to\infty$,
our results show that we can exchange the limits in $k$ (time) and $n$ (number
of vertices).

######  Theorem 3.3.

Define the random variables
$(\boldsymbol{\mathcal{R}}_{\emptyset},\mathcal{J}_{\emptyset})$ according to:

$\displaystyle P(\boldsymbol{\mathcal{R}}_{\emptyset}\in
A|\mathcal{J}_{\emptyset}=r)$
$\displaystyle=\mathbb{P}_{n}\left(\left.\sum_{t=0}^{\infty}(1-c-d)^{t}\mathbf{W}_{i}^{(t)}+\sum_{t=1}^{\infty}\sum_{s=1}^{t}a_{s,t}(M^{s}\bar{W})_{J_{i}}\in
A\right|J_{i}=r\right),\qquad A\subseteq[-1,1]^{\ell},$ $\displaystyle
P(\mathcal{J}_{\emptyset}=r)$ $\displaystyle=\pi_{r},\qquad 1\leq r\leq K.$

Then, there exists a coupling
$(\textbf{R}_{I_{n}},J_{I_{n}},\boldsymbol{\mathcal{R}}_{\emptyset},\mathcal{J}_{\emptyset})$,
such that for any continuous (with respect to $\|\cdot\|_{1}$) and bounded
function $f:[-1,1]^{\ell}\rightarrow\mathbb{R}$, we have for any $1\leq r\leq
K$,

$\mathbb{E}_{n}\left[\|\textbf{R}_{I_{n}}-\boldsymbol{\mathcal{R}}_{\emptyset}\|_{1}\right]\stackrel{{\scriptstyle
P}}{{\rightarrow}}0\quad\text{and}\quad\dfrac{1}{n}\sum_{i=1}^{n}f(\textbf{R}_{i})1(J_{i}=r)\stackrel{{\scriptstyle
P}}{{\rightarrow}}E[f(\boldsymbol{\mathcal{R}}_{\emptyset})1(\mathcal{J}_{\emptyset}=r)]$

as $n\rightarrow\infty$. Furthermore, for any arbitrary collection of vertices
$\\{i_{1},\dots,i_{m}\\}\subseteq V_{n}$ having community labels
$\\{r_{1},\dots,r_{m}\\}$, $m\geq 1$, and any set of continuous (with respect
to $\|\cdot\|_{1}$) bounded functions $\\{f_{1},\dots,f_{m}\\}$ on
$[-1,1]^{\ell}$, we have

$\mathbb{E}_{n}\left[\prod_{j=1}^{m}f_{j}(\textbf{R}_{i_{j}})\right]\xrightarrow{P}\prod_{j=1}^{m}E[f_{j}(\boldsymbol{\mathcal{R}}_{\emptyset})|\mathcal{J}_{\emptyset}=r_{j}],\qquad
n\to\infty.$

######  Remark 3.2.

Note that the shape of $\boldsymbol{\mathcal{R}}_{\emptyset}$ is simply the
limit as $k\to\infty$ of $\boldsymbol{\mathcal{R}}_{I_{n}}^{(k)}$ after a time
reversal of the external signals, i.e.,
$\mathbf{W}_{I_{n}}^{(k-t)}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\mathbf{W}_{I_{n}}^{(t)}$.

The proofs of all the theorems are contained in Section 5.

##  4\. Related Literature

Interest in the evolution of opinions on social networks dates back to the
50’s, with the work of French [25] and DeGroot [20]. The model in [20]
corresponds in our notation to the recursion
$\mathbf{R}^{(k+1)}=A\mathbf{R}^{(k)}$, for a given $\mathbf{R}^{(0)}$ and
$A=c\,C+(1-c)I$, with $C=(c_{ij})$ as in (2.1) (the model is for a single
topic, hence the vectors instead of matrices). The main question studied in
[20, 8] was the existence of consensus, seen as a limit
$\mathbf{R}=\lim_{k\to\infty}\mathbf{R}^{(k)}$ whose components are all equal
to each other (a consequence of the Perron-Frobenius theorem when the matrix
$A$ is irreducible and aperiodic). In [26], Friedkin and Johnsen extended the
model to allow disagreement by considering the recursion
$\mathbf{R}^{(k+1)}=A\mathbf{R}^{(k)}+\mathbf{Q}$, with $\mathbf{Q}$ a
deterministic vector, which is a special case of our model. The models in [54]
replace the deterministic $\mathbf{Q}$ with a sequence of random signals
$\\{\mathbf{W}^{(k)}:k\geq 0\\}$, as we do, although they are independent of
the underlying network, since they are used to model miscommunication. A more
recent generalization of the DeGroot model was given in [17], where the
authors introduced the concept of biased assimilation, namely the tendency of
individuals to pull their opinion towards their initial opinion once presented
with inconclusive evidence, in order to make the repeated averaging scheme of
DeGroot lead to polarization. Another closely related model that is capable of
introducing confirmation bias by rejecting an opinion from a neighbor when it
is too different from their own expressed opinion is the Hegselmann-Krause
model [45], which due to its non-linear updating rule is not covered by our
analysis. All these models are defined on a fixed graph, so the stochastic
matrix $A$ is deterministic, unlike ours, where we use both the updating rules
of the opinion process and the properties of the underlying graph to explain
complex phenomena. Other variants of the DeGroot and Friedkin-Johnsen models
that incorporate multiple topics and time-varying self-weights (e.g., $d$ in
our model is allowed to be different for each vertex and change with time) are
given in [34, 44, 50].

While all the models mentioned above are defined on discrete time with
synchronous updating rules, there is a different family of popular opinion
models where interactions occur one at a time, at either random or
deterministic times. Among those are the bounded confidence models, such as
the Deffuant-Weisbuch model [53, 19, 18]. In this model, at each time step a
pair of neighboring individuals is randomly selected. Then, the two neighbors
update their opinions according to a simple linear equation if, and only if,
the difference of their current opinions is less than a specified threshold.
This model, like the Hegselmann-Krause model, is meant to explain
fragmentation and polarization through a direct confirmation bias. Its non-
linearity and lack of an external signal means that its analysis is usually
done using the methods of interacting particle systems or numerical stochastic
simulation [33, 6, 37, 16, 31, 40]. A more recent analysis of the Deffuant-
Weisbuch model that takes into account the network’s topology is [22]. Our
model is not meant to tackle confirmation bias at the level of the opinions
being shared, but rather at the level of the individuals who share them, and
the main appeal of our model is that it accounts for the combined effects of
the network topology, the media framing effect, and people’s selective
exposure, while still producing computable formulas for means and variances
for the opinion process.

As mentioned in the introduction, the main focus of this paper is not the
explanatory and predictive power of our model, but rather its behavior on
graphs of various levels of edge density. So, before we discuss that aspect of
the related literature, we just want to mention that there is yet another
family of classical opinion models taking values on finite sets (rather than
continuous intervals), like the voter model [39], where opinions can be either
0 or 1, or the Axelrod model [4], where each vertex has a fixed set of
features and traits, leading to a notion of “similarity” between vertices. The
former can be used to model consensus through asynchronous updates, whereas
the latter achieves a diversity of opinions by using a trait updating rule
that depends on how similar the features of the two interacting vertices are,
a concept known as homophily. The underlying graph in both of these models is
usually a lattice, although the voter model has also been analyzed in
heterogeneous graphs in [48]. The work in [46] contains a review of
interesting variants of the voter model.

Our opinion model falls in the category of interacting particle systems in
discrete time with synchronous updates and continuous state space, although
only vertices in the same community are exchangeable. The approximating
process $\\{\mathcal{R}^{(k)}:k\geq 0\\}$ is a classical mean-field
approximation, where the complex interactions between neighboring vertices are
replaced with their average behavior. Our main theorem proves propagation of
chaos by coupling the trajectories, as described in the surveys [13, 12]. The
literature on mean-field approximations is so vast, and covers such a wide
range of fields, that it would be impossible to mention all the related models
for which results similar to ours have been derived. The closest work to the
techniques used in this paper is the analysis of the personalized PageRank
algorithm done in [3], where a stochastic block model is the only source of
randomness in what otherwise would be a deterministic linear recursion. The
main results in [3] are closely related to our Theorem 3.1 for density
parameters $\theta_{n}/\log n\to\infty$, albeit for a different recursion and
under an $l_{2}$-norm (rather than the $l_{\infty}$-norm we use). Our work
shows that the approximation itself continues to hold beyond the $\log n$
threshold, for any $\theta_{n}\to\infty$, but with lesser precision (a weaker
norm). Relative to the majority of mean-field results in the interacting
particles literature, our work is different in the explicit role that the
underlying random graph plays, its ability to seamlessly cover the entire
range of edge densities (other than the sparse case), the explicit
characterization of the limiting process as the number of particles goes to
infinity, and the exchange of limits with the stationary version of the
limiting process. Other works that analyze stochastic processes on graphs with
various levels of edge density are [11], which studies the supermarket model
on graphs, and [10], which analyzes weakly interacting diffusions on time
varying random graphs. It is also worth pointing out that mean-field
approximations for bounded confidence models such as the Deffuant-Weisbuch
model and some of its variants have been given in [37, 16, 31].

Finally, we would like to point out that the analysis of our model in the
semi-sparse regime, i.e., $\theta_{n}$ below the $\log n$ threshold, is based
on a coupling of the underlying random graph with a marked multi-type
branching process. This technique is based on the notion of local weak
convergence of random graph sequences [7, 2] (see also [52]). Although for
non-sparse random graphs the local weak limit is not a locally bounded graph,
the dSBM can still be coupled with a marked multi-type Galton-Watson tree
(with average degree that grows with $n$). In fact, a strong coupling, in the
sense of the intermediate coupling in [43], still holds, which is what enables
the work in this paper. For sparse graphs, local weak convergence or strong
couplings have been used to study the PageRank algorithm in [14, 29, 5],
general discrete-time stochastic recursions on sparse graphs in [23],
interacting diffusions in [35, 36], and continuous jump process models [27,
28, 15]. The techniques in this paper will likely extend to more general
classes of stochastic recursions on random graphs with growing edge densities.

##  5\. Proofs

This section contains the proofs for all the theorems in Section 3. The proof
of our main result, Theorem 3.1, requires two different approaches depending
on the speed at which $\theta_{n}\to\infty$, however, both approaches start
with the same intermediate approximation. We will start by presenting the
intermediate approximation in this section, and then complete the analysis for
the two different density regimes; in Section 5.1 for the case when
$\theta_{n}\geq\gamma\log n$ for some $\gamma>0$, and in Section 5.2 for the
case when $\limsup_{n\to\infty}\log n/\theta_{n}>0$. Finally, as mentioned
earlier, Theorems 3.2 and 3.3 are consequences of Theorem 3.1, so we give
their proofs in Section 5.3.

Recall that the opinion process will be constructed on a fixed directed graph
$G_{n}$ sampled according to Section 2.2, where each vertex $i\in V_{n}$ has
an attribute $\mathbf{A}_{i}=(J_{i},\mathbf{Q}_{i})$ and an extended attribute
$\mathbf{Y}_{i}=(J_{i},\mathbf{Q}_{i},\mathbf{B}_{i})$, with
$\mathbf{B}_{i}=(B_{ij})_{1\leq j\leq n}$ the unnormalized weights.

In order for us to derive the intermediate approximation, we first note that
the opinion recursion (2.2) can be rewritten in matrix notation as

$R^{(k)}=AR^{(k-1)}+W^{(k)},$ (5.1)

where $R^{(k)}\in[-1,1]^{n\times\ell}$ and $W^{(k)}\in[-1,1]^{n\times\ell}$
are the matrices having $(i,j)$th components $R_{ij}^{(k)}$ and
$W_{ij}^{(k)}$, respectively, and $A\in[0,1]^{n\times n}$ the matrix
satisfying

$A_{ij}=c\cdot C_{ij},\quad i\neq j,\qquad A_{ii}=1-c-d,$

with $C_{ij}$ constructed according to (2.1) using the random unnormalized
weighs $\\{B_{ij}:i,j\in V_{n}\\}$ (the use of upper case is to remind the
reader that these are random). Iterating (5.1) gives the explicit solution

$R^{(k)}=\sum_{t=0}^{k-1}A^{t}W^{(k-t)}+A^{k}R^{(0)}.$

Using the observation that $A=c\,C+(1-c-d)I$, where $C$ is the matrix having
$(i,j)$th component $C_{ij}$, and $I$ is the identity matrix in
$\mathbb{R}^{n\times n}$, we get

$A^{t}=(c\,C+(1-c-d)I)^{t}=\sum_{s=0}^{t}\binom{t}{s}(1-c-d)^{t-s}c^{s}C^{s}=\sum_{s=0}^{t}a_{s,t}C^{s},\qquad
t\geq 0,$

and, therefore,

$R^{(k)}=\sum_{t=0}^{k-1}\sum_{s=0}^{t}a_{s,t}C^{s}W^{(k-t)}+\sum_{s=0}^{k}a_{s,k}C^{s}R^{(0)},\qquad
k\geq 1.$ (5.2)

Now, construct the matrix $\tilde{M}\in\mathbb{R}^{n\times n}$ according to

$\tilde{M}_{ij}=\frac{\beta_{J_{i},J_{j}}\kappa(J_{j},J_{i})}{n\left(\beta_{J_{i},1}\pi_{1}^{(n)}\kappa(1,J_{i})+\dots+\beta_{J_{i},K}\pi_{K}^{(n)}\kappa(K,J_{i})\right)}1(i\neq
j),$

and recall that $\beta_{r,s}=E[B_{ij}|J_{i}=r,J_{j}=s]$, with
$\tilde{M}_{ij}\equiv 0$ if the denominator is zero. The intuition behind this
definition of $\tilde{M}$ is that it is the “approximate” conditional mean of
$C$ given the community labels $\mathscr{J}_{n}$, meaning that for $i,j\in
V_{n}$, $i\neq j$, and $n$ sufficiently large (so that the minimum in
$p_{ij}^{(n)}$ can be dropped), we have

$\tilde{M}_{ij}=\dfrac{\beta_{J_{i},J_{j}}p_{ij}^{(n)}}{n\left(\pi_{1}^{(n)}\beta_{J_{i},1}p_{1i}^{(n)}+\dots+\pi_{K}^{(n)}\beta_{J_{i},K}p_{Ki}^{(n)}\right)}=\dfrac{\mathbb{E}_{n}[B_{ij}1(j\to
i)]}{\mathbb{E}_{n}\left[\,\sum_{r=1}^{n}B_{ir}1(r\to i)\right]}.$

Define $\breve{W}=\mathbb{E}_{n}\left[W^{(0)}\right]$,
$\breve{R}=\mathbb{E}_{n}\left[R^{(0)}\right]$, and construct the new process
$\\{\tilde{R}^{(k)}:k\geq 0\\}$ defined by

$\tilde{R}^{(0)}=R^{(0)},$
$\tilde{R}^{(k)}=\sum_{t=0}^{k-1}(1-c-d)^{t}W^{(k-t)}+1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\tilde{M}^{s}\breve{W}+\sum_{s=1}^{k}a_{s,k}\tilde{M}^{s}\breve{R}+(1-c-d)^{k}R^{(0)},\quad
k\geq 1.$ (5.3)

Intuitively, $\tilde{R}^{(k)}$ replaces all neighbor contributions with their
approximate means, i.e., every term of the form $C^{s}X$ with $s\geq 1$ and
$X$ a random matrix is replaced with $\tilde{M}^{s}\mathbb{E}_{n}[X]$. It is
important to point out that the rows of $\tilde{R}^{(k)}$, which we will
denote $\\{\mathbf{\tilde{R}}_{i}^{(k)}:i\in V_{n}\\}$, become independent as
a consequence. Our first result computes a bound for
$\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]$
and $\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\mathbf{\tilde{R}}_{i}^{(k)}\right\|_{i}\right]$
.

######  Theorem 5.1.

For any $k\geq 1$, we have

$\displaystyle\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\mathbf{\tilde{R}}_{i}^{(k)}\right\|_{1}\right]$
$\displaystyle\leq 1(k\geq 2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|(C^{s}W^{(0)})_{i\bullet}-(\tilde{M}^{s}\breve{W})_{i\bullet}\right\|_{1}\right]$
$\displaystyle\hskip 14.22636pt+\sum_{s=1}^{k}a_{s,k}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|(C^{s}R^{(0)})_{i\bullet}-(\tilde{M}^{s}\breve{R})_{i\bullet}\right\|_{1}\right].$

Furthermore, for
$h(X)=\mathbb{E}_{n}\left[\left\|(C-\tilde{M})X\right\|_{\infty}\right]$, we
have

$\displaystyle\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]$
$\displaystyle\leq\max_{r\geq
1}h(\tilde{M}^{r}\breve{W})\sum_{t=0}^{k-1}(1-d)^{t-1}t+\mathbb{E}_{n}\left[\left\|CW^{(0)}-\tilde{M}\breve{W}\right\|_{\infty}\right]\sum_{t=0}^{k-1}(1-d)^{t}$
$\displaystyle\hskip 14.22636pt+\max_{r\geq
1}h(\tilde{M}^{r}\breve{R})\,k(1-d)^{k-1}+\mathbb{E}_{n}\left[\left\|CR^{(0)}-\tilde{M}\breve{R}\right\|_{\infty}\right](1-d)^{k}.$

###### Proof.

Recall that $a_{s,t}=\binom{t}{s}(1-c-d)^{t-s}c^{s}$ and note that for any
$i\in V_{n}$ we have

$\displaystyle\left\|\mathbf{R}_{i}^{(k)}-\mathbf{\tilde{R}}^{(k)}_{i}\right\|_{1}$
$\displaystyle=\left\|1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\left(C^{s}W^{(k-t)}-\tilde{M}^{s}\breve{W}\right)_{i\bullet}+\sum_{s=1}^{k}a_{s,k}\left(C^{s}R^{(0)}-\tilde{M}^{s}\breve{R}\right)_{i\bullet}\right\|_{1}$
$\displaystyle\leq 1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\left\|\left(C^{s}W^{(k-t)}-\tilde{M}^{s}\breve{W}\right)_{i\bullet}\right\|_{1}+\sum_{s=1}^{k}a_{s,k}\left\|\left(C^{s}R^{(0)}-\tilde{M}^{s}\breve{R}\right)_{i\bullet}\right\|_{1}.$

To obtain the first statement of the theorem simply take expectations on both
sides to get

$\displaystyle\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\mathbf{\tilde{R}}^{(k)}_{i}\right\|_{1}\right]$
$\displaystyle\leq 1(k\geq 2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\left(C^{s}W^{(k-t)}-\tilde{M}^{s}\breve{W}\right)_{i\bullet}\right\|_{1}\right]$
$\displaystyle\hskip 14.22636pt+\sum_{s=1}^{k}a_{s,k}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\left(C^{s}R^{(0)}-\tilde{M}^{s}\breve{R}\right)_{i\bullet}\right\|_{1}\right].$

To continue to the second statement, note that from the properties of the norm
$\|\cdot\|_{\infty}$, we obtain that

$\displaystyle\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}$
$\displaystyle\leq 1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\left\|C^{s}W^{(k-t)}-\tilde{M}^{s}\breve{W}\right\|_{\infty}+\sum_{s=1}^{k}a_{s,k}\left\|C^{s}R^{(0)}-\tilde{M}^{s}\breve{R}\right\|_{\infty}.$

Furthermore, since for any matrices $X,\breve{X}\in\mathbb{R}^{n\times\ell}$
and any $s\geq 1$ we have

$\displaystyle C^{s}X-\tilde{M}^{s}\breve{X}$
$\displaystyle=C^{s-1}(CX-\tilde{M}\breve{X})+(C^{s-1}-\tilde{M}^{s-1})\tilde{M}\breve{X}$
$\displaystyle=C^{s-1}(CX-\tilde{M}\breve{X})+\sum_{r=1}^{s-1}C^{s-r-1}(C-\tilde{M})\tilde{M}^{r}\breve{X},$

then

$\displaystyle\left\|C^{s}X-\tilde{M}^{s}\breve{X}\right\|_{\infty}$
$\displaystyle\leq\sum_{r=1}^{s-1}\left\|C^{s-r-1}(C-\tilde{M})\tilde{M}^{r}\breve{X}\right\|_{\infty}+\left\|C^{s-1}(CX-\tilde{M}\breve{X})\right\|_{\infty}$
$\displaystyle\leq\sum_{r=1}^{s-1}\|C\|_{\infty}^{s-r-1}\left\|(C-\tilde{M})\tilde{M}^{r}\breve{X}\right\|_{\infty}+\|C\|_{\infty}^{s-1}\left\|CX-\tilde{M}\breve{X}\right\|_{\infty}$
$\displaystyle=\sum_{r=1}^{s-1}\left\|(C-\tilde{M})\tilde{M}^{r}\breve{X}\right\|_{\infty}+\left\|CX-\tilde{M}\breve{X}\right\|_{\infty},$

where we used the fact that $\|C\|_{\infty}=1$. We conclude that

$\displaystyle\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]$
$\displaystyle\leq 1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\mathbb{E}_{n}\left[\left\|C^{s}W^{(k-t)}-\tilde{M}^{s}\breve{W}\right\|_{\infty}\right]+\sum_{s=1}^{k}a_{s,k}\mathbb{E}_{n}\left[\left\|C^{s}R^{(0)}-\tilde{M}^{s}\breve{R}\right\|_{\infty}\right]$
$\displaystyle\leq 1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\left(\sum_{r=1}^{s-1}\mathbb{E}_{n}\left[\left\|(C-\tilde{M})\tilde{M}^{r}\breve{W}\right\|_{\infty}\right]+\mathbb{E}_{n}\left[\left\|CW^{(k-t)}-\tilde{M}\breve{W}\right\|_{\infty}\right]\right)$
$\displaystyle\hskip
14.22636pt+\sum_{s=1}^{k}a_{s,k}\left(\sum_{r=1}^{s-1}\mathbb{E}_{n}\left[\left\|(C-\tilde{M})\tilde{M}^{r}\breve{R}\right\|_{\infty}\right]+\mathbb{E}_{n}\left[\left\|CR^{(0)}-\tilde{M}\breve{R}\right\|_{\infty}\right]\right)$
$\displaystyle\leq\max_{r\geq 1}h(\tilde{M}^{r}\breve{W})1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}(s-1)+\mathbb{E}_{n}\left[\left\|CW^{(0)}-\tilde{M}\breve{W}\right\|_{\infty}\right]1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}$ $\displaystyle\hskip
14.22636pt+\max_{r\geq
1}h(\tilde{M}^{r}\breve{R})\sum_{s=1}^{k}a_{s,k}(s-1)+\mathbb{E}_{n}\left[\left\|CR^{(0)}-\tilde{M}\breve{R}\right\|_{\infty}\right]\sum_{s=1}^{k}a_{s,k}.$

To compute the double sums more explicitly, let $\text{Bin}(n,p)$ denote a
binomial random variable with parameters $(n,p)$, and note that for $k\geq 1$,

$\displaystyle\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}s$
$\displaystyle=\sum_{t=1}^{k}\sum_{s=1}^{t}\binom{t}{s}(1-c-d)^{t-s}c^{s}s=\sum_{t=1}^{k}(1-d)^{t}E[\text{Bin}(t,c/(1-d))]=c\sum_{t=1}^{k}(1-d)^{t-1}t,$
(5.4)

and

$\displaystyle\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}$
$\displaystyle=\sum_{t=1}^{k}\sum_{s=1}^{t}\binom{t}{s}(1-c-d)^{t-s}c^{s}=\sum_{t=1}^{k}(1-d)^{t}P(\text{Bin}(t,c/(1-d))\geq
1)$
$\displaystyle=\sum_{t=1}^{k}(1-d)^{t}\left(1-(1-c-d)^{t}/(1-d)^{t}\right)=\sum_{t=1}^{k}\left((1-d)^{t}-(1-c-d)^{t}\right).$
(5.5)

Similarly, the single sums can be computed to be

$\sum_{s=1}^{k}a_{s,k}s=\sum_{s=1}^{k}\binom{k}{s}(1-c-d)^{k-s}c^{s}s=(1-d)^{k}E[\text{Bin}(k,c/(1-d))]=ck(1-d)^{k-1}$
(5.6)

and

$\sum_{s=1}^{k}a_{s,k}=\sum_{s=1}^{k}\binom{k}{s}(1-c-d)^{k-s}c^{s}=(1-d)^{k}P(\text{Bin}(k,c/(1-d))\geq
1)=(1-d)^{k}-(1-c-d)^{k}.$ (5.7)

Consequently,

$\displaystyle\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]$
$\displaystyle\leq\max_{r\geq 1}h(\tilde{M}^{r}\breve{W})1(k\geq
2)\sum_{t=1}^{k-1}(1-d)^{t-1}t$ $\displaystyle\hskip
14.22636pt+\mathbb{E}_{n}\left[\left\|CW^{(0)}-\tilde{M}\breve{W}\right\|_{\infty}\right]1(k\geq
2)\sum_{t=1}^{k-1}(1-d)^{t}+$ $\displaystyle\hskip 14.22636pt+\max_{r\geq
1}h(\tilde{M}^{r}\breve{R})\,k(1-d)^{k-1}+\mathbb{E}_{n}\left[\left\|CR^{(0)}-\tilde{M}\breve{R}\right\|_{\infty}\right](1-d)^{k}.$

∎

Once the intermediate approximation $\\{\tilde{R}^{(k)}:k\geq 0\\}$ given by
(5.3) is obtained, its connection to the final approximation
$\\{\mathcal{R}^{(k)}:k\geq 0\\}$ given by (3.2) becomes apparent, since for
all $s\geq 1$ we have

$(\tilde{M}^{s}\breve{W})_{i\bullet}\approx(M^{s}\bar{W})_{J_{i}\bullet}\qquad\text{and}\qquad(\tilde{M}^{s}\breve{R})_{i\bullet}\approx(M^{s}\bar{R})_{J_{i}\bullet},$

for large $n$. The following result provides a bound for the norm between
these two processes.

######  Theorem 5.2.

For any $\theta_{n}\to\infty$,

$\sup_{k\geq
0}\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\leq\frac{\ell
c}{d^{2}}\cdot\mathcal{E}_{n},$

where $\mathcal{E}_{n}=\max_{1\leq r,s\leq
K}\left|\frac{\pi_{s}^{(n)}\pi_{r}-\pi_{s}\pi_{r}^{(n)}}{\pi_{r}^{(n)}\pi_{s}}\right|$.

###### Proof.

Note that for any $1\leq j\leq K$,

$\displaystyle\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}$
$\displaystyle=\max_{1\leq i\leq n}\sum_{j=1}^{\ell}\left|1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}(\tilde{M}^{s}\breve{W})_{ij}+\sum_{s=1}^{k}a_{s,k}(\tilde{M}^{s}\breve{R})_{ij}-\right.$
$\displaystyle\hskip 113.81102pt\left.-1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}(M^{s}\bar{W})_{J_{i}j}-\sum_{s=1}^{k}a_{s,k}(M\bar{R})_{J_{i}j}\right|$
$\displaystyle=\max_{1\leq i\leq n}\sum_{j=1}^{\ell}\left|1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\left((\tilde{M}^{s}\breve{W})_{ij}-(M^{s}\bar{W})_{J_{i}j}\right)+\sum_{s=1}^{k}a_{s,k}\left((\tilde{M}^{s}\breve{R})_{ij}-(M^{s}\bar{R})_{J_{i}j}\right)\right|$
$\displaystyle\leq 1(k\geq 2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\max_{1\leq
i\leq
n}\sum_{j=1}^{\ell}\left|(\tilde{M}^{s}\breve{W})_{ij}-(M^{s}\bar{W})_{J_{i}j}\right|+\sum_{s=1}^{k}a_{s,k}\max_{1\leq
i\leq
n}\sum_{j=1}^{\ell}\left|(\tilde{M}^{s}\breve{R})_{ij}-(M^{s}\bar{R})_{J_{i}j}\right|.$

Note that $\tilde{M}\in\mathbb{R}^{n\times n}$ is such that all the rows
$\mathcal{S}_{r}=\\{\tilde{M}_{i\bullet}:J_{i}=r\\}$ are equal to each other,
all the columns $\\{\tilde{M}_{\bullet j}:J_{j}=r\\}$ are equal to each other,
and the cardinality of the $\mathcal{S}_{r}$ is $n\pi_{r}^{(n)}$, for $1\leq
r\leq K$. Similarly, the vector $\breve{W}_{\bullet j}\in\mathbb{R}^{n}$
satisfies that all the components $\\{\breve{W}_{ij}:J_{i}=r\\}$ are equal to
each other and the order in which the vertex labels appear is the same as the
columns of $\tilde{M}$. Define the matrix $\breve{M}\in\mathbb{R}^{K\times K}$
according to

$\breve{M}_{rs}=\frac{\beta_{r,s}\pi_{s}^{(n)}\kappa(s,r)}{\beta_{r,1}\pi_{1}^{(n)}\kappa(1,r)+\dots+\beta_{r,K}\pi_{K}^{(n)}\kappa(K,r)},\qquad
1\leq r,s\leq K,$ (5.8)

with $\breve{M}_{rs}\equiv 0$ if the denominator is zero, and note that

$\breve{M}_{rs}=\sum_{j=1}^{n}\tilde{M}_{ij}1(J_{j}=s)\qquad\text{for any $i$
such that $J_{i}=r$}.$

It follows that for any $i\in V_{n}$,

$(\tilde{M}\breve{W})_{ij}=\sum_{l=1}^{n}\tilde{M}_{il}\breve{W}_{lj}=\sum_{r=1}^{K}\sum_{l=1}^{n}\tilde{M}_{il}\breve{W}_{lj}1(J_{l}=r)=\sum_{r=1}^{K}\breve{M}_{J_{i},r}\bar{W}_{rj}=(\breve{M}\bar{W})_{J_{i}j}.$
(5.9)

Now suppose that
$(\tilde{M}^{s-1}\breve{W})_{ij}=(\breve{M}^{s-1}\bar{W})_{J_{i}j}$ for $s\geq
2$, and note that

$\displaystyle(\tilde{M}^{s}\breve{W})_{ij}$
$\displaystyle=\sum_{l=1}^{n}\tilde{M}_{il}(\tilde{M}^{s-1}\breve{W})_{lj}=\sum_{r=1}^{K}\sum_{l=1}^{n}\tilde{M}_{il}(\breve{M}^{s-1}\bar{W})_{J_{l}j}1(J_{l}=r)=\sum_{r=1}^{K}\breve{M}_{J_{i}r}(\breve{M}^{s-1}\bar{W})_{rj}=(\breve{M}^{s}\bar{W})_{J_{i}j},$

therefore, by induction, we conclude that

$(\tilde{M}^{s}\breve{W})_{ij}=(\breve{M}^{s}\bar{W})_{J_{i}j}\qquad\text{for
all }s\geq 1\text{ and all }i\in V_{n}.$

The same arguments also yield
$(\tilde{M}^{s}\breve{R})_{ij}=(\breve{M}^{s}\bar{R})_{J_{i}j}$ for all $s\geq
1$ and all $i\in V_{n}$. Hence,

$\max_{1\leq i\leq
n}\sum_{j=1}^{\ell}\left|(\tilde{M}^{s}\breve{W})_{ij}-(M^{s}\bar{W})_{J_{i}j}\right|=\max_{1\leq
i\leq
n}\sum_{j=1}^{\ell}\left|(\breve{M}^{s}\bar{W})_{J_{i}j}-(M^{s}\bar{W})_{J_{i}j}\right|=\|(\breve{M}^{s}-M^{s})\bar{W}\|_{\infty}$

and

$\max_{1\leq i\leq
n}\sum_{j=1}^{\ell}\left|(\tilde{M}^{s}\bar{R})_{ij}-(M^{s}\bar{R})_{J_{i}j}\right|=\|(\breve{M}^{s}-M^{s})\bar{R}\|_{\infty}.$

The first inequality now becomes

$\displaystyle\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}$
$\displaystyle\leq 1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\|(\breve{M}^{s}-M^{s})\bar{W}\|_{\infty}+\sum_{s=1}^{k}a_{s,k}\|(\breve{M}^{s}-M^{s})\bar{R}\|_{\infty}$
$\displaystyle\leq 1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\|\breve{M}^{s}-M^{s}\|_{\infty}\|\bar{W}\|_{\infty}+\sum_{s=1}^{k}a_{s,k}\|\breve{M}^{s}-M^{s}\|_{\infty}\|\bar{R}\|_{\infty}$
$\displaystyle\leq\ell\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}\|\breve{M}^{s}-M^{s}\|_{\infty},$

where in the last step we used the observation that
$\|\bar{W}\|_{\infty}\leq\ell$ and $\|\bar{R}\|_{\infty}\leq\ell$. For the
remaining norm, note that

$\displaystyle x_{s}$
$\displaystyle:=\|\breve{M}^{s}-M^{s}\|_{\infty}\leq\|\breve{M}^{s}-\breve{M}^{s-1}M\|_{\infty}+\|\breve{M}^{s-1}M-M^{s}\|_{\infty}$
$\displaystyle\leq\|\breve{M}\|_{\infty}^{s-1}\|\breve{M}-M\|_{\infty}+\|\breve{M}^{s-1}-M^{s-1}\|_{\infty}\|M\|_{\infty}\leq\|\breve{M}-M\|_{\infty}+x_{s-1}$
$\displaystyle\leq s\|\breve{M}-M\|_{\infty},$

since $x_{0}=0$ and $\|M\|_{\infty}=\|\breve{M}\|_{\infty}=1$. Finally, note
that for $\mathcal{I}$ the set of non-zero rows of $M$ (same as the non-zero
rows of $\breve{M}$), we have

$\displaystyle\|\breve{M}-M\|_{\infty}$
$\displaystyle=\max_{r\in\mathcal{I}}\sum_{s=1}^{K}\left|\frac{\beta_{r,s}\pi_{s}^{(n)}\kappa(s,r)}{\beta_{r,1}\pi_{1}^{(n)}\kappa(1,r)+\dots+\beta_{r,K}\pi_{K}^{(n)}\kappa(K,r)}-\frac{\beta_{r,s}\pi_{s}\kappa(s,r)}{\beta_{r,1}\pi_{1}\kappa(1,r)+\dots+\beta_{r,K}\pi_{K}\kappa(K,r)}\right|$
$\displaystyle=\max_{r\in\mathcal{I}}\dfrac{\sum_{s=1}^{K}\beta_{r,s}\kappa(s,r)\left|(\pi_{s}^{(n)}\pi_{1}-\pi_{s}\pi_{1}^{(n)})\beta_{r,1}\kappa(1,r)+\dots+(\pi_{s}^{(n)}\pi_{K}-\pi_{s}\pi_{K}^{(n)})\beta_{r,K}\kappa(K,r))\right|}{(\beta_{r,1}\pi_{1}^{(n)}\kappa(1,r)+\dots+\beta_{r,K}\pi_{K}^{(n)}\kappa(K,r))(\beta_{r,1}\pi_{1}\kappa(1,r)+\dots+\beta_{r,K}\pi_{K}\kappa(K,r))}$
$\displaystyle=\max_{r\in\mathcal{I}}\dfrac{\sum_{s=1}^{K}\beta_{r,s}\pi_{s}\kappa(s,r)\sum_{l=1}^{K}\left|\frac{\pi_{s}^{(n)}\pi_{l}-\pi_{s}\pi_{l}^{(n)}}{\pi_{l}^{(n)}\pi_{s}}\right|\beta_{r,l}\pi_{l}^{(n)}\kappa(l,r)}{\sum_{m=1}^{K}\beta_{r,m}\pi_{m}^{(n)}\kappa(m,r)\sum_{n=1}^{K}\beta_{r,n}\pi_{n}\kappa(n,r)}$
$\displaystyle\leq\max_{1\leq r,s\leq
K}\left|\frac{\pi_{s}^{(n)}\pi_{r}-\pi_{s}\pi_{r}^{(n)}}{\pi_{r}^{(n)}\pi_{s}}\right|=\mathcal{E}_{n}.$

Combining our estimates, we deduce

$\displaystyle\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}$
$\displaystyle\leq\ell\mathcal{E}_{n}\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}s=\ell
c\,\mathcal{E}_{n}\sum_{t=1}^{k}(1-d)^{t-1}t\leq\ell
c\,\mathcal{E}_{n}\sum_{t=1}^{\infty}(1-d)^{t-1}t\leq\frac{\ell
c}{d^{2}}\cdot\mathcal{E}_{n},$

where the last equality comes from (5.4). Taking the supremum over $k$
completes the proof. ∎

The proof of Theorem 3.1 is based on the estimation in Theorem 5.1 of the
expected norms

$\mathbb{E}_{n}\left[\left\|(C-\tilde{M})\breve{X}\right\|_{\infty}\right]\qquad\text{and}\qquad\mathbb{E}_{n}\left[\left\|CX-\tilde{M}\breve{X}\right\|_{\infty}\right]$
(5.10)

for $X$ conditionally independent of $C$ given
$\mathscr{F}_{n}=\sigma\left(\mathbf{Y}_{i}:i\in V_{n}\right)$ and having mean
$\breve{X}=\mathbb{E}_{n}[X]$, when $\theta_{n}\geq\gamma\log n$, and of the
expected norms

$\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|(C^{s}X)_{i\bullet}-(\tilde{M}^{s}\breve{X})_{i\bullet}\right\|_{1}\right]$
(5.11)

for $s\geq 1$, when $\theta_{n}/\log n\to 0$ as $n\to\infty$. This is done in
the next two sections.

###  5.1. The semi-sparse to dense regimes

When the edge density in the graph is sufficiently large, the concentration of
the matrix $C$ around the matrix $\tilde{M}$ is very strong. It is worth
pointing out that $\tilde{M}$ is not the mean of $C$, but rather, its more
tractable asymptotic mean. For the norm involving $R^{(0)}$, the concentration
occurs around its mean matrix $\bar{R}$, and the strength of this
concentration is determined by the matrix $\tilde{M}$. The main result in this
section provides estimates for the two expected norms in (5.10). Its proof
relies on the following concentration inequality for Binomial or Poisson
random sums, and its consequence on ratios of random sums.

######  Proposition 5.1.

Let $\\{Y_{i}^{(r)}:i\geq 1,1\leq r\leq K\\}$ be independent random variables
on $[-H,H]$, with $\\{Y_{i}^{(r)}:i\geq 1\\}$ i.i.d. for each $1\leq r\leq K$,
and $E[(Y_{1}^{(r)})^{2}]\leq v_{r}$. Let $\\{N_{r}:1\leq r\leq K\\}$ be
independent random variables on $\mathbb{N}$, independent of
$\\{Y_{i}^{(r)}:i\geq 1,1\leq r\leq K\\}$, and satisfying $E[e^{sN_{r}}]\leq
e^{E[N_{r}](e^{s}-1)}$ for $s\in\mathbb{R}$. Define
$S_{r}=\sum_{i=1}^{N_{r}}Y_{i}^{(r)}.$ Then, for any $\epsilon>0$,

$P\left(\sum_{r=1}^{K}(S_{r}-E[S_{r}])>\epsilon\mu\right)\leq\text{exp}\left(-\frac{(\epsilon\mu)^{2}}{2\nu}+H\frac{(\epsilon\mu)^{3}}{2\nu^{2}}\right),$

where $\mu=\sum_{r=1}^{K}E[N_{r}]E[|Y_{1}^{(r)}|]$ and
$\nu=\sum_{r=1}^{K}E[N_{r}]v_{r}$.

###### Proof.

Start by conditioning on $\\{N_{r}:1\leq r\leq K\\}$ and use Chernoff’s bound
to obtain that for any $\theta>0$,

$\displaystyle P\left(\sum_{r=1}^{K}(S_{r}-E[S_{r}])>\epsilon\mu\right)$
$\displaystyle=E\left[P\left(\left.\sum_{r=1}^{K}(S_{r}-E[S_{r}])>\epsilon\mu\right|N_{1},\dots,N_{K}\right)\right]$
$\displaystyle\leq
E\left[e^{-\theta\epsilon\mu}\prod_{r=1}^{K}E\left[\left.e^{\theta(S_{r}-E[S_{r}])}\right|N_{r}\right]\right]=e^{-\theta\epsilon\mu}\prod_{r=1}^{K}e^{-\theta
E[S_{r}]}E\left[E\left[e^{\theta Y_{1}^{(r)}}\right]^{N_{r}}\right].$

Using the third order Taylor approximation for $e^{\theta x}$, we obtain

$\displaystyle E[e^{\theta Y_{1}^{(r)}}]$ $\displaystyle\leq 1+\theta
E[Y_{1}^{(r)}]+\sum_{k=2}^{\infty}\frac{\theta^{k}E[|Y_{1}^{(r)}|^{k}]}{k!}\leq
1+\theta
E[Y_{1}^{(r)}]+\left(\sum_{k=2}^{\infty}\frac{\theta^{k}H^{k-2}}{k!}\right)E[(Y_{1}^{(r)})^{2}]$
$\displaystyle\leq 1+\theta E[Y_{1}^{(r)}]+\frac{v_{r}}{H^{2}}(e^{\theta
H}-\theta H-1)=:1+\lambda_{r}(\theta).$

It follows from the assumption on the moment generating function of $N_{r}$
and the observation $E[S_{r}]=E[N_{r}]E[Y_{1}^{(r)}]$, that

$\displaystyle P\left(\sum_{r=1}^{K}(S_{r}-E[S_{r}])>\epsilon\mu\right)$
$\displaystyle\leq e^{-\theta\epsilon\mu}\prod_{r=1}^{K}e^{-\theta
E[S_{r}]}E\left[(1+\lambda_{r}(\theta))^{N_{r}}\right]=e^{-\theta\epsilon\mu}\prod_{r=1}^{K}e^{-\theta
E[S_{r}]}E\left[e^{N_{r}\log(1+\lambda_{r}(\theta))}\right]$
$\displaystyle\leq e^{-\theta\epsilon\mu}\prod_{r=1}^{K}e^{-\theta
E[S_{r}]+E[N_{r}](e^{\log(1+\lambda_{r}(\theta))}-1)}=e^{-\theta\epsilon\mu+\sum_{r=1}^{K}E[N_{r}](\lambda_{r}(\theta)-\theta
E[Y_{1}^{(r)}])}$
$\displaystyle=e^{-\theta\epsilon\mu+\frac{\nu}{H^{2}}(e^{\theta H}-\theta
H-1)}.$

Picking
$\theta=\frac{1}{H}\log\left(1+H\epsilon\mu/\nu\right)\geq\epsilon\mu/\nu-(H\epsilon^{2}\mu^{2})/(2\nu^{2})$,
we get

$\displaystyle P\left(\sum_{r=1}^{K}(S_{r}-E[S_{r}])>\epsilon\mu\right)$
$\displaystyle\leq
e^{-\theta\epsilon\mu+\frac{\nu}{H}(\epsilon\mu/\nu-\theta)}\leq
e^{-\left(\frac{\epsilon\mu}{\nu}-\frac{H\epsilon^{2}\mu^{2}}{2\nu^{2}}\right)(\epsilon\mu+\nu/H)+\frac{\epsilon\mu}{H}}=e^{-\frac{\epsilon^{2}\mu^{2}}{2\nu}+\frac{H\epsilon^{3}\mu^{3}}{2\nu^{2}}}.$

∎

Next, we use Proposition 5.1 to bound the event that ratios of random sums are
far from the ratios of their means.

######  Lemma 5.1.

Let $\\{B_{i}^{(r)},X_{i}^{(r)}:i\geq 1,1\leq r\leq K\\}$ be independent
random variables, with $B_{i}^{(r)}\in[0,H]$, $X_{i}^{(r)}\in[-1,1]$, and such
that $\\{(B_{i}^{(r)},X_{i}^{(r)}):i\geq 1\\}$ are i.i.d. for each $1\leq
r\leq K$. Let $\\{N_{r}:1\leq r\leq K\\}$ be independent random variables on
$\mathbb{N}$, independent of the $\\{(B_{i}^{(r)},X_{i}^{(r)}):i\geq 1,1\leq
r\leq K\\}$, and satisfying $E[e^{sN_{r}}]\leq e^{E[N_{r}](e^{s}-1)}$ for
$s\in\mathbb{R}$. Define $S_{r}=\sum_{i=1}^{N_{r}}B_{i}^{(r)}$ and
$\tilde{S}_{r}=\sum_{i=1}^{N_{r}}X_{i}^{(r)}B_{i}^{(r)}$. Then, for any
$\epsilon>0$,

$P\left(\left|\frac{\tilde{S}_{1}+\dots+\tilde{S}_{K}}{S_{1}+\dots+S_{K}}-\frac{E[\tilde{S}_{1}]+\dots+E[\tilde{S}_{K}]}{E[S_{1}]+\dots+E[S_{K}]}\right|>\epsilon\right)\leq
4\text{exp}\left(-\frac{(\epsilon/2)^{2}\mu^{2}}{2\nu}+\frac{H(\epsilon/2)^{3}\mu^{3}}{2\nu^{2}}\right),$

where $\mu=\sum_{r=1}^{K}E[N_{r}]E[B_{1}^{(r)}]$ and
$\nu=\sum_{r=1}^{K}E[N_{r}]E[(B_{1}^{(r)})^{2}]$.

###### Proof.

To start, note that since $|\tilde{S}_{r}|\leq S_{r}$ for each
$r\in\\{1,\dots,K\\}$, then

$\displaystyle\left|\frac{\tilde{S}_{1}+\dots+\tilde{S}_{K}}{S_{1}+\dots+S_{K}}-\frac{E[\tilde{S}_{1}]+\dots+E[\tilde{S}_{K}]}{E[S_{1}]+\dots+E[S_{K}]}\right|$
$\displaystyle=\frac{1}{(S_{1}+\dots+S_{K})E[S_{1}+\dots+S_{K}]}\left|\sum_{r=1}^{K}\sum_{t=1}^{K}E[S_{r}]\tilde{S}_{t}-\sum_{r=1}^{K}\sum_{t=1}^{K}S_{r}E[\tilde{S}_{t}]\right|$
$\displaystyle\leq\frac{1}{(S_{1}+\dots+S_{K})\mu}\left(\left|\sum_{r=1}^{K}\sum_{t=1}^{K}E[S_{r}]\tilde{S}_{t}-\sum_{r=1}^{K}\sum_{t=1}^{K}S_{r}\tilde{S}_{t}\right|+\left|\sum_{r=1}^{K}\sum_{t=1}^{K}S_{r}\tilde{S}_{t}-\sum_{r=1}^{K}\sum_{t=1}^{K}S_{r}E[\tilde{S}_{t}]\right|\right)$
$\displaystyle=\frac{1}{(S_{1}+\dots+S_{K})\mu}\left(\left|\sum_{t=1}^{K}\tilde{S}_{t}\right|\left|\sum_{r=1}^{K}(E[S_{r}]-S_{r})\right|+\sum_{r=1}^{K}S_{r}\left|\sum_{t=1}^{K}(\tilde{S}_{t}-E[\tilde{S}_{t}])\right|\right)$
$\displaystyle\leq\frac{1}{\mu}\left(\left|\sum_{r=1}^{K}(E[S_{r}]-S_{r})\right|+\left|\sum_{t=1}^{K}(\tilde{S}_{t}-E[\tilde{S}_{t}])\right|\right).$

Next, define the events

$F=\left\\{\left|\sum_{r=1}^{K}(S_{r}-E[S_{r}])\right|>\epsilon\mu/2\right\\}\qquad\text{and}\qquad
G=\left\\{\left|\sum_{r=1}^{K}(\tilde{S}_{r}-E[\tilde{S}_{r}])\right|>\epsilon\mu/2\right\\},$

and use the union bound to obtain that

$\displaystyle
P\left(\left|\frac{\tilde{S}_{1}+\dots+\tilde{S}_{K}}{S_{1}+\dots+S_{K}}-\frac{E[\tilde{S}_{1}]+\dots+E[\tilde{S}_{K}]}{E[S_{1}]+\dots+E[S_{K}]}\right|>\epsilon\right)$
$\displaystyle\leq
P\left(\left|\sum_{r=1}^{K}(E[S_{r}]-S_{r})\right|+\left|\sum_{t=1}^{K}(\tilde{S}_{t}-E[\tilde{S}_{t}])\right|>\epsilon\mu\right)$
$\displaystyle\leq P(F^{c})+P(G^{c}).$

Finally, let
$\tilde{\mu}=\sum_{r=1}^{K}E[N_{r}]E[|X_{1}^{(r)}|]E[B_{1}^{(r)}]$, and use
Proposition 5.1 with $Y_{i}^{(r)}=B_{i}^{(r)}$ and $Y_{i}^{(r)}=-B_{i}^{(r)}$
to obtain that

$P(F^{c})\leq
2\text{exp}\left(-\frac{(\epsilon/2)^{2}\mu^{2}}{2\nu}+\frac{H(\epsilon/2)^{3}\mu^{3}}{2\nu^{2}}\right),$

and then again with $Y_{i}^{(r)}=-X_{i}^{(r)}B_{i}^{(r)}$ and
$Y_{i}^{(r)}=X_{i}^{(r)}B_{i}^{(r)}$ to get

$P(G^{c})\leq
2\text{exp}\left(-\frac{(\epsilon\mu/(2\tilde{\mu}))^{2}\tilde{\mu}^{2}}{2\nu}+\frac{H(\epsilon\mu/(2\tilde{\mu}))^{3}\tilde{\mu}^{3}}{2\nu^{2}}\right)=2\text{exp}\left(-\frac{(\epsilon/2)^{2}\mu^{2}}{2\nu}+\frac{H(\epsilon/2)^{3}\mu^{3}}{2\nu^{2}}\right).$

This completes the proof. ∎

Now, we are able to prove the main result of this section. Recall that
$\beta_{r,s}=E[B_{ij}|J_{i}=r,J_{j}=s]$,
$v_{r,s}=E[B_{ij}^{2}|J_{i}=r,J_{j}=s]$ for $1\leq r,s\leq K$,

$\mu_{r}^{(n)}=\sum_{s=1}^{K}\beta_{r,s}\pi_{s}^{(n)}\kappa(s,r)\qquad\text{and}\qquad\nu_{r}^{(n)}=\sum_{s=1}^{K}v_{r,s}\pi_{s}^{(n)}\kappa(s,r),$

for $1\leq r\leq K$ and large enough $n$,
$\Delta_{n}=\max\limits_{r\in\mathcal{I}}\nu_{r}^{(n)}/(\mu_{r}^{(n)})^{2}$
and $\Lambda_{n}=\max\limits_{r\in\mathcal{I}}\mu_{r}^{(n)}/\nu_{r}^{(n)}$,
where $\mathcal{I}$ is the set of nonzero rows of $M$.

######  Theorem 5.3.

Let $X\in\mathbb{R}^{n\times\ell}$ be a random matrix conditionally
independent of $C$ given $\mathscr{F}_{n}$ and having mean
$\breve{X}=\mathbb{E}_{n}[X]$. Furthermore, suppose $X$ has conditionally
independent rows $\\{\mathbf{X}_{i}:i\in V_{n}\\}$ given $\mathscr{F}_{n}$ and
satisfies $\|\mathbf{X}_{i}\|_{\infty}\leq 1$ a.s., and for each $1\leq r\leq
K$, its rows $\\{\mathbf{X}_{i}:J_{i}=r\\}$ are identically distributed. Then,
for $\theta_{n}\geq(2H\Lambda_{n}/\gamma)^{2}\Delta_{n}\log n$ and
$0<\gamma<1/2$, there exists a constant $\Gamma^{\prime}<\infty$ such that

$\displaystyle\mathbb{E}_{n}\left[\left\|CX-\tilde{M}\breve{X}\right\|_{\infty}\right]$
$\displaystyle\leq\Gamma^{\prime}\sqrt{\frac{\log n}{\theta_{n}}},$
$\displaystyle\mathbb{E}_{n}\left[\left\|(C-\tilde{M})\breve{X}\right\|_{\infty}\right]$
$\displaystyle\leq\Gamma^{\prime}\sqrt{\frac{\log n}{\theta_{n}}}.$

###### Proof.

To start, note that since $C$ and $\tilde{M}$ have the same deterministically
zero rows (if any), we can simply ignore them throughout the proof. Now let
$\mathcal{I}_{*}$ denote the set of non-zero rows of $\tilde{M}$, fix
$\epsilon>0$, and define the events

$F_{it}=\left\\{\left|(CX)_{it}-(\tilde{M}\breve{X})_{it}\right|\leq
2\epsilon\right\\},\quad i\in\mathcal{I}_{*},\,1\leq t\leq\ell.$

Next, note that

$\displaystyle\mathbb{E}_{n}\left[\left\|CX-\tilde{M}\breve{X}\right\|_{\infty}\right]$
$\displaystyle=\mathbb{E}_{n}\left[\max_{i\in\mathcal{I}_{*}}\sum_{t=1}^{\ell}\left|(CX)_{it}-(\tilde{M}\breve{X})_{it}\right|\right]$
$\displaystyle\leq\mathbb{E}_{n}\left[\max_{i\in\mathcal{I}_{*}}\sum_{t=1}^{\ell}\left|(CX)_{it}-(\tilde{M}\breve{X})_{it}\right|1\left(F_{it}\right)\right]$
$\displaystyle\hskip
14.22636pt+\mathbb{E}_{n}\left[\max_{i\in\mathcal{I}_{*}}\sum_{t=1}^{\ell}\left(|(CX)_{it}|+|(\tilde{M}\breve{X})_{it}|\right)1\left(F_{it}^{c}\right)\right]$
$\displaystyle\leq\mathbb{E}_{n}\left[\max_{i\in\mathcal{I}_{*}}\sum_{t=1}^{\ell}2\epsilon
1\left(F_{it}\right)\right]+\mathbb{E}_{n}\left[\max_{i\in\mathcal{I}_{*}}2\sum_{t=1}^{\ell}1(F_{it}^{c})\right]$
$\displaystyle\leq
2\ell\epsilon+2\sum_{i\in\mathcal{I}_{*}}\mathbb{E}_{n}\left[\sum_{t=1}^{\ell}1\left(F_{it}^{c}\right)\right],$

where in the last step we used the observation that

$\sum_{t=1}^{\ell}|(CX)_{it}|1(F_{it}^{c})\leq\sum_{t=1}^{\ell}\sum_{j=1}^{n}C_{ij}|X_{jt}|1(F_{it}^{c})\leq\sum_{t=1}^{\ell}\|C_{i\bullet}\|_{1}1(F_{it}^{c})\leq\sum_{t=1}^{\ell}1(F_{it}^{c}),$

and similarly,
$\sum_{t=1}^{\ell}|(\tilde{M}\breve{X})_{it}|1(F_{it}^{c})\leq\sum_{t=1}^{\ell}1(F_{it}^{c})$.
It follows that

$\mathbb{E}_{n}\left[\left\|CX-\tilde{M}\breve{X}\right\|_{\infty}\right]\leq
2\epsilon\ell+2\sum_{i\in\mathcal{I}_{*}}\sum_{t=1}^{\ell}\mathbb{P}_{n}\left(F_{it}^{c}\right).$

To bound $\mathbb{P}_{n}\left(F_{it}^{c}\right)$, start by noting that

$\displaystyle\left|(CX)_{it}-(\tilde{M}\breve{X})_{it}\right|$
$\displaystyle=\left|\sum_{j=1}^{n}C_{ij}X_{jt}-\sum_{j=1}^{n}\tilde{M}_{ij}\breve{X}_{jt}\right|=\left|\frac{\sum_{j=1}^{n}X_{jt}B_{ij}1(j\to
i)}{\sum_{r=1}^{n}B_{ir}1(r\to
i)}-\frac{\sum_{j=1}^{n}\breve{X}_{jt}\beta_{J_{i},J_{j}}p_{ji}^{(n)}}{\sum_{r=1}^{n}\beta_{J_{i},J_{r}}p_{ri}^{(n)}}\right|.$

Next, note that we can rewrite

$\sum_{j=1}^{n}X_{jt}B_{ij}1(j\to
i)=\sum_{r=1}^{K}\sum_{j=1}^{n}X_{jt}B_{ij}1(j\to
i)1(J_{j}=r)=:\sum_{r=1}^{K}S_{i,r}^{(t)}$

and

$\sum_{j=1}^{n}B_{ij}1(j\to i)=\sum_{r=1}^{K}\sum_{j=1}^{n}B_{ij}1(j\to
i)1(J_{j}=r)=:\sum_{r=1}^{K}S_{i,r}.$

Moreover, conditionally on $J_{i}$, we have that
$S_{i,r}^{(t)}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\sum_{j=1}^{N_{i,r}}X_{j}^{(t,r)}B_{j}^{(i,r)}$
and
$S_{i,r}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\sum_{j=1}^{N_{i,r}}B_{j}^{(i,r)}$,
with $N_{i,r}$ a binomial with parameters
$(n\pi_{r}^{(n)},\kappa(r,J_{i})\theta_{n}/n)$, independent of the i.i.d.
sequences $\\{B_{j}^{(i,r)}:j\geq 1\\}$ and $\\{X_{j}^{(t,r)}:j\geq 1\\}$,
which satisfy
$B_{j}^{(i,r)}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(B_{ij}|J_{i},J_{j}=r)$,
$X_{j}^{(t,r)}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(X_{jt}|J_{j}=r)$, and
$\bar{x}_{j}=\breve{X}_{jt}$ for $J_{j}=r$. It follows from Lemma 5.1 that

$\displaystyle\mathbb{P}_{n}\left(F_{it}^{c}\right)$
$\displaystyle=P\left(\left|\frac{S_{i,1}^{(t)}+\dots+S_{i,K}^{(t)}}{S_{i,1}+\dots+S_{i,K}}-\frac{E[S_{i,1}^{(t)}]+\dots+E[S_{i,K}^{(t)}]}{E[S_{i,1}]+\dots+E[S_{i,K}]}\right|>2\epsilon\right)$
$\displaystyle\leq
4\text{exp}\left(-\frac{\epsilon^{2}(\theta_{n}\mu_{J_{i}}^{(n)})^{2}}{2\theta_{n}\nu_{J_{i}}^{(n)}}+\frac{H\epsilon^{3}(\theta_{n}\mu_{J_{i}}^{(n)})^{3}}{2(\theta_{n}\nu_{J_{i}}^{(n)})^{2}}\right)=4\text{exp}\left(-\frac{\epsilon^{2}\theta_{n}(\mu_{J_{i}}^{(n)})^{2}}{2\nu_{J_{i}}^{(n)}}\left(1-\frac{H\epsilon\mu_{J_{i}}^{(n)}}{\nu_{J_{i}}^{(n)}}\right)\right)$

where

$\displaystyle\mu_{J_{i}}^{(n)}$
$\displaystyle=\sum_{r=1}^{K}\pi_{r}^{(n)}\kappa(r,J_{i})\beta_{J_{i},r}=\theta_{n}^{-1}\sum_{r=1}^{K}E[N_{i,r}]E[B_{1}^{(i,r)}]$
$\displaystyle\nu_{J_{i}}^{(n)}$
$\displaystyle=\sum_{r=1}^{K}\pi_{r}^{(n)}\kappa(r,J_{i})v_{J_{i},r}=\theta_{n}^{-1}\sum_{r=1}^{K}E[N_{i,r}]E[(B_{1}^{(r)})^{2}].$

Therefore,

$\displaystyle\mathbb{E}_{n}\left[\left\|CX-\tilde{M}\breve{X}\right\|_{\infty}\right]$
$\displaystyle\leq
2\ell\epsilon+8\sum_{i\in\mathcal{I}_{*}}\sum_{t=1}^{\ell}\text{exp}\left(-\frac{\epsilon^{2}\theta_{n}(\mu_{J_{i}}^{(n)})^{2}}{2\nu_{J_{i}}^{(n)}}\left(1-\frac{H\epsilon\mu_{J_{i}}^{(n)}}{\nu_{J_{i}}^{(n)}}\right)\right)$
$\displaystyle=2\ell\epsilon+8\ell\sum_{r\in\mathcal{I}}n\pi_{r}^{(n)}\text{exp}\left(-\frac{\epsilon^{2}\theta_{n}(\mu_{r}^{(n)})^{2}}{2\nu_{r}^{(n)}}\left(1-\frac{H\epsilon\mu_{r}^{(n)}}{\nu_{r}^{(n)}}\right)\right)$
$\displaystyle\leq
2\ell\epsilon+8\ell\sum_{r\in\mathcal{I}}n\pi_{r}^{(n)}\text{exp}\left(-\frac{\epsilon^{2}\theta_{n}(\mu_{r}^{(n)})^{2}}{2\nu_{r}^{(n)}}\left(1-H\epsilon\Lambda_{n}\right)\right)$
$\displaystyle\leq 2\ell\epsilon+8\ell
n\,\text{exp}\left(-\frac{\epsilon^{2}\theta_{n}}{2\Delta_{n}}\left(1-H\epsilon\Lambda_{n}\right)\right),$

where $\Delta_{n}=\max_{r\in\mathcal{I}}\nu_{r}^{(n)}/(\mu_{r}^{(n)})^{2}$ and
$\Lambda_{n}=\max_{r\in\mathcal{I}}\mu_{r}^{(n)}/\nu_{r}^{(n)}$. Next, choose
$\epsilon=\sqrt{4\Delta_{n}\log n/\theta_{n}}$ to obtain

$\displaystyle
n\,\text{exp}\left(-\frac{\epsilon^{2}\theta_{n}}{2\Delta_{n}}\left(1-H\epsilon\Lambda_{n}\right)\right)$
$\displaystyle=n\,\text{exp}\left(-2\log
n\left(1-\frac{2H\Lambda_{n}\sqrt{\Delta_{n}\log
n}}{\theta_{n}^{1/2}}\right)\right)$ $\displaystyle=\text{exp}\left(-\log
n\left(1-\frac{4H\Lambda_{n}\sqrt{\Delta_{n}\log
n}}{\theta_{n}^{1/2}}\right)\right),$

which in turn yields

$\mathbb{E}_{n}\left[\left\|CX-\tilde{M}\breve{X}\right\|_{\infty}\right]\leq
4\ell\sqrt{\Delta_{n}\log n/\theta_{n}}+8\ell\,\text{exp}\left(-\log
n\left(1-\frac{4H\Lambda_{n}\sqrt{\Delta_{n}\log
n}}{\theta_{n}^{1/2}}\right)\right).$

Since the second norm corresponds to the case when $X$ is deterministic, the
same argument also yields

$\mathbb{E}_{n}\left[\left\|(C-\tilde{M})\breve{X}\right\|_{\infty}\right]\leq
4\ell\sqrt{\Delta_{n}\log n/\theta_{n}}+8\ell\,\text{exp}\left(-\log
n\left(1-\frac{4H\Lambda_{n}\sqrt{\Delta_{n}\log
n}}{\theta_{n}^{1/2}}\right)\right).$

To complete the proof, note that if $(2H\Lambda_{n}/\gamma)^{2}\Delta_{n}\log
n\leq\theta_{n}\leq(\log n)^{3}$, then

$\displaystyle\sqrt{\Delta_{n}\log n/\theta_{n}}+\text{exp}\left(-\log
n\left(1-\frac{4H\Lambda_{n}\sqrt{\Delta_{n}\log
n}}{\theta_{n}^{1/2}}\right)\right)$ $\displaystyle\hskip
14.22636pt\leq\Delta_{n}^{1/2}\sqrt{\frac{\log
n}{\theta_{n}}}+\exp\left(-\left(1-2\gamma\right)\log
n\right)=\Delta_{n}^{1/2}\sqrt{\frac{\log
n}{\theta_{n}}}+n^{-1+2\gamma}=O\left(\sqrt{\frac{\log n}{\theta_{n}}}\right)$

as $n\to\infty$, while for $(\log n)^{3}<\theta_{n}\leq n/\kappa_{*}$, with
$\kappa_{*}=\max_{1\leq r,s\leq K}\kappa(r,s)$,

$\displaystyle\sqrt{\Delta_{n}\log n/\theta_{n}}+\text{exp}\left(-\log
n\left(1-\frac{4H\Lambda_{n}\sqrt{\Delta_{n}\log
n}}{\theta_{n}^{1/2}}\right)\right)$ $\displaystyle\hskip
14.22636pt\leq\Delta_{n}^{1/2}\sqrt{\frac{\log
n}{\theta_{n}}}+n^{-1}e^{4H\Lambda_{n}\sqrt{\Delta_{n}}}=O\left(\sqrt{\frac{\log
n}{\theta_{n}}}\right)$

as $n\to\infty$. The statement of the theorem now follows. ∎

We can now give the proof to the first part of Theorem 3.1.

###### Proof of Theorem 3.1.

Suppose $\theta_{n}\geq(6H\Lambda_{n})^{2}\Delta_{n}\log n$. We will prove
that

$\sup_{k\geq
0}\mathbb{E}_{n}\left[\left\|R^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right]=O\left(\sqrt{\frac{\log
n}{\theta_{n}}}+\mathcal{E}_{n}\right)$

as $n\to\infty$, where $\mathcal{E}_{n}=\max_{1\leq r,s\leq
K}\left|\frac{\pi_{s}^{(n)}\pi_{r}-\pi_{s}\pi_{r}^{(n)}}{\pi_{r}^{(n)}\pi_{s}}\right|$.
To start, use the triangle inequality to obtain

$\displaystyle\sup_{k\geq
0}\mathbb{E}_{n}\left[\left\|R^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right]$
$\displaystyle\leq\sup_{k\geq
0}\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]+\mathbb{E}_{n}\left[\sup_{k\geq
0}\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right].$

Theorem 5.2 yields

$\sup_{k\geq
0}\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\leq\frac{c\ell}{d^{2}}\,\mathcal{E}_{n}.$

For the remaining term, use Theorem 5.1 to obtain that

$\displaystyle\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]$
$\displaystyle\leq\max_{r\geq
1}h(\tilde{M}^{r}\breve{W})\sum_{t=0}^{k-1}(1-d)^{t-1}t+\mathbb{E}_{n}\left[\left\|CW^{(0)}-\tilde{M}\breve{W}\right\|_{\infty}\right]\sum_{t=0}^{k-1}(1-d)^{t}$
$\displaystyle\hskip 14.22636pt+\max_{r\geq
1}h(\tilde{M}^{r}\breve{R})\,k(1-d)^{k-1}+\mathbb{E}_{n}\left[\left\|CR^{(0)}-\tilde{M}\breve{R}\right\|_{\infty}\right](1-d)^{k}$

where
$h(X)=\mathbb{E}_{n}\left[\left\|(C-\tilde{M})X\right\|_{\infty}\right]$. Now
use Theorem 5.3 to obtain that, since
$\left\|\tilde{M}^{r}\breve{W}\right\|_{\infty}\leq\ell$ and
$\left\|\tilde{M}^{r}\breve{R}\right\|_{\infty}\leq\ell$ for all $r\geq 0$,
then

$\displaystyle\max\left\\{\max_{r\geq
1}h(\tilde{M}^{r}\breve{W}),\,\max_{r\geq
1}h(\tilde{M}^{r}\breve{R}),\,\mathbb{E}_{n}\left[\left\|CW^{(0)}-\tilde{M}\breve{W}\right\|_{\infty}\right],\,\mathbb{E}_{n}\left[\left\|CR^{(0)}-\tilde{M}\breve{R}\right\|_{\infty}\right]\right\\}\leq\ell\Gamma^{\prime}\sqrt{\frac{\log
n}{\theta_{n}}}.$

Therefore,

$\displaystyle\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]$
$\displaystyle\leq\ell\Gamma^{\prime}\sqrt{\frac{\log
n}{\theta_{n}}}\left(\sum_{t=0}^{k-1}(1-d)^{t-1}t+\sum_{t=0}^{k-1}(1-d)^{t}+k(1-d)^{k-1}+(1-d)^{k}\right),$

and since the supremum over $k$ is finite, there exists some other constant
$\Gamma<\infty$ such that

$\sup_{k\geq
0}\left(\mathbb{E}_{n}\left[\left\|R^{(k)}-\tilde{R}^{(k)}\right\|_{\infty}\right]+\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right)\leq\Gamma\left(\sqrt{\frac{\log
n}{\theta_{n}}}+\mathcal{E}_{n}\right).$

This completes the proof for the first part of the theorem. ∎

We now move to the density regime where $\log n/\theta_{n}$ may not converge
to zero. In that case, we can still prove concentration of the opinion matrix
$R^{(k)}$ to the mean-field limit $\mathcal{R}^{(k)}$ as $n\to\infty$, but in
a weaker mode of convergence.

###  5.2. The subcritical to sparse regimes

In this section we complete the proof of Theorem 3.1 by analyzing the expected
norms (5.11). When $\limsup_{n\to\infty}(\log n)/\theta_{n}>0$, the number of
neighbors is not enough to provide a full concentration of the matrix $C$
around its asymptotic mean $\tilde{M}$, since up to an $o(n)$ number of
vertices will not be sufficiently close to their limits. Instead of using the
supremum norm as in the denser case, we use an averaged $l_{1}$-norm, which is
what we typically use in sparse graphs where the local limiting structure of
the dSBM is what enables the analysis. The key observation in this section is
that for any matrix $X\in\mathbb{R}^{n\times\ell}$, $(C^{s}X)_{ij}$ is a
function of the inbound neighborhood of vertex $i\in V_{n}$ of length $s$,
which is approximately equal to $(\tilde{M}^{s}X)_{ij}$. In order for us to
make this connection, we need to describe the local behavior of neighborhoods
in the marked graph $G_{n}=(V_{n},E_{n};\mathscr{A}_{n})$, where
$\mathscr{A}_{n}=\\{\mathbf{Y}_{i}:i\in V_{n}\\}$ are the extended vertex
attributes.

####  5.2.1. Coupling with a multi-type Galton-Watson tree

Pick a vertex $I_{n}$, chosen uniformly at random from the vertex set $V_{n}$.
The idea behind local weak convergence is to couple the exploration of the
inbound neighborhood of $I_{n}$ with the construction of a rooted graph, whose
root $\emptyset$ corresponds to $I_{n}$. We point out that in our setting, the
local weak limit of the dSBM is a non locally-finite graph, so the coupling we
need is one between the exploration of the inbound neighborhood of $I_{n}$
with a branching tree whose degree distribution grows with $n$. We start by
introducing some terminology for trees.

We enumerate nodes in a rooted tree using the Ulam-Harris notation, which
contains the ancestry path of any node all the way to the root. For that, let
any node in generation $k\geq 1$ of the tree have a label of the form
$\mathbf{i}=(i_{1},\dots,i_{k})\in\mathbb{N}_{+}^{k}$, and define the
concatenation operation $(\mathbf{i},j)=(i_{1},\dots,i_{k},j)$ for a node in
generation $k+1$. The root is always denoted by $\emptyset$, but is omitted
from the label of any other node; to simplify the notation, we omit the
parentheses for nodes in the first generation. We denote by
$\mathcal{U}=\\{\emptyset\\}\cup\bigcup_{k=1}^{\infty}\mathbb{N}_{+}^{k}$ the
set of all possible node labels. The generation of a node
$\mathbf{i}\in\mathcal{U}$ is denoted by $|\mathbf{i}|$, for
$\mathbf{i}\neq\emptyset$.

The local weak limit of a sparse dSBM with $K$ communities is a marked
$K$-type Galton-Watson tree. Recall that our network is not a sparse graph, so
instead we are using an intermediate coupling (see [43] for a detailed
description of the construction). In order to obtain a description of the
coupled tree, we start by reminding the reader that vertices in $G_{n}$ have
extended attributes:

$\mathbf{Y}_{i}=(J_{i},\mathbf{Q}_{i},\mathbf{B}_{i})\in\\{1,\dots,K\\}\times[-1,1]^{\ell}\times[0,H]^{n},$
(5.12)

and $\mathscr{F}_{n}=\sigma\left(\mathbf{Y}_{i}:i\in V_{n}\right)$. In the
$K$-type Galton-Watson tree, each node $\mathbf{i}$ will have an attribute:

$\boldsymbol{\hat{A}}_{\mathbf{i}}=\left(\hat{J}_{\mathbf{i}},\boldsymbol{\hat{Q}}_{\mathbf{i}}\right)\in\\{1,\dots,K\\}\times[-1,1]^{\ell},$

and a full mark of the form:

$\boldsymbol{\hat{X}}_{\mathbf{i}}=\left(\hat{J}_{\mathbf{i}},\boldsymbol{\hat{Q}}_{\mathbf{i}},\\{\hat{N}_{\mathbf{i}}^{(r)}\\}_{r=1}^{K},\\{\hat{B}_{(\mathbf{i},s)}\\}_{s=1}^{\hat{N}_{\mathbf{i}}}\right)\in\\{1,\dots,K\\}\times[-1,1]^{\ell}\times\mathbb{N}^{K}\times[0,H]^{\infty},$

where $\hat{J}_{\mathbf{i}}$ is the type of node $\mathbf{i}$,
$\hat{N}_{\mathbf{i}}^{(r)}$ is the number of type $r$ offspring that node
$\mathbf{i}$ has, and
$\hat{N}_{\mathbf{i}}=\hat{N}_{\mathbf{i}}^{(1)}+\dots+\hat{N}_{\mathbf{i}}^{(K)}$.

We will construct the tree conditionally on the community labels
$\mathscr{J}_{n}=\\{J_{i}:i\in V_{n}\\}$. The unmarked tree will be denoted
$\mathcal{T}=\bigcup_{k=0}^{\infty}\mathcal{A}_{k}\subset\mathcal{U}$, where
$\mathcal{A}_{k}$ is the set of nodes in its $k$th generation, and each node
$\mathbf{i}\in\mathcal{T}$ will have a type $\hat{J}_{\mathbf{i}}$. To start,
set $\mathcal{A}_{0}=\\{\emptyset\\}$ and choose the type of the root
$\emptyset$ according to:

$\mathbb{P}_{n}\left(\hat{J}_{\emptyset}=r\right)=\dfrac{1}{n}\sum\limits_{i=1}^{n}1(J_{i}=r)=\pi_{r}^{(n)}.$

From here on, any node $\mathbf{i}\in\mathcal{A}_{k}$, will have an offspring
vector $(\hat{N}_{\mathbf{i}}^{(1)},\dots,\hat{N}_{\mathbf{i}}^{(K)})$,
conditionally independent of everything else given its type, and having
distribution:

$\mathbb{P}_{n}\left(\hat{N}_{\mathbf{i}}^{(1)}=n_{1},\dots,\hat{N}_{\mathbf{i}}^{(K)}=n_{K}\,\big{|}\,\hat{J}_{\mathbf{i}}=r\right)=\prod\limits_{s=1}^{K}e^{-q_{sr}^{(n)}}\dfrac{(q_{sr}^{(n)})^{n_{s}}}{n_{s}!},$

where $q_{sr}^{(n)}=\kappa(s,r)\pi_{s}^{(n)}\theta_{n}$. In other words, given
$\hat{J}_{\mathbf{i}}=r$, the numbers of offspring of each type $s$ of a node
of type $r$ are independent Poisson random variables with means
$q_{sr}^{(n)}$, $1\leq s\leq K$. To prevent the labels from conveying any
information, we usually permute the $\hat{N}_{\mathbf{i}}$ offspring uniformly
at random, and then set

$\mathcal{A}_{k+1}=\left\\{(\mathbf{i},j):\mathbf{i}\in\mathcal{A}_{k},1\leq
j\leq\hat{N}_{\mathbf{i}}\right\\}.$

Note that the conditional distribution of $\hat{J}_{(\mathbf{i},j)}$ for
$|\mathbf{i}|=k$, $k\geq 0$, depends on $\hat{J}_{\mathbf{i}}$ and is given by

$\mathbb{P}_{n}\left(\left.\hat{J}_{(\mathbf{i},j)}=s\right|\hat{J}_{\mathbf{i}}=r\right)=\mathbb{E}_{n}\left[\left.\frac{\hat{N}_{\mathbf{i}}^{(s)}1(\hat{N}_{\mathbf{i}}>0)}{\hat{N}_{\mathbf{i}}}\right|\hat{J}_{\mathbf{i}}=r\right]=\frac{q_{sr}^{(n)}}{\sum_{t=1}^{K}q_{tr}^{(n)}}=\frac{\kappa(s,r)\pi_{s}^{(n)}}{\sum_{t=1}^{K}\kappa(t,r)\pi_{t}^{(n)}}.$

Moreover, conditionally on $\hat{J}_{\mathbf{i}}$, the
$\\{\hat{J}_{(\mathbf{i},j)}:j\geq 1\\}$ are independent of each other.

Now that the unmarked tree $\mathcal{T}=\bigcup_{k=0}^{\infty}\mathcal{A}_{k}$
has been constructed, we assign to each node $\mathbf{i}\in\mathcal{T}$ a mark
$\left(\boldsymbol{\hat{Q}}_{\mathbf{i}},\\{\hat{B}_{(\mathbf{i},s)}\\}_{s=1}^{\hat{N}_{\mathbf{i}}}\right)$.
The internal belief vector $\boldsymbol{\hat{Q}}_{\mathbf{i}}$ depends only on
$\hat{J}_{\mathbf{i}}$ and is distributed according to
$F_{\hat{J}_{\mathbf{i}}}$. Finally, the unnormalized weights satisfy for
$x\in\mathbb{R}$,

$\mathbb{P}_{n}\left(\left.\hat{B}_{(\mathbf{i},j)}\leq
x\right|\hat{J}_{\mathbf{i}},\hat{J}_{(\mathbf{i},j)}\right)=G_{\hat{J}_{\mathbf{i}},\hat{J}_{(\mathbf{i},j)}}(x),$
(5.13)

independently of everything else.

######  Definition 5.1.

Two simple vertex-marked directed graphs, $G=(V,E;\mathscr{A})$ and
$G^{\prime}=(V^{\prime},E^{\prime};\mathscr{A}^{\prime})$, whose vertices have
marks $\mathbf{a}_{i}$, $i\in V$, and $\mathbf{a}_{i}^{\prime}$, $i\in
V^{\prime}$, respectively, are said to be isomorphic if there exists a
bijection $\vartheta:V\rightarrow V^{\prime}$ such that $(i,j)\in E$ if, and
only if, $(\vartheta(i),\vartheta(j))\in E^{\prime}$, for nodes $i,j\in V$,
and for all $i\in V$ the vertex mark
$\mathbf{a}_{i}=\mathbf{a}_{\vartheta(i)}^{\prime}$. We write $G\simeq
G^{\prime}$ to express that the graphs $G$ and $G^{\prime}$ are isomorphic.

For each $i\in V_{n}$, the intermediate coupling will construct a marked tree
$\mathcal{T}_{\emptyset(i)}(\hat{J})\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(\mathcal{T}(\hat{J})|\hat{J}_{\emptyset}=J_{i})$
using as marks in Definition 5.1 the types, which correspond to the community
labels in the dSBM (we do not need the internal opinions nor the unnormalized
weights for this purpose, since their distribution is determined by the
types). Note that the subscript $\emptyset(i)$ emphasizes that the root of the
tree corresponds to vertex $i$ in the graph. For any fixed $s\geq 0$, let
$\mathcal{G}_{i}^{(s)}(J)$ denote the induced subgraph of $G_{n}$ determined
by the vertices in $V_{n}$ that have directed paths of length at most $s$
connecting them to vertex $i$, including their community labels, and let
$\mathcal{T}_{\emptyset(i)}^{(s)}(\hat{J})$ denote the restriction of
$\mathcal{T}_{\emptyset(i)}(\hat{J})$ to its first $s$ generations. Then,
using the same type of intermediate coupling as in [38], one obtains the
following theorem.

######  Theorem 5.4.

For the dSBM under Assumption Assumption A, with $\theta_{n}\leq(\log n)^{b}$
for some $b>0$, and any fixed $k\geq 0$, there exists a sequence of marked
$K$-type Galton-Watson trees $\\{\mathcal{T}_{\emptyset(i)}(\hat{J}):i\in
V_{n}\\}$ such that
$\mathcal{T}_{\emptyset(i)}(\hat{J})\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(\mathcal{T}(\hat{J})|\hat{J}_{\emptyset}=J_{i})$
and

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}_{n}\left(\mathcal{G}_{i}^{(k)}(J)\not\simeq\mathcal{T}_{\emptyset(i)}^{(k)}(\hat{J})\right)\xrightarrow{P}0,\qquad
n\to\infty.$

Note that when the coupling holds for a vertex $i$ up to generation $s$, i.e.,
$\mathcal{G}_{i}^{(s)}(J)\simeq\mathcal{T}_{\emptyset(i)}^{(s)}(\hat{J})$, we
can copy the internal belief vectors and the unnormalized weights from the
graph, so
$\boldsymbol{\hat{Q}}_{\mathbf{i}}=\mathbf{Q}_{\vartheta(\mathbf{i})}$ and
$\hat{B}_{(\mathbf{i},j)}=B_{\vartheta(\mathbf{i}),\vartheta((\mathbf{i},j))}$,
where $\vartheta$ is the bijection defining the isomorphism. When the coupling
fails, we simply sample them independently according to
$F_{\hat{J}_{\mathbf{i}}}$ and (5.13), respectively. Once we have the
unnormalized weights, we define

$\hat{C}_{(\mathbf{i},j)}=\frac{\hat{B}_{(\mathbf{i},j)}}{\sum_{s=1}^{\hat{N}_{\mathbf{i}}}\hat{B}_{(\mathbf{i},s)}}\cdot
1\left(\sum_{s=1}^{\hat{N}_{\mathbf{i}}}\hat{B}_{(\mathbf{i},s)}>0\right).$

On the tree, the weights $\\{\hat{C}_{\mathbf{i}}:\mathbf{i}\in\mathcal{T}\\}$
are used to construct the weights

$\Pi_{(\mathbf{i},j)}=\Pi_{\mathbf{i}}\hat{C}_{(\mathbf{i},j)},\qquad\Pi_{\emptyset}=1.$

####  5.2.2. Proof of Theorem 3.1 for semi-sparse graphs

Our goal is to bound the norm

$\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|(C^{s}X)_{i\bullet}-(\tilde{M}^{s}\breve{X})_{i\bullet}\right\|_{1}\right]=\max_{i\in
V_{n}}\sum_{j=1}^{t}\mathbb{E}_{n}\left[\left|(C^{s}X)_{ij}-(\tilde{M}^{s}\breve{X})_{ij}\right|\right]$

for $X\in[-1,1]^{n\times\ell}$ a random matrix, conditionally independent of
$C$ given $\mathscr{F}_{n}$ and having mean $\breve{X}=\mathbb{E}_{n}[X]$.

To simplify the notation, note that if we set $\mathbf{X}=X_{\bullet j}$ and
$\mathbf{\bar{x}}=\breve{X}_{\bullet j}=\mathbb{E}_{n}[\mathbf{X}]$, then

$\mathbb{E}_{n}\left[\left|(C^{s}X)_{ij}-(\tilde{M}^{s}\breve{X})_{ij}\right|\right]=\mathbb{E}_{n}\left[\left|(C^{s}\mathbf{X})_{i}-(\tilde{M}^{s}\mathbf{\bar{x}})_{i}\right|\right],$

so it suffices to analyze expectations of this form. We start by defining for
each $i\in V_{n}$ and any $s\geq 1$, the event that the coupling with the
$K$-type Galton-Watson tree holds:

$\displaystyle
D_{s,i}=\left\\{\mathcal{G}_{i}^{(s)}(J)\simeq\mathcal{T}_{\emptyset(i)}^{(s)}(\hat{J})\right\\}.$

######  Lemma 5.2.

Let $\mathbf{X}=(X_{1},\dots,X_{n})^{\top}\in[-1,1]^{n}$ be a random vector
such that $X_{i}$ has distribution $H_{\mathbf{A}_{i}}$, independently of
everything else; let
$\mathbf{\bar{x}}=(\bar{x}_{1},\dots,\bar{x}_{n})^{\top}=\mathbb{E}_{n}[\mathbf{X}]$
denote its mean. Furthermore, suppose $\bar{x}_{i}=x_{r}$ for all $i$ such
that $J_{i}=r$, $1\leq r\leq K$. Then, for any $i\in V_{n}$ and $s\geq 1$,

$\mathbb{E}_{n}\left[\left|(C^{s}\mathbf{X})_{i}-(\tilde{M}^{s}\mathbf{\bar{x}})_{i}\right|\right]\leq\mathbb{E}_{n}\left[\left.\left|\sum_{|\mathbf{i}|=s}\Pi_{\mathbf{i}}\hat{X}_{\mathbf{i}}-(\breve{M}\mathbf{x})_{J_{i}}\right|\right|\hat{J}_{\emptyset}=J_{i}\right]+2\mathbb{P}_{n}\left(D_{s,i}^{c}\right),$

where $\breve{M}$ is defined in (5.8),
$\mathbf{x}=(x_{1},\dots,x_{K})^{\top}$, the $\Pi_{\mathbf{j}}$ are defined on
the marked tree $\mathcal{T}(\hat{J})$, and $\hat{X}_{\mathbf{i}}$ is
distributed according to $H_{\boldsymbol{\hat{A}}_{\mathbf{i}}}$,
independently of everything else.

###### Proof.

We start by considering one vertex $i\in V_{n}$ and construct its coupled tree
$\mathcal{T}_{\emptyset(i)}(\hat{J})\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(\mathcal{T}(\hat{J})|\hat{J}_{\emptyset}=J_{i})$.
Note that on the event $D_{s,i}$ there is a unique path connecting vertex $i$
to each of its neighbors at distance $s$, and these paths are the same as
those in the tree, so

$(C^{s}\mathbf{X})_{i}=\sum_{j_{1}=1}^{n}\cdots\sum_{j_{s}=1}^{n}C_{ij_{1}}C_{j_{1}j_{2}}\cdots
C_{j_{s-1}j_{s}}X_{j_{s}}=\sum_{|\mathbf{i}|=s}\Pi_{\mathbf{i}}\hat{X}_{\mathbf{i}},$
(5.14)

with $\hat{X}_{\mathbf{i}}=X_{\vartheta(\mathbf{i})}$, with $\vartheta$ the
bijection determining the event $D_{s,i}$. Since the distribution of
$X_{\vartheta(\mathbf{i})}$ depends only on
$\mathbf{A}_{\vartheta(\mathbf{i})}$ and
$\mathbf{A}_{\vartheta(\mathbf{i})}=\boldsymbol{\hat{A}}_{\mathbf{i}}$, then
$(\hat{X}_{\mathbf{i}}|\boldsymbol{\hat{A}}_{\mathbf{i}})$ is distributed
according to $H_{\boldsymbol{\hat{A}}_{\mathbf{i}}}$.

The induction proof given within the proof of Theorem 5.2 shows that

$(\tilde{M}^{s}\mathbf{\bar{x}})_{i}=(\breve{M}\mathbf{x})_{J_{i}}.$

Consequently,

$\displaystyle\mathbb{E}_{n}\left[\left|(C^{s}\mathbf{X})_{i}-(\tilde{M}^{s}\mathbf{\bar{x}})_{i}\right|\right]$
$\displaystyle=\mathbb{E}_{n}\left[\left|(C^{s}\mathbf{X})_{i}-(\tilde{M}^{s}\mathbf{\bar{x}})_{i}\right|\right]$
$\displaystyle\leq\mathbb{E}_{n}\left[1(D_{s,i})\left|(C^{s}\mathbf{X})_{i}-(\tilde{M}^{s}\mathbf{\bar{x}})_{i}\right|\right]+\mathbb{E}_{n}\left[1(D_{s,i}^{c})\left(|(C^{s}\mathbf{X})_{i}|+|(\tilde{M}^{s}\mathbf{\bar{x}})_{i}|\right)\right]$
$\displaystyle\leq\mathbb{E}_{n}\left[\left.\left|\sum_{|\mathbf{i}|=s}\Pi_{\mathbf{i}}\hat{X}_{\mathbf{i}}-(\breve{M}\mathbf{x})_{J_{i}}\right|\right|\hat{J}_{\emptyset}=J_{i}\right]+2\mathbb{P}_{n}\left(D_{s,i}^{c}\right),$

where the weights $\Pi_{\mathbf{i}}$ and the terminal values
$\hat{X}_{\mathbf{i}}$ are defined on the marked tree
$\mathcal{T}_{\emptyset(i)}(\hat{J})$, and we have used the observation that
$\|C^{s}\mathbf{X}\|_{\infty}\leq 1$ and
$\|\tilde{M}^{s}\mathbf{\bar{x}}\|_{\infty}\leq 1$. ∎

Next, define the vector $\mathbf{a}_{s}:=(a_{s}(1),\dots,a_{s}(K))^{\top}$
given by:

$a_{s}(r):=\mathbb{E}_{n}\left[\left.\left|\sum_{|\mathbf{i}|=s}\hat{\Pi}_{\mathbf{i}}\hat{X}_{\mathbf{i}}-(\breve{M}^{s}\mathbf{x})_{r}\right|\right|\hat{J}_{\emptyset}=r\right].$
(5.15)

Before proving the main theorem of this section, we give a bound for
$\|\mathbf{a}_{1}\|_{\infty}$.

######  Lemma 5.3.

For $\mathbf{a}_{1}$ defined according to (5.15), and provided
$\theta_{n}\to\infty$ as $n\to\infty$, there exists a constant
$\Gamma^{\prime}<\infty$ that does not depend on the choice of
$\\{\hat{X}_{i}\\}$ such that

$\|\mathbf{a}_{1}\|_{\infty}\leq\Gamma^{\prime}\theta_{n}^{-1/2}.$

###### Proof.

Note that if the $r$th row of $\breve{M}$ is zero, then $a_{1}(r)=0$, and
since the non-zero rows of $\breve{M}$ coincide with those of $M$, it suffices
to consider $r\in\mathcal{I}$. For $r\in\mathcal{I}$,

$a_{1}(r)=\mathbb{E}_{n}\left[\left.\left|\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}\hat{X}_{i}-(\breve{M}\mathbf{x})_{r}\right|\right|\hat{J}_{\emptyset}=r\right],$

and let

$S_{j}:=\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{B}_{i}\hat{X}_{i}1(\hat{J}_{i}=j)\qquad\text{and}\qquad\tilde{S}_{j}:=\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{B}_{i}\hat{X}_{i}1(\hat{J}_{i}=j),$

so that

$\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}\hat{X}_{i}=\sum_{i=1}^{\hat{N}_{\emptyset}}\frac{\hat{B}_{i}}{\sum_{s=1}^{\hat{N}_{\emptyset}}\hat{B}_{s}}\hat{X}_{i}=\frac{\tilde{S}_{1}+\dots+\tilde{S}_{K}}{S_{1}+\dots+S_{K}}.$

Define the event

$F=\left\\{\left|\frac{\tilde{S}_{1}+\dots+\tilde{S}_{K}}{S_{1}+\dots+S_{K}}-(\breve{M}\mathbf{x})_{\hat{J}_{\emptyset}}\right|\leq
2/(3H\Lambda_{n})\right\\},$

and condition on $\hat{J}_{\emptyset}$ to obtain that

$\displaystyle\mathbb{E}_{n}\left[\left.\left|\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}\hat{X}_{i}-(\breve{M}\mathbf{x})_{r}\right|\right|\hat{J}_{\emptyset}=r\right]$
$\displaystyle\leq\mathbb{E}_{n}\left[\left.1(F)\left|\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}\hat{X}_{i}-(\breve{M}\mathbf{x})_{r}\right|\right|\hat{J}_{\emptyset}=r\right]+\mathbb{E}_{n}\left[\left.1(F^{c})\left(\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}|\hat{X}_{i}|+|(\breve{M}\mathbf{x})_{r}|\right)\right|\hat{J}_{\emptyset}=r\right]$
$\displaystyle=\int_{0}^{2/(3H\Lambda_{n})}\mathbb{P}_{n}\left(\left.\left|\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}\hat{X}_{i}-(\breve{M}\mathbf{x})_{r}\right|>t\right|\hat{J}_{\emptyset}=r\right)dt+2\,\mathbb{P}_{n}\left(F^{c}\left|\hat{J}_{\emptyset}=r\right.\right),$

where we used the observation that
$\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}|\hat{X}_{i}|\leq 1$ and
$|(\breve{M}\mathbf{x})_{r}|\leq\|\breve{M}\mathbf{x}\|_{\infty}\leq\|\breve{M}\|_{\infty}\|\mathbf{x}\|_{\infty}\leq
1$, and therefore, the integrand is bounded by one.

Next, note that conditionally on $\hat{J}_{\emptyset}=r$, we have that
$\tilde{S}_{j}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\sum_{i=1}^{N_{j}}B_{i}^{(r,j)}X_{i}^{(j)}$,
where $N_{j}$ is a Poisson random variable with mean
$q_{jr}^{(n)}=\kappa(j,r)\pi_{j}^{(n)}\theta_{n}$, and is independent of the
i.i.d. sequences $\\{B_{i}^{(r,j)}:i\geq 1\\}$ and $\\{X_{i}^{(j)}:i\geq
1\\}$, with
$B_{i}^{(r,j)}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(\hat{B}_{i}|\hat{J}_{\emptyset}=r,\hat{J}_{i}=j)$
and
$X_{i}^{(j)}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}(\hat{X}_{i}|\hat{J}_{i}=j)$.
Similarly,
$S_{j}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}\sum_{i=1}^{N_{r}}B_{i}^{(r,j)}$,
and all the random variables $\\{S_{j},\tilde{S}_{j}:1\leq j\leq K\\}$ are
conditionally independent of each other given $\hat{J}_{\emptyset}$. It
follows from Lemma 5.1 that for $r\in\mathcal{I}$,

$\displaystyle\mathbb{P}_{n}\left(\left.\left|\sum_{i=1}^{\hat{N}_{\emptyset}}\hat{C}_{i}\hat{X}_{i}-(\breve{M}\mathbf{x})_{r}\right|>t\right|\hat{J}_{\emptyset}=r\right)$
$\displaystyle\leq
4\,\text{exp}\left(-\frac{(t/2)^{2}(\theta_{n}\mu_{r}^{(n)})^{2}}{2\theta_{n}\nu_{r}^{(n)}}+\frac{H(t/2)^{3}(\theta_{n}\mu_{r}^{(n)})^{3}}{2(\theta_{n}\nu_{r}^{(n)})^{2}}\right)$
$\displaystyle\leq
4\,\text{exp}\left(-\frac{(t/2)^{2}\theta_{n}}{2\Delta_{n}}\left(1-H\Lambda_{n}t/2\right)\right),$

as in the proof of Theorem 5.3, and

$\mathbb{P}_{n}\left(F^{c}\left|\hat{J}_{\emptyset}=r\right.\right)\leq
4\,\text{exp}\left(-\frac{(1/(3H\Lambda_{n}))^{2}\theta_{n}}{2\Delta_{n}}\left(1-H\Lambda_{n}/(3H\Lambda_{n})\right)\right)=4\,\text{exp}\left(-\frac{\theta_{n}}{27\Delta_{n}(H\Lambda_{n})^{2}}\right).$

Since the bounds do not depend on $\hat{J}_{\emptyset}$, we obtain that

$\displaystyle\|\mathbf{a}_{1}\|_{\infty}$ $\displaystyle\leq
4\int_{0}^{2/(3H\Lambda_{n})}\text{exp}\left(-\frac{(t/2)^{2}\theta_{n}}{2\Delta_{n}}\left(1-H\Lambda_{n}t/2\right)\right)dt+8\,\text{exp}\left(-\frac{\theta_{n}}{27\Delta_{n}(H\Lambda_{n})^{2}}\right)$
$\displaystyle\leq
4\int_{0}^{2/(3H\Lambda_{n})}\text{exp}\left(-\frac{(t/2)^{2}\theta_{n}}{3\Delta_{n}}\right)dt+8\,\text{exp}\left(-\frac{\theta_{n}}{27\Delta_{n}(H\Lambda_{n})^{2}}\right)$
$\displaystyle=\frac{4}{\sqrt{\theta_{n}/(6\Delta_{n})}}\int_{0}^{2\sqrt{\theta_{n}/(6\Delta_{n})}/(3H\Lambda_{n})}e^{-z^{2}/2}dz+8\,\text{exp}\left(-\frac{\theta_{n}}{27\Delta_{n}(H\Lambda_{n})^{2}}\right)$
$\displaystyle\leq\frac{8\sqrt{3\Delta_{n}\pi}}{\sqrt{\theta_{n}}}\int_{0}^{\infty}\frac{e^{-z^{2}/2}}{\sqrt{2\pi}}dz+8\,\text{exp}\left(-\frac{\theta_{n}}{27\Delta_{n}(H\Lambda_{n})^{2}}\right)$
$\displaystyle=\frac{4\sqrt{3\Delta_{n}\pi}}{\sqrt{\theta_{n}}}+8\,\text{exp}\left(-\frac{\theta_{n}}{27\Delta_{n}(H\Lambda_{n})^{2}}\right)=O\left(\theta_{n}^{-1/2}\right)$

as $n\to\infty$. Noting that the last estimates do not depend on the choice of
the $\\{\hat{X}_{i}\\}$ completes the proof. ∎

As a corollary to the previous lemma, we obtain the following bound for
$\|\mathbf{a}_{s}\|_{\infty}$.

######  Corollary 5.1.

For $s\geq 1$ and $\mathbf{a}_{s}$ defined according to (5.15), and provided
$\theta_{n}\to\infty$ as $n\to\infty$, there exists a constant
$\Gamma^{\prime}<\infty$ that does not depend on the choice of
$\\{\hat{X}_{i}\\}$ such that

$\|\mathbf{a}_{s}\|_{\infty}\leq\Gamma^{\prime}s\theta_{n}^{-1/2}.$

###### Proof.

To derive a recursion for $\mathbf{a}_{s}$, $s\geq 1$, note that for each
$j\in\\{1,\dots,K\\}$,

$\displaystyle a_{s}(j)$
$\displaystyle=\mathbb{E}_{n}\left[\left.\left|\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}\sum_{|(r,\mathbf{i})|=s}\frac{\hat{\Pi}_{(r,\mathbf{i})}}{\hat{C}_{r}}\hat{X}_{(r,\mathbf{i})}-\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}(\breve{M}^{s-1}\mathbf{x})_{\hat{J}_{r}}+\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}(\breve{M}^{s-1}\mathbf{x})_{\hat{J}_{r}}-(\breve{M}^{s}\mathbf{x})_{j}\right|\right|\hat{J}_{\emptyset}=j\right]$
$\displaystyle\leq\mathbb{E}_{n}\left[\left.\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}\left|\sum_{|(r,\mathbf{i})|=s}\frac{\hat{\Pi}_{(r,\mathbf{i})}}{\hat{C}_{r}}\hat{X}_{(r,\mathbf{i})}-(\breve{M}^{s-1}\mathbf{x})_{\hat{J}_{r}}\right|\right|\hat{J}_{\emptyset}=j\right]$
$\displaystyle\hskip
14.22636pt+\mathbb{E}_{n}\left[\left.\left|\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}(\breve{M}^{s-1}\mathbf{x})_{\hat{J}_{r}}-(\breve{M}^{s}\mathbf{x})_{j}\right|\right|\hat{J}_{\emptyset}=j\right]$
$\displaystyle=\mathbb{E}_{n}\left[\left.\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}\mathbb{E}_{n}\left[\left.\left|\sum_{|(r,\mathbf{i})|=s}\frac{\hat{\Pi}_{(r,\mathbf{i})}}{\hat{C}_{r}}\hat{X}_{(r,\mathbf{i})}-(\breve{M}^{s-1}\mathbf{x})_{\hat{J}_{r}}\right|\right|\hat{N}_{\emptyset},\\{\hat{C}_{r},\hat{J}_{r}\\}_{r=1}^{\hat{N}_{\emptyset}}\right]\right|\hat{J}_{\emptyset}=j\right]$
$\displaystyle\hskip
14.22636pt+\mathbb{E}_{n}\left[\left.\left|\sum_{l=1}^{K}\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}1(\hat{J}_{r}=l)(\breve{M}^{s-1}\mathbf{x})_{l}-\sum_{l=1}^{K}\breve{M}_{jl}(\breve{M}^{s-1}\mathbf{x})_{l}\right|\right|\hat{J}_{\emptyset}=j\right]$
$\displaystyle=\mathbb{E}_{n}\left[\left.\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}a_{s-1}(\hat{J}_{r})\right|\hat{J}_{\emptyset}=j\right]+\mathbb{E}_{n}\left[\left.\left|\sum_{l=1}^{K}(\breve{M}^{s-1}\mathbf{x})_{l}\left(\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}1(\hat{J}_{r}=l)-\breve{M}_{jl}\right)\right|\right|\hat{J}_{\emptyset}=j\right]$
$\displaystyle\leq\max_{1\leq j\leq
K}a_{s-1}(j)\mathbb{E}_{n}\left[\left.\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}\right|\hat{J}_{\emptyset}=j\right]+\mathbb{E}_{n}\left[\left.\left|\sum_{l=1}^{K}(\breve{M}^{s-1}\mathbf{x})_{l}\left(\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}1(\hat{J}_{r}=l)-\breve{M}_{jl}\right)\right|\right|\hat{J}_{\emptyset}=j\right].$

To simplify the bound, recall that
$\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}=1$. To bound the second
expectation, let $\hat{Y}_{r}=y_{l}=(\breve{M}^{s-1}\mathbf{x})_{l}$ for all
$r$ such that $\hat{J}_{r}=l$, define $\mathbf{y}=(y_{1},\dots,y_{K})^{\top}$,
and note that

$\mathbb{E}_{n}\left[\left.\left|\sum_{l=1}^{K}(\breve{M}^{s-1}\mathbf{x})_{l}\left(\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}1(\hat{J}_{r}=l)-\breve{M}_{jl}\right)\right|\right|\hat{J}_{\emptyset}=j\right]=\mathbb{E}_{n}\left[\left.\left|\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}\hat{Y}_{r}-(\breve{M}\mathbf{y})_{j}\right|\right|\hat{J}_{\emptyset}=j\right],$

so by Lemma 5.3 we get

$\max_{1\leq j\leq
K}\mathbb{E}_{n}\left[\left.\left|\sum_{r=1}^{\hat{N}_{\emptyset}}\hat{C}_{r}\hat{Y}_{r}-(\breve{M}\mathbf{y})_{j}\right|\right|\hat{J}_{\emptyset}=j\right]\leq\Gamma^{\prime}s\theta_{n}^{-1/2}$

for some constant $\Gamma^{\prime}$ that does not depend on the
$\\{\hat{Y}_{i}\\}$. Therefore,

$\|\mathbf{a}_{s}\|_{\infty}\leq\|\mathbf{a}_{s-1}\|_{\infty}+\Gamma^{\prime}\theta_{n}^{-1/2}.$

Iterating the recursion gives

$\|\mathbf{a}_{s}\|_{\infty}\leq\Gamma^{\prime}s\theta_{n}^{-1/2}.$

∎

We now state the counterpart of Theorem 5.3 for this regime.

######  Theorem 5.5.

Let $\mathbf{X}=(X_{1},\dots,X_{n})^{\top}\in[-1,1]^{n}$ be a random vector
such that $X_{i}$ has distribution $H_{\mathbf{A}_{i}}$, independently of
everything else; let
$\mathbf{\bar{x}}=(\bar{x}_{1},\dots,\bar{x}_{n})^{\top}=\mathbb{E}_{n}[\mathbf{X}]$
denote its mean. Furthermore, suppose $\bar{x}_{i}=x_{r}$ for all $i$ such
that $J_{i}=r$, $1\leq r\leq K$. Then, there exists a constant
$\Gamma^{\prime}$ that does not depend on the choice of $\mathbf{X}$ such that
for any $i\in V_{n}$ and $s\geq 1$,

$\mathbb{E}_{n}\left[\left|(C^{s}\mathbf{X})_{i}-(\tilde{M}^{s}\mathbf{\bar{x}})_{i}\right|\right]\leq\frac{\Gamma^{\prime}s}{\theta_{n}^{1/2}}+2\mathbb{P}_{n}\left(D_{s,i}^{c}\right).$

###### Proof.

By Lemma 5.2 and Corollary 5.1, we have that

$\displaystyle\mathbb{E}_{n}\left[\left|(C^{s}\mathbf{X})_{i}-(\tilde{M}^{s}\mathbf{\bar{x}})_{i}\right|\right]$
$\displaystyle\leq\mathbb{E}_{n}\left[\left.\left|\sum_{|\mathbf{i}|=s}\Pi_{\mathbf{i}}\hat{X}_{\mathbf{i}}-(\breve{M}\mathbf{x})_{J_{i}}\right|\right|\hat{J}_{\emptyset}=J_{i}\right]+2\mathbb{P}_{n}\left(D_{s,i}^{c}\right)$
$\displaystyle\leq
a_{s}(J_{i})+2\mathbb{P}_{n}\left(D_{s,i}^{c}\right)\leq\|\mathbf{a}_{s}\|_{\infty}+2\mathbb{P}_{n}\left(D_{s,i}^{c}\right)$
$\displaystyle\leq\Gamma^{\prime}s\theta_{n}^{-1/2}+2\mathbb{P}_{n}\left(D_{s,i}^{c}\right).$

∎

We can now give the proof to the second part of Theorem 3.1.

###### Proof of Theorem 3.1.

Suppose $\theta_{n}\to\infty$ as $n\to\infty$, and recall that we need to
prove that

$\sup_{k\geq 0}\,\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]\xrightarrow{P}0$

as $n\to\infty$. Note that by Remark 3.1(a), it suffices to assume that
$\theta_{n}\leq(\log n)^{b}$ for some $b>1$. To start, note that by Theorem
5.1, we have that for any fixed $k\geq 0$,

$\displaystyle\max_{i\in
V_{n}}\,\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]$
$\displaystyle\leq\max_{i\in
V_{n}}\,\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\mathbf{\tilde{R}}_{i}^{(k)}\right\|_{1}\right]+\max_{i\in
V_{n}}\,\mathbb{E}_{n}\left[\left\|\mathbf{\tilde{R}}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]$
$\displaystyle\leq 1(k\geq 2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\max_{i\in
V_{n}}\,\mathbb{E}_{n}\left[\left\|(C^{s}W^{(0)})_{i\bullet}-(\tilde{M}^{s}\breve{W})_{i\bullet}\right\|_{1}\right]$
$\displaystyle\hskip 14.22636pt+\sum_{s=1}^{k}a_{s,k}\max_{i\in
V_{n}}\,\mathbb{E}_{n}\left[\left\|(C^{s}R^{(0)})_{i\bullet}-(\tilde{M}^{s}\breve{R})_{i\bullet}\right\|_{1}\right]+\mathbb{E}_{n}\left[\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right].$

Moreover, by Theorem 5.2,

$\mathbb{E}_{n}\left[\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right]\leq\mathbb{E}_{n}\left[\sup_{k\geq
0}\left\|\tilde{R}^{(k)}-\mathcal{R}^{(k)}\right\|_{\infty}\right]\leq\frac{\ell
c}{d^{2}}\cdot\mathcal{E}_{n}.$

Now use Theorem 5.5 to obtain that

$\mathbb{E}_{n}\left[\left\|(C^{s}W^{(0)})_{i\bullet}-(\tilde{M}^{s}\breve{W})_{i\bullet}\right\|_{1}\right]=\sum_{j=1}^{\ell}\mathbb{E}_{n}\left[\left\|(C^{s}W^{(0)}_{\bullet
j})_{i}-(\tilde{M}^{s}\breve{W}_{\bullet
j})_{i}\right\|_{1}\right]\leq\ell\left(\Gamma^{\prime}s\theta_{n}^{-1/2}+2\mathbb{P}_{n}(D_{s,i}^{c})\right)$

and

$\mathbb{E}_{n}\left[\left\|(C^{s}R^{(0)})_{i\bullet}-(\tilde{M}^{s}\breve{R})_{i\bullet}\right\|_{1}\right]\leq\ell\left(\Gamma^{\prime}s\theta_{n}^{-1/2}+2\mathbb{P}_{n}(D_{s,i}^{c})\right).$

It follows that

$\displaystyle\max_{i\in
V_{n}}\,\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]$
$\displaystyle\leq 1(k\geq 2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}\max_{i\in
V_{n}}\,\ell\left(\Gamma^{\prime}s\theta_{n}^{-1/2}+2\mathbb{P}_{n}(D_{s,i}^{c})\right)$
$\displaystyle\hskip 14.22636pt+\sum_{s=1}^{k}a_{s,k}\max_{i\in
V_{n}}\,\ell\left(\Gamma^{\prime}s\theta_{n}^{-1/2}+2\mathbb{P}_{n}(D_{s,i}^{c})\right)+\frac{\ell
c}{d^{2}}\cdot\mathcal{E}_{n}$
$\displaystyle=\ell\Gamma^{\prime}\theta_{n}^{-1/2}\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}s+2\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{s,i}^{c})+\frac{\ell c}{d^{2}}\cdot\mathcal{E}_{n}$
$\displaystyle=\ell\Gamma^{\prime}\theta_{n}^{-1/2}c\sum_{t=1}^{k}(1-d)^{t-1}t+2\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{s,i}^{c})+\frac{\ell c}{d^{2}}\cdot\mathcal{E}_{n},$

where in the last equality we used (5.4). Since
$\sum_{t=1}^{k}(1-d)^{t-1}t\leq d^{-2}$ for all $k\geq 0$, and

$\displaystyle\sum_{t=1}^{k}\sum_{s=1}^{t}a_{s,t}\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{s,i}^{c})$ $\displaystyle=\sum_{s=1}^{k}\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{s,i}^{c})c^{s}\sum_{t=s}^{k}\binom{t}{s}(1-c-d)^{t-s}$
$\displaystyle=\sum_{s=1}^{k}\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{s,i}^{c})c^{s}(c+d)^{-s-1}\sum_{m=0}^{k-s}\binom{m+s}{m}(1-c-d)^{m}(c+d)^{s+1}$
$\displaystyle\leq\sum_{s=1}^{\infty}\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{s,i}^{c})\frac{c^{s}}{(c+d)^{s+1}}=\frac{c}{(c+d)d}\mathbb{E}_{n}\left[\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{T,i}^{c})\right],$

where $T$ is a geometric random variable on $\\{1,2,\dots\\}$ with success
probability $p=d/(c+d)$, we have shown that

$\sup_{k\geq 0}\max_{i\in
V_{n}}\,\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}^{(k)}\right\|_{1}\right]\leq\frac{\ell
c}{d^{2}}\left(\Gamma^{\prime}\theta_{n}^{-1/2}+\mathcal{E}_{n}\right)+\frac{2c}{(c+d)d}\mathbb{E}_{n}\left[\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{T,i}^{c})\right].$

It only remains to show that $\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{T,i}^{c})\xrightarrow{P}0$ as $n\to\infty$ for any
fixed $T$, since then the bounded convergence theorem would complete the
proof. To see this is the case, note that all vertices $\\{i\in
V_{n}:J_{i}=r\\}$, $1\leq r\leq K$, are exchangeable, so for any $i\in V_{n}$,

$\displaystyle\mathbb{P}_{n}(D_{T,i}^{c})$
$\displaystyle=\sum_{r=1}^{K}\mathbb{P}_{n}(D_{T,i}^{c})1(J_{i}=r)=\sum_{r=1}^{K}\frac{1}{\pi_{r}^{(n)}n}\sum_{m=1}^{n}\mathbb{P}_{n}(D_{T,m}^{c})1(J_{m}=r)=\frac{1}{n}\sum_{m=1}^{n}\mathbb{P}_{n}(D_{T,m}^{c})\sum_{r=1}^{K}\frac{1(J_{m}=r)}{\pi_{r}^{(n)}},$

and therefore, by Theorem 5.4 and Assumption Assumption A,

$\max_{i\in
V_{n}}\mathbb{P}_{n}(D_{T,i}^{c})\leq\frac{1}{n}\sum_{m=1}^{n}\mathbb{P}_{n}(D_{T,m}^{c})\cdot\sum_{r=1}^{K}\frac{1}{\pi_{r}^{(n)}}\xrightarrow{P}0$

as $n\to\infty$. This completes the proof. ∎

The last section of the paper contains the proofs of Theorems 3.2 and 3.3,
which are a consequence of Theorem 3.1.

###  5.3. Proofs of Theorems 3.2 and 3.3

We start by proving Theorem 3.2, which focuses on the trajectories of the
process $\\{R^{(k)}:k\geq 0\\}$.

###### Proof of Theorem 3.2.

Fix $k\geq 0$ and recall that $V_{k,i}\in[-1,1]^{\ell\times(k+1)}$ is the
matrix having $j$th column $(V_{k,i})_{\bullet j}=\mathbf{R}_{i}^{(j-1)}$, and
$\mathcal{V}_{k}\in[-1,1]^{\ell\times(k+1)}$ is the matrix having $j$th column
$(\mathcal{V}_{k})_{\bullet j}=\boldsymbol{\mathcal{R}}_{\emptyset}^{(j-1)}$.
Assume $f:[-1,1]^{\ell\times(k+1)}\to\mathbb{R}$ is bounded and continuous
with respect to $\|\cdot\|_{1}$ (the induced operator norm) . Since $f$ is
continuous on a compact set, it is also uniformly continuous, so for every
$\epsilon>0$ there exists a $\delta>0$ such that

$\left|f(X)-f(Y)\right|<\varepsilon\qquad\text{ whenever
}\qquad\|X-Y\|_{1}<\delta.$

Let $\mathcal{V}_{k,i}\in[-1,1]^{\ell\times(k+1)}$ denote the matrix having
$j$th column $(\mathcal{V}_{k,i})_{\bullet
j}=\boldsymbol{\mathcal{R}}_{i}^{(j-1)}$, and let

$f^{*}=\max_{X\in[-1,1]^{\ell\times(k+1)}}|f(X)|.$

It follows that for any $1\leq r\leq K$,

$\displaystyle\dfrac{1}{n}\sum_{i=1}^{n}\left|f\left(V_{k,i}\right)-f\left(\mathcal{V}_{k,i}\right)\right|1(J_{i}=r)$
$\displaystyle\hskip
14.22636pt\leq\varepsilon\cdot\dfrac{1}{n}\sum_{i=1}^{n}1\left(\|V_{k,i}-\mathcal{V}_{k,i}\|_{1}<\delta\right)+2f^{*}\cdot\dfrac{1}{n}\sum_{i=1}^{n}1\left(\|V_{k,i}-\mathcal{V}_{k,i}\|_{1}\geq\delta\right)$
$\displaystyle\hskip
14.22636pt\leq\varepsilon+\dfrac{2f^{*}}{\delta}\cdot\dfrac{1}{n}\sum_{i=1}^{n}\|V_{k,i}-\mathcal{V}_{k,i}\|_{1}$
$\displaystyle\hskip
14.22636pt=\varepsilon+\dfrac{2f^{*}}{\delta}\cdot\frac{1}{n}\sum_{i=1}^{n}\max_{0\leq
m\leq
k}\left\|\mathbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}$
$\displaystyle\hskip
14.22636pt\leq\varepsilon+\dfrac{2f^{*}}{\delta}\cdot\dfrac{1}{n}\sum_{m=0}^{k}\sum_{i=1}^{n}\left\|\textbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}$

Take expectations on both sides to obtain

$\displaystyle\mathbb{E}_{n}\left[\dfrac{1}{n}\sum_{i=1}^{n}\left|f\left(V_{k,i}\right)-f\left(\mathcal{V}_{k,i}\right)\right|1(J_{i}=r)\right]$
$\displaystyle\leq\varepsilon+\dfrac{2f^{*}}{\delta}\cdot\dfrac{1}{n}\sum_{m=0}^{k}\sum_{i=1}^{n}\mathbb{E}_{n}\left[\left\|\textbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right]$
$\displaystyle\leq\varepsilon+\dfrac{2f^{*}}{\delta}\cdot\sum_{m=0}^{k}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\textbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right]$
$\displaystyle\leq\varepsilon+\frac{2(k+1)f^{*}}{\delta}\cdot\sup_{m\geq
0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\textbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right].$

From Theorem 3.1, we have that $\sup_{m\geq 0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\textbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right]\xrightarrow{P}0$
as $n\to\infty$. The bounded convergence theorem then gives

$\lim_{n\to\infty}E\left[\dfrac{1}{n}\sum_{i=1}^{n}\left|f\left(V_{k,i}\right)-f\left(\mathcal{V}_{k,i}\right)\right|1(J_{i}=r)\right]\leq\varepsilon+\frac{2(k+1)f^{*}}{\delta}\cdot\lim_{n\to\infty}E\left[\sup_{m\geq
0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\textbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right]\right]=\varepsilon,$

which in turn implies that

$\dfrac{1}{n}\sum_{i=1}^{n}\left|f\left(V_{k,i}\right)-f\left(\mathcal{V}_{k,i}\right)\right|1(J_{i}=r)\xrightarrow{P}0,\qquad
n\to\infty.$

Moreover, Kolmogorov’s strong law of large numbers gives

$\left|\frac{1}{n}\sum_{i=1}^{n}\left(f(\mathcal{V}_{k,i})1(J_{i}=r)-E\left[f\left(\mathcal{V}_{k,i}\right)1(J_{i}=r)\right]\right)\right|\to
0\qquad a.s.$

as $n\to\infty$. Since

$E[f(\mathcal{V}_{k,i})1(J_{i}=r)]=E[f(\mathcal{V}_{k,i})|J_{i}=r]E[\pi_{r}^{(n)}]=E[f(\mathcal{V}_{k})|\mathcal{J}_{\emptyset}=r]E[\pi_{r}^{(n)}]=E[f(\mathcal{V}_{k})1(\mathcal{J}_{\emptyset}=r)]E[\pi_{r}^{(n)}]/\pi_{r},$

we have shown that

$\displaystyle\left|\frac{1}{n}\sum_{i=1}^{n}f(V_{k,i})1(J_{i}=r)-E\left[f\left(\mathcal{V}_{k}\right)1(\mathcal{J}_{\emptyset}=r)\right]\right|$
$\displaystyle\hskip
14.22636pt\leq\dfrac{1}{n}\sum_{i=1}^{n}\left|f\left(V_{k,i}\right)-f\left(\mathcal{V}_{k,i}\right)\right|1(J_{i}=r)+\left|\frac{1}{n}\sum_{i=1}^{n}f(\mathcal{V}_{k,i})1(J_{i}=r)-E\left[f\left(\mathcal{V}_{k}\right)1(\mathcal{J}_{\emptyset}=r)\right]\right|$
$\displaystyle\hskip
14.22636pt\leq\dfrac{1}{n}\sum_{i=1}^{n}\left|f\left(V_{k,i}\right)-f\left(\mathcal{V}_{k,i}\right)\right|1(J_{i}=r)+\left|\frac{1}{n}\sum_{i=1}^{n}\left(f(\mathcal{V}_{k,i})1(J_{i}=r)-E\left[f\left(\mathcal{V}_{k,i}\right)1(J_{i}=r)\right]\right)\right|$
$\displaystyle\hskip
28.45274pt+\left|E[f(\mathcal{V}_{k})1(\mathcal{J}_{\emptyset}=r)]\right|\left|\frac{E[\pi_{r}^{(n)}]}{\pi_{r}}-1\right|\xrightarrow{P}\varepsilon$

as $n\to\infty$. Since $\varepsilon>0$ was arbitrary, the first statement of
the theorem follows.

For the second statement, let $\\{f_{1},\dots,f_{m}\\}$ be bounded and
continuous (with respect to $\|\cdot\|_{1}$) functions on
$[-1,1]^{\ell\times(k+1)}$. Recall that we may assume that the functions are
uniformly continuous. Now note that

$E\left[\left.f_{j}\left(\mathcal{V}_{k}\right)\right|\mathcal{J}_{\emptyset}=J_{i_{j}}\right]=\mathbb{E}_{n}\left[f_{j}\left(\mathcal{V}_{k,i_{j}}\right)\right],$

and since the $\\{\mathcal{V}_{k,i}:i\in V_{n}\\}$ are conditionally
independent given the community labels $\mathscr{J}_{n}$, then

$\displaystyle\left|\mathbb{E}_{n}\left[\prod_{j=1}^{m}f_{j}\left(V_{k,i_{j}}\right)\right]-\prod_{j=1}^{m}E\left[\left.f_{j}\left(\mathcal{V}_{k}\right)\right|\mathcal{J}_{\emptyset}=J_{i_{j}}\right]\right|$
$\displaystyle=\left|\mathbb{E}_{n}\left[\prod_{j=1}^{m}f_{j}\left(V_{k,i_{j}}\right)\right]-\mathbb{E}_{n}\left[\prod_{j=1}^{m}f_{j}\left(\mathcal{V}_{k,i_{j}}\right)\right]\right|$
$\displaystyle\leq\mathbb{E}_{n}\left[\left|\prod_{j=1}^{m}f_{j}\left(V_{k,i_{j}}\right)-\prod_{j=1}^{m}f_{j}\left(\mathcal{V}_{k,i_{j}}\right)\right|\right]$
$\displaystyle\leq\prod_{j=1}^{m}f_{j}^{*}\sum_{j=1}^{m}\mathbb{E}_{n}\left[\left|f_{j}\left(V_{k,i_{j}}\right)-f_{j}\left(\mathcal{V}_{k,i_{j}}\right)\right|\right],$

where $f_{j}^{*}=\max_{X\in[-1,1]^{\ell\times(k+1)}}|f_{j}(X)|$, and we have
used the inequality

$\left|\prod_{i=1}^{m}x_{i}-\prod_{i=1}^{m}y_{i}\right|\leq\prod_{i=1}^{m}(|x_{i}|\vee|y_{i}|)\sum_{i=1}^{m}|x_{i}-y_{i}|.$

To complete the proof, note that the random variables
$\\{\left|f_{j}\left(V_{k,t}\right)-f_{j}\left(\mathcal{V}_{k,t}\right)\right|:J_{t}=r\\}$
are exchangeable, so if $J_{i_{j}}=r_{j}$, then

$\displaystyle\mathbb{E}_{n}\left[\left|f_{j}\left(V_{k,i_{j}}\right)-f_{j}\left(\mathcal{V}_{k,i_{j}}\right)\right|\right]$
$\displaystyle=\frac{1}{n\pi_{r_{j}}^{(n)}}\sum_{t:J_{t}=r_{j}}\mathbb{E}_{n}\left[\left|f_{j}\left(V_{k,t}\right)-f_{j}\left(\mathcal{V}_{k,t}\right)\right|\right]$
$\displaystyle=\frac{1}{\pi_{r_{j}}^{(n)}}\mathbb{E}_{n}\left[\frac{1}{n}\sum_{t=1}^{n}\left|f_{j}\left(V_{k,t}\right)-f_{j}\left(\mathcal{V}_{k,t}\right)\right|1(J_{t}=r_{j})\right].$

Now apply the same arguments used in the first part of the theorem to obtain
that for any $\varepsilon>0$ there exists a $\delta>0$ such that

$\mathbb{E}_{n}\left[\left|f_{j}\left(V_{k,i_{j}}\right)-f_{j}\left(\mathcal{V}_{k,i_{j}}\right)\right|\right]\leq\frac{1}{\pi_{r_{j}}^{(n)}}\left(\varepsilon+\frac{2(k+1)f_{j}^{*}}{\delta}\sup_{m\geq
0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right]\right).$

We conclude that

$\displaystyle\left|\mathbb{E}_{n}\left[\prod_{j=1}^{m}f_{j}\left(V_{k,i_{j}}\right)\right]-\prod_{j=1}^{m}E\left[\left.f_{j}\left(\mathcal{V}_{k}\right)\right|\mathcal{J}_{\emptyset}=J_{i_{j}}\right]\right|$
$\displaystyle\hskip
14.22636pt\leq\prod_{j=1}^{m}f_{j}^{*}\sum_{j=1}^{m}\frac{1}{\pi_{r_{j}}^{(n)}}\left(\varepsilon+\frac{2(k+1)f_{j}^{*}}{\delta}\sup_{m\geq
0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right]\right)\xrightarrow{P}\prod_{j=1}^{m}f_{j}^{*}\sum_{j=1}^{m}\frac{\varepsilon}{\pi_{r_{j}}}$

as $n\to\infty$. Taking $\varepsilon\downarrow 0$ completes the proof. ∎

We now prove Theorem 3.3, which refers to the stationary behavior of the
process $\\{R^{(k)}:k\geq 0\\}$.

###### Proof of Theorem 3.3.

We will start by constructing a coupling of two matrices,
$R\in[-1,1]^{n\times\ell}$ and $\mathcal{R}\in[-1,1]^{n\times\ell}$, the first
one with rows $R_{j\bullet}=\mathbf{R}_{j}$ and the second one with rows
$\mathcal{R}_{j\bullet}=\boldsymbol{\mathcal{R}}_{j}$, as well as of the
random variable $\mathcal{J}_{\emptyset}$, such that $R$ has the stationary
distribution of $\\{R^{(k)}:k\geq 0\\}$,

$\boldsymbol{\mathcal{R}}_{i}=\sum_{t=0}^{\infty}(1-c-d)^{t}\textbf{W}^{(t)}_{i}+\sum_{t=1}^{\infty}\sum_{s=1}^{t}a_{s,t}(M^{s}\bar{W})_{J_{i}},\qquad
i\in V_{n},$

and

$\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}-\boldsymbol{\mathcal{R}}_{i}\right\|_{1}\right]\to
0,\qquad n\to\infty.$

Note that exactly the same arguments used in the proof of Theorem 3.2 (set
$k=0$) will then yield

$\frac{1}{n}\sum_{i=1}^{n}f(\textbf{R}_{i})1(J_{i}=r)\xrightarrow{P}E[f(\boldsymbol{\mathcal{R}}_{\emptyset})1(\mathcal{J}_{\emptyset}=r)]\qquad\text{and}\qquad\mathbb{E}_{n}\left[\prod_{j=1}^{m}f_{j}(\mathbf{R}_{i_{j}})\right]\xrightarrow{P}\prod_{j=1}^{m}E[f_{j}(\boldsymbol{\mathcal{R}}_{\emptyset})|\mathcal{J}_{\emptyset}=J_{i_{j}}],$

as $n\to\infty$. Hence, we only need to exhibit the coupling.

Define $\\{B^{(k)}:k\geq 0\\}\subset[-1,1]^{n\times\ell}$ to be the process
defined according to

$B^{(k)}=\sum_{t=0}^{k-1}A^{t}W^{(t)},$

and let $B=\sum_{t=0}^{\infty}A^{t}W^{(t)}$. To see that $B$ is well-defined,
recall that $\|A\|_{\infty}=1-d<1$, and therefore,

$\left\|B-B^{(k)}\right\|_{\infty}=\left\|\sum_{t=k}^{\infty}A^{t}W^{(t)}\right\|_{\infty}\leq\sum_{t=k}^{\infty}\|A\|_{\infty}^{t}\|W^{(t)}\|_{\infty}\leq\ell\sum_{t=k}^{\infty}(1-d)^{t}=\ell(1-d)^{k}/d\to
0,$

as $k\to\infty$, which yields $B=\lim_{k\to\infty}B^{(k)}$.

Going back to the original opinion recursion (5.1), note that it satisfies

$R^{(k)}=\sum_{r=0}^{k-1}A^{t}W^{(k-t)}+A^{k}R^{(0)}\stackrel{{\scriptstyle\mathcal{D}}}{{=}}B^{(k)}+A^{k}R^{(0)},$

from where we obtain

$R^{(k)}\Rightarrow B,\qquad k\to\infty.$

It follows that $B\stackrel{{\scriptstyle\mathcal{D}}}{{=}}R$. The coupling we
need is given by $(B,\mathcal{R})$. It remains to show that

$\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{B}_{i}-\boldsymbol{\mathcal{R}}_{i}\right\|_{1}\right]\to
0,\qquad n\to\infty,$

where $\mathbf{B}_{i}$ is the $i$th row of $B$.

To this end, define the matrix $\mathcal{B}^{(k)}\in[-1,1]^{n\times\ell}$
having rows
$(\mathcal{B}^{(k)})_{i\bullet}=\boldsymbol{\mathcal{B}}_{i}^{(k)}$ given by

$\boldsymbol{\mathcal{B}}^{(k)}_{i}=\sum_{t=0}^{k-1}(1-c-d)^{t}\textbf{W}^{(t)}_{i}+1(k\geq
2)\sum_{t=1}^{k-1}\sum_{s=1}^{t}a_{s,t}(M^{s}\bar{W})_{J_{i}}.$

Next, note that for any $k\geq 1$ and any $i\in V_{n}$,

$\displaystyle\left\|\mathbf{B}_{i}-\boldsymbol{\mathcal{R}}_{i}\right\|_{1}$
$\displaystyle\leq\left\|\mathbf{B}_{i}-\mathbf{B}_{i}^{(k)}\right\|_{1}+\left\|\mathbf{B}_{i}^{(k)}-\boldsymbol{\mathcal{B}}_{i}^{(k)}\right\|_{1}+\left\|\boldsymbol{\mathcal{B}}_{i}^{(k)}-\boldsymbol{\mathcal{R}}_{i}\right\|_{1}$
$\displaystyle\leq\|B-B^{(k)}\|_{\infty}+\left\|\mathbf{B}_{i}^{(k)}-\boldsymbol{\mathcal{B}}_{i}^{(k)}\right\|_{1}+\|\mathcal{B}^{(k)}-\mathcal{R}\|_{\infty}.$

We have already computed
$\left\|B-B^{(k)}\right\|_{\infty}\leq\ell(1-d)^{k}/d$, and the last norm can
be computed as follows:

$\displaystyle\left\|\mathcal{B}^{(k)}-\mathcal{R}\right\|_{\infty}$
$\displaystyle\leq\sum_{t=k}^{\infty}(1-c-d)^{t}\|W^{(t)}\|_{\infty}+\sum_{t=k}^{\infty}\sum_{s=1}^{t}a_{s,t}\left\|M^{s}\bar{W}\right\|_{\infty}$
$\displaystyle\leq\ell\sum_{t=k}^{\infty}(1-c-d)^{t}+\ell\sum_{t=k}^{\infty}\sum_{s=1}^{t}a_{s,t}=\ell\sum_{t=k}^{\infty}(1-c-d)^{t}+\ell\sum_{t=k}^{\infty}\sum_{s=1}^{t}\binom{t}{s}(1-c-d)^{t-s}c^{s}$
$\displaystyle=\ell\sum_{t=k}^{\infty}(1-c-d)^{t}+\ell\sum_{t=k}^{\infty}((1-d)^{t}-(1-c-d)^{t})=\ell\sum_{t=k}^{\infty}(1-d)^{t}=\ell(1-d)^{k}/d,$

where in the second inequality we used the observation that
$\|W^{(t)}\|_{\infty}\leq\ell$ and $\|M^{s}\bar{W}\|_{\infty}\leq\ell$.

We have thus shown that for any $i\in V_{n}$ and any $k\geq 0$,

$\left\|\mathbf{B}_{i}-\boldsymbol{\mathcal{R}}_{i}\right\|_{1}\leq\left\|\mathbf{B}_{i}^{(k)}-\boldsymbol{\mathcal{B}}_{i}^{(k)}\right\|_{1}+2\ell(1-d)^{k}/d.$

Taking expectations on both sides, followed by the maximum over $i$, we get

$\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{B}_{i}-\boldsymbol{\mathcal{R}}_{i}\right\|_{1}\right]\leq
2\ell(1-d)^{k}/d+\sup_{m\geq 0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{B}_{i}^{(m)}-\boldsymbol{\mathcal{B}}_{i}^{(m)}\right\|_{1}\right].$
(5.16)

Finally, note that by Theorem 3.1,

$\displaystyle\sup_{m\geq 0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{B}_{i}^{(m)}-\boldsymbol{\mathcal{B}}_{i}^{(m)}\right\|_{1}\right]$
$\displaystyle=\sup_{m\geq 0}\max_{i\in
V_{n}}\mathbb{E}_{n}\left[\left\|\mathbf{R}_{i}^{(m)}-\boldsymbol{\mathcal{R}}_{i}^{(m)}\right\|_{1}\right]\xrightarrow{P}0,\qquad
n\to\infty.$

Taking $k\to\infty$ in (5.16) completes the proof. ∎

### Acknowledgments

This work was supported by NSF grant CMMI-2243261.

## References

  * Abramowitz and Saunders, [2008] Abramowitz, A. I. and Saunders, K. L. (2008).  Is polarization a myth?  The Journal of Politics, 70(2):542–555.
  * Aldous and Steele, [2004] Aldous, D. and Steele, J. M. (2004).  The objective method: probabilistic combinatorial optimization and local weak convergence.  Probability on discrete structures, pages 1–72.
  * Avrachenkov et al., [2018] Avrachenkov, K., Kadavankandy, A., and Litvak, N. (2018).  Mean field analysis of personalized PageRank with implications for local graph clustering.  Journal of statistical physics, 173:895–916.
  * Axelrod, [1997] Axelrod, R. (1997).  The dissemination of culture: A model with local convergence and global polarization.  Journal of conflict resolution, 41(2):203–226.
  * Banerjee and Olvera-Cravioto, [2022] Banerjee, S. and Olvera-Cravioto, M. (2022).  Pagerank asymptotics on directed preferential attachment networks.  The Annals of Applied Probability, 32(4):3060–3084.
  * Ben-Naim et al., [2003] Ben-Naim, E., Krapivsky, P. L., and Redner, S. (2003).  Bifurcations and patterns in compromise processes.  Physica D: nonlinear phenomena, 183(3-4):190–204.
  * Benjamini and Schramm, [2001] Benjamini, I. and Schramm, O. (2001).  Recurrence of Distributional Limits of Finite Planar Graphs.  Electronic Journal of Probability, 6(none):1 – 13.
  * Berger, [1981] Berger, R. L. (1981).  A necessary and sufficient condition for reaching a consensus using DeGroot’s method.  Journal of the American Statistical Association, 76(374):415–418.
  * Bessi et al., [2016] Bessi, A., Zollo, F., Del Vicario, M., Puliga, M., Scala, A., Caldarelli, G., Uzzi, B., and Quattrociocchi, W. (2016).  Users polarization on Facebook and YouTube.  PLOS ONE, 11(8):1–24.
  * Bhamidi et al., [2019] Bhamidi, S., Budhiraja, A., and Wu, R. (2019).  Weakly interacting particle systems on inhomogeneous random graphs.  Stochastic Processes and their Applications, 129(6):2174–2206.
  * Budhiraja et al., [2019] Budhiraja, A., Mukherjee, D., and Wu, R. (2019).  Supermarket model on graphs.  The Annals of Applied Probability, 29(3):1740 – 1777.
  * [12] Chaintron, L.-P. and Diez, A. (2022a).  Propagation of chaos: A review of models, methods and applications. I. Models and methods.  Kinetic and Related Models, 15(6):895–1015.
  * [13] Chaintron, L.-P. and Diez, A. (2022b).  Propagation of chaos: A review of models, methods and applications. II. Applications.  Kinetic and Related Models, 15(6):1017–1173.
  * Chen et al., [2014] Chen, N., Litvak, N., and Olvera-Cravioto, M. (2014).  Pagerank in scale-free random graphs.  In Algorithms and Models for the Web Graph: 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings 11, pages 120–131. Springer.
  * Cocomello and Ramanan, [2023] Cocomello, J. and Ramanan, K. (2023).  Exact description of limiting SIR and SEIR dynamics on locally tree-like graphs.  arXiv preprint arXiv:2309.08829.
  * Como and Fagnani, [2011] Como, G. and Fagnani, F. (2011).  Scaling limits for continuous opinion dynamics systems.  The Annals of Applied Probability, 21(4):1537–1567.
  * Dandekar et al., [2013] Dandekar, P., Goel, A., and Lee, D. T. (2013).  Biased assimilation, homophily, and the dynamics of polarization.  Proceedings of the National Academy of Sciences, 110(15):5791–5796.
  * Deffuant et al., [2002] Deffuant, G., Amblard, F., Weisbuch, G., and Faure, T. (2002).  How can extremism prevail? A study based on the relative agreement interaction model.  Journal of artificial societies and social simulation, 5(4).
  * Deffuant et al., [2000] Deffuant, G., Neau, D., Amblard, F., and Weisbuch, G. (2000).  Mixing beliefs among interacting agents.  Advances in Complex Systems, 3(01n04):87–98.
  * DeGroot, [1974] DeGroot, M. H. (1974).  Reaching a consensus.  Journal of the American Statistical association, 69(345):118–121.
  * Del Vicario et al., [2017] Del Vicario, M., Scala, A., Caldarelli, G., Stanley, H. E., and Quattrociocchi, W. (2017).  Modeling confirmation bias and polarization.  Scientific reports, 7(1):40391.