theorem[definition]Theorem proposition[definition]Proposition

# Traces left by random walks on large random graphs: local limits

Steffen Dereich

> Abstract: In this article, we develop a theory for understanding the traces
> left by a random walk in the vicinity of a randomly chosen reference vertex.
> The analysis is related to interlacements but goes beyond previous research
> by showing weak limit theorems for the vicinity around the reference vertex
> together with the path segments of the random walk in this vicinity. Roughly
> speaking, our limit theorem requires appropriate mixing properties for the
> random walk together with a stronger variant of Benjamini-Schramm
> convergence for the underlying graph model. If these assumptions are
> satisfied, the limiting object can be explicitly given in terms of the
> Benjamini-Schramm limit of the graph model.

_MSc Classification:_ Primary 05C81 Secondary 05C82, 60C05, 90B15.

_Keywords:_ Random walk on random graph, Benjamini-Schramm convergence, local
convergence, configuration model, interlacements

###### Contents

  1. 1 Introduction
    1. 1.1 The setup
    2. 1.2 The visiting counting measure
    3. 1.3 The main result
    4. 1.4 Exploration convergence
  2. 2 Markov process estimates
  3. 3 Proof of the main result
  4. 4 Vacant set percolation
  5. A Exploration convergence for the configuration model

##  1\. Introduction

In this article, we analyse reversible random walks on large random or
deterministic finite, rooted graphs. The aim is to understand the traces left
by the random walk in the neighbourhood of the root, where typically the root
vertex is a uniformly chosen vertex of the underlying graph. In our analysis,
we assume a strengthened version of Benjamini-Schramm convergence [BS01], see
also [AS04], and we impose an assumption on the mixing times of the random
walks.

Local convergence techniques are the main tool for understanding the
asymptotic behaviour of large random graphs. For instance, the relative size
of the largest cluster typically converges to the probability of the limitting
graph (appearing as local limit) being infinite, see [ER61] for the Erdős-
Rényi model and [MR98] and [JL09] for results concerning random graphs with
fixed degree sequence (also known as configuration model). Similar results
hold when applying percolation on the graphs. The theory is nowadays well
established and it is the topic of several monographs, see [AS00, JLuR00,
Dur07, vdH17].

More recently, [vdH21] showed that the relationship between the relative size
of the largest component and the local limit becomes more transparent when
replacing local convergence by a stronger type of convergence that is coined
_local convergence in probability_ in the article. We face a similar problem
in this article since the quantities that we need to control in the graph are
not continuous in the topology of local convergence. A remedy for this will be
a stronger type of convergence.

Since we consider a random walk on the largest component the respective
percolation problem is _vacant set percolation_ , where one removes all sites
seen by a random walk and then asks whether a large component remains. As
observed by Sznitman in [Szn10, SS10] so called interlacements are central
towards the understanding of such problems.

When considering vacant set percolation on the configuration model one obtains
analogies of the results known for classical percolation, where the relative
size of the largest component for the vacant set equals the probability that
in the limiting random rooted graph the root is in an infinite component after
removal of all the sites seen by an interlacement, see [vTW11, vT13, vH22] for
results concerning the configuration model. We stress that from a technical
point of view the analysis of vacant set percolation often make strong use of
particularities of the configuration model as established in [JL09].

Our primary focus does not lie on percolation (although we will explain how
one can extend the approach taken in [vdH21] to vacant set percolation).
Instead we record information on the behaviour of the random walk around a
possibly randomly picked root. We take the role of an observer placed in the
root that tracks the movement of the random walk once it comes into a certain
distance to the observer for a certain amount of time. We prove limit theorems
in total variation distance for the traces seen by the observer. From a
statistical point of view the distribution of the limiting object can be used
as a prior distribution for filtering applications. An easy example for a
statistic that then will converge in distribution is a function of the time
spent in the vertices around the root. Significantly more elaborate statistics
are included.

From a mathematical point of view the problem is that incoming new paths may
come from various directions and the probabilities governing this process are
_not_ local quantities. To cope with this we demand to have control about the
goodness of the local approximation (of the graph) which has to increase
sufficiently fast as the size of the graph tends to infinity. We formalise the
meaning of the latter and we will relate this to the mixing times of the
random walks. Roughly speaking, one needs to be able to couple an exploration
of the graph along the random walk started in the root for at least the mixing
time. The analysis relies on new estimates for the total variation distance of
certain entrance locations and times to an idealised decoupled random
variable. The estimates are in spirit similar to the ones derived in [AB92],
but unknown to the best of our knowledge.

###  1.1. The setup

We consider random walk in random environment, where the environment is given
in terms of a connected, undirected graph $G$ with vertex- and edge-weights.
For technical reasons we also allow multigraphs. To be formally precise we let
$\mathcal{V}$ and $\mathcal{E}$ be disjoint, countable, totally ordered111The
ordering allows us to later define particular operations on the graphs. The
particular choice of the ordering has no impact on the results of the article.
sets and denote by $\partial$ a cemetery state that is neither in
$\mathcal{V}$ nor $\mathcal{E}$. We endow $\mathcal{V}$ and $\mathcal{E}$ with
the discrete topology and conceive $\mathcal{V}\cup\\{\partial\\}$ and
$\mathcal{E}\cup\\{\partial\\}$ as one-point compactifications of the latter
sets. We will use $\mathcal{V}$ and $\mathcal{E}$ for the labels of the
vertices and edges, respectively. Formally a weighted _multigraph_ (briefly
_$\mathbb{G}$ -graph_) is a tuple $G=(V,E,\psi,\alpha,\beta)$ consisting of

  1. (i)

a non-empty set $V\subset\mathcal{V}$, the set of _vertices_ , and
$E\subset\mathcal{E}$, the set of _edges_ ,

  2. (ii)

a mapping $\psi$ that maps every $e\in E$ to an unordered $V$-valued pair

$\psi(e)=\langle e^{\prime},e^{\prime\prime}\rangle,$

such that every vertex $v$ appears in at most finitely many pairs $\psi(e)$
($e\in E$),

  3. (iii)

a mapping $\alpha:V\to(0,\infty)$, the _vertex-weights_ , and

  4. (iv)

a mapping $\beta:E\to(0,\infty)$, the _edge-weights_ $\beta$.

We denote by $\mathbb{G}$ the set of all such graphs. Formally, a _graph
isomorphism_ taking a graph $G$ to a graph $\bar{G}$ is a mapping
$\varphi:V\cup E\to\bar{V}\cup\bar{E}$ such that $\varphi|_{V}:V\to\bar{V}$
and $\varphi|_{E}:E\to\bar{E}$ are one-to-one and for all $v\in V$ and $e\in
E$

$\bar{\alpha}_{\varphi(v)}=\alpha_{v},\,\bar{\beta}_{\varphi(e)}=\beta_{e}\text{
\ and \
}\bar{\psi}(\varphi(e))=\langle\varphi(e^{\prime}),\varphi(e^{\prime\prime})\rangle.$

A rooted graph is a graph $G\in\mathbb{G}$ together with a designated vertex
$o\in V$ and we briefly write for the graph $G$ with root $o$, $G^{o}$. We
denote by $\mathbb{G}^{\mathrm{root}}$ the set of rooted multigraphs and,
additionally, write $\mathbb{G}^{\mathrm{finite}}$
($\mathbb{G}^{\mathrm{finite,\,root}}$) for the finite (rooted)
$\mathbb{G}$-graphs.

A _graph isomorphism_ $\varphi$ between two rooted graphs $G^{o}$ and
$\bar{G}^{\bar{o}}$ is a graph isomorphism that takes $G$ to $\bar{G}$ and
additionally satisfies $\bar{o}=\varphi(o)$. We call two rooted or unrooted
graphs _equivalent_ if there is a graph isomorphism taking one to the other.
The concept agrees with the one used in [vdH23] up to the additional weights
and the fact that our graphs have explicit labels (from $\mathcal{V}$). Both
will be needed to formally introduce the respective random walks.

A _generalised multigraph_ is a tuple $G=(V,E,\psi,\alpha,\beta)$ where
condition (ii) above is replaced by

  1. (ii’)

a mapping $\Psi$ that maps every $e\in E$ to an unordered
$V\cup\\{\partial\\}$-valued pair

$\psi(e)=\langle
e^{\prime},e^{\prime\prime}\rangle\not=\langle\partial,\partial\rangle,$

such that every vertex $v$ appears in at most finitely many pairs $\psi(e)$
($e\in E$)

and we write $\bar{\mathbb{G}}$ for the respective set of graphs. In
generalised graphs In analogy to above, we write
$\bar{\mathbb{G}}^{\mathrm{finite,\,root}}$ for the generalised graphs with
designated root.

We let $\overline{W}_{+}$ denote the space of all paths
$w:[0,\infty)\to\mathcal{V}\cup\\{\partial\\}$ for which there exists
$t^{\partial}\in(0,\infty]$ such that for all $t\in[0,\infty)$

$t<t^{\partial}\ \Leftrightarrow\ w_{t}\in\mathcal{V}.$

We associate a graph $G\in\mathbb{G}$ with the continuous time Markov process
family $(P^{x}_{G}:x\in V)$ (with all paths lying in $W_{+}$) with generator
$L=L^{G}=(L^{G}_{x,y})_{x,y\in V}$ given by

$\displaystyle\begin{cases}L_{x,y}^{G}=\sum_{e:\langle
e^{\prime},e^{\prime\prime}\rangle=\langle
x,y\rangle}\beta_{e}/\alpha_{x},&\text{ for }x\neq y,\\\
L^{G}_{x,x}=-\sum_{y\not=x}L^{G}_{x,y}=:-L^{G}_{x},&\text{ for }x\in
V.\end{cases}$ (1)

The respective Markov process will be called _random walk associated with
$G$_. Note that for every distribution $\mu$, a $P^{\mu}_{G}$-Markov process
can be generated iteratively as follows: let $X_{0}$ be a $\mu$-distributed
random variable and then iteratively repeat the following

  * (i)

stay in the current state, say $v\in V$, for an
$\mathrm{Exp}(L_{v}^{G})$-distributed amount of time and

  * (ii)

then choose an edge $e\in\\{\langle
e^{\prime},e^{\prime\prime}\rangle:v\in\\{e^{\prime},e^{\prime\prime}\\}\\}$
with probability proportionally to $\beta_{e}$ and change the current state
along the edge $e$ (meaning that the new state is just the endpoint of $e$
that is not equal to $v$).

We denote by $S_{1},\dots$ the time points at which transitions according to
(ii) are carried out and set $X_{t}=\partial$ for all
$t\geq\sup_{n\in\mathbb{N}}S_{n}$. We denote by $(X_{t})_{t\geq 0}$ the
canonical process on the Markov family $(P^{v}:v\in V)$. In view of the above
construction we mention that, in the case that the $L_{G}$-Markov process has
multiple edges or loops, the edges along which transitions occur cannot be
recovered by the states of the Markov process $(X_{t})_{t\geq 0}$ itself and
we suppose that in the background there is always a construction as above and
we can speak about the first, second, .. transition and assign each transition
to a unique edge of the multigraph as above.

We note that by construction the Markov-process is $\alpha$-reversible. If the
graph is connected and if $\alpha(V)=\sum_{v\in V}\alpha_{v}$ is finite, then
the Markov process has as unique invariant distribution

$\pi=\pi^{G}=\mbox{$\frac{1}{\alpha(V)}$}\alpha.$

In this case, we denote for $\tau\geq 0$

$d_{G}(\tau)=\sup_{v\in
V}\,d_{\mathrm{TV}}(P_{G}^{v}(X_{t}\in\,\cdot\,),\pi^{G}).$

###  1.2. The visiting counting measure

Let $G\in\mathbb{G}$. Now we introduce the central object that records
information about the visits to a certain region of the graph. Its definition
relies on three parameters: the _entrance region_ $B\subset V$, the
_observation time_ $\tau>0$ and the _scaling factor_ $a>0$. For a given choice
of parameters a trajectory $X=(X_{t})_{t\geq 0}\in\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{+}$ (that later will be
a random walk on the random environment $G$) is mapped to a counting measure
on $\operatorname{\mathbb{S}}:=[0,\infty)\times W_{+}$, where $W_{+}$ denotes
the space of _transient paths_ , i.e.,

$\displaystyle W_{+}$ $\displaystyle=\bigl{\\{}(w_{t})_{t\geq 0}\in\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern 1.5mu_{+}:\forall
x\in\mathcal{V}\text{ \ the set }\\{t\in[0,\infty):w_{t}=x\\}\text{ is
bounded}\bigr{\\}}$ $\displaystyle=\bigl{\\{}(w_{t})_{t\geq 0}\in\mkern
1.5mu\overline{\mkern-1.5muW\mkern-1.5mu}\mkern
1.5mu_{+}:\lim_{t\to\infty}w_{t}=\partial\bigr{\\}}.$

We set

$T_{1}=\inf\\{t\geq 0:X_{t}\in B\\}$

and

$T_{k}=\inf\\{t>T_{k-1}+\tau:X_{t}\in B\\},\text{ \ for \ }k=2,3,\dots$

and call the sequence $(T_{k}:k\in\ N)$ the sequence of _$(B,\tau)$ -entrance
times_ of $X$. Further we denote for every $k\in\mathbb{N}$ with
$T_{k}<\infty$ by $(Y_{k}(t))_{t\geq 0}$ the $k$th _$(B,\tau)$ -visit_ of $X$
given by

$Y_{k}(t)=\begin{cases}X_{T_{k}+t},&\text{ if }t<\tau,\\\ \partial,&\text{
else.}\end{cases}$

For completeness we set for $k\in\mathbb{N}$ with $T_{k}=\infty$,
$Y_{k}\equiv\partial$. Finally, we define the _$(B,\tau,a)$ -visiting measure_
to be the counting measure on $\operatorname{\mathbb{S}}$ given by

$\Xi=\sum_{\begin{subarray}{c}k\in\mathbb{N}:\\\
T_{k}<\infty\end{subarray}}\delta_{T_{k}/a,Y_{k}}.$

Roughly speaking, a new (macroscopic) visit to $B$ is initiated when the path
hits $B$ again after time $\tau$ has passed since the last visit and the
$k$-th visit is just the time changed trajectory of $X$ in the time interval
$[T_{k},T_{k}+\tau]$. Note that the previous definitions make perfect sense
when the set $B$ and the graph $G$ are random.

###  1.3. The main result

We will use the concept of exploration convergence for a sequence of random
$\mathbb{G}^{\mathrm{root}}$-graphs $(G_{n}^{o_{n}}:n\in\mathbb{N})$ as
introduced in Section 1.4 below. Intuitively, a sequence of random
$\mathbb{G}^{\mathrm{root}}$-graphs $(G_{n}^{o_{n}}:n\in\mathbb{N})$ converges
$(\ell_{n})$-locally to a random rooted standard graph $G^{o}$ (for an
$\mathbb{N}$-valued sequence $(\ell_{n})$) if exploration processes that
collect information about the two graphs $G_{n}^{o_{n}}$ and $G^{o}$ step by
step can be coupled in such a way that they find the same structure modulo
graph isomorphism with high probability as long as they are run for $\ell_{n}$
steps.

From now on for each $n\in\mathbb{N}$, $G_{n}^{o_{n}}$ denotes a random
finite, connected $\mathbb{G}^{\mathrm{root}}$-graph and
$X=X^{(n)}=(X^{(n)}_{t})_{t\geq 0}$ denotes a càdlàg process on
$\operatorname{\mathbb{I}}$ such that under $\mathbb{P}$ given $G_{n}^{o_{n}}$
the process $X^{(n)}$ is an $L_{G_{n}}$-Markov process started in the unique
$L_{G_{n}}$-invariant distribution $\pi_{n}:=\pi^{G_{n}}$. Moreover, $G^{o}$
will denote a random connected $\mathbb{G}^{\mathrm{root}}$-graph. We denote
for $R\in\mathbb{N}_{0}$, by $V^{o}[R]$ the vertices of $G$ that have graph
distance (hop-count distance) less or equal to $R$ to the root $o$. Moreover,
$\partial V^{o}[R]$ denotes the set of vertices of $G$ with graph distance $R$
to the root vertex. We use analogous notation for the graphs $G_{n}$ and write
$V_{n}^{o_{n}}[R]$ and $\partial V_{n}^{o_{n}}[R]$ for the respective sets.

[Coupling visiting measures] Let $(\ell_{n}^{\prime})_{n\in\mathbb{N}}$ and
$(\ell_{n})_{n\in\mathbb{N}}$ be $\mathbb{N}$-valued and
$(\tau_{n})_{n\in\mathbb{N}}$ and $(a_{n})_{n\in\mathbb{N}}$ be
$(0,\infty)$-valued with all three sequences tending to infinity and suppose
that the random finite connected $\mathbb{G}^{\mathrm{root}}$-graphs
$G_{1}^{o_{1}},\dots$ converge $(\ell_{n})$-locally to the connected
$\mathbb{G}^{\mathrm{root}}$-graph $G^{o}$. Moreover, suppose that
$\ell_{n}^{\prime}=o(\ell_{n})$, $\tau_{n}=o(\alpha_{n}(V_{n}))$,

$\lim_{n\to\infty}d_{G_{n}}(\tau_{n})=0,\ \
\lim_{n\to\infty}P_{G_{n}}^{o_{n}}\bigl{(}\\#\text{
range}\bigl{(}(X_{t})_{[0,2\tau_{n}]}\bigr{)}>\ell_{n}^{\prime}\bigr{)}=0\text{
\ and }$ $\lim_{n\to\infty}\frac{\alpha_{n}(V_{n})}{a_{n}}=\mathfrak{a},\text{
in probability.}$

Let $R,R^{\prime}\in\mathbb{N}$ and $\sigma>0$. For $n\in\mathbb{N}$, let
$\Xi_{n}$ be the $(V_{n}^{o_{n}}[R],\tau_{n},a_{n})$-visiting measure and let
$\Gamma$ be the Cox-process that is conditionally on $G^{o}$ a Poisson point
process with intensity

$\displaystyle\mbox{$\frac{1}{\mathfrak{a}}$}\mathrm{Leb}|_{[0,\infty)}\otimes
P^{e_{V^{o}[R],G}}_{G}$ (2)

and let $\Gamma_{n}$ be the point process obtained from $\Gamma$ by killing
all paths at time $\tau_{n}$. One can couple $(G^{o_{n}}_{n},\Xi_{n})$ and
$(G^{o},\Gamma)$ such that, the following holds, with high probability:

  * •

There are subsets $\bar{\mathcal{V}}_{n}\supset V_{n}^{o_{n}}[R^{\prime}]$ and
${\mathcal{V}}_{n}\supset V^{o}[R^{\prime}]$ of $V_{n}$ and $V$, respectively,
and a graph isomorphism taking the $\bar{\mathcal{V}}_{n}$-disclosed graph of
$G_{n}^{o_{n}}$ to the $\mathcal{V}_{n}$-disclosed graph of $G^{o}$.

  * •

The trajectories appearing in $\Xi_{n}|_{[0,\sigma]\times W_{+}}$ do not leave
$\bar{\mathcal{V}}_{n}$ and the point process $\Gamma_{n}|_{[0,\sigma]\times
W_{+}}$ is obtained from $\Xi_{n}|_{[0,\sigma]\times W_{+}}$ by applying the
isomorphism $\varphi_{n}$ on the states of the trajectories.

######  Remark 1.1 (Interlacement representation).

Following [Szn10] the measure $P_{G}^{e_{V^{o}}[R],G}$ appearing in the
theorem admits a description in terms of interlacements. Let $\bar{W}$ be the
space of all càdlàg paths $w:\mathbb{R}\to\mathcal{V}\cup\\{\partial\\}$ such
that there exist $-\infty\leq t_{\partial}<t^{\partial}\leq\infty$ so that for
all $t\in\operatorname{\mathbb{R}}$

$t_{\partial}\leq t<t^{\partial}\ \Leftrightarrow\ w_{t}\in\mathcal{V}.$

We let $W$ denote the subspace of $\overline{W}$ consisting of transient
paths, i.e.,

$W=\\{(w_{t})_{t\in\operatorname{\mathbb{R}}}\in\overline{W}:\forall
v\in\mathcal{V}\text{ the set
}\\{t\in\operatorname{\mathbb{R}}:w_{t}=v\\}\text{ is bounded}\\}$

We call two paths $(w_{t})$ and $(\bar{w}_{t})$ of $W$ equivalent ($\sim$), if
there exists $\tau\in\operatorname{\mathbb{R}}$ such that
$w_{t}=\bar{w}_{\tau+t}$ for all $t\in\operatorname{\mathbb{R}}$. Note that
$\sim$ is an equivalence relation and we denote by $W^{*}=W/\\!\sim$ the set
of equivalence classes. Following [Szn10] we equip $W^{*}$ with the finest
$\sigma$-field such that the embedding

$W\ni w\mapsto[w]\in W^{*}$

is measurable222Here $[w]$ denotes the $\sim$-equivalence class of $w$.. Then
for every connected fixed graph $G^{o}\in\mathbb{G}^{\mathrm{root}}$ for which
$P_{G}$ is transient we have that there exists a $\sigma$-finite measure
$\nu_{G}$ (an _interlacement_) on $W^{*}$ such that for every $R\in\mathbb{N}$

$\displaystyle
P_{G}^{e_{V}^{o}[R],G}=\nu_{G}|_{W^{*}_{V^{o}[R]}}\circ\pi_{V^{o}[R]}^{-1},$
(3)

where $W^{*}_{V^{o}[R]}$ denotes the set of transient paths modulo $\sim$ that
enter $V^{o}[R]$ and

$\pi_{V^{o}[R]}:W^{*}_{V^{o}[R]}\to
W_{+},\,[(w_{t})_{t\in\operatorname{\mathbb{R}}}]\mapsto(w_{T_{V^{o}[R]}(w)+t})_{t\geq
0}$

sends an equivalence class $[(w_{t})]\in W^{*}_{V^{o}[R]}$ to the trajectory
that is following the trajectory $(w_{t})$ from its first entrance into
$V^{o}[R]$ onwards. Based on (3) we get an alternative representation for the
intensity measure (14) based on interlacements.

