# Discordant edges for the voter model
on regular random graphs

Luca Avena, Rangel Baldasso, Rajat Subhra Hazra, Frank den Hollander, Matteo
Quattropani  Mathematical Institute, Leiden Univerisity, P.O. Box 9521, 2300RA
Leiden, The Netherlands
<EMAIL_ADDRESS>
###### Abstract.

We consider the two-opinion voter model on a regular random graph with $n$
vertices and degree $d\geq 3$. It is known that consensus is reached on time
scale $n$ and that on this time scale the volume of the set of vertices with
one opinion evolves as a Fisher-Wright diffusion. We are interested in the
evolution of the number of discordant edges (i.e., edges linking vertices with
different opinions), which can be thought as the perimeter of the set of
vertices with one opinion. We show that if initially the two opinions are
drawn independently from a Bernoulli distribution with parameter $u\in(0,1)$,
then on time scale $1$ the fraction of discordant edges decreases and
stabilises to a value that depends on $d$ and $u$, and is related to the
meeting time of two random walks on an infinity tree of degree $d$ starting
from two neighbouring vertices. Moreover, we show that on time scale $n$ the
fraction of discordant edges moves away from the constant plateau and
converges to zero in an exponential fashion. Our proofs exploit the classical
dual system of coalescing random walks and use ideas from Cooper et al.,
(2010) built on the so-called First Visit Time Lemma. We further introduce a
novel technique to derive concentration properties from weak-dependence of
coalescing random walks on moderate time scales.

_Key words._ Regular random graph, voter model, random walks, discordant
edges, concentration.

_MSC2020:_ 05C81, 60K35.

_Acknowledgement._ This research was supported by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant
agreement no. 101034253 , and by the NWO Gravitation project NETWORKS under
grant no. 024.002.003.

##  1\. Model, literature and results

Random processes on random graphs constitute a research area that poses many
challenges. In the past decade, considerable progress has been made in
understanding how the geometry of the graph affects the evolution of the
process. In terms of the choice of graph, the focus has been on the Erdös-
Rényi random graph, the configuration model, the preferential attachment
model, and the exponential random graph, either directed or undirected, and in
regimes ranging from sparse to dense. In terms of the choice of process, the
focus has been on percolation, random walk, the stochastic Ising model, the
contact process, and the voter model. What makes the area particularly
interesting is that there is a delicate interplay between the _size_ of the
graph and the _time scale_ on which the process is observed. For short times,
the process behaves as if it lives on an infinite graph. For instance, many
sparse graphs are locally tree-like and therefore the process behaves as if it
evolves on an infinite Galton-Watson tree. For long times, however, the
process sees that the graph is finite and exhibits a crossover in its
behaviour. For instance, the voter model, which will be the process of
interest in the present paper, eventually reaches consensus on any finite
connected graph, but the time at which it does depends on the size of the
graph. Many such instances can be captured under the name of _finite-systems
scheme_ , i.e., the challenge to identify how a finite truncation of a
stochastic system behaves as both the time and the truncation level tend to
infinity, properly tuned together (Cox and Greven, (1990), Cox and Greven,
(1994)).

Random processes on random graphs are part of the larger research area of
random processes in _random environment_ , where the environment selects the
random transition probabilities or transition rates. Another name is that of
_interacting particle systems_ in random environment. For random process on
lattices a more or less complete theory has been developed over the past four
decades. The challenge is to extend this patrimony to random graphs. In the
present paper we focus on the voter model on the regular random graph in the
sparse regime. We track how the fraction of _discordant edges_ evolves over
time in the limit as the size of the graph tends to infinity, and identify its
scaling behaviour on _three time scales_ : short, moderate, and long.

Voter models were introduced and studied in Clifford and Sudbury, (1973) and
Holley and Liggett, (1975). Voter models and their consensus times on finite
graphs were analysed in Donnelly and Welsh, (1983) and Cox, (1989). The
behaviour of voter models on random networks depends on the realisation of the
network: Sood et al., (2008) made various predictions for the expected
consensus time on heterogeneous random networks (including power-law random
graphs). More recently, Fernley and Ortgiese, (2019) study the asymptotics of
the consensus time on inhomogeneous random graph models like the Chung-Lu
model and the Norros-Reitu model. The expected consensus time for regular
random graphs was studied in Cooper et al., (2010), in the discrete-time
synchronous setting. As far as we know, there is no literature on the
evolution of the number of discordant edges on random graphs.

###  1.1. Model and background

Given a connected graph $G=(V,E)$, the voter model is the Markov process
$(\eta_{t})_{t\geq 0}$ on state space $\\{0,1\\}^{V}$, with
$\eta_{t}=\\{\eta_{t}(x)\colon\,x\in V\\}$, where $\eta_{t}(x)$ represents the
opinion at time $t$ of vertex $x$. Each vertex is equipped with an independent
exponential clock that rings at rate one, after which the vertex selects one
of the neighbouring vertices uniformly at random and copies its opinion. (A
formal description of this interacting particle system, its generator, and how
its dynamics can be built up via the so-called graphical representation is
postponed to Section 2.)

As mentioned previously, while the voter dynamics has been widely studied on
periodic lattices, periodic tori, and complete graphs, only recently its
evolution on general connected graphs has been considered. In particular, as
discussed below, if the underlying (random or non-random) graph has
sufficiently nice properties, then it is possible to identify the time scale
on which consensus takes place, and to determine how the process behaves on
this time scale. In the present paper we specialise to the $d$-regular random
graph ensemble with $d\geq 3$. In particular, we consider the sequence of
random graphs $(G_{d,n}(\omega))_{n\in\mathbb{N}}$, with law denoted by
$\mathbb{P}$, where each element $G_{d,n}(\omega)=(V,E(\omega))$ is a regular
random graph of degree $d\geq 3$, consisting of $|V|=n$ vertices and
$|E(\omega)|=m=dn/2$ edges, uniformly sampled from the set of simple
$d$-regular graphs with $n$ vertices (to guarantee that $dn$ is even, for $d$
odd we restrict to $n$ even). These graphs are locally tree-like and have good
expansion properties (see Section 2.3), lying within the realm of so-called
_mean-field geometries_ (see Section 1.2). Therefore the voter model on the
$d$-regular random graph ensemble can be investigated in some depth, and
refined statements clarifying how consensus is reached can be derived. In the
present paper we analyse the evolution of the density of _discordances_. In
other words, denoting the set of discordant edges at time $t$ by

$D^{n}_{t}=\big{\\{}e=(x,y)\in E\colon\,\eta_{t}(x)\neq\eta_{t}(y)\big{\\}},$

we will study the fraction of discordant edges at time $t\geq 0$ given by

$\mathcal{D}^{n}_{t}=\frac{|D^{n}_{t}|}{m}$ (1.1)

in the limit as $n\to\infty$.

###  1.2. Voter model on mean-field geometries

$\bullet$ _Voter model._ A classical model of relevance in population genetics
is the voter model on the _complete graph_ , which is referred to as the
_Moran model_ or the _Fisher-Wright model_ (depending on whether continuous-
time asynchronous or discrete-time parallel updates are considered). The
states $\\{0,1\\}$ represent two different alleles, each coding for a specific
genetic trait, and the $n$ vertices of the complete graph $K_{n}$ represent
individuals in a population of size $n$. In the limit as $n\to\infty$, the
consensus time (to be interpreted as the extinction time of one of the two
traits) is known to scale linearly in $n$. Furthermore, on time scale $n$ the
fraction of the individuals of, say, type $1$ converges as a process to the
so-called _Fisher-Wright diffusion_. These results can be derived by analysing
the backward genealogical progeny, which amounts to studying $n$ coalescing
random walks evolving on the same graph, which in turn is related to the so-
called _Kingman coalescent_ (we refer to Durrett, (2008) for details). In
Section 2 we give a precise description of this _duality_ on arbitrary graphs.

These by now classical results have been recently extended to general _mean-
field geometries_ under two main conditions that can be roughly described as
follows: (I) the stationary distribution of the random walk on the random
graph must be _not too concentrated_ ; (II) _fast-mixing_ in the sense of an
asymptotically vanishing ratio between the mixing time of a single random walk
and the expected meeting time of two independent random walks starting from
stationarity.

$\bullet$ _Dual process._ For what concerns the dual process of coalescing
random walks, Oliveira, (2013) computes the distributional limit of the
coalescence time under the above mentioned assumptions. In particular, it
follows from (Oliveira,, 2013, Theorem 1.2) that

$\lim_{n\to\infty}\frac{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau_{\rm
coal}]}{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\pi\otimes\pi}_{\rm
meet}]}=2,$ (1.2)

where $\tau_{\rm coal}$ is the coalescence time of $n$ random walks, each
starting from a different vertex, and $\tau_{\rm meet}^{\pi\otimes\pi}$ is the
meeting time of two random walks independently starting from stationarity.
This offers insight into how the dual voter model behaves in mean-field like
geometries. In particular, (1.2) allows us to translate the question of how
long it takes for the voter model to achieve consensus to the question of
controlling the meeting time of two random walks starting from stationarity.
Indeed, as a consequence of this duality, it is immediate that the
$n$-coalescence time $\tau_{\rm coal}$ stochastically dominates the above
mentioned _consensus time_ , defined as

$\tau_{\rm cons}=\inf\\{t\geq 0\colon\,\eta_{t}(x)=\eta_{t}(y),\text{ for all
}x,y\in V\\}.$ (1.3)

For what concerns the convergence to a Fisher-Wright diffusion after proper
scaling, the recent work by Chen et al., (2016) considers the _fraction of
vertices in state $1$ at time $t$_ in the voter model,

$\mathcal{B}^{n}_{t}=\frac{1}{n}\sum_{x\in V}\eta_{t}(x),\qquad t\geq 0,$
(1.4)

under the above mentioned _mean-field conditions_ (see (Chen et al.,, 2016,
Theorem 2.2) for a precise formulation). The main result states that, when
time is speeded up by a factor
$\gamma_{n}\coloneqq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau_{\rm
meet}^{\pi\otimes\pi}]$, the rescaled density of vertices in state $1$, i.e.,
$(\mathcal{B}_{\gamma_{n}t}^{n})_{t\geq 0}$, converges as $n\to\infty$ to a
Fisher-Wright diffusion in the Skorokhod topology.

$\bullet$ _Regular random graphs as mean-field geometries._ Let us next
discuss the implications of the results mentioned above within the specific
framework of $d$-regular random graphs. The latter is a geometric setting that
satisfies the aforementioned _mean-field conditions_ with high probability
with respect to the law $\mathbb{P}$ of the environment. Indeed, it is well
known that a typical realisation of the graph is connected with high
probability as soon as $d\geq 3$. Due to the undirectedness of the edges, the
corresponding stationary distribution is uniform over the vertex set.
Furthermore, with high probability under $\mathbb{P}$, the mixing time is of
order $\log n$ (see Lubetzky and Sly, (2010)), while the expected meeting time
(see Chen, (2021)) satisfies

$\frac{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau_{\rm
meet}^{\pi\otimes\pi}]}{n}\overset{\mathbb{P}}{\longrightarrow}\frac{1}{2\theta_{d}}$

with

$\theta_{d}=\frac{d-2}{d-1}.$ (1.5)

Hence, by applying (1.2) to this setting, we find that

$\frac{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau_{\rm
coal}]}{n}\overset{\mathbb{P}}{\longrightarrow}\frac{1}{\theta_{d}}.$

Moreover, for the voter model starting from independent Bernoulli opinions
with parameter $u\in(0,1)$, by Chen et al., (2016) we also have that the
fraction of opinions of type $1$, i.e., $\mathcal{B}^{n}_{t}$ converges, after
time is speeded up by a factor $n$, to the Fisher-Wright diffusion
$(\bar{}\mathcal{B}_{s})_{s\geq 0}$ given by the SDE

$\mathrm{d}\bar{}\mathcal{B}_{s}=\sqrt{2\theta_{d}\bar{}\mathcal{B}_{s}(1-\bar{}\mathcal{B}_{s})}\,\mathrm{d}W_{s},\qquad\bar{}\mathcal{B}_{0}=u,$
(1.6)

where $(W_{s})_{s\geq 0}$ denotes the standard Brownian motion (with generator
$\tfrac{1}{2}\Delta$).

In conclusion, on $d$-regular ensembles consensus is reached on average on
time scale $n$ and, as far as the law is concerned, on the time scale of the
consensus the process can be well approximated by the Fisher-Wright diffusion
in (1.6). Interestingly, as pointed out by Chen et al., (2016), the diffusion
coefficient in (1.6) (which is referred to as the _genetic variability_ in a
population genetics context) can be related to the fraction of discordant
edges. This will be the starting point of our investigation, which is devoted
to a deeper understanding of the evolution of the voter model beyond the
consensus time scale $n$, via a detailed analysis of the discordant edges .

###  1.3. Main theorems: evolution of discordances and stabilisation before
consensus

Before we present our main results, we introduce some notation. The symbols
$\mathbb{P}$ and $\mathbb{E}$ will be reserved for the probability space of
the $d$-regular random graph. The abbreviation whp refers to events that occur
with probability $\mathbb{P}$ tending to $1$ as $n\to\infty$.

Thanks to the duality between the $n$-vertex voter model and a system of
$n$-coalescing random walks (to be described in more detail in Section 2), it
is sufficient to look at a collection of $2m$ Poisson processes, each
associated with an (oriented) edge of the graph, together with the initial
assignment of the opinions. In this way, we can use the very same source of
randomness to sample the evolution of the voter model, the dual system of
coalescing random walks, and a system of $n$ independent random walks, each
starting at a different vertex of the graph. For this reason we adopt the
symbols
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}$
and
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}$
to refer to any of these three stochastic processes evolving on a quenched
realisation of the graph. To distinguish between the random walks and the
voter model, in the latter case we use a sub-index to refer to the initial
distribution of the process. For instance,
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}$
denotes the law of the voter model starting from the configuration
$\eta_{0}=\xi\in\\{0,1\\}^{V}$. Similarly, when we write
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}$,
we refer to the voter model initialised by a product of Bernoulli random
variables of mean $u\in(0,1)$. On the other hand, when considering a system of
two or more independent or coalescing random walks, we simply use the symbols
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}$
and
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}$,
and the starting positions of the random walks will be clear from the context
(with the exception of Section 5, where an _ad-hoc_ notation will be
introduced). Finally, we write ${\rm Ber}(u)$ for a Bernoulli distribution of
parameter $u$.

We now present our main results. The first theorem identifies whp the first
order asymptotics of the expected number of discordant edges on all time
scales.

######  Theorem 1.1 (Expected density of discordances at all time scales).

Fix $d\geq 3$, and let $\theta_{d}$ be as in (1.5). Fix $u\in(0,1)$, and
consider the voter model on a $d$-regular random graph $G_{d,n}(\omega)$ with
initial distribution $[{\rm Ber}(u)]^{\otimes V}$. Then, for any non-negative
time $t_{n}$, the density of discordant edges in (1.1) satisfies

$\left|{\bf
E}_{u}\left[\mathcal{D}^{n}_{t_{n}}\right]-2u(1-u)(1-f_{d}(t_{n}))\mathrm{e}^{-2\theta_{d}\frac{t_{n}}{n}}\right|\overset{\mathbb{P}}{\longrightarrow}0,$
(1.7)

where

$f_{d}(t)={\bf P}^{\mathcal{T}_{d}}(\tau^{x,y}_{\rm meet}\leq
t)=\sum_{\kappa=0}^{\infty}\mathrm{e}^{-2t}\frac{(2t)^{\kappa}}{\kappa!}\sum_{s=0}^{\lfloor\frac{\kappa-1}{2}\rfloor}\binom{2s}{s}\frac{1}{s+1}\Big{(}\frac{1}{d}\Big{)}^{s+1}\Big{(}\frac{d-1}{d}\Big{)}^{s},$
(1.8)

with ${\bf P}^{\mathcal{T}_{d}}$ denoting the law of two independent random
walks on the infinite $d$-regular tree $\mathcal{T}_{d}$ starting from the
endpoints of an edge $e=(x,y)$ in $\mathcal{T}_{d}$.

Note that the limit is different depending on the time scale we are looking
at:

  * •

(Short time scale) For $t_{n}=\Theta(1)$, the first order of the above
expectation is given by $2u(1-u)(1-f_{d}(t_{n}))$, and the behaviour is
governed by the non-decreasing function captured in (1.8), representing the
meeting time of two random walks starting from adjacent vertices on an
infinite $d$-regular tree. See Figure 1.

  * •

(Moderate time scale) For $t_{n}=\omega(1)\cap o(n)$, the discordances
stabilise at a limiting plateau $2u(1-u)(1-f_{d}(\infty))$ characterised by
the probability that two adjacent random walks on an infinite tree never meet,
i.e., $1-f_{d}(\infty)=\theta_{d}$.

  * •

(Long time scale) For $t_{n}=sn$, $s\in(0,\infty)$, the dual system coalesces
and the voter model reaches consensus. The evolution of the density of
opinions is approximated by the Fisher-Wright diffusion in (1.6), and the
expected density of discordances is characterised by the mean of the genetic
variability ${\bf
E}_{u}\left[\bar{}\mathcal{B}_{s}(1-\bar{}\mathcal{B}_{s})\right]=2u(1-u)\theta_{d}\mathrm{e}^{-2\theta_{d}s}$.
See Figure 2.

  * •

(Consensus) For $t_{n}=\omega(n)$, the system has reached consensus and the
limiting formula in (1.7) degenerates to zero.

Figure 1. The two plots show a single simulation of the voter model on a
regular random graph of size $n=1000$, degree $d=3$ and initial density
$u=0.5$. _Left_ : In blue the density of blue opinions up to consensus
($\tau_{\rm cons}\approx 2.6\times 10^{3}$), in orange the density of
discordant edges up to consensus. _Right_ : In blue the density of discordant
edges up to time $t=5$ (corresponding to a zoom-in of the plot to the left),
in red the function $t\mapsto 2u(1-u)f_{d}(t)$. Figure 2. Scatter plot in blue
for the same simulation as in Figure 1: the density of discordant edges versus
the density of the minority opinion. The piece sticking out corresponds to
short times. The curve in red is $x\mapsto x(1-x)$.

The second theorem characterises the process $\mathcal{D}^{n}$ in (1.1) beyond
its expectation. In particular, we show that on time scale $o(n)$ the density
of discordances concentrates around the expectation, while on time scale
$\Theta(n)$ it behaves as a deterministic function of the Fisher-Wright
diffusion.

######  Theorem 1.2 (Beyond expectation).

Consider the voter model on a $d$-regular random graph $G_{d,n}(\omega)$ with
$d\geq 3$.

  1. (i)

Concentration before coalescence. Let $t_{n}$ be such that $t_{n}/n\to 0$.
Then, for every $\varepsilon>0$,

$\sup_{\xi\in\\{0,1\\}^{V}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(\left|\mathcal{D}^{n}_{t_{n}}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}[\mathcal{D}_{t_{n}}^{n}]\right|>\varepsilon\right)\overset{\mathbb{P}}{\longrightarrow}0.$

  2. (ii)

Discordance on consensus time scale. Let $t_{n}$ be such that $t_{n}/n\to
s\in(0,\infty)$. Then, for every $u\in(0,1)$,

$\sup_{x\in[0,1]}\left|\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\left(\mathcal{D}^{n}_{t_{n}}\leq
x\right)-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\left(\bar{}\mathcal{B}_{2s\theta_{d}}(1-\bar{}\mathcal{B}_{2s\theta_{d}})\leq
x\right)\right|\overset{\mathbb{P}}{\longrightarrow}0,$

where $(\bar{}\mathcal{B}_{s})_{s\geq 0}$ is the solution of (1.6).

The third and last theorem is a strengthening of Theorem 1.2 _(i)_. More
precisely, we show that as soon as we focus on the process for times that are
polynomially smaller than the consensus time, the concentration around the
mean is actually uniform in time.

######  Theorem 1.3 (Uniform concentration on moderate time scale).

Consider the voter model on a $d$-regular random graph $G_{d,n}(\omega)$.
Then, for every $u\in(0,1)$ and $\delta,\varepsilon>0$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\Big{(}\sup_{0\leq
t\leq
n^{1-\delta}}\big{|}\mathcal{D}_{t}^{n}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}[\mathcal{D}_{t}^{n}]\big{|}>\varepsilon\Big{)}\overset{\mathbb{P}}{\longrightarrow}0.$

###  1.4. Open problems

We point out two open problems.

  * •

Theorem 1.3 says that the concentration of the fraction of discordant edges is
uniform up to times $n^{1-\delta}$, for any $\delta>0$. We expect that Theorem
1.3 can be strengthened to the statement that for every $t_{n}$ such that
$t_{n}/n\to 0$ and every $C_{n}\to\infty$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\left|\mathcal{D}^{n}_{t_{n}}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\mathcal{D}^{n}_{t_{n}}]\right|>C_{n}\sqrt{t_{n}/n}\,\big{)}\overset{\mathbb{P}}{\longrightarrow}0.$
(1.9)

Note that, thanks to Azuma inequality, the concentration in (1.9) holds for
the quantity $\mathcal{B}_{t}^{n}$ in (1.4), because this is a martingale.
Note further that the concentration in Theorem 1.3 follows from (1.9) and a
union bound. For now, (1.9) is beyond our reach.

  * •

We expect that Theorems 1.1–1.3 can be extended to _non-regular_ sparse random
graphs. We do not have a conjecture on how the function $f_{d}$ and the
diffusion constant $\theta_{d}$ modify in this more general setting.

###  1.5. Description of techniques

All our proofs are based on the classical notion of duality between the voter
model and a collection of coalescent random walks. In particular, on time
scales $o(\log n)$, i.e., below the typical distance between two vertices, the
analysis can be carried out by coupling a system of two random walks, starting
at adjacent vertices and evolving on the $d$-regular random graph, with two
random walks on the $d$-regular tree. Because the tree is regular, the
distance of the two random walks can be viewed as the distance to the origin
of a single biased random walk on $\mathbb{N}_{0}$. Note that the same does
not hold when the tree is not regular.

Clearly, in order to analyse the process on time scales $\Theta(\log n)$,
i.e., on the typical distance between two vertices, the coupling argument must
be combined with a finer control of the two random walks on the regular random
graph. To this aim, we exploit the strategy developed in Cooper et al.,
(2010), which uses the so-called _First Visit Time Lemma_ (see Theorem 2.2).
Such control, together with a first-moment argument, is enough to compute the
evolution of the expected number of discordant on every time scale.

On the other hand, in order to obtain the concentration result in Theorem 1.3,
a much deeper analysis is required. Roughly, in order to have proper control
on the correlations between the edges constituting $\mathcal{D}_{t}^{n}$, we
must analyse a dual system of random walks whose number grows with $n$.
Exploiting a classical result by Aldous and Brown, (1992), we derive upper
bounds for the number of meetings of a poly-logarithmic number of independent
random walks evolving on the random graph for a time $n^{1-o(1)}$. Such a
bound will be exploited in the forthcoming Proposition 5.1 to deduce an upper
bound for the deviation from the mean that is exponentially small in $n$ and
uniform in time. This upper bound can in turn be translated to the result in
Theorem 1.3 by taking a union bound.

###  1.6. Outline

Section 2 lists definitions and notations, recalls the graphical construction
and duality, states a key lemma, and collects a few basic facts about regular
random graphs and random walks on such geometries. Theorems 1.1–1.3 are proved
in Sections 3–5, respectively. Appendix A contains two auxiliary facts for
càdlàg processes.

##  2\. Notation and preparation

In this section we properly introduce the voter model on general graphs, and
collect some results that will be needed along the way. In Section 2.1 we
introduce the graphical construction for the voter model and the associated
dual process, known as _coalescing random walks_. Section 2.2 contains the
_First Visit Time Lemma_ , which has been introduced by Cooper and Frieze,
(2005). Section 2.3 collects some useful facts about the geometry of
$d$-regular random graphs and the behaviour of random walks on them. In what
follows we drop the upper index $n$ to lighten the notation.

###  2.1. The voter model and coalescing random walks

Let $G(V,E)$ be a connected (possibly infinite and locally-finite) undirected
graph. For each $x\in V$, let $d_{x}$ denote the degree of vertex $x$. The
voter model on $G$ is defined as the interacting particle system with state
space $\\{0,1\\}^{V}$ and generator $\mathcal{L}$ acting on local functions
$f\colon\,V\to\mathbb{R}$ as

$(\mathcal{L}f)(\eta)=\sum_{x\in V}\sum_{y\sim
x}\frac{1}{d_{x}}\big{(}f(\eta^{x\leftarrow
y})-f(\eta)\big{)},\qquad\eta\in\\{0,1\\}^{V},$

where $\eta^{x\leftarrow y}$ is obtained from $\eta$ as

$\eta^{x\leftarrow y}(z)=\begin{cases}\eta(y),&\quad\text{if }z=x,\\\
\eta(z),&\quad\text{otherwise}.\end{cases}$

In this system, agents (represented by the vertices of $G$) start with binary
opinions and update these at rate one by copying the opinion of a uniformly
chosen neighbour. For $t\geq 0$ and $x\in V$, denote by
$\eta_{t}(x)\in\\{0,1\\}$ the opinion of vertex $x$ at time $t$.

When $G$ is finite and regular, i.e., $d_{x}=d$ for every $x\in V$, the number
of vertices that have opinion $1$,

$B_{t}=\sum_{x\in V}\eta_{t}(x),$

is a martingale. Since $B_{t}$ is bounded by $|V|$, it converges, which
implies that the voter model eventually fixates on a constant configuration,
composed entirely of $0$’s or $1$’s, denoted by $\bar{0}$ and $\bar{1}$,
respectively. Define the consensus time of $G$ as the stopping time

$\tau_{\rm cons}=\inf\big{\\{}t\geq
0\colon\,\eta_{t}\in\\{\bar{0},\bar{1}\\}\big{\\}}.$

Let us next introduce the _graphical construction_ of the voter model.
Associate to every oriented edge $\vec{e}=(x,y)$ a Poisson point process
$\mathscr{P}_{\vec{e}}$ on $\mathbb{R}$ with intensity $1/d_{x}$. When a clock
from $\vec{e}=(x,y)$ rings, vertex $x$ receives the opinion of vertex $y$.
This constriction allows us to track the joint evolution of all the opinions
via time duality. In order to determine $\eta_{t}(x)$, the state of a vertex
$x$ at time $t$, we start from the space time point $(x,t)$, and go backwards
in time, crossing every clock ring from an edge that reaches the current
position of the path (see Figure 3).

$t$$-2$$-1$$0$$1$$2$ Figure 3. The graphical construction of the voter model
on the integer lattice $\mathbb{Z}$. The red path allows us to determine that
$\eta_{t}(1)$ is equal to $\eta_{0}(2)$.

The process that tracks the origin of the opinions can be viewed as a
collection of _coalescing random walks_. To define this process we assume that
$G$ is finite and consider a family $\\{(X^{v}_{t})_{t\geq 0}\\}_{v\in V}$ of
independent rate-one continuous-time random walks such that $X^{v}_{0}=v$
almost surely. In what follows we identify $V$ with $[n]=\\{1,\ldots,n\\}$.
When two walks meet at the same vertex they coalesce into a single walk (this
can be seen immediately by the graphical representation in 3.)

Because $G$ is finite, any two independent random walks meet in finite time.
Consequently, $\tau_{\rm coal}$, the first time at which all the random walks
sit at the same vertex called the _coalescence time_ , satisfies $\tau_{\rm
coal}<\infty$ almost surely. In particular, the above mentioned duality
implies that $\tau_{\rm cons}\leq\tau_{\rm coal}$, and therefore any upper
bound on the coalescence time immediately yields an upper bound on the
consensus time of the voter model.

Given $x,y\in[n]$, let

$\tau_{\rm meet}^{x,y}=\inf\\{t\geq 0\colon\,X_{t}^{x}=X_{t}^{y}\\}$ (2.1)

denote the _meeting time_ of two independent continuous-time random walks
starting from $x$ and $y$, respectively. More generally, if the two random
walks are initialised randomly and independently according to two
distributions $\mu$ and $\nu$ on $[n]$, then we denote their meeting time by
$\tau_{\rm meet}^{\mu\otimes\nu}$. We note that the extension to infinite
graphs $G$ follows from standard estimates on the probability that the process
can be approximated by a finite dynamics in finite portions of space during a
bounded amount of time.

###  2.2. The First Visit Time Lemma

In this section we state the _First Visit Time Lemma_ (FVTL), which was
introduced by Cooper and Frieze, (2005) and recently simplified by Manzo et
al., (2021). This lemma contains estimates on the time a random walk takes to
reach a distinguished site when starting from the stationary distribution.

######  Remark 2.1.

Since the FVTL is defined in discrete time, in what follows it will be easier
to derive the results in discrete time and then translate them to continuous
time. For this reason, when considering two random walks in discrete time,
where at each step the random walk that moves is selected uniformly at random,
we use the notation
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}$ to refer to their law.

######  Theorem 2.2 (First Visit Time Lemma; Manzo et al., (2021)).

Consider a sequence of ergodic Markov chains labelled by $N\in\mathbb{N}$,
living on a finite state space $\Omega_{N}$ of size $N$, with transition
matrix $Q_{N}$ and stationary distribution $\mu_{N}$ and a target state
$x\in\Omega_{N}$. Define

$T_{\rm mix}^{(N)}=\inf\left\\{t\geq
0\colon\,\max_{x,y\in\Omega_{N}}|Q_{N}^{t}(x,y)-\mu_{N}(y)|\leq\frac{1}{N^{3}}\right\\},$
(2.2)