A particular family of random graphs for which the assumptions of the main
theorem can be verified are sparse Erdős-Rényi random graphs and random graphs
with fixed degree sequence.

######  Example 1.2 (Random graphs with fixed degree sequence).

For every $n\in\mathbb{N}$ we denote by
$\mathbf{d}^{(n)}=(d_{k}^{(n)})_{k=1,\dots,n}$ an $\mathbb{N}_{0}$-valued
sequence so that $N^{(n)}:=\sum_{k=1,\dots,n}d_{k}^{(n)}$ is even and strictly
positive. The random graph model with fixed degree sequence
$(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ is constituted by a sequence of random
multigraphs that is formed by pairing the half-edges in

$\mathbb{H}_{n}=\bigcup_{j\in\\{1,\dots,n\\}}\\{j\\}\times\\{1,\dots,d_{j}^{(n)}\\}$

and forming the random multigraph $G_{n}$ by taking as vertex set
$\\{1,\dots,n\\}$ and establishing for each pair
$\langle(j_{1},r_{1}),(j_{2},r_{2})\rangle$ of the latter random pairing an
edge connecting $j_{1}$ and $j_{2}$. The edge-weights are chosen to be one and
the vertex-weights are chosen as the respective degrees.

We denote by $\mathcal{C}_{n}^{\mathrm{max}}$ the largest component of $G_{n}$
and let $\bar{G}_{n}^{\bar{o}_{n}}$ denote the graph $G_{n}$ restricted to
$\mathcal{C}_{n}^{\mathrm{max}}$ equipped with a uniformly chosen root. As
parameters of the generator of the underlying random walk we choose $\alpha$
to be the degree and $\beta$ to be constantly one.

  1. (a)

_Mixing times._ Provided that for large $n\in\mathbb{N}$,

$\displaystyle
3\leq\min_{j=1,\dots,n}d_{j}^{(n)}\leq\max_{j=1,\dots,n}d_{j}^{(n)}\leq
n^{0.02}$ (4)

one has that there exists $\alpha>0$ such that, with high probability, $G_{n}$
is an $\alpha$-expander [BKW14, Lemma 5.3]. Moreover, with high probability,
$G_{n}$ is connected. This entails that provided that for a finite constant
$C$, with high probability, $\sum_{j=1}^{n}d_{j}^{(n)}\leq Cn$, one has w.h.p.
that the minimal mass of the stationary distribution tends to zero of order
$\frac{1}{n}$ and the mixing time is of order $\mathcal{O}(\log n)$.

  2. (b)

_Local convergence._ We denote by $D_{n}$ an $\mathbb{N}_{0}$-valued random
variable with distribution

$\frac{1}{n}\sum_{k=1}^{n}\delta_{d_{k}^{(n)}}$

and let $D_{n}^{*}$ denote a $\mathbb{N}$-valued random variable with size
biased distribution

$\frac{1}{N^{(n)}}\sum_{k=1}^{n}d_{k}^{(n)}\delta_{d_{k}^{(n)}}.$

As is shown in the appendix (see Theorem A and Remark A.2.(a)) we have the
following: Suppose that for an $\mathbb{N}$-valued sequence
$(\ell_{n})_{n\in\mathbb{N}}$ and for $\mathbb{N}_{0}$-valued random variables
$D$ and $D^{*}$, one has

$\ell_{n}=o\bigl{(}\sqrt{n}\,\mathbb{E}[D_{n}^{*}\wedge\sqrt{n}]^{-1}\bigr{)}$

and

$\displaystyle\lim_{n\to\infty}d_{\mathrm{TV}}(\mathbb{P}_{D_{n}},\mathbb{P}_{D})+\ell_{n}\,d_{\mathrm{TV}}(\mathbb{P}_{D_{n}^{*}},\mathbb{P}_{D^{*}})=0.$
(5)

Then the respective sequence $(G_{n}^{o_{n}})_{n\in\mathbb{N}}$ of uniformly
rooted random graphs with degree sequence
$(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ converges $(\ell_{n})$-locally to a
$\mathrm{GWP}(D,D^{*})$-tree as introduced in the appendix.

Suppose now that the $\mathrm{GWP}(D,D^{*})$-tree is infinite with strictly
positive probability. Then by Corollary 1.9 the rooted graphs
$(\bar{G}^{\bar{o}_{n}})$ converge $(\ell_{n})$-locally to the
$\mathrm{GWP}(D,D^{*})$ process conditioned to be infinite.

  3. (c)

_Application of the main theorem._ In the situation where we can apply (a) and
(b) above, we choose $a_{n}=n$ and, moreover, $(\tau_{n})$,
$(\ell^{\prime}_{n})$ and $(\ell_{n})$ such that

$\lim_{n\to\infty}\frac{\log n}{\tau_{n}}=0,\
\lim_{n\to\infty}\frac{\tau_{n}}{\ell_{n^{\prime}}}=0,\lim_{n\to\infty}\frac{\ell_{n^{\prime}}}{\ell_{n}}=0\text{
and
}\lim_{n\to\infty}\frac{\ell_{n}}{\sqrt{n}\,\mathbb{E}[D_{n}^{*}\wedge\sqrt{n}]^{-1}}.$

This is easily established since assumption (4) in (a) entails that

$\sqrt{n}\,\mathbb{E}[D_{n^{*}}\wedge\sqrt{n}]^{-1}\geq n^{0.48}.$

The number of jumps of the random walk in the time interval $[0,2\tau_{n}]$ is
by choice of the walk Poisson-distributed with parameter $2\tau_{n}$ so that
obviously the range constraint is satisfied. We assume that (5) is satisfied
for random variables $D$ and $D^{*}$.

Recall that $G_{n}$ is with high probability connected and

$\alpha_{n}(V_{n})=\sum_{k=1}^{n}d_{k}^{(n)}=n\,\mathbb{E}[D_{n}].$

Next, we show that $\lim_{n\to\infty}\mathbb{E}[D_{n}]=\mathbb{E}[D]$. Note
that for all $k\in\mathbb{N}$,
$\mathbb{P}(D_{n}^{*}=k)=\mathbb{E}[D_{n}]^{-1}k\,\mathbb{P}(D_{n}=k)$. Pick
an index $\ell\in\mathbb{N}$ with $\mathbb{P}(D^{*}=\ell)>0$ and observe that

$\lim_{n\to\infty}\mathbb{E}[D_{n}]^{-1}\ell\,\mathbb{P}(D_{n}=\ell)=\mathbb{P}(D^{*}=\ell)>0$

and

$\limsup_{n\to\infty}\mathbb{E}[D_{n}]\leq\ell\,\mathbb{P}(D=\ell)\,\mathbb{P}(D^{*}=\ell)^{-1}<\infty.$

Since
$\lim_{n\to\infty}d_{\mathrm{TV}}(\mathbb{P}_{D_{n}^{*}},\mathbb{P}_{D^{*}})=0$
we get that

$\displaystyle\lim_{n\to\infty}\mathbb{E}[D_{n}]^{-1}\sum_{k=1}^{\infty}\bigl{|}k\,\mathbb{P}(D_{n}=k)-\mathbb{E}[D_{n}]\,\mathbb{P}(D^{*}=k)\bigr{|}=0.$

Since $(\mathbb{E}[D_{n}])$ is bounded it follows that

$\Bigl{|}\sum_{k=1}^{\infty}k\,\mathbb{P}(D_{n}=k)-\mathbb{E}[D_{n}]\Bigr{|}\leq\sum_{k=1}^{\infty}\bigl{|}k\,\mathbb{P}(D_{n}=k)-\mathbb{E}[D_{n}]\,\mathbb{P}(D^{*}=k)\bigr{|}\to
0$

so that $\mathbb{E}[D_{n}]\to\mathbb{E}[D]$ with a finite limit. Thus we need
to choose $\mathfrak{a}=\mathbb{E}[D]$.

Consequently, the visiting measure converges to the respective limit process
on the $\mathrm{GWP}(D,D^{*})$ tree.

######  Example 1.3 (Erdős-Rényi random graphs).

We let $(m(n))_{n\in\mathbb{N}}$ be a $\mathbb{N}$-valued sequence such that

$\lambda=\lim_{n\to\infty}\frac{m(n)}{n}$

exists and lies in he interval $(1,\infty)$. Denote for every
$n\in\mathbb{N}$, by $G_{n}$ a uniformly chosen graph under all (simple)
graphs with vertex set $\\{1,\dots,n\\}$ with $m(n)$ edges333If
$m(n)>{n\choose 2}$, then there are no such graphs. In that case we pick the
complete graph.. The edge weights are chosen to be one and the vertex weights
are equal to the respective degree. We denote by
$\mathcal{C}_{n}^{\mathrm{max}}$ the largest component of $G_{n}$. As shown in
[BKW14], one has, with high probability, that the mixing time is of order
$\Theta\bigl{(}(\log n)^{2}\bigr{)}$ for the random walk on the maximal
cluster $\mathcal{C}_{n}^{\mathrm{max}}$ of $G$. Let
$(\ell_{n})_{n\in\mathbb{N}}$ be an $\mathbb{N}$-valued sequence with
$\ell_{n}=o(\sqrt{n})$. Similarly, as in the appendix one can show that the
uniformly rooted graph $G_{n}^{o_{n}}$ converges $(\ell_{n})$-locally to a
$\mathrm{GWP}(D,D+1)$-tree, where $D$ denotes a Poisson-distributed random
variable with parameter $\lambda$. Then again one can use Corollary 1.9 to
deduce the local limit for the graph restricted to the giant component. One
still needs to verify the convergence towards an appropriate $\mathfrak{a}$ in
the respective model.

###  1.4. Exploration convergence

Classical Benjamini-Schramm convergence is a form of weak convergence for
random rooted graphs. More explicitly, a sequence of random rooted graphs
$G_{n}^{o_{n}}$ converges to a random rooted graph $G^{o}$ in the sense of
Benjamini-Schramm [BS01] if for every radius $R\in\mathbb{N}$ the rooted
graphs can be coupled such that (after relabeling) the $R$-neighbourhoods of
$G_{n}^{o_{n}}$ agree with $G^{o}$ in the limit with probability one. In this
article we work with a different notion of local convergence, one which
incorporates a control of the quality of the latter approximation depending on
the index $n$. For this we will use the concept of an exploration process.

We start with the formal definition of an _exploration rule_. Recall that
$\bar{\operatorname{\mathbb{G}}}^{\mathrm{finite,\,root}}$ is the set of
finite, rooted, generalised graphs. An _exploration_ is a tuple

$\mathfrak{E}=(\mathcal{G},(e_{1},\dots,e_{n}))\in\bar{\operatorname{\mathbb{G}}}^{\mathrm{finite,\,root}}\times\mathcal{E}^{*}$

so that for each $i=1,\dots,n$ the edge $e_{i}$ is in $\mathcal{G}$ and the
edge $e_{i}$ has both of its endpoints in the set of vertices in
$\mathcal{G}$.

An _exploration rule_ $K$ is a probability kernel that assigns an exploration
$(\mathcal{G},(e_{1},\dots,e_{n}))$ to a distribution on the edges of
$\mathcal{G}$ that is invariant under isomorphisms. More explicitly, for an
exploration $\mathfrak{E}=(\mathcal{G},(e_{1},\dots,e_{n}))$ and a graph
isomorphism $\phi$ taking the exploration $\mathfrak{E}$ to
$\mathfrak{E}^{\prime}=\phi(\mathfrak{E})$ (meaning that
$\mathfrak{E}^{\prime}=(\phi(\mathcal{G}),(\phi(e_{1}),\dots,\phi(e_{n})))$)
we have

$K(\mathfrak{E},\varphi\in\,\cdot\,)=K(\mathfrak{E}^{\prime},\,\cdot\,).$

For a graph $G$ and a finite subset $V_{0}\subset V$ of vertices we build the
_$V_{0}$ -disclosed subgraph_ $G_{|V_{0}}$ of $G$ as follows: it is the
generalised weighted finite graph that

  * •

has vertices $V_{0}$ and edges $\\{e\in
E(G):\\{e^{\prime},e^{\prime\prime}\\}\cap V_{0}\not=\emptyset\\}$
(all edges with one of the endpoints lying in $V_{0}$)

  * •

where every edge connecting to a vertex outside of $V_{0}$ is redirected to
$\partial$ and

  * •

all vertex and edge weights are as in $G$.

An _exploration process_ is now a stochastic process that is defined for an
arbitrary rooted graph $G^{o}$ and an exploration rule $K$ as follows:
$\mathfrak{E}_{0}=(\mathcal{G}_{0}^{o},\emptyset)$ where $\mathcal{G}^{o}_{0}$
is the $V(0)=\\{o\\}$-disclosed subgraph of $G$ with root $o$ and for every
$k=1,\dots$ we iteratively

  * •

choose an $K(\mathfrak{E}_{k-1};\,\cdot\,)$-distributed edge $e_{k}$,

  * •

form $V(k)$ by adding to $V(k-1)$ the endpoints of $e_{k}$ in the graph $G$
(if $e_{k}=\partial$ no vertices are added) and

  * •

let $\mathfrak{E}_{k}=(\mathcal{G}_{k}^{o},(e_{1},\dots,e_{k}))$ where
$\mathcal{G}_{k}^{o}$ denotes the $V(k)$-disclosed subgraph of $G$ with root
$o$.

Note that during the exploration the disclosed subgraph changes whenever the
exploration rule picks an edge that leaves the set of previously disclosed
vertices. In the case that $G^{o}$ is itself random we run the exploration
with the respective conditional distributions.

######  Definition 1.4.

We call an exploration rule $K$ proper if for every
$\operatorname{\mathcal{E}}\in\operatorname{\mathbb{G}}^{\mathrm{expl}}$ with
at least one edge connecting to $\partial$ the distribution
$K(\operatorname{\mathcal{E}},(e_{1},\dots,e_{k});\,\cdot\,)$ puts all mass on
edges connected to $\partial$.

######  Example 1.5 (Breadth-first exploration).

Choosing $K(\operatorname{\mathcal{E}},(e_{1},\dots,e_{k});\,\cdot\,)$ as the
uniform distribution on all edges connecting to $\partial$ with minimal
distance to the root, leads to the breadth-first exploration process of a
component of the graph.

######  Example 1.6 (Exploration governed by the Markov procecss).

Let $G^{o}\in\mathbb{G}^{\mathrm{root}}$. We denote by
$(X_{t})_{t\in[0,\infty)}$ a $P^{o}_{G}$-distributed process and let for
$k\in\mathbb{N}_{0}$

$S_{k}=\inf\bigl{\\{}t\geq
0:\\#\mathrm{range}\bigl{(}(X_{s})_{s\in[0,t]}\bigr{)}>k\bigr{\\}}.$

Moreover, let for every $k\in\mathbb{N}_{0}$, $e_{k}$ denote the random edge
that is traversed by the Markov process at time $S_{k}$ if the latter time is
finite and $\partial$ otherwise. Note that one can read of the state of the
Markov process at time $S_{k}$ from $\mathfrak{E}_{k-1}$ and the edge passed
by $X$ at that time. Given $(X_{t})_{t\in[0,S_{k}]}$, the conditional
distribution of $((X_{t-S_{k}})_{t\in[0,S_{k+1}-S_{k})},e_{k+1})$ is just the
distribution of the Markov process started in $X_{S_{k}}$ that is killed
immediately when leaving the set of disclosed vertices in $\mathfrak{E}_{k}$
with $e_{k+1}$ being the edge traversed by the Markov process when exiting.
Obviously, the conditional distribution is $\mathfrak{E}_{k}$-measurable and
invariant under graph isomorphisms. Therefore, this defines an exploration
rule. We call this exploration _exploration along the Markov process_.

A slight modification of this exploration rule is obtained by fixing $\tau>0$
and letting $X^{1},\dots$ independent $P_{G}^{o}$-distributed processes and by
exploring new edges along
$(X^{1}_{t})_{t\in[0,\tau]},\,(X^{2}_{t})_{t\in[0,\tau]},\,\dots$
consecutively. Meaning that one explores new edges ones one of the paths hits
a vertex that has not yet been visited before. We call this exploration
_$\tau$ -exploration along the Markov process_.

######  Definition 1.7.

Let $G^{o},G^{o_{1}}_{1},\dots$ be random $\mathbb{G}^{\mathrm{root}}$-graphs
and let $G$ be connected. Furthermore, let $(K_{n})$ be a sequence of
exploration rules and $(\ell_{n})$ be an $\mathbb{N}$-valued sequence. We say
that $(G_{n}^{o_{n}})_{n\in\mathbb{N}}$ _converges $(K_{n},\ell_{n})$-locally_
to $G^{o}$ if there exists a coupling of the $K_{n}$-explorations
$\bar{\mathfrak{E}}^{(n)}$ of $G_{n}^{o_{n}}$ and $\mathfrak{E}^{(n)}$ of
$G^{o}$ such that

$\lim_{n\to\infty}\mathbb{P}(\bar{\mathfrak{E}}^{(n)}_{\ell_{n}}\sim\mathfrak{E}^{(n)}_{\ell_{n}})=1.$

If one has local convergence along every sequence of rules $(K_{n})$, then we
briefly say that $(G_{n}^{o_{n}})_{n\in\mathbb{N}}$ _converges
$(\ell_{n})$-locally_ to $G^{o}$.

For many network models one can prove local convergence in the sense of
Benjamini-Schramm when choosing the root vertex uniformly at random. It is a
technical issue to derive $(\ell_{n})$-local convergence for sufficiently
slowly growing $(\ell_{n})$. Often one encounters the following situation,
e.g., for the configuration model, inhomogeneous graph model or preferential
attachment model: in the limit the graph possesses one giant component
(meaning that the relative number of vertices in the largest component is
typically close to a deterministic value $p>0$) with all other components
being significantly smaller. In this case, we consider the restricted graph
$G_{n}^{o_{n}}$ onto the giant component conditionally on choosing the root
$o_{n}$ from the giant component. We provide technical results that allow to
deduce from $(\ell_{n})$-local convergence for the unconditional setting the
respective $(\ell_{n})$-local convergence for the restricted graphs with the
root vertex chosen uniformly from the giant component.

Let $(\ell_{n})$ be an $\mathbb{N}_{0}$-valued sequence converging to
infinity. Let $(G_{n}^{o_{n}})_{n\in\mathbb{N}}$ be a sequence of random,
finite $\mathbb{G}^{\mathrm{root}}$-graphs that converges $(\ell_{n})$-locally
to a connected random $\mathbb{G}^{\mathrm{root}}$-graph $G^{o}$ and suppose
that $\mathbb{P}(G\text{ is infinite})>0$. Then there is an
$\mathbb{N}$-valued sequence $(\rho_{n})_{n\in\mathbb{N}}$ that converges
monotonically to $\infty$ for which

$\displaystyle\liminf_{n\to\infty}\,\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})\geq\mathbb{P}(G\text{
is infinite}),$ (6)

where $\mathcal{C}_{n}(o_{n})$ denotes the component of $o_{n}$ in $G_{n}$,
and for every such $(\rho_{n})$ we have that $G_{n}^{o_{n}}$ under
$\mathbb{P}_{|\\{\mathcal{C}_{n}(o_{n})\geq\rho_{n}\\}}$ converges
$(\ell_{n})$-locally to the graph $G^{o}$ under $\mathbb{P}_{|\\{G\text{ is
infinite}\\}}$.

######  Remark 1.8.

Let $(K_{n})$ be a sequence of proper exploration rules. Then demanding in
Proposition 1.4 that $(G_{n}^{o_{n}})$ converges $(K_{n},\ell_{n})$-locally to
$G^{o}$ instead one can deduce as in the proof of the proposition that then
$G_{n}^{o_{n}}$ under $\mathbb{P}_{|\\{\mathcal{C}_{n}(o_{n})\geq\rho_{n}\\}}$
converges $(K_{n},\ell_{n})$-locally to the graph $G^{o}$ under
$\mathbb{P}_{|\\{G\text{ is infinite}\\}}$.

###### Proof.

Let $K_{1},K_{2},\dots$ be a sequence of proper exploration rules. By
assumption we can couple the $K_{n}$-explorations $\bar{\mathfrak{E}}^{(n)}$
and $\mathfrak{E}^{(n)}$ of $G_{n}^{o_{n}}$ and $G^{o}$, respectively, such
that $\bar{\mathfrak{E}}^{(n)}_{\ell_{n}}\sim{\mathfrak{E}}^{(n)}_{\ell_{n}}$,
with high probability. Since the exploration rules are proper we have that if
$\ell_{n}\geq\rho$, on
$\\{\bar{\mathfrak{E}}^{(n)}_{\ell_{n}}\sim{\mathfrak{E}}^{(n)}_{\ell_{n}}\\}$
one has $\\#\mathcal{C}_{n}(o_{n})\geq\rho$ iff $\\#\mathcal{C}(o)\geq\rho$.
Consequently,

$\lim_{n\to\infty}\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho)=\mathbb{P}(\\#V\geq\rho).$

Obviously, as $\rho\to\infty$, we have
$\mathbb{P}(\\#V\geq\rho)\to\mathbb{P}(G\text{ is infinite})$ and existence of
an appropriate sequence $(\rho_{n})$ follows by a diagonalisation argument.
For every sequence $(\rho_{n})$ tending to infinity one has

$\limsup_{n\to\infty}\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})\leq\limsup_{n\to\infty}\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho)=\mathbb{P}(\\#V\geq\rho)\to\mathbb{P}(G\text{
is infinite})$

as $\rho\to\infty$ so that (6) entails that indeed

$\lim_{n\to\infty}\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})=\mathbb{P}(G\text{
is infinite}).$

In order to show the second statement we first suppose that
$\rho_{n}\leq\ell_{n}$ for all large $n$. Then one can read off the
$K_{n}$-exploration $\mathfrak{E}^{(n)}_{\ell_{n}}$ with $\ell_{n}$ steps of
$G^{o}$ whether $\\#\mathcal{C}(o)\geq\rho_{n}$ and the same is true for the
respective exploration of the graph $G_{n}^{o_{n}}$, say
$\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$. Conceiving the explorations
$\mathfrak{E}^{(n)}_{\ell_{n}}$ and $\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ as
equivalence classes (modulo graph isomorphisms) we get that

$d_{\mathrm{TV}}\bigl{(}\mathbb{P}\circ(\mathfrak{E}^{(n)}_{\ell_{n}})^{-1},\mathbb{P}\circ(\bar{\mathfrak{E}}^{(n)}_{\ell_{n}})^{-1}\bigr{)}\to
0.$

Now generally for two distributions $\mathcal{P}$ and $\mathcal{Q}$ and an
event $A$ one has for the conditional distributions $\mathcal{P}_{|A}$ and
$\mathcal{Q}_{|A}$ that for every event $B$

$\displaystyle\mathcal{P}_{|A}(B)-\mathcal{Q}_{|A}(B)$
$\displaystyle=\frac{1}{\mathcal{P}(A)}\mathcal{P}(A\cap
B)-\frac{1}{\mathcal{Q}(A)}\mathcal{Q}(A\cap B)$
$\displaystyle=\frac{1}{\mathcal{P}(A)}(\mathcal{P}(A\cap B)-\mathcal{Q}(A\cap
B))+\bigl{(}\frac{1}{\mathcal{P}(A)}-\frac{1}{\mathcal{Q}(A)}\bigr{)}\mathcal{Q}(A\cap
B)$
$\displaystyle\leq\frac{1}{\mathcal{P}(A)}d_{\mathrm{TV}}(\mathcal{P},\mathcal{Q})+\Bigl{(}\frac{\mathcal{Q}(A)}{\mathcal{P}(A)}-1\Bigr{)}_{+}$

With an analogous estimate in the converse direction one thus gets that

$|\mathcal{P}_{|A}(B)-\mathcal{Q}_{|A}(B)|\leq\frac{1}{\mathcal{P}(A)}d_{\mathrm{TV}}(\mathcal{P},\mathcal{Q})+\Bigl{|}\frac{\mathcal{Q}(A)}{\mathcal{P}(A)}-1\Bigr{|}.$

Using this estimate with $A$ being the event that the exploration yields a
cluster with more or equal to $\rho_{n}$ elements yields the estimate

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle\bigl{(}\mathbb{P}_{|\\{\\#\mathcal{C}(o)\geq\rho_{n}\\}}\circ(\mathfrak{E}_{\ell_{n}}^{(n)})^{-1},\mathbb{P}_{|\\{\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n}\\}}\circ(\bar{\mathfrak{E}}_{\ell_{n}}^{(n)})^{-1}\bigr{)}$
$\displaystyle\leq\frac{1}{\mathbb{P}(\\#\mathcal{C}(o)\geq\rho_{n})}\,d_{\mathrm{TV}}(\mathbb{P}\circ(\mathfrak{E}_{\ell_{n}}^{(n)})^{-1},\mathbb{P}\circ(\bar{\mathfrak{E}}^{(n)}_{\ell_{n}})^{-1})+\Bigl{|}\frac{\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})}{\mathbb{P}(\\#\mathcal{C}(o)\geq\rho_{n})}-1\Bigr{|}.$

The latter tends to zero by choice of $\rho_{n}$. Clearly,

$\displaystyle\begin{split}d_{\mathrm{TV}}&\bigl{(}\mathbb{P}_{|\\{\\#\mathcal{C}(o)\geq\rho_{n}\\}}\circ(\mathfrak{E}_{\ell_{n}}^{(n)})^{-1},\mathbb{P}_{|\\{\\#\mathcal{C}(o)=\infty\\}}\circ({\mathfrak{E}}_{\ell_{n}}^{(n)})^{-1}\bigr{)}\\\
&\leq
d_{\mathrm{TV}}\bigl{(}\mathbb{P}_{|\\{\\#\mathcal{C}(o)\geq\rho_{n}\\}}\circ(G^{o})^{-1},\mathbb{P}_{|\\{\\#\mathcal{C}(o)=\infty\\}}\circ(G^{o})^{-1}\bigr{)}\to
0,\end{split}$ (7)

since $\mathbb{P}(\mathcal{C}(o)=\infty)>0$. It remains to consider $n$ with
$\rho_{n}>\ell_{n}$. First note that applying an arbitrary proper exploration
rule for $\ell_{n}$ steps yields that

$\displaystyle|\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\ell_{n})-\mathbb{P}(\\#\mathcal{C}(o)=\infty)|$
$\displaystyle\leq|\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\ell_{n})-\mathbb{P}(\\#\mathcal{C}(o)\geq\ell_{n})|$
$\displaystyle\quad+|\mathbb{P}(\\#\mathcal{C}(o)\geq\ell_{n})-\mathbb{P}(\\#\mathcal{C}(o)=\infty)|\to
0.$

Consequently, we get along a subsequence of $n$’s with $\rho_{n}>\ell_{n}$
that as in (7)

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle\bigl{(}\mathbb{P}_{|\\{\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n}\\}}\circ(\bar{\mathfrak{E}}_{\ell_{n}}^{(n)})^{-1},\mathbb{P}_{|\\{\\#\mathcal{C}_{n}(o_{n})\geq\ell_{n}\\}}\circ(\bar{\mathfrak{E}}_{\ell_{n}}^{(n)})^{-1}\bigr{)}$
$\displaystyle\leq\frac{\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\in[\ell_{n},\rho_{n}))}{\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\ell_{n})}=\frac{\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\ell_{n})-\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})}{\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\ell_{n})}.$

The latter tends to zero since by assumption
$\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})$ tends also to
$\mathbb{P}(\\#\mathcal{C}(o)=\infty)$. ∎

######  Corollary 1.9.

Let $(G_{n})_{n\in\mathbb{N}}$ be a sequence of random $\mathbb{G}$-graphs so
that every graph $G_{n}$ has $n$ vertices. Given $G_{n}$ we choose a root
$o_{n}$ uniformly from the respective set of vertices and we suppose that
$(G_{n}^{o_{n}})$ converges $(\ell_{n})$-locally to a random, connected
$\mathbb{G}^{\mathrm{root}}$-graph $G^{o}$. We let
$\mathcal{C}_{n}^{\mathrm{max}}$ denote the largest component444If there is
not a unique largest component we choose one uniformly at random. of $G^{o}$
and suppose that

$\lim_{n\to\infty}\frac{\\#\mathcal{C}_{n}^{\mathrm{max}}}{n}=\mathbb{P}(G\text{
is infinite}),\text{ \ in probability}.$

We denote by $o_{n}^{\mathrm{max}}$ a vertex of $G_{n}$ that is, given
$G_{n}$, uniformly distributed on $\mathcal{C}_{n}^{\mathrm{max}}$. Then
$(G_{n}^{o_{n}^{\mathrm{max}}})_{n\in\mathbb{N}}$ converges
$(\ell_{n})$-locally to the distribution of $G^{o}$ under
$\mathbb{P}_{|\\{G\text{ is infinite}\\}}$.

###### Proof.

We set $p=\mathbb{P}(G\text{ is infinite})>0$. First we show that

$\displaystyle
d_{\mathrm{TV}}(G_{n}^{o_{n}^{\mathrm{max}}},\mathbb{P}_{|\\{o_{n}\in\mathcal{C}^{\mathrm{max}}_{n}\\}}\circ(G_{n}^{o_{n}})^{-1})\to
0.$ (8)

Note that for an event $A$

$\displaystyle\mathbb{P}(o_{n}\in\mathcal{C}_{n}^{\mathrm{max}},G_{n}^{o_{n}}\in
A)$
$\displaystyle=\int\int\operatorname{\mathbbm{1}}_{\mathcal{C}_{n}^{\mathrm{max}}}(\bar{o}_{n})\,\operatorname{\mathbbm{1}}_{A}(G_{n}^{\bar{o}_{n}})\,d\mathrm{Unif}_{V_{n}}(\bar{o}_{n})\,d\mathbb{P}$
$\displaystyle=\int\frac{\\#\mathcal{C}_{n}^{\mathrm{max}}}{n}\int\operatorname{\mathbbm{1}}_{A}(G_{n}^{\bar{o}_{n}})\,d\mathrm{Unif}_{\mathcal{C}_{n}^{\mathrm{max}}}(\bar{o}_{n})\,d\mathbb{P}$
$\displaystyle=\int\frac{\\#\mathcal{C}_{n}^{\mathrm{max}}}{n}\operatorname{\mathbbm{1}}_{A}(G_{n}^{o_{n}^{\mathrm{max}}})\,d\mathbb{P}.$

Consequently,

$\bigl{|}\mathbb{P}_{|\\{o_{n}\in\mathcal{C}^{\mathrm{max}}_{n}\\}}(G_{n}^{o_{n}}\in
A)-\mathbb{P}(G_{n}^{o_{n}^{\mathrm{max}}}\in
A)\bigr{|}\leq\int\Bigl{|}\frac{1}{\mathbb{P}(o_{n}\in\mathcal{C}^{\mathrm{max}}_{n})}\frac{\\#\mathcal{C}_{n}^{\mathrm{max}}}{n}-1\Bigr{|}\,d\mathbb{P}$

and the right hand side does not depend on the choice of the event $A$.
Moreover, it converges to $0$ as $n\to\infty$ as consequence of dominated
convergence, $\frac{\\#\mathcal{C}_{n}^{\mathrm{max}}}{n}\to p$, in
probability, and $\mathbb{P}(o_{n}\in\mathcal{C}^{\mathrm{max}}_{n})\to p$.

Next, we apply Proposition 1.4 with $\rho_{n}=\frac{p}{2}n$: one has

$\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})\geq\int\operatorname{\mathbbm{1}}_{\\{o_{n}\in\mathcal{C}_{n}^{\mathrm{max}}\\}}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}_{n}^{\mathrm{max}}\geq\rho_{n}\\}}d\mathbb{P}=\int\frac{\mathcal{C}_{n}^{\mathrm{max}}}{n}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}_{n}^{\mathrm{max}}\geq\rho_{n}\\}}\,d\mathbb{P}$

and the right hand side converges to $p$ as consequence of dominated
convergence. Hence, $G_{n}^{o_{n}}$ under
$\mathbb{P}_{|\\{\mathcal{C}_{n}(o_{n})\geq\rho_{n}\\}}$ converges
$(\ell_{n})$-locally to the graph $G^{o}$ under $\mathbb{P}_{|\\{G\text{ is
finite}\\}}$. Once we showed that

$d_{\mathrm{TV}}\bigl{(}\mathbb{P}_{|\\{o_{n}\in\mathcal{C}_{n}^{\mathrm{max}}\\}}\circ(G_{n}^{o_{n}})^{-1},\mathbb{P}_{|\\{\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n}\\}}\circ(G_{n}^{o_{n}})^{-1}\bigr{)}\to
0$

we can deduce the statement of the proposition with (8) and the previously
derived local convergence. One has

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle\bigl{(}\mathbb{P}_{|\\{o_{n}\in\mathcal{C}_{n}^{\mathrm{max}}\\}}\circ(G_{n}^{o_{n}})^{-1},\mathbb{P}_{|\\{\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n}\\}}\circ(G_{n}^{o_{n}})^{-1}\bigr{)}$
$\displaystyle=1-\frac{\mathbb{P}(o_{n}\in\mathcal{C}_{n}^{\mathrm{max}},\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})}{\mathbb{P}(o_{n}\in\mathcal{C}_{n}^{\mathrm{max}})\vee\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})}$

which converges to $0$ since
$\mathbb{P}(o_{n}\in\mathcal{C}_{n}^{\mathrm{max}},\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})$,
$\mathbb{P}(o_{n}\in\mathcal{C}_{n}^{\mathrm{max}})$ and
$\mathbb{P}(\\#\mathcal{C}_{n}(o_{n})\geq\rho_{n})$ all tend to $p$. ∎

Let $(m_{n})$, $(\ell_{n})$ be $\mathbb{N}$-valued sequences and $(\tau_{n})$
a $(0,\infty)$-valued sequence. Moreover, let $G_{1}^{o_{1}},\dots$ random
$\mathbb{G}^{\mathrm{root}}$-valued random variables converging
$(m_{n}\ell_{n})$-locally to a andom rooted graph $G^{o}$. Moreover, suppose
that

$m_{n}\,P^{o}_{G}\bigl{(}\\#\mathrm{range}\bigl{(}(X_{t})_{t\in[0,2\tau_{n}]}\bigr{)}>\ell_{n})\to
0,\text{ in probability}.$

For $n\in\mathbb{N}$, let $V^{(n)}_{0}$ be the set of vertices seen by
independent (conditionally on $G^{o}$) $P^{o}_{G}$-processes
$X^{(n,1)}=(X^{(1)}_{t})_{t\in[0,2\tau_{n}]},\dots,X^{(n,m_{n})}=(X^{(m_{n})}_{t})_{t\in[0,2\tau_{n}]}$
and let $G|_{V^{(n)}_{0}}$ denote the $V_{0}^{(n)}$-disclosed subgraph of $G$.
Analogously, let $\bar{V}^{(n)}_{0}$ be the set of vertices seen by the
independent $P^{o_{n}}_{G_{n}}$-processes
$(\bar{X}^{(n,1)}_{t})_{t\in[0,2\tau_{n}]},\dots,(\bar{X}^{(n,m_{n})}_{t})_{t\in[0,2\tau_{n}]}$
and let $G_{n}|_{\bar{V}^{(n)}_{0}}$ denote the $V_{0}^{(n)}$-disclosed
subgraph of $G$. One can couple

$(G^{o_{n}}_{n}|_{\bar{V}^{(n)}_{0}},(\bar{X}^{(n,1)},\dots,\bar{X}^{(n,m_{n})}))\text{
and }(G^{o}|_{V^{(n)}_{0}},(X^{(n,1)},\dots,X^{(n,m_{n})}))$

so that for the coupled random objects, with high probbaility, there is a
graph isomorphism $\varphi_{n}$ taking $G^{o_{n}}_{n}|_{\bar{V}^{(n)}_{0}}$ to
$G^{o}|_{V^{(n)}_{0}}$ which also takes the trajectories
$\bar{X}^{(n,1)},\dots,\bar{X}^{(n,m_{n})}$ to
$X^{(n,1)},\dots,X^{(n,m_{n})}$.

###### Proof.

For $n\in\mathbb{N}$ we consider exploration along independent Markov
processes of length $\tau_{n}$ as introduced in Example 1.6. Since

$\displaystyle P_{G}^{o}$
$\displaystyle(\\#\mathrm{range}(X^{(n,1)},\dots,X^{(n,m_{n})})>m_{n}\ell_{n})$
$\displaystyle\leq
m_{n}\,P_{G}^{o}\bigl{(}\\#\mathrm{range}((X_{t})_{t\in[0,2\tau_{n}]})>\ell_{n}\bigr{)}\to
0,\text{ in probability},$

the coupling succeeds with high probability meaning that the disclosed areas
and the exploration edges of the exploration of the first $m_{n}$ paths can be
transformed into each other by an appropriate graph isomorphism, with high
probability. The $k$-th exploration step can be achieved by following the
“current” trajectory $X^{(n,q)}$ until the next vertex outside of the
currently disclosed area is entered. Provided that the coupling succeeded so
far the conditional distribution of the trajectory given the next exploration
step only depends on the previous exploration step and is invariant under
graph isomorphisms. Consequently, the coupling can be extended to a coupling
as in the statement of the proposition. ∎

##  2\. Markov process estimates

In this section we derive estimates for entrance times that are in the spirit
of Aldous and Brown [AB92]. We denote by $G\in\operatorname{\mathbb{G}}$ a
fixed _connected, deterministic, weighted_ graph and we denote by $(P^{v}:v\in
V)$ the reversible continuous time Markov family with generator $L=L_{G}$
being defined as in (1). Proovided that $\sum_{w\in V}\alpha(w)$ is finite,
the distribution $\pi=\pi^{G}=(\pi^{G}_{v})_{v\in V}$ given by

$\pi_{v}^{G}=\frac{\alpha(v)}{\sum_{w\in V}\alpha(w)}\qquad(v\in V)$

is the unique invariant distribution. We need to introduce some further
quantities. For a subset $B\subset V$ and $\tau\geq 0$ we call the measure
$e^{\tau}_{B,G}$ given by

$e_{B,G}^{\tau}(y)=\operatorname{\mathbbm{1}}_{B}(y)\alpha_{y}\sum_{z\in
B^{c}}L(y,z)\,P_{G}^{z}(T_{B}>\tau)\qquad(y\in V)$

the _$\tau$ -equilibrium measure of $B$_ and let

$\operatorname{cap}_{G}^{\tau}(B)=\|e_{B,G}^{\tau}\|=\sum_{y\in
B}\alpha_{y}\sum_{z\in B^{c}}L(y,z)\,P_{G}^{z}(T_{B}>\tau)$

the _$\tau$ -capacity of $B$_. In the particular case that $\tau=0$, we have

$\operatorname{cap}_{G}^{0}(B)=\sum_{y\in B}\alpha_{y}\sum_{z\in
B^{c}}L(y,z).$

######  Lemma 2.1.

Let $G\in\mathbb{G}$ be a finite graph, $B\subset V$ and $y\in V$. One has the
following:

  1. (a)

The distribution $P^{\pi}(T_{B}\in\cdot,X_{T_{B}}=y)$ has on $(0,\infty)$ the
continuous Lebesgue density

$t\mapsto\pi_{y}\sum_{z\in B^{c}}L(y,z)\,P^{z}(T_{B}>t).$

  2. (b)

For every $t\geq 2\tau>0$, we have

$|P^{y}(T_{B}>t)-P^{y}(T_{B}>\tau)\,P^{\pi}(T_{B}>t)|\leq
2d_{G}(\tau)+\mbox{$\frac{2\tau}{\alpha(V)}$}\operatorname{cap}_{G}^{0}(B).$

###### Proof.

(a) We note that for $y\in B$ as $\delta\downarrow 0$

$\displaystyle P^{\pi}(T_{B}\in(t,t+\delta],X_{T_{B}}=y)$
$\displaystyle=P^{\pi}(T_{B}\in(t,t+\delta],X_{t+\delta}=y)+o(\delta)$
$\displaystyle=\pi_{y}\,P^{y}((X_{s})_{s\in[\delta,t+\delta]}\text{ does not
hit $B$})+o(\delta)$ $\displaystyle=\delta\pi_{y}\sum_{z\in
B^{c}}L(y,z)\,P^{z}(T_{B}>t)+o(\delta)$

where the $o(\delta)$ term can be controlled uniformly for all $t\geq 0$ since
$\max_{x\in V}L_{x}<\infty$ by finiteness of $V$. Hence,

$\lim_{\delta\downarrow 0}\sup_{t\geq
0}\Bigl{|}\frac{1}{\delta}P^{\pi}(T_{B}\in(t,t+\delta],X_{T_{B}}=y)-\pi_{y}\sum_{z\in
B^{c}}L(y,z)\,P^{z}(T_{B}>t)\Bigr{|}=0.$

The term on the right of the minus sign is continuous in $t$ and thus one gets
that the measure $P^{\pi}(T_{B}\in\cdot,X_{T_{B}}=y)$ is continuously
differentiable on $(0,\infty)$ with the respective differential.

(b) We note that under $P^{\pi}$ the expected number of transitions along
edges from $B^{c}$ to $B$ on an interval $I$ is equal to
$\frac{1}{\alpha(V)}\operatorname{cap}_{G}^{0}(B)$ times the length of the
interval. Hence,

$\displaystyle P^{\pi}(T_{B}\in(t-2\tau,t])\leq
P^{\pi}\bigl{(}\\{(X_{t})_{t\in[t-2\tau,t]}$ has a transition along
$\displaystyle\text{ an edge from $B^{c}$ to
$B$}\\}\bigr{)}\leq\mbox{$\frac{2\tau}{\alpha(V)}$}\operatorname{cap}_{G}^{0}(B).$

Now using the Markov property we get with

$\mu_{z,\tau}=P^{z}(X_{\tau}\in\,\cdot\,|T_{B}>\tau)$

that

$\displaystyle P^{z}(T_{B}>t)$
$\displaystyle=P^{z}(T_{B}>\tau)\,P^{\mu_{z,\tau}}(T_{B}>t-\tau)$
$\displaystyle\leq
P^{z}(T_{B}>\tau)\,P^{\mu_{z,\tau}}\bigl{(}(X_{t})_{t\in[\tau,t-\tau]}\text{
does not hit }B\bigr{)}$ $\displaystyle\leq
P^{z}(T_{B}>\tau)(P^{\pi}(T_{B}>t-2\tau)+d(\tau))$ $\displaystyle\leq
P^{z}(T_{B}>\tau)\Bigl{(}P^{\pi}(T_{B}>t)+\mbox{$\frac{2\tau}{\alpha(V)}$}\operatorname{cap}_{G}^{0}(B)+d(\tau)\Bigr{)}.$

Conversely,

$P^{z}(T_{B}>t)\geq P^{z}((X_{t})_{t\in[0,\tau]\cup[2\tau,t]}\text{ does not
hit }B)-P^{z}(X_{\tau}\not\in B,(X_{t})_{t\in[\tau,2\tau]}\text{ hits }B)$

and with $P^{z}(X_{\tau}\not\in B,(X_{t})_{t\in[\tau,2\tau)}\text{ hits
}B)\leq d(\tau)+\frac{\tau}{\alpha(V)}\operatorname{cap}_{G}^{0}(B)$ and

$P^{z}((X_{t})_{t\in[0,\tau]\cup[2\tau,t]}\text{ does not hit }B)\geq
P^{z}(T_{B}>\tau)(P^{\pi}(T_{B}>t-2\tau)-d(\tau))$

we get that

$\displaystyle P^{z}(T_{B}>t)$ $\displaystyle\geq
P^{z}(T_{B}>\tau)(P^{\pi}(T_{B}>t-2\tau)-d(\tau))-d(\tau)-\mbox{$\frac{\tau}{\alpha(V)}$}\operatorname{cap}_{G}^{0}(B)$
$\displaystyle\geq
P^{z}(T_{B}>\tau)\,P^{\pi}(T_{B}>t)-2d(\tau)-\mbox{$\frac{\tau}{\alpha(V)}$}\operatorname{cap}_{G}^{0}(B).$

∎

We will use the previous lemma to show that under appropriate assumptions the
distribution of the first entrance time and its location are close in total
variation norm to a product distribution of the exponential and an appropriate
discrete distribution.

Let $B\subset V$, $\tau>0$,
$\lambda=\frac{1}{\alpha(V)}\operatorname{cap}^{\tau}_{G}(B)$,
$\lambda_{0}=\frac{1}{\alpha(V)}\operatorname{cap}^{0}_{G}(B)$

$\displaystyle\kappa=\kappa_{G,B,\tau}=4\frac{\lambda_{0}}{\lambda}\bigl{(}d(\tau)+\tau\,\lambda_{0}\bigr{)}$
(9)

and suppose that $-\log\kappa\geq 2\tau\lambda$ and
$2\lambda_{0}\leq\pi(B^{c})$, then one has

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle\Bigl{(}P^{\pi}_{G}\circ(T_{B},X_{T_{B}})^{-1},\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\operatorname{cap}_{G}^{\tau}(B)}$}e_{B,G}^{\tau}\Bigr{)}\leq\pi(B)+2\tau\lambda_{0}+\kappa(1+\log
1/\kappa).$

######  Remark 2.2.

We note that $\lambda_{0}\geq\lambda$ so that $2\tau\lambda_{0}\leq\kappa/2$
and the estimate of Proposition 2 entails that under the same assumptions

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle\Bigl{(}P^{\pi}_{G}\circ(T_{B},X_{T_{B}})^{-1},\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\lambda}$}e_{B,G}^{\tau}\Bigr{)}\leq\pi(B)+\kappa\bigl{(}\mbox{$\frac{3}{2}$}+\log\mbox{$\frac{1}{\kappa}$}\bigr{)}.$