and assume that

  1. (1)

$\lim_{N\to\infty}N^{2}\min_{x\in\Omega_{N}}\mu_{N}(x)=\infty$.

  2. (2)

$\lim_{N\to\infty}T_{\rm mix}^{(N)}\max_{x\in\Omega_{N}}\mu_{N}(x)=0$.

  3. (3)

There exists a unique _quasi-stationary distribution_ associated to $x$, i.e.,
for all $N$ large enough the sub-matrix $[Q_{N}]_{x}$ in which the row and
column have been erased is _irreducible_. See also (Quattropani and Sau,,
2022, Remark 3.2 and Section 4.4).

Then there exists a sequence $(\lambda_{x}^{(N)})_{N\in\mathbb{N}}$ such that

$\lim_{N\to\infty}\left|\frac{\lambda^{(N)}_{x}}{\frac{\mu_{N}(x)}{R_{N}(x)}}-1\right|=0,\qquad
R_{N}(x)\coloneqq\sum_{s=0}^{T^{(N)}_{\rm mix}}Q_{N}^{s}(x,x),$

and

$\lim_{N\to\infty}\sup_{t\geq
0}\left|\frac{\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\mu_{N}}(\tau_{x}>t)}{(1-\lambda^{(N)}_{x})^{t}}-1\right|=0,$

with
$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\mu_{N}}$
the path measure of the Markov chain starting from $\mu_{N}$.

In words, the FVTL states that, under the assumptions, the hitting time of a
state $x$ is well approximated by a geometric (exponential, in continuous
time) random variable with mean $\frac{R(x)}{\mu(x)}$.

###  2.3. The geometry of regular random graphs

In this section we collect a number of definitions and asymptotic results
about the _typical geometry_ of regular random graphs. We start by introducing
notation and conclude by stating some basic facts regarding typical
$d$-regular random graphs.

Given a connected graph $G=(V,E)$ and two vertices $x,y\in V$, we denote by
${\rm dist}(x,y)$ the distance between $x$ and $y$, given by the number of
edges of the shortest path joining $x$ and $y$. For a vertex $x\in V$ and a
radius $h\geq 1$, we denote by $\mathcal{B}_{x}(h)$ the ball of radius $h$
centered at $x$, seen as a subgraph of $G$. The tree excess of a graph
quantifies how far away from a tree a given connected graph is.

######  Definition 2.3 (Tree excess).

Given a connected graph $G=(V,E)$, the _tree excess_ of $G$, denoted by
$\operatorname{\textnormal{{tx}}}(G)$, is the minimum number of edges that
must be removed from $G$ in order to obtain a tree. This can also be written
as

$\operatorname{\textnormal{{tx}}}(G)=|V|-|E|-1.$

Next, we introduce the notion of _locally tree-like vertices and edges_.

######  Definition 2.4 (Locally tree-like vertex).

Given a graph $G=(V,E)$, we say that a vertex $x\in V$ is locally tree-like up
to distance $\ell\geq 1$, denoted by $x\in{\rm LTL}(\ell)$, if the subgraph
induced by the vertices at distance at most $\ell$ from $x$, i.e.,
$\mathcal{B}_{x}(\ell)$, is a tree.

######  Definition 2.5 (Locally tree-like edge).

Given a graph $G=(V,E)$ and an edge $e\in E$, we say that $e=\\{x,y\\}$ is
locally tree-like up to distance $\ell\geq 1$, denoted by $e\in{\rm
LTLE}(\ell)$, if the subgraph induced by the vertices at distance at most
$\ell$ from $x$ or $y$, i.e.,
$\mathcal{B}_{x}(\ell)\cup\mathcal{B}_{y}(\ell)$, after removal of the edge
$e$, is composed of two disjoint trees of depth at most $\ell$.

For $d\geq 3$ and $n>d$ such that $nd$ is even, there exists at least one
graph with $n$ vertices and constant degree equal to $d$. In particular, for
this range of parameters the $d$-regular random graph of size $n$, drawn from
the uniform distribution on the set of all graphs with $n$ vertices and
constant degree equal to $d$, is well defined. Denote by $m=dn/2$ the number
of edges of this random graph. The following proposition collects properties
of the $d$-regular random graph that will be needed in the rest of the paper.

######  Proposition 2.6 (Geometry of regular random graphs and random walks;
Lubetzky and Sly, (2010)).

Fix $d\geq 3$, and let $G_{d,n}(\omega)$ denote the $d$-regular random graph
of size $n$. Then, whp,

  1. (i)

$G$ is connected.

  2. (ii)

For every $x\in[n]$,
$\operatorname{\textnormal{{tx}}}(\mathcal{B}_{x}(\tfrac{1}{5}\log_{d}n))\leq
1$.

  3. (iii)

$|{\rm LTLE}(\tfrac{1}{5}\log_{d}n)|=m-o(n)$.

  4. (iv)

There exists a constant $C=C_{d}>1$ such that for $t=C\log n$ and for every
$\varepsilon>0$,

$d_{\rm TV}(t):=\max_{x\in[n]}\|P^{t}(x,\cdot)-\pi\|_{\rm TV}\leq\varepsilon.$
(2.3)

In particular, for $t_{n}$ such that $\displaystyle\lim_{n\to\infty}\log
n/t_{n}=0$, then $\displaystyle\lim_{n\to\infty}d_{\rm TV}(t_{n})=0$.

##  3\. Computation of the expectation

In this section we prove Theorem 1.1, in particular, we provide a whp first-
order estimate of the expected density of discordant edges at time $t=t_{n}$,
for every choice of the sequence $(t_{n})_{n\in\mathbb{N}}$. In Section 3.1 we
collect some basic results for the voter model on the infinite $d$-regular
tree $\mathcal{T}_{d}$, the _local approximation_ of the $d$-regular random
graph. We show that the density of discordant edges at time $t$ on
$\mathcal{T}_{d}$ with ${\rm Ber}(u)$ initialisation behaves as
$2u(1-u)(1-f(t))$. This will be done by exploiting duality: we reduce the
problem to the analysis of a pair of coalescing random walks starting at the
two extremes of an edge of the tree. In Section 3.2 we show that a classical
coupling argument suffices to show that the approximation holds for every
sequence $t=(t_{n})_{n\in\mathbb{N}}$ such that $t/\log n\to 0$. When $t$
starts to become comparable with the typical distance of the graph, i.e.,
$t_{n}=\Theta(\log n)$, the coupling argument fails and we need a refined
analysis of the process to compute the expected density. This scenario will be
handled in Section 3.3. The idea is to track a pair of random walks starting
from the two extremes of a typical (hence, _locally tree-like_) edge up to
their first meeting. Using the First Visit Time Lemma, we show that, under the
event that the two random walks do not meet after a short time, the time of
their first meeting is well approximated by exponential random variable with
rate $\theta_{d}^{-1}n$.

###  3.1. Discordant edges on the regular tree

Let $\mathcal{T}_{d}$ denote the _infinite $d$-regular tree_ with $d\geq 3$.
Our first lemma concerns the probability that two independent random walks,
starting at distance one from each other, do not meet within a time $t$.
Recall that
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}$
denotes the law of two independent random walks starting from then endvertices
of an edge in $\mathcal{T}_{d}$.

######  Lemma 3.1 (Meeting on a regular tree).

Let $x,y\in\mathcal{T}_{d}$ with ${\rm dist}(x,y)=1$. Then

$f_{d}(t)=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}\big{(}\tau^{x,y}_{\rm
meet}\leq
t\big{)}=\sum_{\kappa=0}^{\infty}\mathrm{e}^{-2t}\frac{(2t)^{\kappa}}{\kappa!}\sum_{s=0}^{\lfloor\frac{\kappa-1}{2}\rfloor}\binom{2s}{s}\frac{1}{s+1}\Big{(}\frac{1}{d}\Big{)}^{s+1}\Big{(}\frac{d-1}{d}\Big{)}^{s}.$
(3.1)

From this it follows that

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}(\tau^{x,y}_{\rm
meet}=\infty)=\frac{d-2}{d-1}=\theta_{d}.$ (3.2)

###### Proof.

Let $(X_{t})_{t\geq 0}$ and $(Y_{t})_{t\geq 0}$ be two independent continuous-
time random walks starting from $x\sim y$, respectively. Put $Z_{t}={\rm
dist}(X_{t},Y_{t})$ and note that $(Z_{t})_{t\geq 0}$ is a continuous-time
biased random walk on $\mathbb{N}_{0}$ that starts at $1$, jumps at rate $2$,
and has jump distribution given by

$p(z,z+1)=1-p(z,z-1)=\frac{d-1}{d},\qquad z\in\mathbb{N}.$ (3.3)

The claim in (3.1) follows from the construction of the random walk
$(Z_{t})_{t\geq 0}$ via a Poisson process of rate $2$ for the jump times,
together with a skeleton chain given by the discrete-time biased random walk
with jump distribution given by (3.3), and explicit expressions for hitting
times of discrete-time random walks based on path-counting arguments.

To get (3.2) it is enough to note that, by the standard Gambler’s ruin
argument,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}\big{(}\tau^{x,y}_{\rm
meet}<\infty\big{)}=\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}Z_{t}=0\text{
for some }t\geq 0\mid Z_{0}=1\big{)}=\frac{p(0,-1)}{p(0,1)}=\frac{1}{d-1},$

from which the claim follows. ∎

######  Remark 3.2.

Note that (3.2) can be derived from (3.1) by direct computation. Indeed,
clearly $f(0)=0$. The generating function $c(x)=\sum_{k=0}^{\infty}C_{k}x^{k}$
for the Catalan numbers $C_{k}=\binom{2k}{k}\frac{1}{k+1}$ solves the
quadratic equation $c(x)=1+xc(x)^{2}$. Since $C_{0}=1$, we have

$c(x)=\frac{[1-\sqrt{1-4x}\,]}{2x}.$

It follows that

$f(\infty)=\frac{1}{d}\,c\left(\frac{d-1}{d^{2}}\right)=\frac{1}{d}\,\frac{\left[1-\frac{d-2}{d}\right]}{2\>\frac{d-1}{d^{2}}}=\frac{1}{d-1}=1-\theta_{d}.$

######  Lemma 3.3 (Density of discordant edges).

Consider the voter model on $\mathcal{T}_{d}$ with initial density $u$. Then,
for any given edge $e$ and any time $t\geq 0$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}_{u}\big{(}e\in
D_{t}\big{)}=2u(1-u)(1-f_{d}(t)),$

where $f_{d}(t)$ is given by (3.1).

###### Proof.

Put $e=\\{x,y\\}$. Note that in order to have $e\in D_{t}$, by duality, the
(backward) random walks starting from $x$ and $y$ at time $t$ do not coalesce
before time $0$ and end up at vertices with distinct initial opinions. The
initial opinions are independent of the trajectories of these random walks.
The claim follows by noting that $1-f_{d}(t)$ is the probability that the two
random walks do not meet in time $t$, and $2u(1-u)$ is the probability that
two distinct vertices have different initial opinions. ∎

###  3.2. Expectation for _small times_

We start this section with a general bound that does not require the graph $G$
to be random nor the size of $G$ to grow to infinity.

######  Lemma 3.4 (Discordant LTLEs).

Let $G=(V,E)$ be any $d$-regular graph and let $e=\\{x,y\\}\in E$ be ${\rm
LTLE}(\ell)$ for some $\ell$. Consider the voter model on $G$ with initial
density $u$. Then, for any time $T>0$,

$\sup_{t\in[0,T]}\left|\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}(e\in
D_{t})-2u(1-u)(1-f_{d}(t))\right|\leq\frac{4T}{\ell}.$

###### Proof.

Note first that the term $2u(1-u)(1-f_{d}(t))$ corresponds to the probability
that a given edge in $\mathcal{T}_{d}$ is discordant at time $t$. In
particular, if we consider the dual system with coalescing random walks, then
the probabilities we are interested in are the same, provided the random walks
do not leave the tree-like neighbourhood of $e$. Therefore consider the event

$\mathcal{E}_{T}=\big{\\{}\text{the number of jumps the random walks perform
before time }T\text{ is bounded by }\ell\big{\\}},$

and observe that, by the Markov inequality,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\mathcal{E}_{T}^{c}\big{)}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}\big{(}\mathcal{E}_{T}^{c}\big{)}\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}\big{(}X\geq\ell\big{)}\leq\frac{2T}{\ell},$

where $X\sim{\rm Poisson}(2T)$ stochastically dominates the number of jumps
that both random walks make up to time $T$. By construction, for $t\leq T$ we
can write

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\big{(}e\in
D_{t},\mathcal{E}_{T}\big{)}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}_{u}\big{(}e\in
D_{t},\mathcal{E}_{T}\big{)},$

from which we can estimate

$\begin{split}&\left|\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}(e\in
D_{t})-2u(1-u)(1-f_{d}(t))\right|=\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\big{(}e\in
D_{t}\big{)}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}_{u}\big{(}e\in
D_{t}\big{)}\Big{|}\\\
&\leq\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\big{(}e\in
D_{t},\mathcal{E}_{T}\big{)}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}^{\mathcal{T}_{d}}\big{(}e\in
D_{t},\mathcal{E}_{T}\big{)}\Big{|}+2\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\mathcal{T}_{d}}\big{(}\mathcal{E}_{T}^{c}\big{)}\leq\frac{4T}{\ell},\end{split}$

which settles the claim. ∎

######  Proposition 3.5 (Short time average).

Consider the voter model on a regular random graph $G_{d,n}(\omega)$ with
initial density $u\in(0,1)$. Then, for any time $t_{n}$ satisfying $t_{n}/\log
n\to 0$,

$\left|\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}[\mathcal{D}_{t_{n}}]-2u(1-u)(1-f_{d}(t_{n}))\right|\overset{\mathbb{P}}{\longrightarrow}0.$
(3.4)

###### Proof.

Note that for every realisation of $G$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}[|D_{t_{n}}|]=\sum_{e\in
E}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}(e\in
D^{n}_{t_{n}}).$

Call $E_{\star}\subset E$ the set of ${\rm
LTLE}\big{(}\frac{1}{5}\log_{d}n\big{)}$ edges. Then, by Lemma 3.4 and our
assumption on $t_{n}$,

$\begin{split}\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}[\mathcal{D}_{t_{n}}]-2u(1-u)(1-f_{d}(t_{n}))\big{|}&\leq\Big{|}\frac{1}{m}\sum_{e\in
E}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\big{(}e\in
D_{t}\big{)}-2u(1-u)(1-f_{d}(t_{n}))\Big{|}\\\ &\leq\frac{1}{m}\sum_{e\in
E_{\star}}\frac{4t_{n}}{\frac{1}{5}\log_{d}n}+\frac{1}{m}|E_{\star}^{c}|\overset{\mathbb{P}}{\longrightarrow}0,\end{split}$