Moreover, for the conditional distribution
$\pi_{B^{c}}=\pi(B^{c})^{-1}\pi|_{B^{c}}$ we get that

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle\Bigl{(}P^{\pi_{B^{c}}}_{G}\circ(T_{B},X_{T_{B}})^{-1},\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\lambda}$}e_{B,G}^{\tau}\Bigr{)}\leq\kappa\bigl{(}\mbox{$\frac{3}{2}$}+\log\mbox{$\frac{1}{\kappa}$}\bigr{)}\pi(B^{c})^{-1}.$

###### Proof.

We let $\xi_{t}=P_{G}^{\pi}(T_{B}>t)$ for $t\geq 0$ and observe that by (a)
$\xi_{t}$ is continuously differentiable since the distribution of $T_{B}$ has
no atoms outside of $0$. Further we get with Lemma 2.1 (a) that

$-\dot{\xi}_{t}=\sum_{y\in B}\pi_{y}\sum_{z\in
B^{c}}L(y,z)\,P_{G}^{z}(T_{B}>t)$

Using (b) we thus obtain with $\eta:=2d(\tau)+2\tau\lambda_{0}$ that for
$t\geq 2\tau$

$-\dot{\xi}_{t}\leq\lambda\xi_{t}+\underbrace{\sum_{y\in B}\pi_{y}\sum_{z\in
B^{c}}L(y,z)}_{=\lambda_{0}}\ \eta.$

Moreover,

$\xi_{2\tau}\geq\pi(B^{c})-2\tau\lambda_{0}.$

Consequently, $(\xi_{t})_{t\geq 2\tau}$ is larger than the solution to the
inhomogeneous linear differential equation

$-\dot{\zeta}_{t}=\lambda\zeta_{t}+\lambda_{0}\,\eta,\ \
\zeta_{2\tau}=\pi(B^{c})-2\tau\lambda_{0}$

whose unique solution is $(\zeta_{t})_{t\geq 2\tau}$ given by

$\displaystyle\zeta_{t}$
$\displaystyle=(\pi(B^{c})-2\tau\lambda_{0})e^{-\lambda(t-2\tau)}-\lambda_{0}\eta\lambda^{-1}(1-e^{-\lambda(t-2\tau)})$
$\displaystyle\geq e^{2\tau\lambda}(\pi(B^{c})-2\tau\lambda_{0})e^{-\lambda
t}-\lambda_{0}\eta/\lambda.$

Let $\alpha,\beta:(0,\infty)\times B\to[0,\infty)$ denote the densities of
$P_{G}^{\pi}\circ(T_{B},X_{T_{B}})^{-1}$ (ignoring the atom at zero) and
$\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\lambda}$}e_{B,G}^{\tau}$,
respectively. Then

$\displaystyle\mathrm{err}:=$ $\displaystyle\
d_{\mathrm{TV}}\Bigl{(}P^{\pi}_{G}\circ(T_{B},X_{T_{B}})^{-1},\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\lambda}$}e_{B,G}^{\tau}\Bigr{)}$
$\displaystyle=$ $\displaystyle\ 1-\int_{0}^{\infty}\sum_{y\in
B}\alpha(s,y)\wedge\beta(s,y)\,\mathrm{d}s.$

Again by Lemma 2.1, we get that for $s\geq 2\tau$,

$\displaystyle\begin{split}\alpha(s,y)&\geq\pi_{y}\sum_{z\in
B^{c}}L(y,z)\bigl{(}P^{z}(T_{B}>\tau)\,\xi_{s}-\eta\bigr{)}\\\
&\geq\pi_{y}\sum_{z\in
B^{c}}L(y,z)\bigl{(}P^{z}(T_{B}>\tau)\,(e^{2\tau\lambda}(\pi(B^{c})-2\tau\lambda_{0}e^{-\lambda
s}-\lambda_{0}\,\eta/\lambda)-\eta\bigr{)}\\\
&=(\pi(B^{c})-2\tau\lambda_{0})e^{2\tau\lambda}\beta(s,y)\\\
&\qquad-\pi_{y}\sum_{z\in
B^{c}}L(y,z)\bigl{(}P^{z}(T_{B}>\tau)\,\lambda_{0}\,\eta/\lambda+\eta\bigr{)}.\end{split}$
(10)

Note that

$\sum_{y\in B}\pi_{y}\sum_{z\in
B^{c}}L(y,z)\bigl{(}P^{z}(T_{B}>\tau)\,\lambda_{0}\,\eta/\lambda+\eta\bigr{)}\leq
2\lambda_{0}\eta=\kappa\lambda.$

Letting
$\rho:=\bigl{(}(\pi(B^{c})-2\tau\lambda_{0})e^{2\tau\lambda}\bigr{)}\wedge 1$
we get with (10) that

$\sum_{y\in B}\alpha(s,y)\wedge\beta(s,y)\geq\rho\lambda e^{-\lambda
s}-\kappa\lambda.$

We set $t=\lambda^{-1}\log(\rho/\kappa)$ which is by assumption bigger or
equal to $2\tau$ and obtain that and

$\mathrm{err}\leq 1-\int_{2\tau}^{t}(\rho\lambda e^{-\lambda
s}-\kappa\lambda)\,\mathrm{d}s=1-\rho e^{-2\tau\lambda}+\underbrace{\rho
e^{-t\lambda}}_{=\kappa}+\kappa\underbrace{\lambda(t-2\tau)}_{\leq\log(1/\kappa)}$

We recall that $\lambda\leq\lambda_{0}$ so that by definition of $\rho$

$1-\rho
e^{-2\tau\lambda}=\max(\underbrace{1-(\pi(B^{c})-2\tau\lambda_{0}}_{=\pi(B)+2\tau\lambda_{0}},\underbrace{1-e^{-2\tau\lambda}}_{\leq
2\tau\lambda})\leq\pi(B)+2\tau\lambda_{0}$

which entails the result. ∎

In our application we need a combined estimate for the distribution of the
path of length $\tau$ and the next macroscopic entrance event. In the next
step, this will allow us to couple the visiting measures with an appropriate
Poisson point process.

Under the same assumptions as in Proposition 2 one has

$\displaystyle d_{\mathrm{TV}}\bigl{(}$ $\displaystyle
P^{z}\circ((X_{t})_{t\in[0,\tau]},T_{B}^{\tau},X_{T_{B}^{\tau}})^{-1},P^{z}_{G}\circ((X_{t})_{t\in[0,\tau]})^{-1}\otimes\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\operatorname{cap}_{G}^{\tau}(B)}$}e_{B,G}^{\tau}\bigr{)}$
$\displaystyle\leq 2\pi(B)+\kappa(3+\log 1/\kappa),$

where

$T_{B}^{\tau}=\inf\\{t\geq\tau:X_{t}\in B\\}.$

###### Proof.

We recall that by Proposition 2

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle\bigl{(}P^{\pi}\circ(T_{B},X_{T_{B}})^{-1},\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\lambda}$}e_{B,G}^{\tau}\bigr{)}$
$\displaystyle\leq\pi(B)+2\tau\lambda_{0}+\kappa(1+\log 1/\kappa)$

Moreover, for every $z\in V$

$d_{\mathrm{TV}}\bigl{(}P^{z}\circ(T_{B}^{\tau}-\tau,X_{T_{B}^{\tau}})^{-1},P^{\pi}\circ(T_{B},X_{T_{B}})^{-1}\bigr{)}\leq
d(\tau)$

so that

$\displaystyle d_{\mathrm{TV}}\bigl{(}$ $\displaystyle
P^{z}\circ((X_{t})_{t\in[0,\tau]},T_{B}^{2\tau}-2\tau,X_{T_{B}^{2\tau}}))^{-1},$
$\displaystyle P^{z}\circ((X_{t})_{t\in[0,\tau]})^{-1}\otimes
P^{\pi}\circ(T_{B},X_{T_{B}})^{-1}\bigr{)}\leq d(\tau).$

Since

$\displaystyle P^{z}$
$\displaystyle((T_{B}^{2\tau},X_{T_{B}^{2\tau}})\not=(T_{B}^{\tau},X_{T^{\tau}_{B}}))=P^{z}((X_{t})_{t\in[\tau,2\tau)}\text{
hits }B)$ $\displaystyle\leq d(\tau)+\pi(B)+\tau\lambda_{0}$

we also get that

$\displaystyle d_{\mathrm{TV}}\bigl{(}$ $\displaystyle
P^{z}\circ((X_{t})_{t\in[0,\tau]},T_{B}^{\tau}-2\tau,X_{T_{B}^{\tau}})^{-1},$
$\displaystyle P^{z}\circ((X_{t})_{t\in[0,\tau]})^{-1}\otimes
P^{\pi}\circ(T_{B},X_{T_{B}})^{-1}\bigr{)}\leq
2d(\tau)+\pi(B)+\tau\lambda_{0}.$

Altogether we thus get that

$\displaystyle d_{\mathrm{TV}}\bigl{(}$ $\displaystyle
P^{z}\circ((X_{t})_{t\in[0,\tau]},T_{B}^{\tau}-2\tau,X_{T_{B}^{\tau}})^{-1},P^{z}\circ((X_{t})_{t\in[0,\tau]})^{-1}\otimes\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\lambda}$}e_{B,G}^{\tau}\bigr{)}$
$\displaystyle\leq 2d(\tau)+2\pi(B)+3\tau\lambda_{0}+\kappa(1+\log 1/\kappa)$

Shifting the exponential distribution $\mathrm{Exp}(\lambda)$ by $2\tau$ time
units causes another perturbation that is bounded by $2\tau\lambda\leq
2\lambda_{0})$ and we finally get that

$\displaystyle d_{\mathrm{TV}}\bigl{(}$ $\displaystyle
P^{z}\circ((X_{t})_{t\in[0,\tau]},T_{B}^{\tau},X_{T^{\tau}_{B}})^{-1},P^{z}\circ((X_{t})_{t\in[0,\tau]})^{-1}\otimes\mathrm{Exp}(\lambda)\otimes\mbox{$\frac{1}{\lambda}$}e_{B,G}^{\tau}\bigr{)}$
$\displaystyle\leq 2d(\tau)+2\pi(B)+5\tau Q(B)+\kappa(1+\log 1/\kappa).$

∎

Let $G\in\mathbb{G}$ be a finite graph and let $\tau>0$, $B\subset V$ and
$a>0$. We denote by $\Xi$ the $(B,\tau,a)$-local visits of an $L_{G}$-process
$X$ started in equilibrium. Further let $\kappa$ be as in Prop. 2.

We denote by $\Gamma$ the Poisson point process on $[0,\infty)\times W_{+}$
with intensity measure

$\frac{a}{\alpha(V)}\,\mathrm{Leb}|_{[0,\infty)}\otimes\bigl{(}P^{e_{B,G}^{\tau}}_{G}\circ((X_{t})_{t\in[0,\tau]})^{-1}\bigr{)}.$

Then for every $t\geq 0$ and $\rho\in\mathbb{N}$

$d_{\mathrm{TV}}(\Xi|_{[0,t]\times W_{+}},\Gamma|_{[0,t]\times W_{+}})\leq
c(G,B,\tau)\,\rho+2^{-\rho}e^{a\operatorname{cap}_{G}^{\tau}(B)t/\alpha(V)},$

where

$c(G,B,\tau)=2\pi(B)+\kappa(3+\log 1/\kappa).$

The proof is based on the following lemma whose proof is straight-forward and
left to the reader.

######  Lemma 2.3.

For $i=1,2$ let $A_{i}$ and $B_{i}$ be random variables taking values in the
same Polish space. Then

$d_{\mathrm{TV}}(\mathbb{P}_{A_{1},A_{2}},\mathbb{P}_{B_{1},B_{2}})\leq
d_{\mathrm{TV}}(\mathbb{P}_{A_{1}},\mathbb{P}_{B_{1}})+\mathbb{E}[d_{\mathrm{TV}}(\mathbb{P}_{A_{2}|A_{1}}(A_{1},\cdot),\mathbb{P}_{B_{2}|B_{1}}(A_{1},\cdot))],$

where $\mathbb{P}_{A_{2}|A_{1}}$ and $\mathbb{P}_{B_{2}|B_{1}}$ are arbitrary
regular conditional distributions.

###### Proof of Proposition 2.

As in Section 1.2, we denote by $T_{1},\dots$ and $Y_{1},\dots$ the
$(B,\tau)$-entrance times and $(B,\tau)$-visits of $X$, respectively. We
control the total variation distance between the distributions of

$(T_{1},Y_{1},\dots,Y_{\rho-1},T_{\rho}-T_{\rho-1})$

and

$(S_{1},Z_{1},\dots,S_{\rho-1},Z_{\rho-1},S_{\rho}),$

where $S_{1},\dots$ and $Z_{1},\dots$ are independent random variables, the
former ones being
$\mathrm{Exp}(a\operatorname{cap}^{\tau}_{G}(B)/\alpha(V))$-distributed and
the latter ones being
$P^{\frac{1}{\operatorname{cap}_{G}^{\tau}(B)}e_{B,G}^{\tau}}_{G}\circ((X_{t})_{t\in[0,\tau]})^{-1}$-distributed
processes. It is more convenient to control the total variation distance of
the extended vectors

${\bf
Y}^{\rho}:=(T_{1},Y_{1}(0),Y_{1},T_{2}-T_{1},Y_{2}(0),\dots,Y_{\rho-1},T_{\rho}-T_{\rho-1},Y_{\rho}(0))$

and

${\bf
Z}^{\rho}:=(S_{1},Z_{1}(0),Z_{1},S_{2},Z_{2}(0),\dots,Z_{\rho-1},S_{\rho},Z_{\rho}(0)).$

We choose $A_{1}={\bf Y}^{\rho-1}$,
$A_{2}=(Y_{\rho-1},T_{\rho}-T_{\rho-1},Y_{\rho}(0))$, $B_{1}={\bf Z}^{\rho-1}$
and $B_{2}=(Z_{\rho-1},S_{\rho},Z_{\rho}(0))$ and apply Proposition 2 together
with Lemma 2.3 to infer that

$d_{\mathrm{TV}}({\bf Y}^{\rho},{\bf Z}^{\rho})\leq d_{\mathrm{TV}}({\bf
Y}^{\rho-1},{\bf Z}^{\rho-1})+c(G,B,\tau).$

Iteration of this argument yields together with an application of Proposition
2 that

$d_{\mathrm{TV}}({\bf Y}^{\rho},{\bf Z}^{\rho})\leq
d_{\mathrm{TV}}((T_{1},Y_{1}(0)),(S_{1},Z_{1}(0)))+(\rho-1)c(G,B,\tau)\leq\rho\,c(G,B,\tau).$

Note that the Poisson point process $\Gamma$ has the same distribution as

$\sum_{k=1}^{\infty}\delta_{(S_{1}+\ldots+S_{k},Z_{k})}$

so that for positive $\theta$

$\displaystyle d_{\mathrm{TV}}(\Xi|_{[0,t]\times D_{+}},$
$\displaystyle\Gamma|_{[0,t]\times D_{+}})\leq d_{\mathrm{TV}}({\bf
Y}^{\rho},{\bf Z}^{\rho})+\mathbb{P}(S_{1}+\ldots+S_{\rho}\leq t)$
$\displaystyle\leq mc+\mathbb{E}[e^{-\theta S_{1}}]^{\rho}/e^{-\theta t}=\rho
C+\Bigl{(}\frac{1}{1+\alpha(V)\theta/(a\operatorname{cap}_{G}^{\tau}(B)})\Bigr{)}^{\rho}e^{\theta
t}.$

Choosing $\theta=a\operatorname{cap}_{G}^{\tau}(B)/\alpha(V)$ yields the
result. ∎

##  3\. Proof of the main result

As we have seen in Proposition 2 that under appropriate mixing conditions the
visiting measure is related to a Poisson point process. In the view of local
approximation the equilibrium measures appearing in the intensity measures are
in a certain sense global properties. In oder to establish coupling we need to
replace these quantities by quantities that can be derived via exploration.

We introduce the concept for a fixed general finite graph
$G^{o}\in\mathbb{G}^{\mathrm{root}}$. Later we will apply the results on the
sequence of random finite graphs.

######  Construction 3.1.

Beyond a fixed rooted graph $G^{o}\in\mathbb{G}^{\mathrm{root}}$ the
construction depends on four parameters $m,R\in\mathbb{N}$ and
$\tau,\mathfrak{a}>0$.

Let $X^{(1)}=(X^{(1)}_{t})_{t\in[0,2\tau]}$,
$X^{(2)}=(X^{(2)}_{t})_{t\in[0,2\tau]},\dots$ be independent
$P^{o}_{G}$-distributed processes (killed at time $2\tau$). Based on the
trajectories we build two stacks of paths. First we use the first $m$
trajectories $X^{(1)},\dots,X^{(m)}$ to build stacks labeled by the vertices
in $\partial V^{o}[R+1]$. For this we briefly write $T_{r}^{(k)}$
$(r\in\\{R,R+1\\})$ for the first hitting time of $X^{(k)}$ of $\partial
V^{o_{n}}[r]$ and put for every $k=1,\dots,m$ with $T_{R+1}^{(k)}\leq\tau$ the
path $(X^{(k)}_{T^{(k)}_{R+1}+t})_{t\in[0,\tau]}$ on the
$X^{(k)}_{T^{(k)}_{R+1}}$-stack. The second stack makes use of the
trajectories from index $m+1$ on. We iteratively put for every $k=m+1,\dots$
with $T_{R}^{(k)}\leq\tau$ the path $(X^{(k)}_{T^{(k)}_{R}+t})_{t\in[0,\tau]}$
on the $X^{(k)}_{T^{(k)}_{R}}$-stack.

Note that by construction the number of trajectories on the first kind of
stacks forms a multinomially-distributed random variable with $m$-draws and
success probabilities

$P^{o}_{G}(T_{\partial V_{n}^{o}[R+1]}\leq\tau,X_{T_{\partial
V^{o}[R+1]}}=v).$

Moreover, every stack $v\in\partial V^{o}[R]$ (of the second kind) has
infinitely many paths since $P^{o}_{G}(T_{\partial
V_{n}^{o}[R]}\leq\tau,X_{T_{\partial V^{o}[R]}}=v)$ is strictly positive.
Given the sizes of the stacks of the first kind, all stacks contain
independent $L_{G}$-Makrov processes on $[0,\tau]$ started in the label of the
respective stack.

We declare every trajectory on one of the stacks $v$ of first kind as
$v$-escape if the trajectory does not hit $V^{o}[R]$ and we denote by
$\mathfrak{s}_{v}$ the relative number of $v$-escapes on the $v$-stack (with
the convention that $\mathfrak{s}_{v}=0$, if the stack is empty). We let, for
every vertex $v\in V$,

$\mathfrak{e}_{V^{o}[R],G}^{\tau}(v)=\operatorname{\mathbbm{1}}_{V^{o}[R]}(v)\,\alpha(v)\sum_{w\in\partial
V^{o}[R+1]}L_{v,w}^{G}\mathfrak{s}_{w}.$

We introduce a doubly stochastic Poisson point process (Cox process) $\gamma$
on $[0,\infty)\times\partial V^{o}[R]$ that is conditionally on the first $m$
trajectories a Poisson point process with density
$\mathfrak{a}^{-1}\mathrm{Leb}|_{[0,\infty)}\otimes\mathfrak{e}_{V^{o}[R],G}^{\tau}$
and is independent of the paths $m+1,\dots$. Next, we construct a point
process $\Gamma$ on $[0,\infty)\times W_{+}$ by ordering for each
$v\in\partial V^{o}[R]$ the epochs of $\gamma$ on $[0,\infty)\times\\{v\\}$
increasingly and adding for the $k$-th point, say at time $s_{k}$, the tuple
consisting of $s_{k}$ and the $k$-th trajectory of the $v$-stack to $\Gamma$.
By construction the trajectories on the stacks are independent of $\gamma$ and
we get that $\Gamma$ is a Cox-process that is, given the first $m$
trajectories, a Poisson point process with random intensity measure