where the last convergence follows from Proposition 2.6(iii). ∎

###  3.3. Expectation for _long times_

In this section we show how the behaviour in Proposition 3.5 can be extended
up to the linear time scale. Clearly, we need a different argument, since we
can no longer assume that the dual random walks starting at the extremes of a
locally tree-like edge do not exit their neighbourhood of size
$\tfrac{1}{5}\log_{d}(n)$. In order to proceed, we adapt the arguments in
(Cooper et al.,, 2010, Lemmas 17 and 20) to our framework, which will
constitute a crucial tool for our analysis. In what follows, we fix

$\sigma_{n}=\lceil\left(\log\log n\right)^{2}\rceil.$ (3.5)

The following lemma says that whp for every pair of starting vertices that are
more than $\sigma_{n}$ apart the probability that the two random walks meet
before time $\log^{3}n$ is exponentially small in $\sigma_{n}$.

######  Lemma 3.6 (Meeting time of distant random walks).

Let $G_{d,n}(\omega)$ be a regular random graph. Then there exists a constant
$c_{\ref{c:bound_meeting_time}}>0$ such that

$\mathds{1}\left\\{\max_{x,y\colon\,{\rm
dist}(x,y)>\sigma_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
meet}^{x,y}\leq\log^{3}n\big{)}\leq\mathrm{e}^{-c_{\ref{c:bound_meeting_time}}\sigma_{n}}\right\\}\overset{\mathbb{P}}{\longrightarrow}1.$

###### Proof.

The proof comes in several steps.

1. Consider two independent random walks $(X_{t})_{t\geq 0}$ and $(Y_{t})_{t\geq 0}$ that start from $x$ and $y$, respectively. The number of steps each random walk performs before time $\log^{3}n$ has distribution ${\rm Poisson}(\log^{3}n)$. In particular, Markov’s inequality with exponential moments implies that, for $\lambda=\log\log n$,

$\begin{split}&\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\bigg{(}\begin{array}[]{c}X_{t}\text{
or }Y_{t}\text{ performs more than}\log^{4}n\text{ steps before time
}\log^{3}n\end{array}\bigg{)}\\\ &\leq
2\mathrm{e}^{-\lambda\log^{4}n}\exp\big{\\{}(\mathrm{e}^{\lambda}-1)\log^{3}n\big{\\}}=2\exp\big{\\{}(\mathrm{e}^{\lambda}-1)\log^{3}n-\lambda\log^{4}n\big{\\}}\\\
&=2\exp\big{\\{}(\log n-1-\log\log n\log
n)\log^{3}n\big{\\}}\leq\mathrm{e}^{-c_{\ref{c:bound_meeting_time}}\sigma_{n}},\end{split}$

provided $n$ is large enough. We can consider only the case where $X$ and $Y$
perform discrete-time random walks in which at every step one of the random
walks is selected uniformly at random to move. We then just need to verify
that whp

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}\leq
2\log^{4}n\big{)}\leq\mathrm{e}^{-c_{\ref{c:bound_meeting_time}}\sigma_{n}},$

uniformly over the pairs $x$ and $y$ that are at least $\sigma_{n}$ apart.

2. Let $Z_{t}$ denote the graph distance of $X_{t}$ and $Y_{t}$ at time $t$. Note that $Z_{0}\geq\sigma_{n}$, and $Z_{t+1}-Z_{t}\in\\{-1,0,1\\}$ for every $t\geq 0$ (the case $Z_{t+1}-Z_{t}=0$ corresponds to jumps like the one in Figure 4). This implies that the random walks cannot meet before time $\sigma_{n}$. Recall from Proposition 2.6 that whp

$\operatorname{\textnormal{{tx}}}(\mathcal{B}_{2\sigma_{n}}(v))\leq
1,\qquad\text{for all }v\in V.$

$X$$Y$ Figure 4. In a general $d$-regular graph the potential existence of
cycles of length $3$ allows the distance between the two random walks to
remain constant after $1$ step. In the picture, if $Y$ moves along the blue
arrow, then it remains at distance $1$ to $X$.

It is now enough to show that

$q_{n}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\Big{(}\tau_{\rm
meet}^{x,y}\in\big{\\{}\sigma_{n},\dots,2\log^{4}n\big{\\}}\Big{)}\leq
4\log^{8}n\mathrm{e}^{-2c_{\ref{c:bound_meeting_time}}\sigma_{n}}\leq\mathrm{e}^{-c_{\ref{c:bound_meeting_time}}\sigma_{n}},$

for some positive $c_{\ref{c:bound_meeting_time}}$ and all $n$ large enough.
Put $\rho=\max\\{t\leq\tau_{\rm meet}^{x,y}\colon Z_{t}\geq\sigma_{n}\\}$. We
rewrite the probability of interest as

$q_{n}\leq 2\log^{4}n\max_{r\leq
2\log^{4}n}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}\leq 2\log^{4}n,\rho=r\big{)}.$

We aim at providing bounds on the above probability that are uniform in $r\leq
2\log^{4}n$. To that end, consider the ball of radius $2\sigma_{n}$ around
$X_{\rho}$, which by assumption satisfies

$\operatorname{\textnormal{{tx}}}(\mathcal{B}_{2\sigma_{n}}(X_{\rho}))\leq 1.$

We distinguish between two cases: (1) the quantity above is $0$ (and thus
$\mathcal{B}_{2\sigma_{n}}(X_{\rho})$ is a tree); (2) the tree excess of
$\mathcal{B}_{2\sigma_{n}}(X_{\rho})$ is $1$.

3. First, consider the case when $\mathcal{B}_{2\sigma_{n}}(X_{\rho})$ is a tree. Call $\mathfrak{p}$ the unique path joining $X_{\rho}$ and $Y_{\rho}$ within the tree, and recall that $|\mathfrak{p}|={\rm dist}(X_{\rho},Y_{\rho})=\sigma_{n}$. Let us argue that at least one of the random walks does $\sigma_{n}/2$ steps along $\mathfrak{p}$. Indeed, suppose first that for all $t\in\\{\rho,\dots,\tau_{\rm meet}^{x,y}\\}$ neither $X_{t}$ nor $Y_{t}$ leaves the tree $\mathcal{B}_{2\sigma_{n}}(X_{\rho})$. In order for the two random walks to meet, they need to jointly traverse the path $\mathfrak{p}$. If, on the other hand, one of the two random walks leaves $\mathcal{B}_{2\sigma_{n}}(X_{\rho})$, then our claim is met by the definition of $\rho$. Here, note that when we say that the first/second random walk must have made $\sigma_{n}/2$ steps along $\mathfrak{p}$, we do not require that the steps are made consecutively. Nonetheless, under $\\{\rho=r\\}$, requiring that at least one of the two random walks does $\sigma_{n}/2$ steps along $\mathfrak{p}$ within time $2\log^{4}n$ is equivalent to requiring that

$\hat{\tau}_{r}=\inf\\{u\geq r\colon\,{\rm dist}(X_{u},Y_{r})\wedge{\rm
dist}(X_{r},Y_{u})\leq\tfrac{\sigma_{n}}{2}\\}$

satisfies $\hat{\tau}_{r}\leq 2\log^{4}n$. We can now bound, uniformly in
$r\leq 2\log^{4}n$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}\leq
2\log^{4}n,\rho=r\big{)}\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\hat{\tau}_{r}\leq 2\log^{4}n,\rho=r\big{)}\leq
2\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
abs}\leq 2\log^{4}n\big{)},$

where $\tau_{\rm abs}$ is the absorption time at the origin of a biased random
walk on $\mathbb{Z}$, and $(W_{u})_{u\geq 0}$ is such that
$W_{0}=\sigma_{n}/2$ and

$p=\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}W_{t+1}-W_{t}=1\big{)}=1-\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}W_{t+1}-W_{t}=-1\big{)}=\frac{d-1}{d}.$

Hence, by the classical Gambler’s ruin argument,

$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
abs}\leq
2\log^{4}n\big{)}\leq\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
abs}<\infty\big{)}=\Big{(}\frac{1-p}{p}\Big{)}^{\sigma_{n}/2}=\Big{(}\frac{1}{d-1}\Big{)}^{\sigma_{n}/2}\leq
2^{-\frac{\sigma_{n}}{2}}.$ (3.6)

The claim follows by choosing $c_{\ref{c:bound_meeting_time}}\leq\frac{\log
2}{5}$.

$X_{\rho}$$Y_{\rho}$$X_{\rho}$$Y_{\rho}$$X_{\rho}$$Y_{\rho}$$X_{\rho}$$Y_{\rho}$$z_{\kappa}$
Figure 5. A sketch of the $4$ possible ways the two paths $\mathfrak{p}$ and
$\tilde{\mathfrak{p}}$ described below can look like.
$Y_{\rho}$$X_{\rho}$$Y_{\rho}$$X_{\rho}$ Figure 6. On the left
$|\tilde{\mathfrak{p}}|=|\mathfrak{p}|+1$, on the right
$|\tilde{\mathfrak{p}}|=|\mathfrak{p}|$.

4. Next, consider the case when $\operatorname{\textnormal{{tx}}}(\mathcal{B}_{2\sigma_{n}}(X_{\rho}))=1$. Then there are at most two paths joining $Y_{\rho}$ to $X_{\rho}$ in $\mathcal{B}_{2\sigma_{n}}(X_{\rho})$ (see Figure 5). Call these two paths $\mathfrak{p}=(z_{0}=Y_{\rho},z_{1},\dots,z_{\sigma_{n}}=X_{\rho})$ and $\tilde{\mathfrak{p}}=(\tilde{z}_{0}=Y_{\rho},\tilde{z}_{1},\dots,\tilde{z}_{\ell}=X_{\rho})$, with $\sigma_{n}\leq\ell\leq 3\sigma_{n}+1$ (the case $\ell=\sigma_{n}$ is exemplified in Figure 6). Let $\kappa$ denote the index of the last vertex such that the paths coincide, i.e.,

$\kappa=\sup\big{\\{}i\leq\sigma_{n}:z_{i}=\tilde{z}_{i}\big{\\}}.$

We split the two paths as
$\mathfrak{p}=(\mathfrak{p}_{\kappa},\mathfrak{p}^{\prime})$ and
$\tilde{\mathfrak{p}}=(\mathfrak{p}_{\kappa},\mathfrak{p}^{\prime\prime})$,
where $\mathfrak{p}_{\kappa}=(z_{0},z_{1},\dots,z_{\kappa})$. If
$\kappa\geq\frac{1}{2}\sigma_{n}$, then the argument from the previous
paragraph can be easily adapted as follows. We first note that, in order for
the random walks to meet, either $Y$ or $X$ must reach
$z_{\frac{1}{2}\kappa}$. If $Y$ is the random walk that reaches this vertex,
then the comparison with the birth-and-death chain is done in the same way as
before. If the random walk that reaches $z_{\frac{1}{2}\kappa}$ is $X$, then
we still need to account for the time it takes $X$ to arrive at $z_{\kappa}$,
which can be taken care of via a union bound, yielding an additional factor
$2\log^{4}n$ in the calculation. More precisely, consider the random variables

$\tilde{\tau}_{r}^{1}=\inf\\{u\geq
r\colon\,X_{u}=z_{\frac{1}{2}\kappa}\\},\qquad\tilde{\tau}_{r}^{2}=\inf\\{u\geq
r\colon\,Y_{u}=z_{\frac{1}{2}\kappa}\\}.$

We can bound

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}\leq
2\log^{4}n,\rho=r\big{)}&\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\Big{(}\tilde{\tau}_{r}^{1}\wedge\tilde{\tau}_{r}^{2}\leq
2\log^{4}n,\rho=r\Big{)}\\\
&\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\Big{(}\tilde{\tau}_{r}^{1}\leq
2\log^{4}n,\rho=r\Big{)}+\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\Big{(}\tilde{\tau}_{r}^{2}\leq 2\log^{4}n,\rho=r\Big{)}\\\
&\leq\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
abs}\leq
2\log^{4}n\big{)}+\sum_{i=1}^{2\log^{4}n}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
abs}\leq\log^{4}n-i\big{)}\\\
&\leq(\log^{4}n+1)2^{-\frac{\sigma_{n}}{4}}.\end{split}$

For the bound in the second line, the first term follows an analogous
reasoning as in the tree case. To handle the second term, we first apply union
bounds on the first time the random walk $X$ reaches $z_{\kappa}$, and the
result follows from the strong Markov property and the same argument as in the
tree case. Conversely, if $\kappa\leq\frac{1}{2}\sigma_{n}$, then both
$\mathfrak{p}^{\prime}$ and $\mathfrak{p}^{\prime\prime}$ are long paths (of
size at least $\frac{1}{2}\sigma_{n}$). Once again, in order for the random
walks to meet, at least one of them must traverse at least half of one of the
paths $\mathfrak{p}^{\prime}$ or $\mathfrak{p}^{\prime\prime}$. The argument
follows the same lines as in the previous case, and we refrain from spelling
out the details. ∎

######  Proposition 3.7 (Exponential scaling of meeting time starting in
stationarity).

Let $G_{d,n}(\omega)$ be a regular random graph. There exists a sequence of
random variables $\Theta_{d}=(\Theta_{d}^{(n)})_{n\in\mathbb{N}}$ such that

$\sup_{t\geq
0}\left|\frac{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\tau_{\rm
meet}^{\pi\otimes\pi}>t)}{\exp\left(-\frac{2\>\Theta_{d}\>t}{n}\right)}-1\right|\overset{\mathbb{P}}{\longrightarrow}0\>,$
(3.7)

and

$\Theta_{d}^{(n)}\overset{\mathbb{P}}{\longrightarrow}\theta_{d}=\frac{d-2}{d-1}.$

###### Proof.

We show that for the discrete-time version of the process, in which at each
time step one randomly chosen walk performs a jump, we have

$\sup_{t\geq
0}\left|\frac{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}(\tau_{\rm
meet}^{\pi\otimes\pi}>t)}{\left(1-\frac{\>\Theta_{d}}{n}\right)^{t}}-1\right|\overset{\mathbb{P}}{\longrightarrow}0.$
(3.8)

The claim in (3.7) follows by Poissonisation. For the discrete-time process we
can exploit the full power of the FVTL in Theorem 2.2. The proof comes in
several steps.

1. Consider the multi-graph $\Gamma$ with vertex set $V_{\Gamma}=\\{(x,y)\colon\,x,y\in[n],\>x\neq y\\}\cup\\{\Delta\\}$, where $\Delta$ is the merge of the vertices on the diagonal that retains the edges. More precisely,

$((x,y),(v,w))\in E_{\Gamma}\text{ if and only if }\begin{cases}x=v\text{ and
}(y,w)\in E,\\\ y=w\text{ and }(x,v)\in E,\end{cases}$

and

$(\Delta,(v,w))\in E_{\Gamma}\text{ if and only if }(v,w)\in E,$

with each edge adjacent to $\Delta$ having multiplicity $2$. Roughly, $\Gamma$
is such that every vertex except $\Delta$ has degree $2d$, while $\Delta$ has
degree $4m=2dn$. It follows that the sum of the degrees in $\Gamma$ equals
$2m_{\Gamma}=2dn(n-1)+2dn=2dn^{2}$, and that the number of vertices is given
by $N=n^{2}-n+1$. Throughout this proof, let
$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}$
denote the distribution of the simple random walk on $\Gamma$, $P_{\Gamma}$
the associated transition matrix, and $V_{\Gamma}$ the set of vertices. The
stationary distribution for this random walk $\pi_{\Gamma}$ is given by

$\pi_{\Gamma}(\Delta)=\frac{1}{n},$

while, for all $(x,y)$ with $x\neq y$,

$\pi_{\Gamma}(x,y)=\frac{1}{n^{2}}.$

2. Concerning the mixing time in (2.2), it is not hard to show that we can choose $T_{\rm mix}=\log^{2}n$. For completeness, we provide a full proof by adapting the proof of (Cooper et al.,, 2010, Lemma 12) to our asynchronous setting. As shown in Friedman, (2008), the second largest eigenvalue of $P$, denoted by $\lambda_{\star}$, is bounded away from $1$ whp, from which it follows via (Levin and Peres,, 2017, Corollary 12.13) that the same holds for the matrix $P_{\otimes 2}=\frac{1}{2}(P\otimes I+I\otimes P)$. Write $\lambda_{\otimes 2}$ (respectively, $\lambda_{\Gamma}$) to denote the spectral gap of the matrix $P_{\otimes 2}$ (respectively, $P_{\Gamma}$). By (Levin and Peres,, 2017, Theorem 13.10) and with the abbreviation

$\Phi_{\otimes 2}\coloneqq\min_{S\subset V^{2}\>:\>\pi_{\otimes
2}(S)\leq\frac{1}{2}}\frac{\sum_{\boldsymbol{x}\in
S}\pi(\boldsymbol{x})\sum_{\boldsymbol{y}\in S^{c}}P_{\otimes
2}(\boldsymbol{x},\boldsymbol{y})}{\pi_{\otimes 2}(S)}$ (3.9)

for the _conductance_ of the product chain, we know that

$\tfrac{1}{2}\Phi_{\otimes 2}^{2}\leq 1-\lambda_{\otimes 2}\leq 2\Phi_{\otimes
2}.$ (3.10)

Therefore $\Phi_{\otimes 2}$ is bounded away from $0$ whp. By the construction
of $\Gamma$, we must have $\Phi_{\otimes 2}\leq\Phi_{\Gamma}$, where the
latter is the conductance of the Markov chain $P_{\Gamma}$. Indeed, the graph
$\Gamma$ is constructed from $G\times G$ by contracting some vertices and
retaining the edges. Moreover, again by (3.10) to the Markov chain
$P_{\Gamma}$,

${1-\lambda_{\Gamma}}\geq\tfrac{1}{2}\Phi_{\Gamma}^{2}\geq\tfrac{1}{2}\Phi_{\otimes
2}^{2}>0.$ (3.11)

Hence, we deduce that $\lambda_{\Gamma}$ must be bounded away from $1$ whp.
Finally, by (Levin and Peres,, 2017, Theorem 12.4), we conclude that $O(\log
n)$ steps suffice to get (2.2).

3. Thus, Assumptions (1) and (3) in Theorem 2.2 are satisfied whp with $N=n^{2}-n+1$, $Q_{N}=P_{\Gamma}$, $\mu_{N}=\pi_{\Gamma}$. Moreover, choosing $x=\Delta$ we easily check the whp existence of a unique quasi-stationary distribution, thanks to the fact that $d\geq 3$, $G$ is connected, and the two random walks move asynchronously. In order to use the FVTL, we are left to compute the expected number of returns to $\Delta$ before time $T_{\rm mix}\leq\log^{2}n$, starting at $\Delta$. For $t\geq 1$, put

$R_{t}(\Delta)=\sum_{s=0}^{t}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{s}=\Delta\mid
X_{0}=\Delta\big{)}.$

We will show that

$R_{T_{\rm
mix}}(\Delta)\overset{\mathbb{P}}{\longrightarrow}1+\frac{1-\theta_{d}}{\theta_{d}}=\frac{1}{\theta_{d}}=\frac{d-1}{d-2}.$
(3.12)

The term $1$ comes from the fact that the random walk starts at $\Delta$.

4. We start by giving the heuristics of the proof. Call $(x,y)$ the vertex of $\Gamma$ visited at time $1$. By Proposition 2.6(ii), the probability that the edge $e=(x,y)\in E$ is ${\rm LTLE}(\tfrac{1}{5}\log_{d}n\big{)}$ is $1-o(1)$. On this event, the probability that there will be a second visit to $\Delta$ before $T_{\rm mix}$ is upper bounded by $\frac{1}{d-1}$. A simple combination of these arguments yields an upper bound. As for the lower bound, the probability that the random walk on $\Gamma$ starting at $(x,y)$ reaches a vertex $(v,w)$ with ${\rm dist}_{G}(v,w)\geq\sigma_{n}$ before reaching $\Delta$ is $\theta_{d}+o(1)$. Once at $(v,w)$, the probability that the random walk visits $\Delta$ before $T_{\rm mix}$ is $o(1)$. Hence, up to $o(1)$ corrections, $R_{T_{\rm mix}}(\Delta)$ can be estimated by the expectation of a geometric random variable with parameter $\theta_{d}+o(1)$, representing the first excursion of the random walk that hits $(v,w)$ with ${\rm dist}_{G}(v,w)\geq\sigma_{n}$ before returning to $\Delta$. 5. With this heuristics in mind, we are ready to provide the proof of (3.12). We will do so by first assuming that

$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tfrac{1}{5}\log_{d}n\leq\tau_{\Delta}^{+}\leq
T_{\rm mix}\mid X_{0}=\Delta\big{)}\overset{\mathbb{P}}{\longrightarrow}0$
(3.13)

and

$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}\leq\tfrac{1}{5}\log_{d}n\mid
X_{0}=\Delta\big{)}\overset{\mathbb{P}}{\longrightarrow}1-\theta_{d}.$ (3.14)

Write

$\begin{split}R_{T_{\rm mix}}(\Delta)&=1+\sum_{s=1}^{T_{\rm
mix}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{s}=\Delta\mid
X_{0}=\Delta\big{)}\\\ &=1+\sum_{r=1}^{T_{\rm mix}}\sum_{s=r}^{T_{\rm
mix}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{s}=\Delta,\tau_{\Delta}^{+}=r\mid
X_{0}=\Delta\big{)}\\\ &=1+\sum_{r=1}^{T_{\rm mix}}\sum_{s=r}^{T_{\rm
mix}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{s}=\Delta\mid
X_{r}=\Delta\big{)}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}=r\mid
X_{0}=\Delta\big{)}\\\ &=1+\sum_{r=1}^{T_{\rm
mix}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}=r\mid
X_{0}=\Delta\big{)}\sum_{s=0}^{T_{\rm
mix}-r}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{s}=\Delta\mid
X_{0}=\Delta\big{)}\\\ &=1+\sum_{r=1}^{T_{\rm
mix}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}=r\mid
X_{0}=\Delta\big{)}R_{T_{\rm mix}-r}(\Delta).\end{split}$ (3.15)

To establish the upper bound in (3.12), observe that (3.15) yields

$R_{T_{\rm mix}}(\Delta)\leq
1+\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}\leq
T_{\rm mix}\mid X_{0}=\Delta\big{)}R_{T_{\rm mix}}(\Delta),$

which yields

$R_{T_{\rm
mix}}(\Delta)\leq\Big{(}1-\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}\leq
T_{\rm mix}\mid X_{0}=\Delta\big{)}\Big{)}^{-1},$

and the claim follows by combining (3.13) and (3.14).

6. To establish the lower bound in (3.12), observe that (3.15) yields

$\begin{split}R_{T_{\rm mix}}(\Delta)&\geq
1+\sum_{r=1}^{\tfrac{1}{5}\log_{d}n}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}=r\mid
X_{0}=\Delta\big{)}R_{T_{\rm mix}-r}(\Delta)\\\ &\geq
1+\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}\leq\tfrac{1}{5}\log_{d}n\mid
X_{0}=\Delta\big{)}R_{T_{\rm mix}-\tfrac{1}{5}\log_{d}n}(\Delta).\end{split}$

By iterating the estimate above, we obtain

$R_{T_{\rm mix}}(\Delta)\geq\sum_{i=0}^{5T_{\rm
mix}/\log_{d}n}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}\leq\tfrac{1}{5}\log_{d}n\mid
X_{0}=\Delta\big{)}^{i}=\frac{1}{\theta_{d}}-o_{\mathbb{P}}(1),$ (3.16)

where the last equality follows from (3.14). This concludes the verification
of the hypotheses of Theorem 2.2.

To conclude the proof, we still need to verify (3.13) and (3.14). We start
with (3.13). By Proposition 2.6(iii), we have

$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{1}\in\text{LTLE}\big{(}\tfrac{1}{5}\log_{d}n\big{)}\mid
X_{0}=\Delta\big{)}\overset{\mathbb{P}}{\longrightarrow}1.$ (3.17)

Indeed, by construction, the random walk on $\Gamma$ starting at $\Delta$
after a single step visits a $(x,y)\in E$ uniformly at random. Assume that
$X_{1}=(x,y)\in{\rm LTLE}\big{(}\tfrac{1}{5}\log_{d}n\big{)}$, and let
$\tilde{\tau}$ denote the first time at which the process on $\Gamma$ is found
at some $(w,z)$ with ${\rm dist}_{G}(w,z)=\sigma_{n}$. Then, up to time
$\tau_{\Delta}\wedge\tilde{\tau}$, the random walk $(X_{t})_{t\geq 1}$ can be
coupled with a biased random walk on $\mathbb{Z}$ (given by the distance
between the two vertices) that starts from $1$, jumps to the right
(respectively, left) with probability $\tfrac{d-1}{d}$ (respectively,
$\tfrac{1}{d}$). Call this random walk $(W_{t})_{t\geq 0}$, and let $\tau_{j}$
, $j\in\mathbb{Z}$, be its first hitting of $j$. Then a gambler’s ruin
argument yields

$\operatorname{\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}}_{1}\big{(}\tau_{0}\wedge\tau_{\sigma_{n}}\big{)}\leq\frac{d\sigma_{n}}{d-2},$

which implies

$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{1}\big{(}\tau_{0}\wedge\tau_{\sigma_{n}}>\tfrac{1}{5}\log_{d}n-1\big{)}\leq\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{1}\big{(}\tau_{0}\wedge\tau_{\sigma_{n}}>\sigma_{n}^{3}\big{)}\leq\frac{1}{\sigma_{n}}$
(3.18)

for all $n$ sufficiently large. Compute

$\begin{split}&\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}\wedge\tilde{\tau}\leq\tfrac{1}{5}\log_{d}n\mid
X_{0}=\Delta\big{)}\\\
&\geq\sum_{(x,y)\in(V_{\Gamma}\setminus\\{\Delta\\})\cap{\rm
LTLE}\big{(}\tfrac{1}{5}\log_{d}n\big{)}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\Delta}\big{(}X_{1}=(x,y)\big{)}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{(x,y)}\big{(}\tau_{\Delta}^{+}\wedge\tilde{\tau}\leq\tfrac{1}{5}\log_{d}n-1\big{)}\\\
&\overset{\eqref{eq:bound_probability}}{\geq}\Big{(}1-\frac{1}{\sigma_{n}}\Big{)}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{1}\in\text{LTLE}\big{(}\tfrac{1}{5}\log_{d}n\big{)}\mid
X_{0}=\Delta\big{)}.\end{split}$

Note that the last line above converges to 1 in probability as $n\to\infty$
(see (3.17)), which concludes the verification of (3.13).

We are left with proving (3.14). In this case, we can assume once again that
$X_{1}\in\text{LTLE}(\tfrac{1}{5}\log_{d}n)$, which in particular implies
that, up to time $\tfrac{1}{5}\log_{d}n$, the random walk can be perfectly
coupled with a biased random walk on $\mathbb{Z}$ that starts at $1$ and jumps
to the right (respectively, left) with probability $\tfrac{d-1}{d}$
(respectively, $\tfrac{1}{d}$). The claim follows by noting that

$\begin{split}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{+}\leq\tfrac{1}{5}\log_{d}n\mid
X_{0}=\Delta\big{)}&=o_{\mathbb{P}}(1)+\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{1}\big{(}\tau_{0}\leq\tfrac{1}{5}\log_{d}n-1\big{)}\\\
&=o_{\mathbb{P}}(1)+\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{1}\big{(}\tau_{0}<\infty\big{)}=o(1)+\frac{1}{d-1},\end{split}$

which concludes the verification of (3.14). ∎

######  Lemma 3.8 (Tail of meeting time of distant random walks).

Let $G_{d,n}(\omega)$ be a regular random graph and consider two independent
random walks. Then

$\max_{x,y\colon\,{\rm dist}(x,y)\geq\sigma_{n}}\sup_{t\geq
0}\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{x,y}_{\rm
meet}>t\big{)}-\mathrm{e}^{-\frac{2t\theta_{d}}{n}}\Big{|}\overset{\mathbb{P}}{\longrightarrow}0.$
(3.19)

###### Proof.

We need to deduce from Proposition 3.7 an (additive) analogous result when the
two random walks start far away. For that we use Lemma 3.6.

For simplicity we work again in discrete time, so that what we actually need
to show is

$\max_{x,y\colon\,{\rm dist}(x,y)\geq\sigma_{n}}\max_{t\geq
0}\left|\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}(\tau_{\rm
meet}^{x,y}>t)-\Big{(}1-\frac{\theta_{d}}{n}\Big{)}^{t}\right|\overset{\mathbb{P}}{\longrightarrow}0.$
(3.20)

Fix $x$ and $y$ such that ${\rm dist}(x,y)\geq\sigma_{n}$, and let
$\mathcal{E}$ be the event that the two random walks meet before the mixing
time $T_{\rm mix}$. Since $T_{\rm mix}\leq\log^{3}n$, Lemma 3.6 states that
$\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\mathcal{E})\leq\mathrm{e}^{-c_{\ref{c:bound_meeting_time}}\sigma_{n}}$
whp for every pair $(x,y)$ as above. Hence, if $t\leq T_{\rm mix}$, then

$\min_{x,y\colon\,{\rm
dist}(x,y)\geq\sigma_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}>t\big{)}\geq
1-\mathrm{e}^{-c_{\ref{c:bound_meeting_time}}\sigma_{n}}.$ (3.21)

On the other hand, if $t>T_{\rm mix}$, then by definition of $T_{\rm mix}$,