$\mathfrak{a}^{-1}\mathrm{Leb}|_{[0,\infty)}\otimes
P^{\mathfrak{e}_{V^{o}[R],G}^{\tau}}\circ((X_{t})_{t\in[0,\tau]})^{-1}.$

Let $G^{o}\in\mathbb{G}$ be a finite graph, $m,R\in\mathbb{N}$ and
$\tau,\mathfrak{a},a,\sigma>0$. We assume the assumptions of Proposition 2 and
choose $c_{G,V^{o}[R],\tau}$ as in Proposition 2. We denote by $\Xi$ the
$(V^{o}[R],\tau,a)$-visiting measure of a $P_{G}$-Markov process started in
equilibrium and by $\Gamma$ the Cox-process constructed in Construction 3.1.
Then one has

$\displaystyle d_{\mathrm{TV}}$ $\displaystyle(\Xi|_{[0,\sigma]\times
W_{+}},\Gamma|_{[0,\sigma]\times W_{+}})$ $\displaystyle\leq$
$\displaystyle\,\mathbb{E}\Bigl{[}1\wedge\bigl{(}c_{G,V^{o}[R],\tau}\rho+2^{-\rho}e^{a\operatorname{cap}_{G}^{\tau}(V^{o}[R])\sigma/\alpha(V)}+\sigma\bigl{\|}\mathfrak{a}^{-1}\mathfrak{e}_{V^{o}[R],G}^{\tau}-\mbox{$\frac{a}{\alpha(V)}$}e_{V^{o}[R],G}^{\tau}\bigr{\|}_{1}\bigr{)}\Bigr{]},$

where $\|\cdot\|_{1}$ denotes the $\ell^{1}$-norm and

###### Proof.

By Proposition 2 we have that

$d_{\mathrm{TV}}(\Xi|_{[0,\sigma]\times W_{+}},\bar{\Gamma}|_{[0,\sigma]\times
W_{+}})\leq
c_{G,B,\tau}m+2^{-m}e^{a\operatorname{cap}_{G}^{\tau}(V^{o}[R])t/\alpha(V)},$

where $\bar{\Gamma}$ is the Poisson point process as in the latter
proposition. Recalling that $\Gamma$ is a Cox-process that, given the first
$m$ trajectories $X^{(1)},\dots,X^{(m)}$, is a Poisson point process with
intensity measure

$\mathfrak{a}^{-1}\mathrm{Leb}|_{[0,\infty)}\otimes
P^{\mathfrak{e}_{V^{o}[R],G}^{\tau}}\circ((X_{t})_{t\in[0,\tau]})^{-1}$

we conclude that

$d_{\mathrm{TV}}(\bar{\Gamma}|_{[0,\sigma]\times
W_{+}},\Gamma|_{[0,\sigma]\times
W_{+}})\leq\mathbb{E}\Bigl{[}1\wedge\bigl{(}\sigma\bigl{\|}\mathfrak{a}^{-1}\mathfrak{e}_{V^{o}[R],G}^{\tau}-\mbox{$\frac{a}{\alpha(G)}$}e_{V^{o}[R],G}^{\tau}\bigr{\|}_{1}\bigr{)}\Bigr{]}.$

The triangle inequality yields the statement of the proposition. ∎

######  Remark 3.2.

Applying a diagonalization argument one can show that under the same
assumptions as in the previous proposition there exist monotone
$\mathbb{N}$-valued sequences $(R^{\prime}_{n})_{n\in\mathbb{N}}$ and
$(\sigma_{n})_{n\in\mathbb{N}}$ tending to infinity such that the statement of
the theorem still holds when replacing $R^{\prime}$ by $R^{\prime}_{n}$ and
$\sigma$ by $\sigma_{n}$.

###### Proof of Theorem 1.3.

To establish the wanted coupling we do various couplings in between.

First let $\Gamma$ denote a Cox-process with points in $[0,\infty)\times
W_{+}$ that is, given $G^{o}$, a Poisson point process with intensity measure

$\frac{1}{\mathfrak{a}}\mathrm{Leb}|_{[0,\infty)}\otimes
P^{e_{V^{o}[R],G}}\circ((X_{t})_{t\in[0,\infty)})^{-1}.$

We will apply explorations as in Example 1.6 that depend on an index
$n\in\mathbb{N}$. We choose an increasing $\mathbb{N}$-valued sequence
$(m_{n})_{n\in\mathbb{N}}$ tending to infinity with
$m_{n}\ell_{n}^{\prime}\leq\ell_{n}$ and

$m_{n}P^{o}_{G}(\\#\mathrm{\,range}(X_{t})_{t\in[0,2\tau_{n}]}>\ell_{n}^{\prime})\to
0,\text{ in probability}.$

For $n\in\mathbb{N}$ we let $K_{n}$ be the $2\tau_{n}$-exploration along the
Markov process and we denote by
$X^{(n,1)}=(X^{(n,1)}_{t})_{t\in[0,2\tau_{n}]},X^{(n,2)}=(X^{(n,2)}_{t})_{t\in[0,2\tau_{n}]},\dots$
càdlàg processes that are, given $G_{n}$, independent $P^{o}_{G}$-distributed
processes (constrained on the time interval $[0,2\tau_{n}]$) and we denote by
${\mathfrak{E}}_{\ell_{n}}^{n}$ the respective $K_{n}$-exploration after
$\ell_{n}$ steps.

We apply Construction 3.1 with parameters $m_{n},R,\tau_{n},\mathfrak{a}$ for
the processes $X^{(n,1)}$, $X^{(n,2)},\dots$ and let ${\mathfrak{e}}^{(n)}$ be
the estimate of the equilibrium measure $e^{\tau_{n}}_{V^{o}[R],G}$ based on
the first $m_{n}$ trajectories $X^{(n,1)},\dots,X^{(n,m_{n})}$ as introduced
in the construction. Moreover, we denote by $\gamma_{n}$ and $\Gamma_{n}$ the
respective point processes. Then given $X^{(n,1)},\dots,X^{(n,m_{n})}$,
$\Gamma_{n}$ is a Poisson point process with intensity

$\frac{1}{\mathfrak{a}}\mathrm{Leb}|_{[0,\infty)}\otimes
P^{\mathfrak{e}^{(n)}}\circ((X_{t})_{t\in[0,\tau_{n}]})^{-1}.$

Consequently,

$\displaystyle d_{\mathrm{TV}}\bigl{(}$
$\displaystyle(G^{o},\Gamma|_{[0,\sigma]\times
W_{+}}\circ\mathrm{conf}_{[0,\tau_{n}]}^{-1}),(G^{o},\Gamma_{n}|_{[0,\sigma]\times
W_{+}})\bigr{)}$
$\displaystyle\qquad\leq\mathbb{E}\bigl{[}1\wedge\bigl{(}\sigma\|e_{V^{o}[R],G}-\mathfrak{e}^{(n)}\|_{\ell_{1}}\bigr{)}\bigr{]}$

We have a close look at the estimate $\mathfrak{e}^{(n)}$. Given $G^{o}$ it is
the weighted sum of the estimates of the escape probabilities. Since
$m_{n},\tau_{n}\to\infty$ we can apply the law of large numbers (given
$G^{o}$) and obtain that
$\|\mathfrak{e}_{V^{o}[R],G}^{\tau_{n}}-e_{V^{o}[R],G}^{\tau_{n}}\|_{\ell_{1}}\to
0$, in probability. Moreover, by monotone convergence also
$\|e_{V^{o}[R],G}^{\tau_{n}}-e_{V^{o}[R],G}\|_{\ell_{1}}\to 0$, almost surely.
Hence, we can couple $(G^{o},\Gamma)$ and $(G^{o},\Gamma_{n})$ such that, with
high probability, $(G^{o},\Gamma|_{[0,\sigma]\times
W_{+}}\circ\mathrm{conf}_{[0,\tau_{n}]}^{-1})=(G^{o},\Gamma_{n}|_{[0,\sigma]\times
W_{+}})$.

Next, we also apply Construction 3.1 for every $n\in\mathbb{N}$ onto the graph
$G^{o_{n}}_{n}$, again with parameters $m_{n},R,\tau_{n},\mathfrak{a}$: given
$G_{n}^{o_{n}}$ we denote by
$\bar{X}^{(n,1)}=(\bar{X}^{(n,1)}_{t})_{t\in[0,2\tau_{n}]}$,
$\bar{X}^{(n,2)}=(\bar{X}^{(n,2)}_{t})_{t\in[0,2\tau_{n}]},\dots$ independent
$P^{o_{n}}_{G_{n}}$-distributed processes and by $\bar{\gamma}_{n}$ and
$\bar{\Gamma}_{n}$ the respective Cox-process defined as in the construction
on the basis of the trajectories $\bar{X}^{(n,1)},\dots$. We denote by $K_{n}$
the exploration rule associated to $2\tau_{n}$-exploration along the Markov
process as introduced in Example 1.6 and write for the induced $\ell_{n}$-step
$K_{n}$-explorations $\mathfrak{E}_{\ell_{n}}^{(n)}$ and
$\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ when applied to $G^{o}$ along the paths
$X^{(1,n)},\dots$ and to $G^{o_{n}}_{n}$ along the paths
$\bar{X}^{(1,n)},\dots$, respectively. We denote by $\mathcal{V}_{n}$ and
$\bar{\mathcal{V}}_{n}$ the disclosed areas under
$\mathfrak{E}_{\ell_{n}}^{(n)}$ and $\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ and
note that, with high probability, there exists an isomorphism $\varphi_{n}$
taking the $\bar{\mathcal{V}}_{n}$-disclosed graph of $G_{n}^{o_{n}}$ to the
$\mathcal{V}_{n}$-disclosed graph of $G^{o}$. If, additionally, the $2m_{n}$
trajectories $X^{(n,1)},\dots,X^{(n,2m_{n})}$ have combined range less than or
equal to $\ell_{n}$, then the latter trajectories are obtained by applying
$\varphi_{n}$ onto the paths $\bar{X}^{(n,1)},\dots,\bar{X}^{(n,2m_{n})}$.
This happens with high probability, since

$\mathbb{P}(\\#\mathcal{V}_{n}>\ell_{n})\leq\mathbb{E}\bigl{[}\bigl{(}m_{n}P^{o}_{G}\bigl{(}\\#\,\mathrm{range}\bigl{(}(X_{t})_{t\in[0,2\tau_{n}]}\bigr{)}>\ell_{n}^{\prime}\bigr{)}\bigr{)}\wedge
1\bigr{]}\to 0$

In the latter case, in particular, $\varphi_{n}$ takes
$\bar{\mathfrak{e}}^{(n)}$ to ${\mathfrak{e}}^{(n)}$ and we can couple
$\gamma_{n}$ and $\bar{\gamma}_{n}$ in such a way that $\varphi_{n}$ takes
$\bar{\gamma}_{n}$ to $\gamma_{n}$. Note that $m_{n}\to\infty$ implies that
the minimal number (taken over all boundary vertices $v\in\partial V^{o}[R]$)
of trajectories with index in $m_{n}+1,\dots 2m_{n}$ starting in a boundary
vertex tends to infinity, in probability, so that with high probability
$\Gamma_{n}|_{[0,\sigma]\times W_{+}}$ can be constructed from
$\gamma_{n}|_{[0,\sigma]\times W_{+}}$ on the basis of the trajectories
$m_{n}+1,\dots,2m_{n}$. We thus get that, with high probability, $\varphi_{n}$
takes $\bar{\Gamma}_{n}|_{[0,\sigma]\times W_{+}}$ to
$\Gamma_{n}|_{[0,\sigma]\times W_{+}}$.

It remains to couple $(G_{n}^{o_{n}},\Gamma_{n})$ and
$(G_{n}^{o_{n}},\Xi_{n})$. As consequence of Proposition 3, we have that

$\displaystyle d_{\mathrm{TV}}((G_{n}^{o_{n}},\Xi_{n}|_{[0,\sigma]\times
W_{+}}),(G_{n}^{o_{n}},\bar{\Gamma}_{n}|_{[0,\sigma]\times
W_{+}}))\leq\mathbb{E}\bigl{[}1\wedge\bar{\delta}_{n}\bigr{]},$ (11)

where

$\displaystyle\bar{\delta}_{n}$
$\displaystyle=c_{G_{n},V_{n}^{o_{n}}[R],\tau_{n}}\rho+2^{-\rho}e^{a_{n}\operatorname{cap}_{G_{n}}^{\tau_{n}}(V_{n}^{o_{n}}[R])\sigma/\alpha_{n}(V)}$
$\displaystyle\qquad+\sigma\bigl{\|}\mathfrak{a}^{-1}\mathfrak{e}_{V_{n}^{o_{n}}[R],G_{n}}^{\tau_{n}}-\mbox{$\frac{a_{n}}{\alpha_{n}(V_{n})}$}e_{V_{n}^{o_{n}}[R],G_{n}}^{\tau_{n}}\bigr{\|}_{\ell_{1}},$

if

$\displaystyle-\log\kappa_{G_{n},V_{n}^{o_{n}}[R],\tau_{n}}\geq
2\tau_{n}\frac{\operatorname{cap}_{G_{n}}^{\tau_{n}}(V_{n}^{o_{n}}[R])}{\alpha_{n}(V_{n})}\text{
\ and \
}2\operatorname{cap}^{0}_{G_{n}}(V^{o_{n}}_{n}[R])\leq\alpha_{n}(V^{o_{n}}_{n}[R]^{c}),$
(12)

and $\bar{\delta}_{n}=1$, otherwise. It remains to verify that the right hand
side of (11) tends to zero. First we show that
$\|\mathfrak{e}^{\tau_{n}}_{V_{n}^{o_{n}}[R],G_{n}}-e_{V_{n}^{o_{n}}[R],G_{n}}\|_{\ell_{1}}$
tends to zero, in probability. Note that with high probability the exploration
used in the coupling of $\bar{\Gamma}_{n}$ and $\Gamma_{n}$ unveils the
$R^{\prime}$-neighbourhood of the root so that, with high probability,
$\varphi_{n}$ takes the $R^{\prime}$ neighbourhood of $G^{o_{n}}_{n}$ to the
one of $G^{o}$. Moreover, since $m_{n}\to\infty$ the minimal number of
trajectories on one of the stacks of first kind tends to infinity, in
probability. Since given the stack sizes the estimates for the equilibrium
measure is unbiased as long as the stack is nonempty we get that

$\|\mathfrak{e}^{\tau_{n}}_{V_{n}^{o_{n}}[R],G_{n}}-e_{V_{n}^{o_{n}}[R],G_{n}}\|_{\ell_{1}}\to
0,\text{ \ in probability}.$

Since $\alpha_{n}(V_{n})/a_{n}\to\mathfrak{a}>0$, in probability, we also get
that

$\displaystyle\Bigl{\|}\mathfrak{a}^{-1}\mathfrak{e}^{\tau_{n}}_{V_{n}^{o_{n}}[R],G_{n}}-\frac{a_{n}}{\alpha_{n}(V_{n})}e_{V_{n}^{o_{n}}[R],G_{n}}\Bigr{\|}_{\ell_{1}}\to
0,\text{ \ in probability.}$ (13)

Moreover, we have, in probability,

$\displaystyle\pi_{n}(V^{o_{n}}_{n}[R])$
$\displaystyle=\frac{\alpha_{n}(V^{o_{n}}_{n}[R])}{\alpha_{n}(V_{n})}\to
0\text{ \ \ and}$ $\displaystyle\kappa_{G_{n},V^{o_{n}}_{n}[R],\tau_{n}}$
$\displaystyle=4\frac{\mathrm{cap}_{G_{n}}^{0}(V^{o_{n}}_{n}[R])}{\mathrm{cap}_{G_{n}}^{0}(V^{o_{n}}_{n}[R])}\Bigl{(}d_{G_{n}}(\tau_{n})+\tau_{n}\frac{\operatorname{cap}_{G_{n}}^{\tau_{n}}(V^{o_{n}}_{n}[R])}{\alpha_{n}(V_{n})}\Bigr{)}\to
0,$

where we used that

$\alpha_{n}(V^{o_{n}}_{n}[R]),\
\operatorname{\mathbbm{1}}_{\\{\mathrm{cap}_{G_{n}}^{0}(V^{o_{n}}_{n}[R])\not=0\\}}\frac{\mathrm{cap}_{G_{n}}^{0}(V^{o_{n}}_{n}[R])}{\mathrm{cap}_{G_{n}}^{0}(V^{o_{n}}_{n}[R])}\text{
\ and \ }\operatorname{cap}_{G_{n}}^{\tau_{n}}(V^{o_{n}}_{n}[R])$

are tight (as consequence of local convergence) and
$\alpha_{n}(V_{n})\to\infty$, $\tau_{n}/\alpha_{n}(V_{n})\to 0$ and
$d_{G_{n}}(\tau_{n})\to 0$, in probability, by assumption. Consequently,
$c_{G_{n},V_{n}^{o_{n}}[R],\tau_{n}}\to 0$, in probability. We note that (12)
is satisfied with high probability, since
$\kappa_{G_{n},V^{o_{n}}_{n}[R],\tau_{n}}\to 0$,
$\tau_{n}/\alpha_{n}(V_{n})\to 0$ and
$\alpha_{n}(V_{n}^{o_{n}}[R]^{c})\to\infty$, in probability. Hence, we can
choose $\rho$ in dependence on $n$ such that
$\rho_{n}\,c_{G_{n},V_{n}^{o_{n}}[R],\tau_{n}}\to 0$, in probability, and
obtain that $\bar{\delta}_{n}\to 0$, in probability, by tightness of
$(e^{a_{n}\operatorname{cap}_{G_{n}}^{\tau_{n}}(V_{n}^{o_{n}}[R])\sigma/\alpha_{n}(V)}:n\in\mathbb{N})$
and convergence (13).

Consequently, we can also couple $(G_{n}^{o_{n}},\bar{\Gamma}_{n})$ and
$(G_{n}^{o_{n}},\Xi_{n})$ such that, with high probability,
$\bar{\Gamma}_{n}|_{[0,\sigma]\times W_{+}}=\Xi_{n}|_{[0,\sigma]\times
W_{+}}$. As observed above, with high probability, $\mathcal{V}_{n}$ and
$\bar{\mathcal{V}}_{n}$ contain the respective $R^{\prime}$-neighbourhoods and
applying the isomorphism $\varphi_{n}$ between the $\bar{\mathcal{V}}_{n}$\-
and $\mathcal{V}_{n}$-disclosed graphs of $G^{o_{n}}_{n}$ and $G^{o}$ onto the
labels in $\Xi_{n}|_{[0,\sigma]\times W_{+}}$ yields
$\Gamma|_{[0,\sigma]\times W_{+}}\circ\mathrm{conf}_{[0,\tau_{n}]}^{-1}$. ∎

###### Proof.

We choose an $\mathbb{N}$-valued sequence $(m_{n})_{n\in\mathbb{N}}$ tending
to infinity such that $m_{n}\ell_{n}^{\prime}\leq\ell_{n}$ for large $n$ and

$\lim_{n\to\infty}m_{n}\,P_{G}^{o}(\\#\text{ disc.\ of
}(X_{t})_{[0,2\tau_{n}]}>\ell_{n}^{\prime})=0,\text{ in probability.}$

We define an $n$-dependent exploration rule $K_{n}$ as follows. Starting from
the root we explore the graph along the Markov process on chain for
$\ell_{n}^{\prime}$ steps (meaning that the exploration follows the embedded
Markov chain). Once the first path, say
$(Y_{1}^{(n)}(k))_{k=0,\dots,\ell_{n}^{\prime}}$, has been generated, we
generate another path, say $(Y^{(n)}_{2}(k))_{k=0,\dots,\ell_{n}^{\prime}}$,
in the same manner starting again from the root vertex. We continue and
generate further independent paths
$(Y^{(n)}_{3}(k))_{k=0,\dots,\ell_{n}^{\prime}}$,
$(Y^{(n)}_{4}(k))_{k=0,\dots,\ell_{n}^{\prime}}$, …. Obviously, this defines
an exploration rule and the related picked edges are the ones that induce the
respective transitions of the embedded Markov chain.

Since $m_{n}\ell_{n}^{\prime}\leq\ell_{n}$ for large $n$ we can couple the
rooted graphs and their explorations in such a way that, with high
probability, the $K_{n}$-exploration $\mathfrak{E}_{\ell_{n}}^{(n)}$ of
$G^{o}$ of length $\ell_{n}$ is equal to
$\varphi_{n}(\bar{\mathfrak{E}}_{\ell_{n}}^{(n)})$, where
$\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ is a $K_{n}$-exploration of
$G_{n}^{o_{n}}$ of length $\ell_{n}$ and $\varphi_{n}$ is an appropriate
random graph isomorphism between the explorations. In the case that the latter
identity holds we say that the $n$-th coupling succeeds. We write
$(Y_{k}^{(n,1)})_{k=0,\dots,\ell_{n}^{\prime}}$,
$(Y^{(n,2)}_{k})_{k=0,\dots,\ell_{n}^{\prime}}$,…for the chains of vertices
visited by the $n$-th exploration of $G^{o}$ and
$(\bar{Y}^{(n,1)}_{k})_{k=0,\dots,\ell_{n}^{\prime}}$,
$(\bar{Y}_{k}^{(n,2)})_{k=0,\dots,\ell_{n}^{\prime}}$,…for the chains of
vertices visited by the $n$-th exploration of $G_{n}^{o_{n}}$. With high
probability, the explorations $\mathfrak{E}_{\ell_{n}}^{(n)}$, resp.
$\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$, disclose the $R^{\prime}+1$
neighbourhood of $o$ in $G$, resp. of $o_{n}$ in $G_{n}$ since
$m_{n},\ell_{n}^{\prime}\to\infty$.

Next, we relate the embedded chains $Y^{(n,j)}$ and $\bar{Y}^{(n,j)}$ to
continuous time paths: on an appropriately rich probability space we can
assume existence of independent standard exponentials
$(\rho_{j,k})_{j,k\in\mathbb{N}}$ (independent of all the random objects
considered so far) and we let for $n,j\in\mathbb{N}$ and
$k=1,\dots,\ell_{n}^{\prime}+1$,