$\max_{(x,y)\in
V_{\Gamma}}|\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X_{t}^{x}=v,Y^{y}_{t}=w\big{)}-\pi_{\Gamma}(v,w)|\leq\frac{1}{n^{6}}.$
(3.22)

Therefore

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}>t\big{)}&=\sum_{(v,w)\in
V_{\Gamma}\setminus\\{\Delta\\}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{(x,y)}>T_{\rm
mix},\,X^{x}_{T_{\rm mix}}=v,\,Y^{y}_{T_{\rm
mix}}=w\big{)}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{(v,w)}_{\Delta}>t-T_{\rm
mix}\big{)}\\\ &\leq\sum_{(v,w)\in
V_{\Gamma}\setminus\\{\Delta\\}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X^{x}_{T_{\rm
mix}}=v,\,Y^{y}_{T_{\rm
mix}}=w\big{)}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{(v,w)}_{\Delta}>t-T_{\rm
mix}\big{)}\\\ &\leq\sum_{(v,w)\in
V_{\Gamma}\setminus\\{\Delta\\}}\pi_{\Gamma}(v,w)\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{(v,w)}_{\Delta}>t-{T_{\rm
mix}}\big{)}+\frac{1}{n^{6}}\\\
&\leq\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{\pi_{\Gamma}}_{\Delta}>t-T_{\rm
mix}\big{)}+\frac{1}{n^{4}}.\end{split}$

On the other hand,

$\begin{split}&\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}>t\big{)}\\\ &=\sum_{(v,w)\in
V_{\Gamma}\setminus\Delta}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\Delta}^{(x,y)}>T_{\rm
mix},\,X^{x}_{T_{\rm mix}}=v,\,Y^{y}_{T_{\rm
mix}}=w\big{)}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{(v,w)}_{\Delta}>t-T_{\rm
mix}\big{)}\\\ &\geq\left(\sum_{(v,w)\in
V_{\Gamma}\setminus\\{\Delta\\}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}X^{x}_{T_{\rm
mix}}=v,\,Y^{y}_{T_{\rm
mix}}=w\big{)}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{(v,w)}_{\Delta}>t-T_{\rm
mix}\big{)}\right)-\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
meet}^{x,y}\leq T_{\rm mix}\big{)}\\\
&\overset{\eqref{eq:mixingtime}}{\geq}\sum_{(v,w)\in
V_{\Gamma}\setminus\\{\Delta\\}}\pi_{\Gamma}(v,w)\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{(v,w)}_{\Delta}>t-T_{\rm
mix}\big{)}-\frac{1}{n^{6}}-\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
meet}^{x,y}\leq T_{\rm mix}\big{)}\\\
&\overset{\eqref{eq:meeting_time_estimate}}{=}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau^{\pi_{\Gamma}}_{\Delta}>t-T_{\rm
mix}\big{)}-\frac{1}{n^{4}}-\mathrm{e}^{-c_{\ref{c:bound_meeting_time}}\sigma_{n}}.\end{split}$

This, when combined with Propostition 3.7, implies the claim because

$\Big{|}\Big{(}1-\frac{\theta_{d}}{n}\Big{)}^{t}-\Big{(}1-\frac{\theta_{d}}{n}\Big{)}^{t-T_{{\rm
mix}}}\Big{|}=\Big{(}1-\frac{\theta_{d}}{n}\Big{)}^{t}\Big{|}1-\Big{(}1-\frac{\theta_{d}}{n}\Big{)}^{-T_{{\rm
mix}}}\Big{|}\leq\mathrm{e}^{-\frac{t\theta_{d}}{n}}\Big{|}1-\Big{(}1-\frac{\theta_{d}}{n}\Big{)}^{-T_{{\rm
mix}}}\Big{|}$

converges to zero as $n\to\infty$, uniformly in $t\geq 0$. ∎

######  Proposition 3.9 (Tail of meeting time of adjacent random walks on a
LTLE).

Let $G_{d,n}(\omega)$ be a regular random graph, let $e=(x,y)$ be in ${\rm
LTLE}\big{(}\tfrac{1}{5}\log_{d}n\big{)}$, and consider two independent random
walks starting from the endvertices of $e$. Then, for all $t_{n}$ such that
$\lim_{n\to\infty}t_{n}=\infty$ and $\lim_{n\to\infty}t_{n}/n=s\geq 0$,

$\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
meet}^{x,y}>t_{n})-\theta_{d}\operatorname{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
###### Proof.

Note that it is enough to assume that $t\geq\sigma_{n}^{3}$, since otherwise
the claim follows from Lemma 3.4. Let $\tau_{\rm far}^{x,y}$ be the first time
at which the two random walks are at distance at least $\sigma_{n}$, and
$\tau_{\rm exit}^{x,y}$ the first time at which one of the two random walks
exits the locally tree-like neighbourhood of radius $\tfrac{1}{5}\log_{d}n$ of
$e$. Put $\tau_{0}^{x,y}=\tau_{\rm meet}^{x,y}\wedge\tau_{\rm
far}^{x,y}\wedge\tau_{\rm exit}^{x,y}$. For simplicity, we start by analysing
the discrete-time process. Up to time $\tau_{0}^{x,y}$, the process can be
coupled to a biased random walk $(W_{t})_{t\geq 0}$ with $W_{0}=1$ and

$p=\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}W_{t+1}-W_{t}=1\big{)}=1-\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}W_{t+1}-W_{t}=-1\big{)}=\frac{d-1}{d}.$

In particular,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}^{\rm
dt}\big{[}\tau_{0}^{x,y}\big{]}\leq\frac{d\sigma_{n}}{d-2},$

and therefore

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau^{x,y}_{0}=\tau^{x,y}_{\rm
exit}\big{)}&\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau^{x,y}_{\rm
exit}\leq\sigma_{n}^{3}\big{)}+\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau^{x,y}_{0}>\sigma_{n}^{3}\big{)}\\\ &\leq
0+\frac{1}{\sigma_{n}^{3}}\frac{d\sigma_{n}}{d-2}=o(1),\end{split}$ (3.23)

where the last term follows from the Markov inequality. Similarly, by a
gambler ruin argument,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\left(\tau^{x,y}_{\rm far}>\sigma_{n}^{3}\right)=o(1),$

and therefore

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
meet}^{x,y}>t_{n}\big{)}$
$\displaystyle=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
meet}^{x,y}>t_{n},\,\tau_{0}^{x,y}=\tau_{\rm
far}^{x,y}\leq\sigma_{n}^{3}\big{)}+o(1).$ (3.24)

The probability in the right-hand side of (3.24) can be written, in the
discrete-time setting, as

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}>t_{n},\,\tau_{0}^{x,y}=\tau_{\rm
far}^{x,y}\leq\sigma_{n}^{3}\big{)}$
$\displaystyle=\sum_{u=0}^{\sigma_{n}^{3}}\sum_{(v,w)\colon\,{\rm
dist}(v,w)>\sigma_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}(\tau_{0}^{x,y}=\tau_{\rm
far}^{x,y}=u,\>(X_{\tau_{0}^{x,y}},Y_{\tau_{0}^{x,y}})=(v,w))\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\tau_{\rm
meet}^{v,w}>t_{n}-u)$
$\displaystyle\sim\sum_{u=0}^{\sigma_{n}^{3}}\sum_{(v,w)\colon\,{\rm
dist}(v,w)>\sigma_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}(\tau_{0}^{x,y}=\tau_{\rm
far}^{x,y}=u,\>(X_{\tau_{0}^{x,y}},Y_{\tau_{0}^{x,y}})=(v,w))\left(1-\frac{\theta_{d}}{n}\right)^{t_{n}-u}$
$\displaystyle=\left(1-\frac{\theta_{d}}{n}\right)^{t_{n}}\sum_{u=0}^{\sigma_{n}^{3}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}(\tau_{0}^{x,y}=\tau_{\rm
far}^{x,y}=u)\left(1-\frac{\theta_{d}}{n}\right)^{-u}$
$\displaystyle\sim\left(1-\frac{\theta_{d}}{n}\right)^{t_{n}}\sum_{u=0}^{\sigma_{n}^{3}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}(\tau_{0}^{x,y}=\tau_{\rm
far}^{x,y}=u)\sim\mathrm{e}^{-s\theta_{d}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}(\tau_{0}^{x,y}=\tau_{\rm
far}^{x,y}\leq\sigma_{n}^{3})\sim\theta_{d}\,\mathrm{e}^{-s\theta_{d}}\qquad\textit{whp}.$

In order to pass to the continuous-time setting, it is enough to realise that,
for all $\varepsilon\in(0,s)$,

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\tau_{\rm
meet}^{x,y}>t_{n}\big{)}$
$\displaystyle=\sum_{u=0}^{\infty}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left({\rm
Poisson}(2t_{n})=u\right)\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}>u\big{)}$
$\displaystyle=\sum_{u=2(s-\varepsilon)n\vee
0}^{2(s+\varepsilon)n}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left({\rm
Poisson}(2sn)=u\right)\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}^{\rm
dt}\big{(}\tau_{\rm meet}^{x,y}>u\big{)}+o_{\mathbb{P}}(1)$
$\displaystyle=\theta_{d}\,\mathrm{e}^{-2s\theta_{d}}+O_{\mathbb{P}}(\varepsilon),$

after which the claim follows by taking the limit $\varepsilon\downarrow 0$. ∎

The next two statements turn the result in Proposition 3.9 into a statement
about the expected density of discordant edges at time $O(n)$ for the voter
model.

######  Corollary 3.10 (Discordant edges at small distances).

Let $G_{d,n}(\omega)$ be a $d$-regular random graph, let $e=(x,y)$ be in ${\rm
LTLE}(\tfrac{1}{5}\log_{d}n)$, and consider the voter model with initial
density $u\in(0,1)$. Then, for all $t_{n}$ such that
$\lim_{n\to\infty}t_{n}=\infty$ and $\lim_{n\to\infty}t_{n}/n=s\in[0,\infty)$,

$\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\big{(}e\in
D_{t_{n}}\big{)}-2u(1-u)\,\theta_{d}\,\mathrm{e}^{-2s\theta_{d}}\Big{|}\overset{\mathbb{P}}{\longrightarrow}0.$

###### Proof.

The claim follows from Proposition 3.9 via duality. ∎

######  Proposition 3.11 (Expected density of discordant edges).

Let $G_{d,n}(\omega)$ be a $d$-regular random graph, and consider the voter
model with initial density $u\in(0,1)$. Then, for all $t_{n}$ such that
$\lim_{n\to\infty}t_{n}/n=s\in[0,\infty)$,

$\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}[\mathcal{D}_{t_{n}}]-2u(1-u)\,\theta_{d}\,\mathrm{e}^{-2s\theta_{d}}\Big{|}\overset{\mathbb{P}}{\longrightarrow}0.$

###### Proof.

The claim follows from Corollary 3.10 and the same argument as in the proof of
Proposition 3.5. ∎

##  4\. Beyond the expectation

In this section we prove Theorem 1.2. We start with a proposition that implies
the first statement of the theorem.

######  Proposition 4.1 (Concentration for worst case initialization).

Consider times $t_{n}$ such that $t_{n}\to\infty$ and $t_{n}/n\to 0$. Then,
for any $\varepsilon>0$,

$\sup_{\xi\in\\{0,1\\}^{V}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(\left|\mathcal{D}_{t_{n}}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}\left[\mathcal{D}_{t_{n}}\right]\right|>\varepsilon\right)\overset{\mathbb{P}}{\longrightarrow}0.$

###### Proof.

Putting $E_{\star}={\rm LTLE}(\tfrac{1}{5}\log_{d}n)\subset E$ and recalling
that $|E_{\star}|=m-o(n)$ _whp_ by Proposition 2.6 (ii), we have

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[|D_{t}|^{2}]$
$\displaystyle=\sum_{e,e^{\prime}\in
E}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(e,e^{\prime}\in
D_{t}\right)=\sum_{e,e^{\prime}\in
E_{\star}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(e,e^{\prime}\in
D_{t}\right)+o(n^{2})$ (4.1) $\displaystyle=\sum_{e\in
E_{\star}}\left[\sum_{e^{\prime}\in E_{\star},\>{\rm
dist(e,e^{\prime})>\sigma_{n}}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(e,e^{\prime}\in
D_{t}\right)+O(d^{\sigma_{n}})\right]+o(n^{2}),$

with $\sigma_{n}$ as in (3.5). Fix
$e=(x,y),e^{\prime}=(x^{\prime},y^{\prime})\in E_{\star}$ such that ${\rm
dist}(e,e^{\prime})>\sigma_{n}$, and consider the event

$\mathcal{E}=\mathcal{E}_{e,e^{\prime}}\coloneqq\left\\{\tau_{\rm
meet}^{x,x^{\prime}}\wedge\tau_{\rm meet}^{x,y^{\prime}}\wedge\tau_{\rm
meet}^{y,x^{\prime}}\wedge\tau_{\rm meet}^{y,y^{\prime}}>t\right\\}.$

We observe that, on the event $\mathcal{E}$, the events $\\{e\in D_{t}\\}$ and
$\\{e^{\prime}\in D_{t}\\}$ are negatively correlated. Indeed, denote by
$\sigma_{e}$ (respectively, $\sigma_{e^{\prime}}$) a realisation of length $t$
of the two independent random walk trajectories starting at $x$ and $y$
(respectively, $x^{\prime}$ and $y^{\prime}$). Let
$\mathcal{H}(\sigma_{e^{\prime}})$ denote the set of possible realisations of
$\sigma_{e^{\prime}}$ that never meet the trajectory $\sigma_{e}$. We then
have

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(e,e^{\prime}\in
D_{t},\>\mathcal{E})&=\sum_{\sigma_{e}\in\\{e\in
D_{t}\\}}\sum_{\sigma_{e^{\prime}}\in\\{e^{\prime}\in
D_{t}\\}\cap\mathcal{H}(\sigma_{e})}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(\sigma_{e})\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(\sigma_{e^{\prime}}\mid\sigma_{e}\right)\\\
&=\sum_{\sigma_{e}\in\\{e\in
D_{t}\\}}\sum_{\sigma_{e^{\prime}}\in\\{e^{\prime}\in
D_{t}\\}\cap\mathcal{H}(\sigma_{e})}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(\sigma_{e})\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(\sigma_{e^{\prime}}\right)\\\
&\leq\sum_{\sigma_{e}\in\\{e\in
D_{t}\\}}\sum_{\sigma_{e^{\prime}}\in\\{e^{\prime}\in
D_{t}\\}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(\sigma_{e})\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(\sigma_{e^{\prime}}\right)=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(e\in
D_{t})\>\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(e^{\prime}\in
D_{t}),\end{split}$ (4.2)

which gives the claimed negative dependence.

Furthermore, by Lemma 3.8 , we have
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\mathcal{E}^{c})=o_{\mathbb{P}}(1)$,
which together with (4.2) guarantees that

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(e,e^{\prime}\in
D_{t}\
\right)\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(e,e^{\prime}\in
D_{t},\mathcal{E}\
\right)+\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(\mathcal{E}^{c})\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(e\in
D_{t})\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(e^{\prime}\in
D_{t}\right)+o_{\mathbb{P}}(1).$

Inserting the latter inequality into (4.1), we get

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}[|D_{t}|^{2}]$
$\displaystyle=\sum_{e\in E_{\star}}\left[\sum_{e^{\prime}\in E_{\star},\>{\rm
dist}(e,e^{\prime})>\sigma_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(e,e^{\prime}\in
D_{t}\right)+O(d^{\sigma_{n}})\right]+o(n^{2})$ $\displaystyle\leq\sum_{e\in
E_{\star}}\left[\sum_{e^{\prime}\in E_{\star},\>{\rm
dist}(e,e^{\prime})>\sigma_{n}}\left[\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}(e\in
D_{t})\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(e^{\prime}\in
D_{t}\right)+o_{\mathbb{P}}(1)\right]+O(d^{\sigma_{n}})\right]+o(n^{2})$
$\displaystyle\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}[|D_{t}|]^{2}+o_{\mathbb{P}}(n^{2})+o(n^{2})=(1+o_{\mathbb{P}}(1))\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
Therefore, by Chebyshev’s inequality,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(\big{|}|D_{t}|-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}|D_{t}|\big{|}>\varepsilon
m\right)\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\xi}\left(\big{|}|D_{t}|-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}|D_{t}|\big{|}>\varepsilon\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}|D_{t}|\right)\leq\frac{{\rm
Var}_{\xi}(|D_{t}|)}{\varepsilon^{2}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\xi}[|D_{t}|]^{2}}=o_{\mathbb{P}}(1).$