$\tau_{0}^{(n,j)}=0\text{ \ and \
}\tau_{k}^{(n,j)}=\tau_{k-1}^{(n,j)}+\alpha_{G}(Y^{(n,j)}_{k-1})^{-1}\rho_{j,k}$

and set for $t\in[\tau_{k-1}^{(n,j)}(k-1),\tau_{k}^{(n,j)})$

$\mathcal{X}^{(n,j)}_{t}=Y_{k-1}^{(n,j)}$

and for completeness $\mathcal{X}^{(n,j)}_{t}=\partial$ if
$t\geq\tau^{(n,j)}_{\ell_{n}^{\prime}+1}$. Analogously, we define
$(\bar{\mathcal{X}}^{(n,j)}_{t})_{t\geq 0}$ by replacing in the above
definitions $\alpha_{G}$ by $\alpha_{G_{n}}$ and $Y_{j}^{(n)}$ by
$\bar{Y}_{j}^{(n)}$. Note that in the case that the coupling succeeds one
recovers the paths $\mathcal{X}^{(n,1)},\dots,\mathcal{X}^{(n,1)}$ from
$\bar{\mathcal{X}}^{(n,1)},\dots,\bar{\mathcal{X}}^{(n,1)}$ by applying the
isomorphism $\varphi_{n}$.

We construct an estimate for $P_{G}^{z}(T_{V^{o}[R]}=\infty)$. Although the
following definitions all depend on the index $n$ of the exploration of
$G^{o}$ we omit this in the notation. For $v\in V$ we call
$j\in\\{1,\dots,m_{n}\\}$ a _$v$ -indicator_, if
$(\mathcal{X}^{(n,j)}_{t})_{t\in[0,2\tau_{n}]}$ hits $v$ before time
$\tau_{n}$ and we call it a _$v$ -escape_ if, additionally, the latter path
does not return to $V^{o}[R]$ for $\tau_{n}$ time units after its first
entrance into $v$. We let for $v\in V$, $\mathfrak{e}^{(n)}_{v}$ denote the
relative number of $v$-escapes, i.e.,

$\mathfrak{e}^{(n)}_{v}=\begin{cases}\frac{\\#\\{v\text{-escapes}\\}}{\\#\\{v\text{-indicators}\\}},&\text{
if }\\{v\text{-indicators}\\}\not=\emptyset,\\\ 0,&\text{ else.}\end{cases}$

Next, we show that typically for all $v\in\partial V^{o}[R+1]$,
$\mathfrak{e}_{v}^{(n)}$ is for large $n$ close to $P^{v}_{G}((X_{t})\text{
does not hit }V^{o}[R])$. By construction, one has, conditionally on $G^{o}$,
that the chains of the $K_{n}$ explorations are independent and the respective
continuous time processes $(\mathcal{X}_{t}^{(n,1)})_{t\in[0,2\tau]},\dots$
behave like $P^{o}_{G}$-Markov processes with the modification that the
$\ell_{n}^{\prime}+1$-th jump leads to the cemetery state $\partial$. On an
appropriate probability space, one can define càdlàg processes
$(X^{(n,1)}_{t})_{t\geq 0},(X^{(n,2)}_{t})_{t\in[0,\infty)},\dots$ so that
given $G^{o}$ the processes are independent $P_{G}^{o}$-Markov processes that
satisfies for every $t\geq 0$, $X_{t}^{(n,j)}=\mathcal{X}^{(n,j)}_{t}$ iff
$X^{(n,j)}$ has less than or equal to $\ell^{\prime}$ discontinuities on
$[0,t]$. Hence,

$\displaystyle\mathbb{P}($
$\displaystyle(\mathcal{X}^{(n,j)}_{t})_{t\in[0,2\tau_{n}]}=(X^{(n,j)}_{t})_{t\in[0,2\tau_{n}]}\text{
for }j=1,\dots,m_{n})$ $\displaystyle\geq
1-\mathbb{E}\bigl{[}1\wedge(\underbrace{m_{n}P^{o}_{G}((X_{t})_{t\in[0,\tau_{n}]}\text{
has more than $\ell^{\prime}$ discontinuities})}_{\to 0,\text{ in
probability}})\bigr{]}\to 1.$

We call $j\in\\{1,\dots,m_{n}\\}$ an _idealised_ $v$-indicator or $v$-escape,
if we replace in the above definition the paths
$(\mathcal{X}_{t}^{(n,1)})_{t\in[0,2\tau_{n}]},\dots,(\mathcal{X}_{t}^{(n,m_{n})})_{t\in[0,2\tau_{n}]}$
by the “idealised” paths
$(X_{t}^{(n,1)})_{t\in[0,2\tau_{n}]},\dots,(X_{t}^{(n,m_{n})})_{t\in[0,2\tau_{n}]}$.
We denote by $e^{(n)}_{v}$ the respective relative number of $v$-escapes when
replacing the true exploration paths by the idealised ones. Note that, with
high probability, the original and the idealised indicators/escapes coincide
and $\mathfrak{e}_{v}^{(n)}$ agrees with $e_{v}^{(n)}$ for all $v$.

Obviously, given $G^{o}$, each $j\in\\{1,\dots,m_{n}\\}$ is an idealised
$v$-indicator independently of each other with probability

$P_{G}^{o}\bigl{(}(X_{t})_{t\in[0,\tau_{n}]}\text{ hits }v\bigr{)}\to
P_{G}^{o}\bigl{(}(X_{t})_{t\geq 0}\text{ hits }v\bigr{)}>0$

as $n\to\infty$. Moreover, conditionally that a $j$ is a $v$-indicators it is
additionally a $v$-escape independently with probability

$P^{v}_{G}\bigl{(}(X_{t})_{t\in[0,\tau_{n}]}\text{ does not hit
}V^{o}[R]\bigr{)}\to P^{v}_{G}\bigl{(}(X_{t})_{t\geq 0}\text{ does not hit
}V^{o}[R]\bigr{)}.$

Consequently, since $\partial V^{o}[R+1]$ is finite we get with the law of
large numbers that

$\sum_{v\in\partial V^{o}[R+1]}\bigl{|}e^{(n)}_{v}-P^{v}_{G}((X_{t})\text{
does not hit }V^{o}[R])\bigr{|}\to 0,\text{ in probability.}$

and hence also

$\sum_{v\in\partial
V^{o}[R+1]}\bigl{|}\mathfrak{e}^{(n)}_{v}-P^{v}_{G}((X_{t})\text{ does not hit
}V^{o}[R])\bigr{|}\to 0,\text{ in probability.}$

Next, we continue with a similar analysis for the paths obtained from the
$K_{n}$-exploration of $G_{n}^{o_{n}}$. As before we introduce for every
$n\in\mathbb{N}$, càdlàg processes $(\bar{X}_{t}^{(n,1)})_{t\geq
0},(\bar{X}_{t}^{(n,2)})_{t\geq 0},\dots$ such that given $G_{n}^{o_{n}}$ all
processes are independent $P_{G_{n}}^{o_{n}}$-distributed and satisfy for
$j\in\mathbb{N}$ and $t\geq 0$,
$\bar{X}_{t}^{(n,j)}=\bar{\mathcal{X}}_{t}^{(n,j)}$ iff
$\bar{\mathcal{X}}^{(n,j)}\not=\partial$ (which is equivalent to
$\bar{X}^{(n,j)}$ having less than or equal to $\ell^{\prime}_{n}$
discontinuities on $[0,t]$). In complete analogy we define the concept of
$v$-indicators and $v$-escapes and their idealised versions for the
explorations of $G_{n}^{o_{n}}$. We denote the relative number of escapes for
$v$ by $\bar{\mathfrak{e}}_{v}^{(n)}$ and for their idealised versions by
$\bar{e}_{v}^{(n)}$. If the $n$-th coupling succeeds and if the
$R^{\prime}$-neighbourhoods are disclosed by the exporations we have that $j$
is an $v$-indicator in the $G_{n}^{o_{n}}$-exploration if this is the case for
$\varphi_{n}(v)$ in the $G^{o}$-exploration. Therefore, we have with high
probability that

$\min_{v\in\partial V^{o_{n}}_{n}[R+1]}\\#\\{\text{idealised $v$-indicators in
$G_{n}^{o_{n}}$-exploration}\\}\to\infty,\text{ in probability.}$

Moreover, note that given $G_{n}^{o_{n}}$ and that $j$ is an idealised
$v$-indicator it is also an idealised $v$-escape with conditional probability

$P_{G_{n}}^{v}((X_{t})_{t\in[0,\tau_{n}]}\text{ does not hit
$V^{o_{n}}[R]$}).$

Consequently, by the law of large numbers as $n\to\infty$

$\sum_{v\in\partial
V_{n}^{o_{n}}[R+1]}\bigl{|}\bar{e}_{v}^{(n)}-P_{G_{n}}^{v}((X_{t})_{t\in[0,\tau_{n}]}\text{
does not hit $V^{o_{n}}[R]$})\bigr{|}\to 0,\text{ in probability}.$

We recall that, with high probability, for all $v\in\partial
V_{n}^{o_{n}}[R+1]$,
$\bar{e}_{v}^{(n)}=\bar{\mathfrak{e}}_{v}^{(n)}=\mathfrak{e}_{\varphi_{n}(v)}^{(n)}$,
so that, in probability,

$\displaystyle\lim_{n\to\infty}\sum_{v\in\partial
V_{n}^{o_{n}}[R+1]}\bigl{|}P_{G_{n}}^{v}$
$\displaystyle((X_{t})_{t\in[0,\tau_{n}]}\text{ does not hit $V^{o_{n}}[R]$})$
$\displaystyle-P_{G}^{\varphi_{n}(v)}((X_{t})_{t\geq 0}\text{ does not hit
}V^{o}[R])\bigr{|}=0.$

This entails the result. ∎

##  4\. Vacant set percolation

Vacant set percolation has been considered on random graphs in various
articles [vTW11, vT13, vH22]. In this section, we relate the visiting measure
to vacant set percolation similarly as done in [vdH21] for the existence of
giant components.

We will apply exploration convergence for doubly rooted graphs, i.e., graphs
with two designated vertices $o$ and $o^{\prime}$. That means that an
exploration rule $K$ now acts on $\bar{\mathbb{G}}^{\mathrm{finite,root}^{2}}$
being the set of finite, doubly-rooted, weighted, generalised graphs. Graph
isomorphisms and exploration convergence is defined in complete analogy, where
the graph limit now is a random doubly-rooted graph $G^{o,o^{\prime}}$, where
each vertex is connected to at least one of the two roots.

We let for a doubly rooted graph
$G^{o,o^{\prime}}\in\mathbb{G}^{\mathrm{root}^{2}}$, $V^{o,o^{\prime}}[R]$
denote the set of vertices of $G$ that have distance less or equal to $R$ to
one of the roots. Theorem 1.3 holds analogously for doubly rooted graphs.

Let $(\ell_{n}^{\prime})_{n\in\mathbb{N}}$ and $(\ell_{n})_{n\in\mathbb{N}}$
be $\mathbb{N}$-valued and $(\tau_{n})_{n\in\mathbb{N}}$ and
$(a_{n})_{n\in\mathbb{N}}$ be $(0,\infty)$-valued with all three sequences
tending to infinity and suppose that the random finite connected
$\mathbb{G}^{\mathrm{root}^{2}}$-graphs $G_{1}^{o_{1},o_{1}^{\prime}},\dots$
converge $(\ell_{n})$-locally to the random
$\mathbb{G}^{\mathrm{root}^{2}}$-graph $G^{o,o^{\prime}}$. Moreover, suppose
that $\ell_{n}^{\prime}=o(\ell_{n})$, $\tau_{n}=o(\alpha_{n}(V_{n}))$,

$\lim_{n\to\infty}d_{G_{n}}(\tau_{n})=0,\ \
\lim_{n\to\infty}\max_{\bar{o}\in\\{o,o^{\prime}\\}}P_{G}^{\bar{o}}\bigl{(}\\#\text{
range}\bigl{(}(X_{t})_{[0,2\tau_{n}]}\bigr{)}>\ell_{n}^{\prime}\bigr{)}=0\text{
\ and }$ $\lim_{n\to\infty}\frac{\alpha_{n}(V_{n})}{a_{n}}=\mathfrak{a},\text{
in probability.}$

Let $R,R^{\prime}\in\mathbb{N}$ and $\sigma>0$. For $n\in\mathbb{N}$, let
$\Xi_{n}$ be the $(V_{n}^{o_{n},o_{n}^{\prime}}[R],\tau_{n},a_{n})$-visiting
measure and let $\Gamma$ be the Cox-process that is conditionally on $G^{o}$ a
Poisson point process with intensity

$\displaystyle\mbox{$\frac{1}{\mathfrak{a}}$}\mathrm{Leb}|_{[0,\infty)}\otimes
P^{e_{V^{o,o^{\prime}}[R],G}}_{G}$ (14)

and let $\Gamma_{n}$ be the point process obtained from $\Gamma$ by killing
all paths at time $\tau_{n}$. One can couple
$(G^{o_{n},o_{n}^{\prime}}_{n},\Xi_{n})$ and $(G^{o,o^{\prime}},\Gamma)$ such
that, the following holds, with high probability:

  * •

There are subsets $\bar{\mathcal{V}}_{n}\supset
V_{n}^{o_{n},o_{n}^{\prime}}[R^{\prime}]$ and ${\mathcal{V}}_{n}\supset
V^{o,o^{\prime}}[R^{\prime}]$ of $V_{n}$ and $V$, respectively, and a graph
isomorphism taking the $\bar{\mathcal{V}}_{n}$-disclosed graph of
$G_{n}^{o_{n},o_{n}^{\prime}}$ to the $\mathcal{V}_{n}$-disclosed graph of
$G^{o,o^{\prime}}$.

  * •

The trajectories appearing in $\Xi_{n}|_{[0,\sigma]\times W_{+}}$ do not leave
$\bar{\mathcal{V}}_{n}$ and the point process $\Gamma_{n}|_{[0,\sigma]\times
W_{+}}$ is obtained from $\Xi_{n}|_{[0,\sigma]\times W_{+}}$ by applying the
isomorphism $\varphi_{n}$ on the states of the trajectories.

###### Proof.

Literally the same proof where one now uses path explorations from the two
roots with alternating starting points. ∎

Let us now introduce the setting of vacant set percolation. In the following,
we consider site- and bond-percolation. Both can be treated in complete
analogy. Let $(G_{n})$ be a sequence of random finite, connected
$\mathbb{G}$-graphs and let $(a_{n})$ be a sequence of strictly positive
numbers that is used to govern the time scale (as in the definition of the
visiting counting measure). For $\sigma\geq 0$ we denote by $G_{n}(\sigma)$
the graph that is obtained when removing the sites, resp. bonds seen by the
Markov chain until time $\sigma a_{n}$. For a vertex $v\in V_{n}$ we let
$\mathcal{C}^{v}_{n}(\sigma)$ the component of $v$ in $G_{n}(\sigma)$.

Again we assume that the uniformly rooted graphs converge (in the sense of
exploration convergence) to some $\mathbb{G}$-graph $G^{o}$. We denote by
$G^{o}(\sigma)$ the graph that is obtained by applying interlacement
percolation (site or bond percolation). More explicitly, we use Remark 1.1 and
consider a doubly stochastic Poisson process that is, given the rooted graph
$G^{o}$, a Poisson point process with intensity measure
$\mathrm{Leb}|_{[0,\infty)}\otimes\nu_{G}$. Removing all sites, resp. edges,
seen by the path with time index less than or equal to $\sigma$ we obtain
$G(\sigma)$. We relate the relative size of the largest component in
$\mathcal{C}_{n}(\sigma)$ with the probability of $o$ being in an infinite
component of $G(\sigma)$.

Let $\sigma>0$ and let $G_{1},G_{2},\dots$ random finite, connected
$\mathbb{G}$-graphs. Suppose that the assumptions of the latter theorem are
satisfied when choosing independent uniform roots $o_{n}$ and $o_{n}^{\prime}$
from the graph $G_{n}$ and that the graph limit is in distribution equal to
two independent unconnected copies of $G^{o}$ (with $G^{o}$ itself being the
graph limit of $G^{o_{n}}_{n}$). Then the following is equivalent for every
$\sigma\geq 0$:

  1. (a)

One has

$\lim_{k\to\infty}\limsup_{n\to\infty}\mathbb{P}\bigl{(}\\#\mathcal{C}_{n}^{o_{n}}(\sigma)\geq
k,\\#\mathcal{C}_{n}^{o_{n}^{\prime}}(\sigma)\geq
k,o_{n}\not\in\mathcal{C}_{n}^{o_{n}^{\prime}}(\sigma)\bigr{)}=0.$

  2. (b)

One has, in probability, that

$\lim_{n\to\infty}\frac{1}{\\#V_{n}}\\#\mathcal{C}_{n}^{\mathrm{max}}(\sigma)=\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty).$

######  Lemma 4.1.

For $n\in\mathbb{N}$ and nonnegative reals $a_{1},\dots,a_{n}$ one has

$(a_{1}+\ldots+a_{n})^{2}-3\sum_{i<j}a_{i}a_{j}\leq\max(a_{1},\dots,a_{n})^{2}\leq(a_{1}+\ldots+a_{n})^{2}-2\sum_{i<j}a_{i}a_{j}.$

###### Proof.

1) We start with proving the first inequality. The proof is established by
induction over $n\in\mathbb{N}$. Obviously the statement is true for $n=1$.
Now suppose that the statement is true for $n\in\mathbb{N}$. We let
$a_{1},\dots,a_{n+1}$ with the maximum being attained in the first $n$ entries
(otherwise we rearrange the summands). Then

$\displaystyle(a_{1}+\ldots+a_{n}+a_{n+1})^{2}-3\sum_{1\leq i<j\leq
n+1}a_{i}a_{j}$
$\displaystyle\quad=\underbrace{(a_{1}+\dots+a_{n})^{2}-3\sum_{1\leq i<j\leq
n}a_{i}a_{j}}_{\leq\max(a_{1},\dots,a_{n})^{2}}+\underbrace{a_{n+1}^{2}-(a_{1}+\ldots+a_{n})a_{n+1}}_{\leq
0}$ $\displaystyle\quad\leq\max(a_{1},\dots,a_{n+1})^{2}.$

2) It remains to prove the second inequality. One has

$(a_{1}+\ldots+a_{n})^{2}=\sum_{i=1}^{n}a_{i}^{2}+2\sum_{i<j}a_{i}a_{j}\geq\max(a_{1},\dots,a_{n})^{2}+2\sum_{i<j}a_{i}a_{j}.$

∎

###### Proof of Theorem 4.

First we analyse the random variable $N_{n}^{(k)}=\frac{1}{\\#V_{n}}\sum_{v\in
V_{n}}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}_{n}^{v}(\sigma)\geq k\\}}$
that counts the relative number of vertices in components with at least $k$
entries after vacant set percolation. One has as consequence of Thm. 4 that

$\displaystyle\mathbb{E}\bigl{[}\bigl{(}N_{n}^{(k)}\bigr{)}^{2}\bigr{]}$
$\displaystyle=\mathbb{P}(\\#\mathcal{C}^{o_{n}}_{n}(\sigma)\geq
k,\\#\mathcal{C}^{o_{n}^{\prime}}_{n}(\sigma)\geq k)$
$\displaystyle\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq
k,\\#\mathcal{C}^{o^{\prime}}(\sigma)\geq
k)=\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq k)^{2},$

where we used that the event $\\{\\#\mathcal{C}^{o}(\sigma)\geq
k,\\#\mathcal{C}^{o^{\prime}}(\sigma)\geq k\\}$ is decidable on the basis of
the visiting measure. Analogously,

$\mathbb{E}\bigl{[}N_{n}^{(k)}\bigr{]}=\mathbb{P}(\\#\mathcal{C}^{o_{n}}_{n}(\sigma)\geq
k)\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq k).$

Consequently, $N_{n}^{(k)}$ converges, as $n\to\infty$, in probability, to
$\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq k)$ which itself converges as
$k\to\infty$ to $\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)$.

1) We first prove that (a) implies (b).

1.a) _Lower bound._ For fixed $n\in\mathbb{N}$ we apply the lemma with
$a_{1},\dots,a_{m}$ being the sizes of the components that contain more than
$k$ entries. Then we get

$\displaystyle\bigl{(}\underbrace{\sum_{v\in
V_{n}}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}^{v}_{n}(\sigma)\geq
k\\}}}_{=\\#V_{n}\,N_{n}^{(k)}}\bigr{)}^{2}-\frac{3}{2}\sum_{v,w\in
V_{n}}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}^{v}_{n}(\sigma)\geq
k,\\#\mathcal{C}^{w}_{n}(\sigma)\geq
k,v\not\in\mathcal{C}^{w}_{n}(\sigma)\\}}\leq\bigl{(}\\#\mathcal{C}^{\mathrm{max}}_{n}(\sigma)\bigr{)}^{2}.$
(15)

Now for fixed $\epsilon>0$ we can pick $k\in\mathbb{N}$ sufficiently large
such that for large $n\in\mathbb{N}$

$\displaystyle\mathbb{E}\Bigl{[}$
$\displaystyle\frac{1}{(\\#V_{n})^{2}}\sum_{v,w\in
V_{n}}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}^{v}_{n}(\sigma)\geq
k,\\#\mathcal{C}^{w}_{n}(\sigma)\geq
k,v\not\in\mathcal{C}^{w}_{n}(\sigma)\\}}\Bigr{]}$
$\displaystyle=\mathbb{P}(\\#\mathcal{C}^{o_{n}}_{n}(\sigma)\geq
k,\\#\mathcal{C}^{o_{n}^{\prime}}_{n}(\sigma)\geq
k,o_{n}\not\in\mathcal{C}^{o_{n}^{\prime}}_{n}(\sigma))\leq\epsilon.$

Recalling that $N_{n}^{(k)}\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq k)$,
in probability, we can apply a diagonalisation argument and choose $k(n)$ in
dependence on $n\in\mathbb{N}$ such that $k(n)\to\infty$,
$N_{n}^{(k(n))}\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)$, in
probability, and

$\mathbb{E}\Bigl{[}\frac{1}{(\\#V_{n})^{2}}\sum_{v,w=1}^{n}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}^{v}_{n}(\sigma)\geq
k(n),\\#\mathcal{C}^{w}_{n}(\sigma)\geq
k(n),v\not\in\mathcal{C}^{w}_{n}(\sigma)\\}}\Bigr{]}\to 0.$

With (15) we get that

$\frac{1}{\\#V_{n}}\\#\mathcal{C}_{n}^{\mathrm{max}}(\sigma)\geq\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)-o_{P}(1).$

1.b) _Upper bound_. Note that $\mathcal{C}_{n}^{\mathrm{max}}(\sigma)\leq
k\vee\sum_{v\in
V_{n}}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}_{n}^{v}(\sigma)\geq
k\\}}$. Note that for every $k\in\mathbb{N}$,
$N_{n}^{(k)}\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq k)$ and
$\\#V_{n}\to\infty$, in probability. Again a diagonalisation argument yields a
sequence $(k(n))$ tending to infinity so that
$N_{n}^{(k(n))}\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)$ and
$k(n)/\\#V_{n}\to 0$, in probability. Consequently,

$\frac{1}{\\#V_{n}}\mathcal{C}_{n}^{\mathrm{max}}(\sigma)\leq\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)+o_{P}(1).$

2) It remains to show that (b) implies (a). As above choosing
$a_{1},\dots,a_{m}$ as the sizes of the random components after vacant set
percolation with more than $k$ vertices we get that whenever
$\\#\mathcal{C}^{\mathrm{max}}_{n}(\sigma)\geq k$ or, equivalently,
$N_{n}^{(k)}>0$, one has

$\Bigl{(}\frac{1}{\\#V_{n}}\\#\mathcal{C}^{\mathrm{max}}_{n}(\sigma)\Bigr{)}^{2}\leq(N_{n}^{(k)})^{2}-\underbrace{\frac{1}{(\\#V_{n})^{2}}\sum_{v,w\in
V_{n}}\operatorname{\mathbbm{1}}_{\\{\\#\mathcal{C}^{o_{n}}_{n}(\sigma)\geq
k,\\#\mathcal{C}^{o_{n}^{\prime}}_{n}(\sigma)\geq
k,o_{n}\not\in\mathcal{C}^{o_{n}^{\prime}}_{n}(\sigma)\\}}}_{=:\Delta_{n}^{(k)}}.$

We recall that $N_{n}^{(k)}\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq k)$,
in probability. Now suppose that (a) is not satisfied. Then there is
$\epsilon>0$ such that along a subsequence of $n$’s one has for all
$k\in\mathbb{N}$ that for large $n$

$\mathbb{P}(\\#\mathcal{C}_{n}^{o_{n}}(\sigma)\geq
k,\\#\mathcal{C}_{n}^{o^{\prime}_{n}}(\sigma)\geq
k,o_{n}\not\in\mathcal{C}_{n}^{o_{n}^{\prime}}(\sigma))\geq\epsilon.$

Without loss of generality we can assume that the latter is true along the
whole sequence since we otherwise may drop the graphs that are not in the
subsequence. In particular, we get that as $n\to\infty$

$\epsilon\leq\mathbb{P}(\\#\mathcal{C}_{n}^{o_{n}}(\sigma)\geq
k)\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq k)$

so that
$\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)=\lim_{k\to\infty}\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)\geq
k)\geq\epsilon$. We can now choose an increasing $(k(n))_{n\in\mathbb{N}}$
tending to infinity such that

$\frac{1}{\\#V_{n}}k(n)\to 0\ \text{ and }\
N_{n}^{(k(n))}\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)\text{, \ in
probability,}$

and, for all large $n\in\mathbb{N}$,

$\mathbb{P}(\\#\mathcal{C}_{n}^{o_{n}}(\sigma)\geq
k(n),\\#\mathcal{C}_{n}^{o^{\prime}_{n}}(\sigma)\geq
k(n),o_{n}\not\in\mathcal{C}_{n}^{o_{n}^{\prime}}(\sigma))\geq\epsilon.$

Then using that $\Delta_{n}^{(k(n))}$ is bounded by one we conclude that

$\epsilon\leq\mathbb{P}(\\#\mathcal{C}_{n}^{o_{n}}(\sigma)\geq
k(n),\\#\mathcal{C}_{n}^{o^{\prime}_{n}}(\sigma)\geq
k(n),o_{n}\not\in\mathcal{C}_{n}^{o_{n}^{\prime}}(\sigma))=\mathbb{E}[\Delta_{n}^{(k(n))}]\leq\frac{\epsilon}{2}+\mathbb{P}\bigl{(}\Delta_{n}^{(k(n))}\geq\frac{\epsilon}{2}\bigr{)}$

for large $n$ and thus recalling that
$N_{n}^{k(n)}\to\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)\geq\epsilon$ we
have with high probability that

$\Bigl{(}\frac{1}{\\#V_{n}}\\#\mathcal{C}^{\mathrm{max}}_{n}(\sigma)\Bigr{)}^{2}\leq(N_{n}^{(k(n))})^{2}-\Delta_{n}^{(k(n))}=\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)^{2}+o_{P}(1)-\Delta_{n}^{(k(n))}.$

Since
$\mathbb{P}(\Delta_{n}^{(k(n))}\geq\frac{\epsilon}{2})\geq\frac{\epsilon}{2}$
we get that $\frac{1}{\\#V_{n}}\\#\mathcal{C}^{\mathrm{max}}_{n}(\sigma)$ does
not converge to $\mathbb{P}(\\#\mathcal{C}^{o}(\sigma)=\infty)$, in
probability. ∎

##  Appendix A Exploration convergence for the configuration model

For every $n\in\mathbb{N}$ we denote by
$\mathbf{d}^{(n)}=(d_{k}^{(n)})_{k=1,\dots,n}$ an $\mathbb{N}_{0}$-valued
sequence so that $N^{(n)}:=\sum_{k=1,\dots,n}d_{k}^{(n)}\in 2\mathbb{N}$. We
denote by $D_{n}$ an $\mathbb{N}_{0}$-valued random variable with distribution

$\frac{1}{n}\sum_{k=1}^{n}\delta_{d_{k}^{(n)}}$

and let $D_{n}^{*}$ denote a $\mathbb{N}$-valued random variable with size
biased distribution distribution

$\frac{1}{N^{(n)}}\sum_{k=1}^{n}d_{k}^{(n)}\delta_{d_{k}^{(n)}}$

so that

$\mathbb{P}(D_{n}^{*}=k)=\frac{1}{\mathbb{E}[D_{n}]}\,k\,\mathbb{P}(D_{n}=k).$

The random graph with fixed degree sequence
$(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ is a sequence of random multigraphs that
is formed by pairing the even number of half-edges in

$\mathbb{H}_{n}=\bigcup_{j\in\\{1,\dots,n\\}}\\{j\\}\times\\{1,\dots,d_{j}^{(n)}\\}$

and forming the random multigraph $G_{n}$ by taking as vertex set
$\\{1,\dots,n\\}$ and establishing for each
$\langle(j_{1},r_{1}),(j_{2},r_{2})\rangle$ of the latter random pairing an
edge connecting $j_{1}$ and $j_{2}$. A closely related model is the
configuration model, where the degrees itself are chosen randomly and then the
graph is formed by choosing a random fixed degree graph for this configuration
as above.

As is well known fixed degree sequence graphs converge locally to Galton-
Watson trees with a modified offspring distribution for the root vertex. For a
$\mathbb{N}_{0}$-valued random variable $D$ and a $\mathbb{N}$-valued random
variable $D^{*}$ we call a random rooted graph $G^{o}$ a
$\mathrm{GWP}(D,D^{*})$-tree, if the root has a $D$-distributed number of
descendants and if every descendant has itself an independent
$D^{*}-1$-distributed number of descendants.

[Coupling explorations for the random fixed degree graph] Let
$(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ be a sequence as above satisfying
$\liminf_{n\to\infty}\,\mathbb{E}[D_{n}]>0$. Moreover, let
$(\ell_{n})_{n\in\mathbb{N}}$ be $\mathbb{N}$-valued with

$\displaystyle\ell_{n}=o\bigl{(}\sqrt{n}\,\mathbb{E}[D_{n}^{*}\wedge\sqrt{n}]^{-1}\bigr{)}.$
(16)

Let $(\bar{G}_{n})_{n\in\mathbb{N}}$ denote a sequence of fixed degree random
graphs with degree sequence $(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ as
introduced above and choose independent on $\\{1,\dots,n\\}$ uniformly
distributed roots $\bar{o}_{n}$. Moreover, let for each $n\in\mathbb{N}$,
$G_{n}^{o_{n}}$ be a $\mathrm{GWP}(D_{n},D_{n}^{*})$-tree. Then for every
sequence $(K_{n})$ of exploration rules, one can couple the $\ell_{n}$-step
$K_{n}$-explorations $\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ and
${\mathfrak{E}}_{\ell_{n}}^{(n)}$ of $\bar{G}_{n}^{\bar{o}_{n}}$ and
$G_{n}^{o_{n}}$ such that they agree with high probability as $n\to\infty$.

Before we prove the theorem, we discuss under which conditions the
$\mathrm{GWP}(D_{n},D_{n}^{*})$-trees $G_{n}^{o_{n}}$ can be replaced by a
$\mathrm{GWP}(D,D^{*})$-tree, where $D$ and $D^{*}$ are weak limits of $D_{n}$
and $D_{n}^{*}$. Moreover, we will discuss the constraint (16) in the case of
polynomially decaying tail probabilities of $\mathbb{P}_{D_{n}}$.

######  Lemma A.1.

For two $\mathbb{N}_{0}$-valued random variables $D_{1}$ and $D_{2}$, two
$\mathbb{N}$-valued random variables $D_{1}^{*}$ and $D_{2}^{*}$,
$\ell\in\mathbb{N}$ and an exploration rule one can couple the $\ell$-step
$K$-explorations of a $\mathrm{GWP}(D_{1},D_{1}^{*})$\- and a
$\mathrm{GWP}(D_{2},D_{2}^{*})$-tree such that they agree with probability
greater or equal to

$1-d_{\mathrm{TV}}(\mathbb{P}_{D_{1}},\mathbb{P}_{D_{2}})-\ell\,d_{\mathrm{TV}}(\mathbb{P}_{D_{1}^{*}},\mathbb{P}_{D_{2}^{*}}).$

###### Proof.

The initial explorations can be coupled such that they agree with probability
$1-d_{\mathrm{TV}}(\mathbb{P}_{D_{1}},\mathbb{P}_{D_{2}})$. Moreover, in each
exploration step in which a not yet disclosed vertex is explored we can apply
a coupling hat succeeds with conditional probability
$1-d_{\mathrm{TV}}(\mathbb{P}_{D_{1}}^{*},\mathbb{P}_{D_{2}}^{*})$. ∎

######  Remark A.2.

  1. (a)

If in Theorem A additionally for random variables $D$ and $D^{*}$ one has

$\displaystyle
d_{\mathrm{TV}}(\mathbb{P}_{D_{n}},\mathbb{P}_{D})+\ell_{n}\,d_{\mathrm{TV}}(\mathbb{P}_{D_{n}^{*}},\mathbb{P}_{D^{*}})\to
0,$ (17)

then the result remains true, when letting $G_{n}^{o_{n}}$ be
$\mathrm{GWP}(D,D^{*})$-trees instead (consequence of Remark A.1).

  2. (b)

Let $(p_{k})_{k\in\mathbb{N}_{0}}$ be a sequence of probability weights with
$p_{0}\not=1$. Then one may choose a degree sequence
$(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ such that
$|\mathbb{P}(D_{n}=k)-p_{k}|\leq\frac{1}{n}\wedge p_{k}$. We let
$\epsilon_{n}=\sum_{k=1}^{\infty}(\frac{1}{n}\wedge p_{k})$. Then

$\displaystyle d_{\mathrm{TV}}$
$\displaystyle(\mathbb{P}_{D_{n}^{*}},\mathbb{P}_{D^{*}})=\sum_{k=1}^{\infty}k\Bigl{|}\frac{\mathbb{P}(D_{n}=k)}{\mathbb{E}[D_{n}]}-\frac{p_{k}}{\mathbb{E}[D]}\Bigr{|}$
$\displaystyle\leq\frac{1}{\mathbb{E}[D]}\sum_{k=1}^{\infty}k|\mathbb{P}(D_{n}=k)-p_{k}|+\frac{|\mathbb{E}[D]-\mathbb{E}[D_{n}]|}{\mathbb{E}[D]}\leq
2\frac{\epsilon_{n}}{\mathbb{E}[D]}.$

Thus for given distribution $(p_{k})_{k\in\mathbb{N}_{0}}$ we can choose a
degree sequence $(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ as above and can replace
as described in (a) the GWP-tree if $\ell_{n}\epsilon_{n}\to 0$. An elementary
computation shows that if $p_{k}=\mathcal{O}(k^{-\tau})$ for a $\tau>2$, then
$\epsilon_{n}=\mathcal{O}(n^{-1+\frac{2}{\tau}})$ and one can choose
$(\ell_{n})$ of order $o(n^{1-\frac{2}{\tau}})$ and has validity of (17).

  3. (c)

We analyse constraint (16) on $\ell_{n}$. Suppose that we are given a degree
sequence $(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ such that for a $\tau>2$ and
finite $C$ one has $\mathbb{P}(D_{n}=k)\leq Ck^{-\tau}$ for $k\in\mathbb{N}$
and $n\in\mathbb{N}$. Moreover assume that
$\liminf_{n\to\infty}\mathbb{E}[D_{n}]>0$. Then

$\mathbb{E}[D_{n}^{*}\wedge\sqrt{n}]=\frac{1}{\mathbb{E}[D_{n}]}\sum_{k=1}^{\infty}k\,\mathbb{P}(D_{n}=k)(k\wedge\sqrt{n})\leq\frac{C}{\mathbb{E}[D_{n}]}\sum_{k=1}^{\infty}k^{1-\tau}\,(k\wedge\sqrt{n})$

Elementary calculus gives that

$\sum_{k=1}^{\infty}k^{1-\tau}(k\wedge\sqrt{n})\approx\begin{cases}n^{(3-\tau)/2},&\text{
if }\tau\in(2,3),\\\ \log n,&\text{ if }\tau=3,\\\ 1,&\text{ if }\tau>3.\\\
\end{cases}$

Hence, (16) is satisfied, if

$\displaystyle\ell_{n}=\begin{cases}o(n^{\frac{\tau}{2}-1}),&\text{ if
}\tau<3,\\\ o(\sqrt{n}(\log n)^{-1}),&\text{ if }\tau=3,\\\
o(\sqrt{n}),&\text{ if }\tau>3.\end{cases}$ (18)

  4. (d)

When working with degree sequences $(\mathbf{d}^{(n)})_{n\in\mathbb{N}}$ as in
(b), one also apply (c) and gets that Theorem A is applicable with
$G_{n}^{o_{n}}$ being replaced by $\mathrm{GWP}(D,D^{*})$-trees if
$(\ell_{n})$ is of order
$o\bigl{(}n^{(1-\frac{2}{\tau})\wedge\frac{1}{2}}\bigr{)}$. Indeed, for
$\tau\in(2,3]$, the constraint of (c) is less restrictive than the one of (b)
and for $\tau\geq 4$, we get as assumption that $(\ell_{n})$ is of order
$o(\sqrt{n})$.

###### Proof of Theorem A.

In the proof we will stop explorations once we find vertices with
exceptionally large degree: we let $a_{n}=\lfloor\sqrt{n}\rfloor$ for
$n\in\mathbb{N}$ and note that

$\displaystyle\ell_{n}=o\bigl{(}\mathbb{P}(D_{n}^{*}\geq a_{n})^{-1}\bigr{)}\
\text{ and }\
\ell_{n}=o\Bigl{(}\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]^{-1}\sqrt{n}\Bigr{)}$
(19)

as consequence of (16).

We fix a sequence of exploration rules $(K_{n})$. We directly introduce a
coupling of two explorations $\bar{\mathfrak{E}}_{\ell_{n}}$ and
$\mathfrak{E}_{\ell_{n}}$ of $\bar{G}_{n}^{\bar{o}_{n}}$ and $G_{n}^{o_{n}}$,
respectively. Formally, $\bar{\mathfrak{E}}_{\ell_{n}}$ will not be a
$K_{n}$-exploration of $\bar{G}_{n}^{\bar{o}_{n}}$. However, it will be very
close in an appropriate sense to be discussed later.

We start with the construction of $\mathfrak{E}^{(n)}_{\ell_{n}}$. In
particular, this will include a definition of the graph $G_{n}^{o_{n}}$. First
we pick a label $o_{n}$ from $[n]$ uniformly at random and form
$\mathfrak{E}_{\ell_{n}}$ as the rooted graph with edges labeled
$(o_{n},1),\dots,(o_{n},d_{o_{n}}^{(n)})\in\mathbb{H}_{n}$ that connect
$o_{n}$ with $\partial$ with no edge history. Then we iteratively do the
following for $k=1,2,\dots$:

  1. (a)

We pick a $K_{n}(\mathfrak{E}^{(n)}_{k-1},\,\cdot\,)$-distributed edge
$h_{k}^{\prime}$ of the graph of the exploration $\mathfrak{E}^{(n)}_{k-1}$
and add $h_{k}^{\prime}$ to the edge history.

  2. (b)

If $h_{k}^{\prime}$ points in $\mathfrak{E}^{(n)}_{k-1}$ to $\partial$, we
choose an on $\mathbb{H}_{n}$ uniformly distributed half edge
$h_{k}^{\prime\prime}$ and build the graph of $\mathfrak{E}^{(n)}_{k}$ by

    1. (a)

by redirecting $h_{k}^{\prime}$ to a newly added vertex being labelled by the
vertex $v_{k}$ being associated to $h_{k}^{\prime\prime}$ (if the label has
not appeared yet)

    2. (b)

which has $\mathrm{deg}_{n}(v_{k})-1$ further edges pointing towards
$\partial$ with labels
$\mathbb{H}_{n}(v_{k})\backslash\\{h_{k}^{\prime\prime}\\}$ (if the labels
have not appeared yet).

Obviously the result is an $K_{n}$ exploration of a random rooted tree
$G_{n}^{o_{n}}$ as described above.

We couple this exploration with an “exploration” of
$\bar{G}_{n}^{\bar{o}_{n}}$ as follows. We start with the vertex
$\bar{o}_{n}=o_{n}$ and attach to it edges that are indexed by
$\mathbb{H}_{n}(o_{n})$ all connecting $o_{n}$ and $\partial$ so that
$\bar{\mathfrak{E}}^{(n)}_{0}=\mathfrak{E}^{(n)}_{0}$. Then we iteratively do
the following for $k=1,2,\dots$:

  1. (a)

If $\bar{\mathfrak{E}}^{(n)}_{k-1}$ agrees with $\mathfrak{E}^{(n)}_{k-1}$,
then we choose $\bar{h}_{k}^{\prime}=h_{k}^{\prime}$ and otherwise we choose
an independent $K_{n}(\bar{\mathfrak{E}}^{(n)}_{k-1},\,\cdot\,)$-distributed
$\bar{h}_{k}^{\prime}$ and we continue as follows if
$\bar{h}_{k}^{\prime}\not=\partial$.

  2. (b)

If
$h_{k}^{\prime\prime}\not\in\\{h_{1}^{\prime},\dots,h_{k}^{\prime},h_{1}^{\prime\prime},\dots,h_{k-1}^{\prime\prime}\\}$
we set $\bar{h}_{k}^{\prime\prime}=h_{k}^{\prime\prime}$ and otherwise we draw
$\bar{h}_{k}^{\prime\prime}$ uniformly at random from
$\mathbb{H}_{n}\backslash\\{\bar{h}_{1}^{\prime},\dots,\bar{h}_{k}^{\prime},\bar{h}_{1}^{\prime\prime},\dots,\bar{h}_{k-1}^{\prime\prime}\\}$.

  3. (c)

We distinguish two cases:

    1. (a)

if there is no $\bar{h}_{k}^{\prime\prime}$-indexed edge present in
$\bar{\mathfrak{E}}_{k-1}^{(n)}$, then we reconnect the edge
$\bar{h}_{k}^{\prime}$ towards a newly formed vertex with the to
$\bar{h}_{k}^{\prime\prime}$ associated label $\bar{v}_{k}$ (which equals
$v_{k}$, if we have $\bar{h}_{k}^{\prime\prime}=h_{k}^{\prime\prime}$) and
attach to it further edges indexed by
$\mathbb{H}_{n}(\bar{v}_{k})\backslash\\{\bar{h}_{k}^{\prime\prime}\\}$

    2. (b)

if there is an $\bar{h}_{k}^{\prime\prime}$-indexed edge already present in
the exploration $\mathfrak{E}^{(n)}_{k-1}$, then it has to be connected to
$\partial$ (since it was not yet connected in previous steps) and we connect
the two involved vertices by one edge and use as edge one of the two
identifiers uniformly at random (the other edge is removed).

First note that $\mathfrak{E}_{\ell_{n}}^{(n)}$ coincides with
$\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ if in the first $\ell_{n}$ steps in (b)
one always chooses $\bar{h}_{k}^{\prime\prime}=h_{k}^{\prime\prime}$ and in
(c) always case (i) enters. We let $\mathcal{N}_{k}^{(n)}$ denote the number
of half-edges in $\mathfrak{E}_{k}^{(n)}$ (where an edge connecting two
vertices from $\mathcal{V}$ is counted twice and an edge leading to $\partial$
only once). For $k=1,\dots,\ell_{n}$, we denote

$\mathcal{F}_{k}=\bigl{\\{}\mathfrak{E}_{k}^{(n)}\not=\bar{\mathfrak{E}}_{k}^{(n)},\,\mathfrak{E}_{k-1}^{(n)}=\bar{\mathfrak{E}}_{k-1}^{(n)},\,\mathrm{degmax}(\mathfrak{E}_{k-1}^{(n)})<a_{n}\bigr{\\}},$

where $\mathrm{degmax}(\mathfrak{E}_{k-1}^{(n)})$ denotes the maximal degree
appearing in the graph of the exploration $\mathfrak{E}_{k-1}^{(n)}$.
Moreover, we denote
$\mathcal{F}_{0}=\\{\mathfrak{E}_{0}^{(n)}=\bar{\mathfrak{E}}_{0}^{(n)}\\}$
which is the sure event. Then

$\displaystyle\mathbb{P}(\mathcal{F}_{k})$
$\displaystyle\leq\frac{1}{N^{(n)}}\mathbb{E}\bigl{[}\operatorname{\mathbbm{1}}_{\\{\mathrm{degmax}(\mathfrak{E}_{k-1}^{(n)}<a_{n})\\}}\mathcal{N}_{k-1}\Bigr{]}$
$\displaystyle\leq\frac{1}{N^{(n)}}\bigl{(}\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}<a_{n}\\}}D_{n}]+(k-1)\,\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]\bigr{)}$

and we get that the probability for the coupling to fail within the first
$\ell_{n}$ steps is bounded by

$\displaystyle\mathbb{P}\bigl{(}$
$\displaystyle\mathrm{degmax}(\mathfrak{E}_{\ell_{n}}^{(n)})\geq
a_{n}\bigr{)}+\sum_{k=1}^{\ell_{n}}\mathbb{P}(\mathcal{F}_{k})$
$\displaystyle\leq\underbrace{\mathbb{P}(D_{n}\geq
a_{n})}_{\leq\mathbb{P}(D_{n}^{*}\geq
a_{n})}+\ell_{n}\,\mathbb{P}(D_{n}^{*}\geq
a_{n})+\frac{1}{N^{(n)}}\sum_{k=1}^{\ell_{n}}\bigl{(}\mathbb{E}[D_{n}]+(k-1)\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]\bigr{)}$
$\displaystyle\leq(\ell_{n}+1)\,\mathbb{P}(D_{n}^{*}\geq
a_{n})+\frac{1}{2N^{(n)}}\ell_{n}^{2}\,\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]+\frac{\ell_{n}}{n}.$

By (19),
$\ell_{n}^{2}\,\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]^{2}=o(n)$
and since
$\mathbb{E}[\operatorname{\mathbbm{1}}{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]\geq\mathbb{P}(D_{n}^{*}<a_{n})\to
1$ and $N^{(n)}/n=\mathbb{E}[D_{n}]$ whose liminf is strictly bigger than
zero, we get that
$\ell_{n}^{2}\,\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]=o(N^{(n)})$.
Since by (19) also $(\ell_{n}+1)\,\mathbb{P}(D_{n}^{*}\geq a_{n})\to 0$ we get
that the $\ell_{n}$-step coupling succeeds with high probability.

Now note that $\bar{\mathfrak{E}}_{k}^{(n)}$ is in the sense of our definition
not a $K_{n}$-exploration of any graph since the graphs appearing in
$\bar{\mathfrak{E}}_{1}^{(n)},\dots$ are not necessarily consistent in the
sense that in step (c.ii) edges are removed and paired newly what can’t happen
when exploring a graph. To fix this and rigorously relate
$\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ to a random fixed degree graph we form
$\bar{G}_{n}$ by pairing the half-edges in $\mathbb{H}_{n}$ that have not been
paired in the graph of $\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ uniformly at
random (with ties as in (c.ii) being treated as above). We stress that now
$\bar{G}_{n}^{\bar{o}_{n}}$ is indeed a random fixed degree graph for the
degree sequence $\mathbf{d}^{(n)}$ with an independent uniformly chosen root
vertex $o_{n}$.

Now we are in the position to define a $K_{n}$-exploration of $G_{n}^{o_{n}}$.
We let $\bar{\bar{\mathfrak{E}}}_{0}^{(n)}$ be the
$\\{\bar{o}_{n}\\}$-disclosed graph of $\bar{G}_{n}^{\bar{o}_{n}}$ together
with an empty history of edges. Then for $k=1,\dots,\ell_{n}$, do the
following

  1. (a)

if $\bar{\bar{\mathfrak{E}}}_{k-1}^{(n)}$ agrees with
${\bar{\mathfrak{E}}}_{k-1}^{(n)}$, then form
$\bar{\bar{\mathfrak{E}}}_{k}^{(n)}$ by adding $\bar{h}^{\prime}_{k}$ to the
history of explored edges and form the graph as the appropiately disclosed
graph of $\bar{G}_{n}^{\bar{o}_{n}}$;

  2. (b)

otherwise choose a
$K_{n}(\bar{\bar{\mathfrak{E}}}_{k}^{(n)},\,\cdot\,)$-distributed edge
$\bar{\bar{h}}_{k}^{\prime}$ and form $\bar{\bar{\mathfrak{E}}}_{k}^{(n)}$ by
exploring $\bar{\bar{h}}_{k}^{\prime}$ in $\bar{G}_{n}^{\bar{o}_{n}}$ instead.

We denote by $\mathcal{G}_{k}^{(n)}$ the graph $G_{n}$ restricted to the
vertex set appearing in $\bar{\mathfrak{E}}_{k}^{(n)}$. We note that
$\mathcal{G}_{k}^{(n)}$ does not contain circles if and only if
$\bar{\mathfrak{E}}_{k}^{(n)}=\bar{\bar{\mathfrak{E}}}_{k}^{(n)}$. Now given
$\bar{\mathfrak{E}}_{k-1}^{(n)}$ the event that $\mathcal{G}_{k-1}^{(n)}$ does
not contain circles is independent of the choice of the vertex
$\bar{h}_{k}^{\prime}$. Therefore, $(\bar{\bar{\mathfrak{E}}}_{k}^{(n)})$ is a
$K_{n}$-exploration of $G_{n}^{o_{n}}$. Moreover,
$(\bar{\bar{\mathfrak{E}}}_{\ell_{n}}^{(n)})$ agrees with
$({\bar{\mathfrak{E}}}_{\ell_{n}}^{(n)})$ if and only if
$\mathcal{G}^{(n)}_{\ell_{n}}$ does not contain cycles.

Note that in the case that
${\mathfrak{E}}_{\ell_{n}}^{(n)}=\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ the
graph $\mathcal{G}_{\ell_{n}}^{(n)}$ contains circles, if there are edges in
$\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ that point to $\partial$ that are
actually connected to each other in $\bar{G}_{n}$. On
$\\{\mathfrak{E}_{\ell_{n}}^{(n)}=\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}\\}$,
given $\bar{\mathfrak{E}}_{\ell_{n}}^{(n)}$ the probability of finding no
circle when matching the remaining edges is bounded from above by