∎

We next consider times $t_{n}$ such that $t_{n}/n\to s\in(0,\infty)$ and use
results from Chen et al., (2016). Let

$\gamma_{n}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau_{\textnormal{meet}}^{\pi\otimes\pi}]$
(4.3)

be the expected meeting time of two independent continuous-time simple random
walks with uniformly chosen initial positions. Chen et al., (2016) (see
Theorems 2.1 and 2.2 therein) provide conditions on the underlying sequence of
graphs under which the proportion of type-1 vertices
$(\mathcal{B}^{n}_{\gamma_{n}t})_{t\geq 0}$ converges as a process in the
space of càdlàg paths to the Fisher-Wright diffusion
$(\bar{}\mathcal{B}_{t})_{t\geq 0}$ for $\gamma_{n}$ as in Eq. 4.3. In the
case of $d$-regular random graphs,

$\gamma_{n}=\frac{1}{2}\theta_{d}^{-1}\,n+o_{\mathbb{P}}(1),$ (4.4)

and the requirements in Chen et al., (2016) are easily verified _whp_.

The following lemma is the central estimate that we need in order to establish
convergence of the proportion of discordant edges.

######  Lemma 4.2 (Linking density of discordant edges to density of type-1).

Let $s_{n}$ converge to a finite value. Then

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{D}_{s_{n}\gamma_{n}}-2\theta_{d}\mathcal{B}_{s_{n}\gamma_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}})\Big{|}\Big{]}\overset{\mathbb{P}}{\longrightarrow}0.$

Before proving this lemma, we conclude the proof of Theorem 1.2.

###### Proof of Theorem 1.2 (ii).

Recall that we are assuming that $t_{n}/n\to s$. Consider
$s_{n}=t_{n}/\gamma_{n}$ and note that
$\lim_{n\to\infty}s_{n}=2s\,\theta_{d}$, due to (4.4). Hence Lemma 4.2 yields

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{D}_{t_{n}}-2\theta_{d}\mathcal{B}_{t_{n}}(1-\mathcal{B}_{t_{n}})\Big{|}\Big{]}\overset{\mathbb{P}}{\longrightarrow}0.$
(4.5)

Moreover, since $x\mapsto x(1-x)$ is continuous and so is the Fisher-Wright
diffusion $(\bar{}\mathcal{B}_{t})_{t\geq 0}$, Proposition A.2 implies that

$2\theta_{d}\mathcal{B}_{t_{n}}(1-\mathcal{B}_{t_{n}})\quad\text{ converges in
distribution to }\quad
2\theta_{d}\bar{}\mathcal{B}_{2s\,\theta_{d}}(1-\bar{}\mathcal{B}_{2s\,\theta_{d}}).$

In view of (4.5), the same holds _whp_ for $\mathcal{D}_{t_{n}}$, which
concludes the proof. ∎

To prove Lemma 4.2, we use the following concentration estimate derived in
Chen et al., (2016).

######  Lemma 4.3 (Concentration on arbitrary connected graphs).

Fix a finite connected graph $G$ on $n$ vertices and $m$ edges and let
$(\eta_{t})_{t\geq 0}$ denote the voter model evolving on $G$. For any $0\leq
s\leq t$,

$\sup_{\eta_{0}}\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}[\mathcal{D}_{t}]-2\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}[\tau^{e}>s]\frac{1}{n^{2}}\sum_{x}\eta_{0}(x)\sum_{x}(1-\eta_{0}(x))\Big{|}\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}\in(s,t]\big{]}+4\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}>s\big{]}d_{\rm
TV}(t-s),$

where $\tau^{e}$ denotes the meeting time of two random walks starting from
the two vertices at the end of a uniformly chosen edge of $G$, and $d_{TV}$ is
defined as in (2.3).

The proof of Lemma 4.3 is provided in (Chen et al.,, 2016, Lemma 6.1). Note
that it applies to any deterministic connected graph on which the voter
dynamics takes place.

We will also need the asymptotic estimate

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}\geq
k\log^{2}n\big{]}\overset{\mathbb{P}}{\longrightarrow}\theta_{d},\qquad
k\in\mathbb{N},$ (4.6)

which follows from Proposition 3.9.

###### Proof of Lemma 4.2.

Fix $\delta_{n}=2\log^{2}n$, and split

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{D}_{s_{n}\gamma_{n}}-2\theta_{d}\mathcal{B}_{s_{n}\gamma_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}})\Big{|}\Big{]}\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{D}_{s_{n}\gamma_{n}}-2\theta_{d}\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}})\Big{|}\Big{]}$
(4.7)
$\displaystyle\qquad+2\theta_{d}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}})-\mathcal{B}_{s_{n}\gamma_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}})\Big{|}\Big{]}.$

We will show that each of the expectations in the right-hand side above
converges to zero.

1. Apply the Markov property at time $s_{n}\gamma_{n}-\delta_{n}$, to obtain

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{D}_{s_{n}\gamma_{n}}-2\theta_{d}\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}})\Big{|}\Big{]}\leq\sup_{\eta_{0}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}\Big{[}\Big{|}\mathcal{D}_{\delta_{n}}-2\theta_{d}\mathcal{B}_{0}(1-\mathcal{B}_{0})\Big{|}\Big{]}$
(4.8)
$\displaystyle\leq\sup_{\eta_{0}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}\Big{[}\big{|}\mathcal{D}_{\delta_{n}}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}[\mathcal{D}_{\delta_{n}}]\big{|}\Big{]}+\sup_{\eta_{0}}\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}[\mathcal{D}_{\delta_{n}}]-2\theta_{d}\frac{1}{n^{2}}\sum_{x}\eta_{0}(x)\sum_{x}(1-\eta_{0}(x))\Big{|}.$

The first expectation in the right-hand side of (4.8) converges to zero by
Proposition 4.1 and the fact that
$|\mathcal{D}_{\delta_{n}}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}[\mathcal{D}_{\delta_{n}}]|$
is bounded by one. To control the second expectation in (4.8), apply Lemma 4.3
with $t=\delta_{n}=2\log^{2}n$ and $s=\log^{2}n$, to obtain

$\begin{split}&\sup_{\eta_{0}}\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}[\mathcal{D}_{\delta_{n}}]-2\theta_{d}\frac{1}{n^{2}}\sum_{x}\eta_{0}(x)\sum_{x}(1-\eta_{0}(x))\Big{|}\\\
&\leq\sup_{\eta_{0}}\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{\eta_{0}}[\mathcal{D}_{\delta_{n}}]-2\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}\geq\log^{2}n\big{]}\frac{1}{n^{2}}\sum_{x}\eta_{0}(x)\sum_{x}(1-\eta_{0}(x))\Big{|}+2\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}\geq\log^{2}n\big{]}-\theta_{d}\Big{|}\\\
&\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}\in(\log^{2}n,2\log^{2}n]\big{]}+4\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}>\log^{2}n\big{]}\textnormal{d}_{TV}(\log^{2}n)+2\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
Note that both

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}\in(\log^{2}n,2\log^{2}n]\big{]}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}>2\log^{2}n\big{]}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}>\log^{2}n\big{]}$

and

$\Big{|}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{[}\tau^{e}\geq\log^{2}n\big{]}-\theta_{d}\Big{|}$

converge to zero _whp_ by (4.6), while $d_{\rm TV}(\log^{2}n)$ goes to zero
thanks to Proposition 2.6 (iv). Hence also the second expectation in (4.8)
vanishes, and so we have

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{D}_{t_{n}\gamma_{n}}-2\theta_{d}\mathcal{B}_{t_{n}\gamma_{n}-\delta_{n}}(1-\mathcal{B}_{t_{n}\gamma_{n}-\delta_{n}})\Big{|}\Big{]}\overset{\mathbb{P}}{\longrightarrow}0.$
(4.9)

2. It remains to show that the second term in the right-hand side of Eq. (4.7) vanishes _whp_ , for which we argue by continuity in the proper topology. For an arbitrary $T>0$, let $[0,T]\times\mathcal{D}[0,T]$ denote the product of $[0,T]$ with the càdlàg space $\mathcal{D}[0,T]$ endowed with the $J_{1}$-Skorohod topology. For a given $s>0$ and an arbitrary evaluation function $h\colon\,[0,T]\times\mathcal{D}[0,T]\to\mathbb{R}$ defined via $h(t,\phi)=\phi(t)$, we consider the incremental function $\tilde{h}\colon\,[0,T]^{2}\times\mathcal{D}[0,T]\to\mathbb{R}$ given by

$\tilde{h}(t,u,\phi)=|h(t,\phi)-h(u,\phi)|,$

and note that, by continuity of the modulus function and Lemma A.1, all points
in $[0,T]^{2}\times\mathcal{C}[0,T]$ are continuity points of $\tilde{h}$. In
particular, since $\frac{\delta_{n}}{\gamma_{n}}\to 0$ and with
$s=\lim_{n\to\infty}s_{n}<T$, we have that

$\displaystyle\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}\mathcal{B}_{s_{n}\gamma_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}})-\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}}(1-\mathcal{B}_{s_{n}\gamma_{n}-\delta_{n}})\Big{|}\Big{]}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\Big{|}h\big{(}s_{n},(\mathcal{B}_{u\gamma_{n}}(1-\mathcal{B}_{u\gamma_{n}}))_{u\in[0,T]}\big{)}$
(4.10)
$\displaystyle-h\big{(}s_{n}-\frac{\delta_{n}}{\gamma_{n}},(\mathcal{B}_{u\gamma_{n}}(1-\mathcal{B}_{u\gamma_{n}}))_{u\in[0,T]}\big{)}\Big{|}\Big{]}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\tilde{h}\big{(}s_{n},s_{n}-\frac{\delta_{n}}{\gamma_{n}},(\mathcal{B}_{u\gamma_{n}}(1-\mathcal{B}_{u\gamma_{n}}))_{u\in[0,T]}\big{)}\Big{]}$
$\displaystyle\overset{\mathbb{P}}{\longrightarrow}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}\Big{[}\tilde{h}\big{(}s,s,(\bar{}\mathcal{B}_{u}(1-\bar{}\mathcal{B}_{u}))_{u\in[0,T]}\big{)}\Big{]}=0,$

where the limit is justified by (1.6) and Proposition A.2 .

3. Combine (4.7), (4.9), and (4.10), to conclude the proof. ∎

##  5\. Uniform concentration

In this section we prove Theorem 1.3, i.e., we sharpen the result in Theorem
1.2 _(i)_ to a uniform bound over sublinear times up to the scale
$n^{1-o(1)}$. Note that, up to a union bound on the set of jump times for the
process $\mathcal{D}_{t}^{n}$, the proof amounts to showing the following.

######  Proposition 5.1 (Strengthening of the pointwise concentration).

Consider the voter model with initial density $u\in(0,1)$ on a regular random
graph $G_{d,n}(\omega)$. For any fixed $\varepsilon,\delta,a>0$,

$\mathds{1}\left\\{\max_{t\leq
n^{1-\varepsilon}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}\left(\left|\mathcal{D}_{t}-\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}_{u}[\mathcal{D}_{t}]\right|>\delta\right)\leq
n^{-a}\right\\}\overset{\mathbb{P}}{\longrightarrow}1.$

###### Proof.

The proof comes in several steps. To ease the reading, we drop the subindex
$u$ from the notation of the voter measure
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{u}$
and abbreviate
$p_{t}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\mathcal{D}_{t}]$.

1. Fix

$t\leq n^{1-\varepsilon},\qquad K_{n}=\log^{2}n,$

and write $A$ to denote a collection of $K$ edges of the graph sampled
uniformly at random, independently of the voter dynamics. Call

$\mathcal{D}^{A}_{t}\coloneqq\frac{1}{K_{n}}\sum_{e\in A}\mathds{1}_{\\{e\in
D_{t}\\}}$

the fraction of edges in the random set $A$ that are discordant at time $t$.
By the triangle inequality, we have

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\left|\mathcal{D}_{t}-p_{t}\right|>\delta\right)\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\left|\mathcal{D}_{t}-\mathcal{D}_{t}^{A}\right|>\tfrac{1}{2}\delta\right)+\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\left|\mathcal{D}_{t}^{A}-p_{t}\right|>\tfrac{1}{2}\delta\right).$
(5.1)

Note that, given $\mathcal{D}_{t}=q$, the quantity $\mathcal{D}_{t}^{A}$ is
distributed as $Z/K_{n}$, where $Z\sim{\rm Bin}(K_{n},q)$. Therefore,
conditioning on $\mathcal{D}_{t}=q\in[0,1]$, we can bound the first term on
the right-hand side of (5.1) by means of the Chernoff bound

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\left|\mathcal{D}_{t}-\mathcal{D}_{t}^{A}\right|>\tfrac{1}{2}\delta\>\bigg{\rvert}\>\frac{|D_{t}|}{m}=q\right)\leq
2\exp\left(-\frac{\delta^{2}}{12q}K_{n}\right)\leq
2\exp\left(-\frac{\delta^{2}}{12}K_{n}\right).$ (5.2)

Since the bound in (5.2) is uniform over $q\in[0,1]$ and $t\leq
n^{1-\varepsilon}$, we conclude that, for every $a>0$, $\mathbb{P}$-a.s.,

$\max_{t\leq
n^{1-\varepsilon}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\left|\mathcal{D}_{t}-\mathcal{D}_{t}^{A}\right|>\tfrac{1}{2}\delta\right)\leq
2\exp\left(-\frac{\delta^{2}}{12}K_{n}\right)\leq n^{-a},$

for all $n$ sufficiently large.

2. We next show that a similar bound holds for the second term on the right-hand side of (5.1). The latter will be proved by means of duality. Consider a system of $n$ independent random walks starting from the different vertices of $G$ and evolving independently. We consider a (multi)sub-set of $2K_{n}$ random walks starting at the extremes of the edges in the random set $A$. Note that these are distributed at time zero as $\otimes_{K_{n}}\nu$, where $\nu$ is the probability distribution on $[n]^{2}$ defined as

$\nu(x,y)=\pi(x)\frac{1}{d}\mathds{1}_{x\sim y},\qquad(x,y)\in[n]^{2}.$

Moreover, since $\pi\equiv\frac{1}{n}$, the two marginal distributions of
$\nu$ coincide with the stationary distribution, i.e., for every $x\in[n]$,

$\sum_{z\in[n]}\nu(x,z)=\sum_{z\in[n]}\nu(z,x)=\frac{1}{n}.$

Observe that

$p_{t}=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\mathcal{D}_{t}]=\frac{1}{m}\sum_{e\in
E}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(e\in
D_{t})=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\nu}(e\in
D_{t}).$ (5.3)

In order to simplify the notation, when considering a system of $2K$
independent random walks starting at $\otimes_{K_{n}}\nu$, for each of the
$K_{n}$ random edges $A=\\{e_{1},\dots,e_{K_{n}}\\}$, we label the extremes as
$e_{j}^{-}$ and $e_{j}^{+}$, for all $j\in\\{1,\dots,K_{n}\\}$. For $i,j\leq
K_{n}$, define the quantities

$\tau^{e_{i},e_{j}}\coloneqq\tau_{\rm
meet}^{e_{i}^{-},e_{j}^{-}}\wedge\tau_{\rm
meet}^{e_{i}^{+},e_{j}^{-}}\wedge\tau_{\rm
meet}^{e_{i}^{-},e_{j}^{+}}\wedge\tau_{\rm meet}^{e_{i}^{+},e_{j}^{+}}.$ (5.4)

When $\tau^{e_{i},e_{j}}\leq t$ we say that _the edges $i$ and $j$ interact
before $t$_. We say that $\tau^{e_{i},e_{j}}=0$ when
$\\{e_{i}^{-},e_{i}^{+}\\}\cap\\{e_{j}^{-},e_{j}^{+}\\}\neq\emptyset$. Note
that, for all $i,j\leq K_{n}$ and $t\geq 0$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\otimes_{K_{n}}\nu}(\tau^{e_{i},e_{j}}\leq
t)=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\nu\otimes\nu}(\tau^{e_{1},e_{2}}\leq
t)\leq
4\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\pi\otimes\pi}(\tau_{\rm
meet}^{x,y}\leq t).$ (5.5)

Indeed, the inequality in (5.5) follows from the definition of $\nu$ and a
union bound.

We next argue that for all $t=o(n)$ the probability on the right-hand side of
Eq. 5.5 can be bounded above whp by

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\pi\otimes\pi}(\tau_{\rm
meet}^{x,y}\leq t)=O\left(\frac{t}{n}\right).$ (5.6)

Let us start by pointing out that the FVTL is not enough to deduce (5.6).
Indeed, the FVTL is particularly suited to have sharp estimates of the right
tail of the hitting time of a set on time scales that are _at least_ as big as
the mean hitting time. For this reason, we will exploit a result in Aldous and
Brown, (1992) that in a sense complements the FVTL on short time scales (see
also (Hermon et al.,, 2021, Lemma 2.11)).

######  Lemma 5.2.

For an irreducible and reversible continuous-time Markov chain with stationary
distribution $\mu$ and any subset of states $A$,

$\left|\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\tau^{\mu}_{A}\leq
t)-\frac{t}{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\mu}_{A}]}\right|\leq\left(\frac{t}{\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\mu}_{A}]}\right)^{2}+\frac{1}{\lambda_{\star}\>\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\mu}_{A}]},\qquad
0\leq
t\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\mu}_{A}],$
(5.7)

where $\tau_{A}^{\mu}$ is the hitting time of the set $A$ when starting with
distribution $\mu$, and $\lambda_{\star}$ denotes the minimal non-trivial
eigenvalue of the infinitesimal generator of the process.

In our setting we can think of the Markov chain as the simple random walk on
$G\otimes G$ and of $A$ as the diagonal, so that $\mu=\pi\otimes\pi$,
$\lambda_{\star}\in(0,1)$ and
$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\mu}_{A}]=\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\pi\otimes\pi}_{\Delta}]=\Theta(n)$,
where the latter follows by Proposition 3.7. Note that, as soon as $t/n\to 0$,
we have that the term on the right-hand side of (5.7) is $O(t/n)$, as for
$t/\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}E}}[\tau^{\mu}_{A}]$,
so that (5.6) immediately follows.

The following lemma states that it is unlikely to have within $A$ a density of
edges interacting before time $t$.

######  Lemma 5.3.

Consider a system of $n$ independent random walks, each starting from a
different vertex of a regular random graph $G_{d,n}(\omega)$. Select a
sub(multi)set $A$ of $E$ of size $2K_{n}$ with joint distribution
$\otimes_{K_{n}}\nu$. Fix $\varepsilon,\gamma>0$, $t\leq n^{1-\varepsilon}$
and $K_{n}=\log^{2}n$. Let

$\mathcal{E}_{t,\gamma}:=\left\\{\exists I\subset A\text{ s.t. }\max_{e\in
I}\min_{f\in A\setminus\\{e\\}}\tau^{e,f}\leq t,\text{ and }|I|\geq\gamma
K_{n}\right\\},$

where $\tau^{e,f}$ is defined as in (5.4). Then, for all $a>0$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\otimes_{K_{n}}\nu}\left(\mathcal{E}_{t,\gamma}\right)\leq
n^{-a}\quad\textit{whp}.$

Before proving Lemma 5.3, we show how the latter can be exploited to conclude
the proof of Proposition 5.1.

3. To conclude the proof of Proposition 5.1, we argue as follows. Let

$\mathcal{H}_{t}=\\{|\mathcal{D}^{A}_{t}-p_{t}|>\delta\\}$ (5.8)

be the event of interest. Consider a system of $2K_{n}$ independent random
walks starting at the extremes of the vertices in $A$, and let these evolve up
to time $t$. Let $I\subset K_{n}$ denote the set of edges in $A$ interacting
within time $t$ with other vertices of $A$. Consider the event
$\mathcal{E}_{t}$ in Lemma 5.3 for which we know that, for every constants
$a,\gamma>0$, whp

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\mathcal{E}_{t,\gamma})\leq
n^{-a}.$

Therefore

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\mathcal{H}_{t}\right)\leq\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\mathcal{H}_{t}\cap\mathcal{E}^{c}_{t,\gamma})+n^{-a}.$

In order to conclude the lemma, it suffices to bound the probability on the
right-hand side of the above display.

4. In order to get the desired bound we next show negative correlation for the discordancy of a collection of edges, in the spirit of the proof of Proposition 4.1.

######  Lemma 5.4 (Negative correlation under no-meeting events).

Consider a sub(multi)set of edges $A_{k}=\\{e_{1},\dots,e_{k}\\}$ sampled
according to $\otimes_{k}\nu$, and let $\mathcal{G}_{t,k}$ be the event in
which the $2k$ independent random walks starting at the extremes of the $k$
edges never meet before time $t$. Then, for all $j\in\\{0,1,2,\dots,k\\}$,

$\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\otimes_{k}\nu}\left(\text{Exactly
$j$ of the $k$ edges are discordant at time
$t$},\>\mathcal{G}_{t,k}\right)\leq\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left({\rm
Bin}(k,p_{t})=j\right).$

###### Proof.

For $e=(x,y)\in A_{k}$, call $\sigma_{e}$ a realisation of length $t$ of the
two independent trajectories starting at $x$ and $y$. For $2\leq j\leq k$,
call $\mathcal{H}(\sigma_{1},\dots,\sigma_{j-1})$ the set of the possible
realisations of $\sigma_{j}$ that never meet the $2(j-1)$ trajectories
$\sigma_{1},\dots,\sigma_{j-1}$. Observe that

$\begin{split}&\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\otimes_{k}\nu}(e_{i}\in
D_{t},\forall i\leq j,\>\>e_{i}\not\in D_{t},\forall
i>j,\>\mathcal{G}_{t,k})\\\ &=\sum_{\sigma_{1}\in\\{e_{1}\in
D_{t}\\}}\sum_{\sigma_{2}\in\\{e_{2}\in
D_{t}\\}\cap\mathcal{H}(\sigma_{1})}\cdots\sum_{\sigma_{k}\in\\{e_{k}\not\in
D_{t}\\}\cap\mathcal{H}(\sigma_{1},\dots,\sigma_{k-1})}\prod_{j=1}^{k}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\sigma_{i}\mid\cap_{j<i}\sigma_{j}\right)\\\
&=\sum_{\sigma_{1}\in\\{e_{1}\in D_{t}\\}}\sum_{\sigma_{2}\in\\{e_{2}\in
D_{t}\\}\cap\mathcal{H}(\sigma_{1})}\cdots\sum_{\sigma_{k}\in\\{e_{k}\not\in
D_{t}\\}\cap\mathcal{H}(\sigma_{1},\dots,\sigma_{k-1})}\prod_{j=1}^{k}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\sigma_{i}\right)\\\
&\leq\sum_{\sigma_{1}\in\\{e_{1}\in D_{t}\\}}\sum_{\sigma_{2}\in\\{e_{2}\in
D_{t}\\}}\cdots\sum_{\sigma_{k}\in\\{e_{k}\not\in
D_{t}\\}}\prod_{j=1}^{k}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\left(\sigma_{i}\right)\\\
&=\prod_{i=1}^{j}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\otimes_{k}\nu}(e_{i}\in
D_{t})\prod_{i=j+1}^{k}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}_{\otimes_{k}\nu}(e_{i}\not\in
D_{t})\\\ &=\left(p_{t}\right)^{j}\left(1-p_{t}\right)^{k-j},\end{split}$

where in the last equality we use the identity in (5.3). By the product form
of $\otimes_{k}\nu$ the result immediately follows. ∎

5. Recall (5.8) and that $I$ is the set of edges that are involved in some interaction before time $t$. Under $\mathcal{E}^{c}_{t,\gamma}$, we have $|I|\leq\gamma K_{n}$. Therefore

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\mathcal{H}_{t}\cap\mathcal{E}^{c}_{t,\gamma}\big{)}\leq\sum_{w=0}^{\gamma
K_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\Big{(}\mathcal{H}_{t};\>|I|=w\Big{)}=\sum_{w=0}^{\gamma
K_{n}}\sum_{B\subset
A\colon\,|B|=w}\frac{1}{\binom{K_{n}}{w}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\Big{(}\mathcal{H}_{t};\>I=B\Big{)}.\end{split}$

Setting $k(w)=K_{n}-w$, exchangeability implies

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\mathcal{H}_{t}\cap\mathcal{E}^{c}_{t,\gamma}\big{)}&\leq\sum_{w=0}^{\gamma
K_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\Big{(}\mathcal{H}_{t};A\setminus
I={e_{1},\dots,e_{k(w)}}\Big{)}.\end{split}$

Observe that the event $\\{A\setminus I={e_{1},\dots,e_{k(w)}}\\}$ implies
that the first $k(w)$ edges do not interact with any edge in $A$ _and_ that
each of the last $w$ edges has at least one interaction. This is clearly
contained in the event $\mathcal{G}_{t,k(w)}=\\{\min_{i,j\leq
k(w)}\tau^{e_{i},e_{j}}>t\\}$ introduced in Lemma 5.4. Hence

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\mathcal{H}_{t}\cap\mathcal{E}^{c}_{t,\gamma}\big{)}&\leq\sum_{w=0}^{\gamma
K_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\Big{(}\mathcal{H}_{t}\cap\mathcal{G}_{t,k(w)}\Big{)}.\end{split}$

Observe that, under the event $\mathcal{H}_{t}\cap\mathcal{G}_{t,k(w)}$,

$\displaystyle\delta K_{n}<\Big{|}\sum_{e\in A}\mathds{1}_{\\{e\in
D_{t}\\}}-p_{t}K_{n}\Big{|}$
$\displaystyle\leq\Big{|}\sum_{i=1}^{K_{n}-w}\mathds{1}_{\\{e_{i}\in
D_{t}\\}}-p_{t}|K_{n}-w|\Big{|}+w+p_{t}w$
$\displaystyle\leq\Big{|}\sum_{i=1}^{K_{n}-w}\mathds{1}_{\\{e_{i}\in
D_{t}\\}}-p_{t}|K_{n}-w|\Big{|}+2\gamma K_{n},$

which implies, with

$\mathcal{R}_{t,k(w)}:=\left\\{\Big{|}\sum_{i=1}^{k(w)}\mathds{1}_{\\{e_{i}\in
D_{t}\\}}-p_{t}k(w)\Big{|}>(\delta-2\gamma)k(w)\right\\},$

that

$\mathcal{R}_{t,k(w)}\cap\mathcal{G}_{t,k(w)}\supset\mathcal{H}_{t}\cap\mathcal{G}_{t,k(w)}.$

It follows that

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\mathcal{H}_{t}\cap\mathcal{E}^{c}_{t,\gamma}\big{)}&\leq\sum_{w=0}^{\gamma
K_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\Big{(}\mathcal{H}_{t}\cap\mathcal{G}_{t,k(w)}\Big{)}\leq\sum_{w=0}^{\gamma
K_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\Big{(}\mathcal{G}_{t,k(w)}\cap\mathcal{R}_{t,k(w)}\Big{)},\end{split}$
(5.9)

from which, thanks to Lemma 5.4, for every $a>0$ whp,

$\begin{split}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\mathcal{H}_{t}\cap\mathcal{E}^{c}_{t,\gamma}\big{)}&\leq\sum_{w=0}^{\gamma
K_{n}}\mathbf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}\big{(}\mathcal{G}_{t,k(w)}\cap\mathcal{R}_{t,k(w)}\big{)}\\\
&\leq\sum_{w=0}^{\gamma
K_{n}}\mathsf{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}P}}(\big{|}{\rm
Bin}(K_{n}-w,p_{t})-p_{t}|K_{n}-w|\big{|}>(\delta-2\gamma)(K_{n}-w))\leq
n^{-a}.\end{split}$

∎

###### Proof of Lemma 5.3.

The proof comes in several steps. For simplicity, we suppress the dependence
on $\gamma$ from the notation.

1. For a vertex $x\in[n]$, we call $\mathcal{P}_{x}$ the subset of times $[0,t]$ in which the random walk starting at $x$ moves. Put