$\displaystyle\frac{(\mathcal{N}_{\ell_{n}}^{(n)})^{2}}{N^{(n)}-\mathcal{N}^{(n)}_{\ell_{n}}}.$
(20)

By construction of the $\mathfrak{E}^{(n)}$-exploration we may define (on a
possibly enlarged probability space) a sequence of independent random
variables $\mathcal{D}^{(n)}_{0},\mathcal{D}^{(n)}_{1},\dots$ such that
$\mathcal{D}^{(n)}_{0}$ is a copy of $D_{n}$ and
$\mathcal{D}^{(n)}_{1},\ldots$ are copies of $D_{n}^{*}$ and such that
$\mathcal{N}_{k}^{(n)}\leq\mathcal{D}^{(n)}_{0}+\ldots+\mathcal{D}^{(n)}_{k}$
for $k=0,\dots,\ell_{n}$. We note that
$(\mathcal{D}^{(n)}_{0}:n\in\mathbb{N})$ is tight. Moreover, we have with high
probability that
$\max(\mathcal{D}^{(n)}_{1},\ldots,\mathcal{D}^{(n)}_{\ell_{n}})<a_{n}$.
Together with

$\mathbb{E}\bigl{[}\operatorname{\mathbbm{1}}_{\\{\max(\mathcal{D}^{(n)}_{1},\ldots,\mathcal{D}^{(n)}_{\ell_{n}})<a_{n}\\}}\mathcal{D}_{1}^{(n)}+\ldots+\mathcal{D}_{\ell_{n}}^{(n)}\bigr{]}\leq\ell_{n}\,\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]=o(\sqrt{n})$

and the Markov inequality we conclude that
$\mathcal{N}^{(n)}_{\ell}=o_{P}(\sqrt{n})$. Since $N^{(n)}$ is of order $n$ we
conclude that the probability in (20) converges to zero, in probability. Thus
we showed that, with high probability,
$\mathfrak{E}^{(n)}_{\ell_{n}}={\bar{\mathfrak{E}}}^{(n)}_{\ell_{n}}=\bar{\bar{\mathfrak{E}}}^{(n)}_{\ell_{n}}$.
∎

[Local convergence for the configuration model] Let
$(p_{r})_{r\in\mathbb{N}_{0}}$ be a sequence of probability weights with
$p_{0}\not=1$ and suppose that for a $\tau\in(2,\infty)$

$p_{r}=\mathcal{O}(r^{-\tau})\text{ \ as \ }r\to\infty.$

Let $G_{n}$ be a configuration model with weights
$(p_{r})_{r\in\mathbb{N}_{0}}$ meaning that we take a sequence of i.i.d.
$(p_{r})$-distributed random variables $(q_{k})_{k\in\mathbb{N}}$, let

$d_{k}^{(n)}=q_{k}+\operatorname{\mathbbm{1}}_{\\{k=n\\}}\operatorname{\mathbbm{1}}_{\\{\sum_{v=1}^{n}q_{v}\text{
is odd}\\}}$

and define $(G_{n})$ in such a way that given
$\mathbf{d}^{(n)}=(d^{(n)}_{k})_{k=1,\dots,n}$, $G_{n}$ is a random graph with
fixed degree sequence $\mathbf{d}^{(n)}$. We suppose that $D$ and $D^{*}$ are
random variables with weights $(p_{r})_{r\in\mathbb{N}_{0}}$ and
$(p^{*}_{r})_{r\in\mathbb{N}_{0}}$ given by

$p^{*}_{r}=\frac{1}{\mathbb{E}[D]}rp_{r}.$

If

$\ell_{n}=\begin{cases}o(n^{\frac{\tau-2}{\tau}}),&\text{ if }\tau<4,\\\
o(n^{\frac{1}{2}}(\log n)^{-1}),&\text{ if }\tau=4,\\\
o(n^{\frac{1}{2}}),&\text{ if }\tau>4,\end{cases}$

then $(G_{n}^{o_{n}})$ with an independent uniformly chosen root converges
$(\ell_{n})$-locally to a $\mathrm{GWP}(D,D^{*})$ random tree $G^{o}$.

###### Proof.

We will apply Theorem A and Remark A.2 (a). with the choice
$a_{n}=n^{1/\tau}$. We analyse the analogues of $\mathbb{E}[D_{n}]$,
$\mathbb{P}(D_{n}^{*}\geq a_{n})$,
$\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{D_{n}^{*}<a_{n}\\}}D_{n}^{*}]$ and
$d_{\mathrm{TV}}(D_{n}^{*},D^{*})$ which are now random and which depend on
the degree sequence $\mathbf{d}^{(n)}$. We need to consider

$\mathfrak{m}_{1}^{(n)}=\frac{1}{n}\sum_{k=1}^{n}d_{k}^{(n)},\
\mathfrak{p}_{n}=\frac{1}{n\mathfrak{m}_{1}^{(n)}}\sum_{k=1}^{n}\operatorname{\mathbbm{1}}_{\\{d_{k}^{(n)}\geq
a_{n}\\}}d_{k}^{(n)},\
\mathfrak{m}_{2}^{(n)}=\frac{1}{n\mathfrak{m}_{1}^{(n)}}\sum_{k=1}^{n}\operatorname{\mathbbm{1}}_{\\{d_{k}^{(n)}<a_{n}\\}}(d_{k}^{(n)})^{2}$

and

$\mathfrak{d}^{(n)}=\
\frac{1}{2}\sum_{k=1}^{\infty}\Bigl{|}\frac{1}{n\mathfrak{m}_{1}^{(n)}}k\sum_{r=1}^{n}\operatorname{\mathbbm{1}}_{\\{d_{r}^{(n)}=k\\}}-\frac{1}{\mathbb{E}[D]}kp_{k}\Bigr{|}$

First note that by the strong law of large numbers

$\mathfrak{m}_{1}^{(n)}=\frac{1}{n}\sum_{k=1}^{n}d_{k}^{(n)}\to\mathbb{E}[D]>0,\text{
almost surely}.$

Moreover,

$\mathbb{E}\Bigl{[}\frac{1}{n}\sum_{k=1}^{n}\operatorname{\mathbbm{1}}_{\\{d_{k}^{(n)}\geq
a_{n}\\}}d_{k}^{(n)}\Bigr{]}\leq\frac{1}{n}+\mathbb{E}[\operatorname{\mathbbm{1}}_{\\{q\geq
a_{n}-1\\}}q]=\mathcal{O}(n^{-\frac{\tau-2}{\tau}})$

so that $\mathfrak{p}_{n}=\mathcal{O}_{P}(n^{-\frac{\tau-2}{\tau}})$. Next,
analyse the third term:

$\mathfrak{m}_{2}^{(n)}=\frac{1}{n\,\mathfrak{m}_{1}^{(n)}}\sum_{k=1}^{n}\operatorname{\mathbbm{1}}_{\\{d_{k}^{(n)}<a_{n}\\}}(d_{k}^{(n)})^{2}\leq\frac{1}{n\,\mathfrak{m}_{1}^{(n)}}\Bigl{(}\sum_{k=1}^{n}\operatorname{\mathbbm{1}}_{\\{q_{k}<a_{n}\\}}q_{k}^{2}+2q_{n}+1\Bigr{)}.$

Standard arguments yield that

$\frac{1}{n}\mathbb{E}\Bigl{[}\sum_{k=1}^{n}\operatorname{\mathbbm{1}}_{\\{q_{k}<a_{n}\\}}q_{k}^{2}\Bigr{]}=\mathbb{E}\bigl{[}\operatorname{\mathbbm{1}}_{\\{q<a_{n}\\}}q^{2}\bigr{]}=\begin{cases}\mathcal{O}(n^{\frac{3-\tau}{\tau}}),&\text{
if }\tau<3,\\\ \mathcal{O}(\log n),&\text{ if }\tau=3,\\\
\mathcal{O}(1),&\text{ if }\tau>3,\end{cases}$

so that

$\mathfrak{m}_{2}^{(n)}=\begin{cases}\mathcal{O}_{P}(n^{\frac{3-\tau}{\tau}}),&\text{
if }\tau<3,\\\ \mathcal{O}_{P}(\log n),&\text{ if }\tau=3,\\\
\mathcal{O}_{P}(1),&\text{ if }\tau>3.\end{cases}$

In the case that $\sum_{r=1}^{n}q_{r}\geq 1$ we further have that

$\displaystyle\mathfrak{d}^{(n)}=$ $\displaystyle\
\frac{1}{2}\sum_{k=1}^{\infty}\Bigl{|}\frac{1}{n\mathfrak{m}_{1}^{(n)}}k\sum_{r=1}^{n}\operatorname{\mathbbm{1}}_{\\{d_{r}^{(n)}=k\\}}-\frac{1}{\mathbb{E}[D]}kp_{k}\Bigr{|}$
$\displaystyle\leq$ $\displaystyle\
\frac{1}{2}\frac{1}{\mathbb{E}[D]}\sum_{k=1}^{\infty}k\Bigl{|}\frac{1}{n}\sum_{r=1}^{n}\operatorname{\mathbbm{1}}_{\\{d_{r}^{(n)}=k\\}}-p_{k}\Bigr{|}+\frac{1}{2}\Bigl{|}1-\frac{\mathfrak{m}_{1}^{(n)}}{\mathbb{E}[D]}\Bigr{|}$
$\displaystyle\leq$ $\displaystyle\
\frac{1}{2}\frac{1}{\mathbb{E}[D]}\sum_{k=1}^{\infty}k\Bigl{|}\frac{1}{n}\sum_{r=1}^{n}\operatorname{\mathbbm{1}}_{\\{q_{r}=k\\}}-p_{k}\Bigr{|}+\frac{1}{\mathbb{E}[D]\,n}(q_{n}+1)+\frac{1}{2}\Bigl{|}1-\frac{\mathfrak{m}_{1}^{(n)}}{\mathbb{E}[D]}\Bigr{|}$

Letting
$\bar{S}^{(n)}_{k}=\frac{1}{n}\sum_{r=1}^{n}\operatorname{\mathbbm{1}}_{\\{q_{r}=k\\}}$
we get that

$\mathbb{E}[|\bar{S}^{(n)}_{k}-p_{k}|]\leq\operatorname{var}(\bar{S}^{(n)})^{1/2}\wedge(2p_{k})\leq\sqrt{\frac{p_{k}}{n}}\wedge(2p_{k}).$

Hence,

$\mathbb{E}\Bigl{[}\sum_{k=1}^{\infty}k|\bar{S}_{k}^{(n)}-p_{k}|\Bigr{]}\leq\sum_{k=1}^{\infty}k\sqrt{\frac{p_{k}}{n}}\wedge(2p_{k})=\begin{cases}\mathcal{O}(n^{-\frac{\tau-2}{\tau}}),&\text{
if }\tau<4,\\\ \mathcal{O}(n^{-1/2}\log n),&\text{ if }\tau=4,\\\
\mathcal{O}(n^{-1/2}),&\text{ if }\tau>4,\end{cases}$

where the $\mathcal{O}$ estimates follow with standard computations. In the
case that $\tau>3$ the random variables $q_{1},\dots$ have a finite second
moment and we get that

$|\mathfrak{m}_{1}^{(n)}-\mathbb{E}[D]|=\mathcal{O}_{P}(n^{-1/2}).$

If $\tau<3$, we let
$\bar{\mathfrak{m}}_{1}^{(n)}=\frac{1}{n}\sum_{k=1}^{n}q_{k}\operatorname{\mathbbm{1}}_{\\{q_{k}\leq\lceil
n^{1/(\tau-1)}\rceil\\}}$

$\displaystyle\mathbb{E}[|\mathfrak{m}_{1}^{(n)}-\mathbb{E}[D]|]$
$\displaystyle\leq\mathbb{E}\bigl{[}\mathfrak{m}_{1}^{(n)}-\bar{\mathfrak{m}}_{1}^{(n)}\bigr{]}+\mathbb{E}\bigl{[}\bigl{|}\bar{\mathfrak{m}}_{1}^{(n)}-\mathbb{E}[\bar{\mathfrak{m}}_{1}^{(n)}]\bigr{|}\bigr{]}$
$\displaystyle\qquad+\mathbb{E}[D]-\mathbb{E}\bigl{[}\bar{\mathfrak{m}}_{1}^{(n)}\bigr{]}.$

We bound the term in the middle by

$\mathbb{E}\bigl{[}\bigl{|}\bar{\mathfrak{m}}_{1}^{(n)}-\mathbb{E}[\bar{\mathfrak{m}}_{1}^{(n)}]\bigr{|}\bigr{]}\leq\operatorname{var}(\bar{\mathfrak{m}}_{1}^{(n)})^{1/2}\leq\frac{1}{\sqrt{n}}\Bigl{(}\sum_{k=1}^{\lceil
n^{1/(\tau-1)}\rceil}k^{2}p_{k}\Bigr{)}^{1/2}$

and get with standard computations that all three terms are of order
$\mathcal{O}(n^{-\frac{\tau-2}{\tau-1}})$ which is of lower order than
$n^{-\frac{\tau-2}{\tau}}$. Consequently,

$\mathfrak{d}^{(n)}=\begin{cases}\mathcal{O}_{P}(n^{-\frac{\tau-2}{\tau}}),&\text{
if }\tau<4,\\\ \mathcal{O}_{P}(n^{-1/2}\log n),&\text{ if }\tau=4,\\\
\mathcal{O}_{P}(n^{-1/2}),&\text{ if }\tau>4.\end{cases}$

We can couple $\mathbf{d}^{(1)},\mathbf{d}^{(2)},\dots$ in such a way that the
above $\mathcal{O}_{P}$ estimates hold actually almost surely as
$\mathcal{O}$-estimates (in the sense that the constant is allowed to be
random). For the appropriately coupled sequences one gets that, almost surely,

$\ell_{n}\mathfrak{p}_{n}\to 0,\
\ell_{n}\frac{\mathfrak{m}^{(n)}_{2}}{\sqrt{n}}\to 0\text{ \ and \
}\ell_{n}\mathfrak{d}^{(n)}\to 0.$

Choosing $G_{n}^{o_{n}}$ as random graph with fixed degree sequence
$\mathbf{d}^{(n)}$ we can apply Theorem A $\omega$-wise and get the result. ∎

## References

  * [AB92] D. Aldous and M. Brown.  Inequalities for rare events in time-reversible Markov chains I.  1992\.
  * [AS00] N. Alon and J. H. Spencer.  The probabilistic method.  Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, New York, second edition, 2000.
  * [AS04] D. Aldous and J. M. Steele.  The objective method: probabilistic combinatorial optimization and local weak convergence.  In Probability on discrete structures, volume 110 of Encyclopaedia Math. Sci., pages 1–72. Springer, Berlin, 2004.
  * [BKW14] I. Benjamini, G. Kozma, and N. Wormald.  The mixing time of the giant component of a random graph.  Random Structures Algorithms, 45(3):383–407, 2014.
  * [BS01] I. Benjamini and O. Schramm.  Recurrence of distributional limits of finite planar graphs.  Electron. J. Probab., 6:no. 23, 13, 2001.
  * [Dur07] R. Durrett.  Random graph dynamics, volume 20 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge, 2007.
  * [ER61] P. Erdős and A. Rényi.  On the evolution of random graphs.  Bull. Inst. Internat. Statist., 38:343–347, 1961.
  * [JL09] S. Janson and M. J. Luczak.  A new approach to the giant component problem.  Random Structures Algorithms, 34(2):197–216, 2009.