Research of the first author was funded by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) under Germany ’s Excellence Strategy EXC
2044 390685587, Mathematics Münster: Dynamics–Geometry–Structure

# Spectral properties of the strongly assortative stochastic block model and
their application to hitting times of random walks

Matthias Löwe missing<EMAIL_ADDRESS>and  Sara Terveer
<EMAIL_ADDRESS>
###### Abstract.

We analyze hitting times of simple random walk on realizations of the
stochastic block model. We show that under some natural assumptions the
average starting hitting time as well as the average target hitting time are
asymptotically almost surely given by $N(1+o(1))$. We also show a central
limit theorem for the average target hitting time. Our main techniques are a
spectral decomposition of these hitting times, a spectral analysis of the
adjacency matrix and the graph Laplacian, respectively, as well as a form of
the Delta method.

###### Key words and phrases:

random walk, stochastic block model, starting hitting time, target hitting
time, law of large numbers, central limit theorem, delta method

###### 2020 Mathematics Subject Classification:

05C81;05C80;60F05

##  1\. Introduction

Random walks on random graphs are very topical in contemporary probability
theory, see e.g. [AGvdH+22, Syl21, FKMP18, BLPS18] and the references therein.
Such random walks can be considered a special instance of random walk in
random environment and the principal question is, if and how this random
environment, hence the random graph in the situation considered in this note,
influences characteristic properties of such a random walk. For example,
[FR08] and [AGvdH+22] analyze the mixing time of simple random walks on random
graphs, while the focus in [SRbA05], [LT14], [LT23], and [LT22] is on the
(average) hitting times. Note however, that most results on random walks on
random graphs consider (sparse or dense) Erdős-Rényi graphs (the note [HL19]
is a slight exception, there the authors consider random (Erdős-Rényi type)
hypergraph models). As in [LT14], [LT23], and [LT22] in this note we will
consider average hitting times of random walks on random graphs. Our main
technique will be a spectral representation of the hitting times. Note that in
the recent manuscript [OS23] the authors take a different approach to hitting
times for very dense Erdős-Rényi random graphs (i.e. for them $p$ is a
constant, independent of the number of vertices) exploiting the fact that for
such graphs the diameter is $2$ with high probability.

In the present situation, the random environment, however, will be given by a
stochastic block model. To be more concrete, we consider a random graph
$G_{N}(M,P)=(V_{N},E_{N})$. $G_{N}(M,P)$ will be constructed according to the
stochastic block model, i.e. the vertex set $V_{N}=\\{1,\dots,N\\}$ is fixed
and consists of $M<N$ disjoint “blocks” $V^{(1)}_{N},\dots,V^{(M)}_{N}$ with
$N_{1},\dots,N_{M}$ vertices, where $\sum\limits_{i=1}^{M}N_{i}=N$. In the
present note, we will consider the situation where $N$ is a multiple of $M$
and choose $N_{1}=\dots=N_{M}=\frac{N}{M}$.

The unoriented edges of the graph are realized by stochastically independent
random variables $\varepsilon_{v,w}\in\\{0,1\\}$ (for the edge
$\\{v,w\\},v,w\in V_{N}$). The probabilities for $\varepsilon_{v,w}=1$ are
given by a (symmetric) $M\times M$ matrix denoted by $P\coloneqq P_{M}$. Hence
the probabilities for $\varepsilon_{v,w}=1$ just depend on the blocks the
vertices are in, and the entries $p_{i,j}(N)$ denote the probability for an
edge to exist between two vertices $v\in V^{(i)}_{N}$ and $w\in V^{(j)}_{N}$.

In the present note, we assume all edge probabilities between different blocks
to be identical $p_{0}(N)$, i.e. all off-diagonal entries of $P_{M}$ are
$p_{0}(N)$. The diagonal entries $p_{i,i}(N)$ are abbreviated by $p_{i}(N)$.
We assume that the $p_{i}(N)$ are sorted in descending order, i.e.
$p_{1}(N)\geq p_{2}(N)\geq\dots\geq p_{M}(N)$. This can easily be obtained by
rearranging the blocks of the model in the corresponding order. We will
additionally impose the relatively mild connectivity conditions

$\frac{M\log^{4}(N)}{N\cdot
p_{i}(N)\cdot(1-p_{i}(N))}\xrightarrow[]{N\to\infty}0\quad\text{for
$i=1,\dots,M$ and}\quad Np_{0}(N)\xrightarrow[]{N\to\infty}\infty.$ (1.1)

(note that subsequently, we will frequently omit the dependency of $N$ unless
necessary for clarity).

As a matter of fact, (1.1) implies that $G_{N}(M,P)$ is connected with
probability converging to 1, as $N\to\infty$ (which we will denote by
”asymptotically almost-surely (a.a.s.)” in the rest of the text). Each block
$i$ (without the edges leaving the block) constitutes an Erdős-Rényi graph on
$n=N/M$ vertices and connection probability $p_{i}$. Then,
$\frac{M\log^{4}(N)}{N\cdot p_{i}(N)\cdot(1-p_{i}(N))}$ is (more than)
sufficient to ensure that block number $i$ is connected a.a.s (fore ach
$i=1,\ldots,M$). Moreover, $Np_{0}(N)\xrightarrow[]{N\to\infty}\infty$,
guarantees that all blocks are connected with each other, a.a.s., hence the
entire graph is connected a.a.s. In the following results we will always
tacitly assume that our realization of the stochastic block model is
connected.

We also assume a strongly assortative model, meaning that the connectivity
outside of blocks is lower than within blocks, in particular we require it to
even be of lower order:

$M\cdot p_{0}(N)\ll p_{i}(N)$ (1.2)

for all $i=1,\dots,M$, where by $a_{N}\ll b_{N}$ we denote $a_{N}=o(b_{N})$,
i.e. $\frac{a_{N}}{b_{N}}\to 0$.

For fixed $N$ and a fixed realization $G=G_{N}$ of the stochastic block model,
consider the simple random walk in discrete time $(X_{t})$ on $G$: If $X_{t}$
is in $v\in V$ at time $t$, $X_{t+1}$ will be in $w$ with probability
$\frac{1}{d_{v}}$, where $d_{v}$ denotes the degree of $v$, if $\\{v,w\\}\in
E$, and with probability 0, otherwise. Note that. in principle, $(X_{t})$
could remain in $v$ when starting in $v$, as $\\{v,v\\}$ might be in $E$. The
invariant distribution of this walk is given by the measure

$\pi_{v}\coloneqq\frac{d_{v}}{\sum\limits_{w\in V}d_{w}}=\frac{d_{v}}{2|E|}.$

Let $H_{vw}$ be the expected time it takes the walk to reach vertex $w\in V$
when starting from vertex $v\in V$. Of course, $H_{vw}$ will typically be
sensitive to the choice of $v$ and $w$. To compensate for this, one averages
over either $v$ or $w$. More precisely, we define

$H_{w}:=\sum\limits_{v\in V}\pi_{v}H_{vw}\quad\text{ and }\quad
H^{v}:=\sum\limits_{w\in V}\pi_{w}H_{vw}$ (1.3)

to be the _mean target hitting time_ and the _mean starting hitting time_ ,
respectively. Note that $H_{w}$ and $H^{v}$ are expectation values in the
random walk measure, but with respect to the realization of the random graph,
they are random variables. In [LT14], the asymptotic behaviour of $H_{w}$ and
$H^{v}$ were analyzed on the level of a law of large numbers for an Erdős-
Rényi random graph. It was shown that

$H_{w}=N(1+o(1))\quad\text{ as well as }\quad H^{v}=N(1+o(1))$

asymptotically almost surely proving a conjecture from [SRbA05]. The results
were extended to central limit theorems in [LT23] and [LT22]. In [HL19] the
law of large numbers was extended to random hypergraphs. The aim of this paper
is to prove a similar law of large numbers for random waljks on random graphs
realized according to the stochastic block model.

To this end, we will need to need to introduce some further restrictions on
the $p_{i},i=0,\ldots,M$.

$p_{0}\gg\sqrt{\frac{p_{i}\log N}{NM}}.$ (1.4)

for all $i=1,\dots,M$. The necessity for a lower bound on $p_{0}$ will be
discussed at the end of this note.

Our goal is to prove the following statements:

######  Theorem 1.1.

Assume that $p_{1}=p_{2}=\dots=p_{M}$ and that conditions (1.1), (1.2) and
(1.4) hold. Then

$H^{v}=N(1+o(1))$

asymptotically almost surely.

######  Theorem 1.2.

Assume that $p_{1}=p_{2}=\dots=p_{M}$ and that conditions (1.1), (1.2) and
(1.4) hold. Then

$\displaystyle H_{w}=N(1+o(1))$

asymptotically almost surely.

######  Remark 1.3.

The results remains true if the number of blocks $M\coloneqq M(N)$ depends on
the number of vertices $N$, e.g. $M(N)=\log N$, as long as all other
conditions, especially eq. 1.1 and eq. 1.2 remain intact.

Once we have a result like Theorem 1.1 or Theorem 1.2 the question how large
the fluctuations around such a law of large numbers are, is quite automatic.
Indeed, in the situation of Theorem 1.2 we can extend the law of large numbers
for the average target hitting time above to a central limit theorem. In order
to be able to properly state it define

$\displaystyle\mu_{\mathrm{in}}$
$\displaystyle\coloneqq\bigg{[}(M\\!-\\!1)\binom{N/M+1}{2}+\binom{N/M}{2}\bigg{]}p,\quad$
$\displaystyle\mu_{\mathrm{out}}$
$\displaystyle\coloneqq\bigg{[}\binom{N}{2}-(M-1)\binom{N/M+1}{2}-\binom{N/M}{2}\bigg{]}q\text{
and }$ $\displaystyle\gamma$ $\displaystyle\coloneqq\frac{N}{M}(p+(M-1)q).$

Then the cental limit theorem for the target hitting time reas as follows

######  Theorem 1.4.

If $p\leq\bar{p}<1$ and the conditions of Theorem 1.2 hold, then

$\sqrt{\frac{p}{NM(1-p)}}\left(H_{w}-2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}-2\right)\xRightarrow{N\to\infty}\mathcal{N}(0,1),$

where $\xRightarrow{N\to\infty}$ denotes convergence in distribution.

The rest of this note is organized in the following way: A common approach to
average starting or target hitting times is via a representation in terms of
the eigenvalues and eigenvectors of a version of the Laplacian matrix of the
graph (see e.g [Lov96]). This matrix is closely related to the adjaceny matrix
of the graph. In a first step we therefore bound the eigenvalues of the
expected adjacency matrix in the stochastic block model. This will be done in
Section 2 using estimates for the matrix of the block transition
probabilities. In Section 3 the considerations of Section 2 will result in
asymptotic results for the eigenvalues of the adjacency matrix in the
stochastic block model. As one can already learn from Erdős-Rényi graphs
spectral gap estimates for the adjacency matrix and the Laplacian matrix play
an important role for the order of magnitude of $H^{i}$. These will be given
in Section 4. Finally, Section 5 contains the proof of Theorem 1.1, while in
Section 6 we will prove Theorem 1.2. In Section 7 we will prove the central
limit theorem for the target hitting time Theorem 1.4. A key idea will be a
use of the so called Delta method. Finally, we conclude with a short section
containing open problems and an example that illustrates that a lower bound on
$p_{0}$ is necessary for our theorems to hold.

##  2\. Eigenvalues of the expected adjacency matrix

In this section we will discuss the spectrum of the expected adjacency matrix
of a realization of the stochastic block model. Our approach to this is
analogous to that of [ACK15], and we reformulate it for the reader’s
convenience. Let us denote the (random) adjacency matrix of our random graph
$G_{N}$ by $A_{N}$, i.e. $A_{N}=(a_{v,w})_{v,w\in V_{N}}$ and $a_{v,w}=1$, if
$\\{v,w\\}\in E_{N}$, otherwise $a_{v,w}=0$.

It will turn out that the spectrum of ${\mathbb{E}}A_{N}$ is closely related
to the spectrum of $P_{M}$. We will therefore start with a quick analysis of
the eigenvalues of $P_{M}$. As it turns out, under the above assumptions, the
eigenvalues of $P_{M}$ are approximately given by its diagonal entries:

######  Lemma 2.1.

The eigenvalues $\lambda_{m}(P_{M}),m=1,\dots,M$ of the matrix $P_{M}$ can be
estimated by the following formula

$|\lambda_{m}(P_{M})-p_{m}|\leq(M-1)p_{0}$

$m=1,\dots,M$.

###### Proof.

The statement is an immediate consequence of Gershgorin’s circle theorem (see
e.g. [HJ13], p.388).∎

Next consider the expected adjacency matrix ${\mathbb{E}}A_{N}$ by which we
mean entry-wise expectation. Then ${\mathbb{E}}A_{N}$ consists of entries from
$P_{M}$ depending on the blocks the vertices are in. More precisely,
${\mathbb{E}}a_{v,w}=p_{i}$, if both $v$ and $w$ are in block $i,i=1,\ldots
M$, otherwise ${\mathbb{E}}a_{v,w}=p_{0}$. Not surprisingly, the spectrum of
${\mathbb{E}}A$ can be simply derived from the eigenvalues of $P_{M}$:

######  Lemma 2.2.

${\mathbb{E}}A$ has exactly $M$ non-zero eigenvalues. These are given by

$\frac{N}{M}\lambda_{m}(P_{M}),\qquad m=1,\dots,M.$ (2.1)

###### Proof.

Denoting by $J$ the $(N/M)\times(N/M)$ matrix in which each entry equals $1$,
we see that ${\mathbb{E}}A=P\otimes J$, where $\otimes$ denotes the Kronecker
product of two matrices matrices.

Since $J$ has only one non-zero eigenvalue, which is $\frac{N}{M}$, we obtain
that the $M$ non-zero eigenvalues of the matrix ${\mathbb{E}}A$ are given by
(2.1) as claimed by using the the spectrum of the Kronecker product of
matrices together with 2.1. ∎

##  3\. Eigenvalues of the adjacency matrix

Let us now turn to the actual adjacency matrix $A_{N}$. More precisely, we
consider the centered adjacency matrix of $G_{N}$, $X\coloneqq
A_{N}-{\mathbb{E}}A_{N}$ first.

Denote by

$\sigma^{2}\coloneqq\frac{1}{M}(\max\limits_{m=1,\dots,M}p_{m}(1-p_{m})+(M-1)p_{0}(1-p_{0})).$
(3.1)

With this notation we can give an upper bound on the maximal eigenvalue (in
absolute value) of the matrix $X$:

######  Theorem 3.1.

There is a constant $c$ such that

$\|X\|_{2}\leq 2\sqrt{N\sigma^{2}}+c\log(N)\sqrt[4]{N\sigma^{2}}$

holds asymptotically almost surely.

###### Proof.

We modify the proof of [ACK15], using the original approach by [Vu07] to our
model.

The core idea is to apply Wigner’s trace method and estimate the terms in the
trace of $X^{k}$ appropriately. To this end, we denote by $X_{v,w}$ the
entries of the matrix $X$. Each of the $X_{v,w}$ can only take two values:
Either $X_{v,w}=1-p_{m}$ and this happens with probability $p_{m}$ or
$X_{v,w}=-p_{m}$ and this event has probability $1-p_{m}$. Here $m$ is the
block number, if both $v$ and $w$ are in the $m$-th block, and $m=0$,
otherwise. We denote by

$\sigma_{m}^{2}=p_{m}(1-p_{m})$

the variance of these entries, depending on the edge’s block number
$m\in\\{0,\dots,M\\}$

Now clearly for an even integer $k$, we have

$\mathbb{E}\left[\mathrm{tr}\left(X^{k}\right)\right]=\sum\limits_{v_{1},\dots,v_{k}\in
V}\mathbb{E}\left[X_{v_{1},v_{2}}\cdots X_{v_{k-1},v_{k}}\cdot
X_{v_{k},v_{1}}\right]$ (3.2)

We interpret the sequence $I\coloneqq(v_{1},\dots,v_{k},v_{1})$ as a circular
path on the complete graph $K_{N}$ with edge weights $X_{v,w}$ for an
(undirected) edge $(v,w)\in V_{N}^{2}$.

Now each ordered sequence of vertices that constitutes
$I=(v_{1},\dots,v_{k},v_{1})$ corresponds to a number of distinct vertices
appearing in this sequence,

$s_{I}\coloneqq|S_{I}|\coloneqq|\\{v_{1},\dots,v_{k}\\}|$

and a permutation of $S_{I}$, giving the order in which the vertices appear
for the first time in the sequence: $J_{I}\coloneqq(w_{1},\dots,w_{s_{I}})$
such that $w_{1},\dots,w_{s_{I}}\in S_{I}$, $w_{l}\neq w_{m}$ for all $l\neq
m$.

Notice that the expectation of the weights of a path is 0 if there is at least
one edge $e$ with multiplicity 1 (i.e. $e$ only appears once within
$\\{v_{1},v_{2}\\},\dots\\{v_{k-1},v_{k}\\},\\{v_{k},v_{1}\\}$). We thus only
consider paths in which each edge appears with multiplicity larger or equal
than two. Because the path has $k$ edges in total, the number of distinct
edges, $\nu_{I}$, in the path is bounded by $k/2$, as $k$ is even. In a
circular path, the number of distinct vertices is at most the number of
distinct edges. Hence we also have $s_{I}\leq k/2$.

Now, for $2\leq x\leq s_{I}$ denote by $e_{x}^{I}$ the first edge
$(v_{l},v_{l+1})$ on the path $I$ such that $v_{l+1}=w_{x}$ (i.e. the first
edge that discovers the vertex $w_{x}$, the vertex $w_{1}$ is excluded as the
starting vertex of the path).

Notice that the absolute value of the entries of $X$ is bounded by
$K\coloneqq\max\limits_{i=0,\dots,m}p_{i}(1-p_{i})$. We use this to remove
edges from the product of weights of the path, keeping only “discovery” edges
$e_{2}^{I},\dots,e_{s_{I}}^{I}$ with multiplicity 2 each:

$\mathbb{E}\left[X_{v_{1},v_{2}}\cdots X_{v_{k-1},v_{k}}\cdot
X_{v_{k},v_{1}}\right]\leq
K^{k-2(t_{I}-1)}\mathbb{E}\left[\prod\limits_{s=2}^{t_{I}}X_{e_{s}^{I}}^{2}\right].$

We denote for an edge $e=\\{v,w\\}$ by

$B(e)=\begin{cases}m,&\text{if }v,w\in V^{(m)}\\\ 0,&\text{if }v\in
V^{(m)},w\in V^{(l)},\,l\neq m\end{cases}$

the block number, if $v$ and $w$ are in the same block, and 0 otherwise.

As the discovery edges are clearly pairwise different (as each discovers a new
vertex), we find

$\mathbb{E}\left[\prod\limits_{x=2}^{s_{I}}X_{e_{x}^{I}}^{2}\right]=\prod\limits_{x=2}^{s_{I}}\mathbb{E}\left[X_{e_{x}^{I}}^{2}\right]=\prod\limits_{x=2}^{s_{I}}\sigma_{B(e_{x}^{I})}^{2}$

Hence, we can write from eq. 3.2

$\mathbb{E}\left[\mathrm{tr}\left(X^{k}\right)\right]\leq\sum\limits_{s=1}^{k/2}K^{k-2(s-1)}\sum\limits_{\begin{subarray}{c}I=(v_{1},\dots,v_{k})\\\
s_{I}=s\end{subarray}}\prod\limits_{x=2}^{s}\sigma_{B(e_{x}^{I})}^{2}$

Let $s$ be fixed.

To bound the inner sum, we choose the discovery vertices of the path
successively. For the first one, we have $N$ options. For each following one
$2\leq x\leq s$ we have two scenarios

  * •

if the associated $x$-th discovery edge $e_{x}$ satisfies $B(e_{x})=m$ for
some $m=1,\dots,M$ (i.e. the vertex discovery happens from the same block),
then
$\sigma_{B(e_{x})}^{2}=\sigma_{m}^{2}\leq\max\limits_{l=1,\dots,M}\sigma_{l}^{2}\eqqcolon\sigma_{*}^{2}$,
and there are $N/M$ possibilities to choose the $x$-th discovery vertex.

  * •

if the associated $x$-th discovery edge $e_{x}$ satisfies $B(e_{x})=0$ (i.e.
the vertex discovery happens from a different block), then
$\sigma_{B(e_{x})}^{2}=\sigma_{0}^{2}$ and there are $(M-1)\cdot N/M$
possibilities to choose the $x$-th discovery vertex.

Now that all options for the discovery sequence are exhausted, it remains to
bound the number of paths with this exact discovery sequence which also
satisfies the same-block and different block-discoveries, respectively, as
chosen above. This, however, is bounded from above by the number of paths on
$K_{s}$ with this exact discovery sequence (i.e. we ignore the block
restrictions for discovery). This, in turn, is independent of the particular
discovery sequence, but only depends on the length of the path $k$ and the
length of the discovery sequence $s$. An upper bound for this is given by

$W^{\prime}(k,s)\coloneqq\binom{k}{2s-2}2^{2k-2s+3}s^{k-2s+2}(k-2s+4)^{k-2s+2}$
(3.3)

according to [Vu07, Lemma 4.1].

Overall, we thus obtain by differentiating over the number of same-block
discoveries $t$

$\displaystyle\mathbb{E}\left[\mathrm{tr}\left(X^{k}\right)\right]$
$\displaystyle\leq\sum\limits_{s=1}^{k/2}K^{k-2(s-1)}\cdot
N\cdot\sum\limits_{t=0}^{s-1}\binom{s-1}{t}\left(\frac{N}{M}\sigma_{*}^{2}\right)^{t}\left((M-1)\frac{N}{M}\sigma_{0}^{2}\right)^{s-1-t}\cdot
W^{\prime}(k,s)$ $\displaystyle\leq\sum\limits_{s=1}^{k/2}K^{k-2(s-1)}\cdot
N\cdot\left(\frac{N}{M}\right)^{s-1}\left(\sigma_{*}^{2}+(M-1)\sigma_{0}^{2}\right)^{s-1}\cdot
W^{\prime}(k,s)$ $\displaystyle=\sum\limits_{s=1}^{k/2}S(N,k,s).$ (3.4)

with

$S(N,k,s):=K^{k-2(s-1)}\cdot
N\cdot\left(\frac{N}{M}\right)^{s-1}\left(\sigma_{*}^{2}+(M-1)\sigma_{0}^{2}\right)^{s-1}\cdot
W^{\prime}(k,s).$

Now notice that by the definition of $\sigma^{2}$ (3.1) and by the definition
of the $W^{\prime}$-terms (3.3) we have for $s=1,\dots,k/2-1$

$\displaystyle\frac{S(N,k,s)}{S(N,k,s+1)}$ $\displaystyle\hskip
56.9055pt=\frac{K^{2}}{\sigma^{2}}\cdot\frac{1}{N}\cdot\frac{W^{\prime}(k,s)}{W^{\prime}(k,s+1)}$
$\displaystyle=\frac{K^{2}}{N\sigma^{2}}\cdot\frac{\binom{k}{2s-2}}{\binom{k}{2s}}\cdot\frac{2^{2k-2s+3}}{2^{2k-2s+1}}\cdot\frac{s^{k-2s+2}}{(s+1)^{k-2s}}\cdot\frac{(k-2s+4)^{k-2s+2}}{(k-2s+2)^{k-2s}}$
$\displaystyle=\frac{K^{2}}{N\sigma^{2}}\cdot\frac{2s(2s-1)}{(k+2-2s)(k+1-2s)}\cdot
4\cdot\frac{s^{k-2s+2}}{(s+1)^{k-2s}}\cdot(k-2s+4)^{2}\cdot\left(1+\frac{2}{k-2s+2}\right)^{k-2s}$
$\displaystyle\leq\frac{K^{2}}{N\sigma^{2}}\cdot\frac{2s(2s-1)}{(k+2-2s)(k+1-2s)}\cdot
4\cdot
s^{2}\cdot(k-2s+4)^{2}\cdot\left(\left(1+\frac{1}{k/2-s}\right)^{k/2-s}\right)^{2}$
$\displaystyle\leq\frac{8K^{2}s^{3}(2s-1)}{N\sigma^{2}}\cdot\frac{(k-2s+4)^{2}}{(k+2-2s)(k+1-2s)}\cdot
e^{2}$
$\displaystyle\leq\frac{8e^{2}K^{2}s^{3}(2s-1)}{N\sigma^{2}}\cdot\left(1+\frac{2}{k+2-2s}\right)\left(1+\frac{3}{k+1-2s}\right)$
$\displaystyle\leq\frac{8e^{2}K^{2}s^{3}(2s-1)}{N\sigma^{2}}\cdot
2\cdot\frac{5}{2}\leq\frac{80e^{2}K^{2}s^{4}}{N\sigma^{2}}\leq\frac{5e^{2}K^{2}k^{4}}{N\sigma^{2}}$

Hence, one can easily see that for

$k\leq\sqrt[4]{\frac{N}{10e^{2}}\cdot\frac{\sigma^{2}}{K^{2}}}$ (3.5)

we obtain

$\frac{S(N,k,s)}{S(N,k,s+1)}\leq\frac{1}{2}.$

Therefore, by geometric series and eq. 3.4

$\displaystyle\mathbb{E}\left[\mathrm{tr}(X^{k})\right]$ $\displaystyle\leq
S(N,k,k/2+1)=N\cdot N^{k/2}(\sigma^{2})^{k/2}\cdot
2^{k+1}=2N\left(2\sigma\sqrt{N}\right)^{k}$

Let $k=\sqrt[4]{\frac{N\sigma^{2}}{10e^{2}K^{2}}}$ is an even integer,
otherwise take the largest even integer bounded by eq. 3.5). Due to

$\|X\|_{2}^{k}=\max\limits_{m=1,\dots,N}|\lambda_{m}(X)|^{k}\leq\sum\limits_{m=1}^{N}\lambda_{m}(X)^{k}=\mathrm{tr}(X^{k})$

we obtain for some constant $c\in{\mathbb{R}}$ by a high moment Markov
inequality

$\displaystyle\mathbb{P}\left(\|X\|_{2}\geq
2\sigma\sqrt{N}+c\sigma^{1/2}\log(N)\cdot N^{1/4}\right)$
$\displaystyle\leq\frac{1}{(2\sigma\sqrt{N}+c\sigma^{1/2}\log(N)\cdot
N^{1/4})^{k}}\mathbb{E}\left[\mathrm{tr}(X^{k})\right]$
$\displaystyle\leq\frac{2N\left(2\sigma\sqrt{N}\right)^{k}}{(2\sigma\sqrt{N}+c\sigma^{1/2}\log(N)\cdot
N^{1/4})^{k}}$ $\displaystyle\leq 2N\left(1-\frac{c\sigma^{1/2}\log(N)\cdot
N^{1/4}}{2\sigma\sqrt{N}+c\sigma^{1/2}\log(N)\cdot N^{1/4}}\right)^{k}$
$\displaystyle\leq 2N\exp\left(-\frac{c\sigma^{1/2}\log(N)\cdot N^{1/4}\cdot
k}{2\sigma\sqrt{N}+c\sigma^{1/2}\log(N)\cdot N^{1/4}}\right)$
$\displaystyle=2N\exp\left(-\frac{c\log(N)\cdot
N^{1/2}\cdot\sqrt[4]{\frac{\sigma^{2}}{10e^{2}K^{2}}}}{2\sigma\sqrt{N}+c\sigma^{1/2}\log(N)\cdot
N^{1/4}}\right)$ $\displaystyle\leq
2N\exp\left(-c\sigma^{1/2}\frac{\log(N)\sqrt[4]{\frac{\sigma^{2}}{10e^{2}K^{2}}}}{2\sigma+c\sigma^{1/2}\frac{\log(N)}{N^{1/4}}}\right)$
$\displaystyle\leq
2N\exp\left(-c\sigma^{1/2}\frac{\log(N)\sqrt[4]{\frac{\sigma^{2}}{10e^{2}K^{2}}}}{3\sigma}\right)$
$\displaystyle=2N\exp\left(-c\frac{\log(N)}{3\sqrt[4]{10e^{2}}\sqrt{K}}\right)$
$\displaystyle=2N\exp\left(-c\frac{2\log(N)}{3\sqrt[4]{10e^{2}}}\right)$

where we use eq. 1.1 and $K\leq\frac{1}{4}$. For sufficiently large constant
$c$, the latter term converges to 0. ∎

######  Remark 3.2.

Together with eq. 1.1, the statement of 3.1 can be used to obtain

$\|X\|_{2}\leq 2\sqrt{N\sigma^{2}}(1+o(1))$

asymptotically almost surely. Indeed, note that this is the case, if and only
if

$\sqrt[4]{N\sigma^{2}}\gg\log N$

and by definition of $\sigma^{2}$ this is implied by

$Np_{i}(1-p_{i})\gg M\log^{4}N$

which is the first part of eq. 1.1.

Moreover, notice that this also gives uniform bound on the eigenvalues of $X$
since the spectral norm is sub-multiplicative.

We can finally give the asymptotically leading order of the eigenvalues of the
adjacency matrix $A$:

######  Proposition 3.3.

The $M$ largest eigenvalues of $A$ are given by

$\frac{N}{M}\lambda_{m}(P_{M})+O\left(\sqrt{N\sigma^{2}}\right),$

$m=1,\dots,M$, with probability converging to 1. All other eigenvalues of $A$
are bounded by

$\lambda_{m}(A)=O\left(\sqrt{N\sigma^{2}}\right)$

for $m>M$, with probability converging to 1.

###### Proof.

For a $N\times N$-matrix $R$, denote by
$\lambda_{1}(R)\geq\lambda_{2}(R)\geq\dots\geq\lambda_{N}(R)$ its eigenvalues
in descending order. As $A=X+{\mathbb{E}}A$, by Weyl’s interlacement theorem
[Par98, Theorem 10.3.1] we have

$\lambda_{N+1-i}(X)+\lambda_{N+1-j}({\mathbb{E}}A)\leq\lambda_{N+2-i-j}(A)\text{
and }\lambda_{i+j-1}(A)\leq\lambda_{i}(X)+\lambda_{j}({\mathbb{E}}A)$

From 3.2, we deduce that $\lambda_{i}(X)=O\left(\sqrt{N\sigma^{2}}\right)$
asymptotically almost surely for $i=1,\dots,N$. Therefore,

$O\left(\sqrt{N\sigma^{2}}\right)+\lambda_{N+1-j}({\mathbb{E}}A)\leq\lambda_{N+2-i-j}(A)\text{
and }\lambda_{i+j-1}(A)\leq
O\left(\sqrt{N\sigma^{2}}\right)+\lambda_{j}({\mathbb{E}}A)$

With $i=j=N+1-m$ in the first inequality and $j=m$, $i=1$ in the second, we
obtain for $m=1,\dots,N$

$O\left(\sqrt{N\sigma^{2}}\right)+\lambda_{m}({\mathbb{E}}A)\leq\lambda_{m}(A)\text{
and }\lambda_{m}(A)\leq
O\left(\sqrt{N\sigma^{2}}\right)+\lambda_{m}({\mathbb{E}}A)$

and consequently,

$\lambda_{m}(A)=\lambda_{m}({\mathbb{E}}A)+O\left(\sqrt{N\sigma^{2}}\right),$
(3.6)

with probability converging to 1. Together with 2.2 we obtain the claim. ∎

##  4\. Spectral gap of the symmetric normalized adjacency matrix

We now consider the matrix $B=D^{-1/2}AD^{-1/2}$, where
$D=\mathrm{diag}(d_{1},\dots,d_{n})$ and $d_{i}$ denoting the degree of the
vertex $i$. Since both, the average starting hitting time and average target
hitting time, have a decomposition in terms of the eigenvalues (and
eigenvectors of $B$) we are interested in bounding the spectrum of $B$.

To that end, let us begin by assuming that $p\coloneqq p_{1}=\dots=p_{M}$, and
$q=p_{0}$ (i.e. the probabilities for edges to exist are $p$ within each block
and $q$ between two different blocks).

It can easily be checked that the eigenvalues of $P_{M}$ in this case are
given by $p+(M-1)q$ and $p-q$ (with multiplicity $M-1$), c.f. [Gen86].

######  Remark 4.1.

The bounds on the largest eigenvalues only provide meaningful results when
$\sqrt{N\sigma^{2}}\ll\lambda_{m}({\mathbb{E}}A)$ for all $m=1,\dots,M$, i.e.
in this setting $\sqrt{N\sigma^{2}}\ll\frac{N}{M}(p-q)$, which is
straightforward to check.

Clearly,

$\gamma\coloneqq{\mathbb{E}}d_{v}=\frac{N}{M}p+(M-1)\frac{N}{M}q$ (4.1)

for $v=1,\dots,n$. Furthermore, by Chernoff’s inequality (c.f. Theorem 2.4 in
[CL06]), we find that

$\displaystyle\begin{split}d_{v}>\gamma-c\sqrt{\gamma}&\quad\text{with
probability }1-\exp\left(-\frac{c^{2}}{2}\right)\\\
d_{v}<\gamma+c\sqrt{\gamma}&\quad\text{with probability
}1-\exp\left(-\frac{c^{2}}{2\left(1+\frac{c}{3\sqrt{\gamma}}\right)}\right)\end{split}$
(4.2)

Denote

$R:=B-\gamma^{-1}A.$

It is well known that the spectral radius $\|R\|_{2}$ is bounded by all
consistent matrix norms and thus in particular $\|R\|_{2}\leq\|R\|_{\infty}$.

######  Lemma 4.2.

For $R$ as above, we have

$\|R\|_{\infty}\leq\sqrt{\frac{\log N}{\gamma}}\cdot(1+o(1))$

asymptotically almost surely.

###### Proof.

The proof is similar to that of Lemma 3.3 in [LT14] but given here for the
sake of completeness. Clearly, the entries of $R$ are given by
$r_{v,w}=\frac{\gamma-\sqrt{d_{v}d_{w}}}{\gamma\sqrt{d_{v}d_{w}}}a_{v,w}$ By
setting $c={\sqrt{\log N}}$ in eq. 4.2,

$|d_{v}-\gamma|\leq\sqrt{\log N\gamma}\quad\mbox{ for all $v=1,\dots,N$}$

with probability converging to 1. Hence,

$|\gamma-\sqrt{d_{v}d_{w}}|\leq\sqrt{\log N\gamma}$

with probability tending to 1. Furthermore,

$d_{v}d_{w}>(\gamma-\sqrt{\log N\gamma})^{2}$

with probability converging to 1. Thus,

$\displaystyle\|R\|_{\infty}=\max\limits_{v=1,\dots,N}\sum\limits_{w=1}^{N}|r_{v,w}|$
$\displaystyle=\max\limits_{v=1,\dots,N}\sum\limits_{w=1}^{N}\left|\frac{\gamma-\sqrt{d_{v}d_{w}}}{\gamma\sqrt{d_{v}d_{w}}}a_{v,w}\right|$
$\displaystyle\leq\frac{\sqrt{\log N\gamma}}{\gamma(\gamma-\sqrt{\log
N\gamma})}\max\limits_{v=1,\dots,N}\sum\limits_{w=1}^{N}a_{v,w}$
$\displaystyle=\frac{\sqrt{\log N\gamma}}{\gamma(\gamma-\sqrt{\log
N\gamma})}\max\limits_{v=1,\dots,N}d_{v}$ $\displaystyle\leq\frac{\sqrt{\log
N\gamma}(\gamma+\sqrt{\log N\gamma})}{\gamma(\gamma-\sqrt{\log N\gamma})}$
$\displaystyle=\sqrt{\frac{\log N}{\gamma}}\cdot\frac{(\gamma+\sqrt{\log
N\gamma})}{(\gamma-\sqrt{\log N\gamma})}$ $\displaystyle=\sqrt{\frac{\log
N}{\gamma}}\cdot\frac{1+\sqrt{\frac{\log N}{\gamma}}}{1-\sqrt{\frac{\log
N}{\gamma}}}$ $\displaystyle=\sqrt{\frac{\log N}{\gamma}}\cdot(1+o(1))$

since by condition (1.1) $\gamma\gg\log^{4}(N)$. ∎

Next, consider the eigenvalues of $B$:

######  Proposition 4.3.

The $M$ largest eigenvalues of $B$ are given by

$\lambda_{1}(B)=1+O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$

and

$\lambda_{2}(B)=\dots=\lambda_{M}(B)=\gamma^{-1}\frac{N}{M}(p-q)+O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$ (4.3)

asymptotically almost surely.

The remaining eigenvalues are given by

$\lambda_{m}(B)=O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$

for all $m=M+1,\dots,N$ asymptotically almost surely. .

###### Proof.

Again, by Weyl’s interlacement theorem [Par98, Theorem 10.3.1] we obtain the
inequalities

$\lambda_{N+1-i}(R)+\lambda_{N+1-j}(\gamma^{-1}A)\leq\lambda_{N+2-i-j}(B)\text{
and }\lambda_{i+j-1}(B)\leq\lambda_{i}(R)+\lambda_{j}(\gamma^{-1}A)$

Let $n\in\\{1,\dots,N\\}$. Choosing $i=1$ and $j=N+1-n$ in the first
inequality and $i=1$, $j=n$ in the second inequality, we obtain

$\lambda_{N}(R)+\lambda_{n}(\gamma^{-1}A)\leq\lambda_{n}(B)\text{ and
}\lambda_{n}(B)\leq\lambda_{1}(R)+\lambda_{n}(\gamma^{-1}A).$

Thus, using 3.3, 4.2, the bound from 4.1, we obtain for $m\in\\{1,\dots,M\\}$

$\displaystyle\lambda_{m}(B)$ $\displaystyle\geq O(\sqrt{\gamma^{-1}\log
N})+\gamma^{-1}\frac{N}{M}\lambda_{m}(P_{M})+O(\gamma^{-1}\sqrt{N\sigma^{2}})$
$\displaystyle\lambda_{m}(B)$ $\displaystyle\leq O(\sqrt{\gamma^{-1}\log
N})+\gamma^{-1}\frac{N}{M}\lambda_{m}(P_{M})+O(\gamma^{-1}\sqrt{N\sigma^{2}})$

asymptotically almost surely. For $m^{\prime}\in\\{M+1,\dots,N\\}$ we arrive
at

$\displaystyle\lambda_{m^{\prime}}(B)$ $\displaystyle\geq
O(\sqrt{\gamma^{-1}\log N})+O(\gamma^{-1}\sqrt{N\sigma^{2}})$
$\displaystyle\lambda_{m^{\prime}}(B)$ $\displaystyle\leq
O(\sqrt{\gamma^{-1}\log N})+O(\gamma^{-1}\sqrt{N\sigma^{2}}).$

asymptotically almost surely. ∎

Notice that using the definition of $\gamma$ (4.1) for the $M-1$ largest, non-
Perron eigenvalues, we obtain

$\displaystyle\lambda_{m}(B)$ $\displaystyle=\frac{N}{\gamma
M}(p-q)+O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$
$\displaystyle=\frac{N}{M}\frac{(p-q)}{\frac{N}{M}p+\frac{N}{M}(M-1)q}+O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$
$\displaystyle=\frac{(p-q)}{p-q+Mq}+O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$
$\displaystyle=1-\frac{Mq}{p+(M-1)q}+O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$
$\displaystyle=1-\frac{Nq}{\gamma}+O\left(\sqrt{\gamma^{-1}\log
N}\right)+O\left(\gamma^{-1}\sqrt{N\sigma^{2}}\right)$ (4.4)

asymptotically almost surely and for $m=2,\dots,M$.

Using equations (1.1) and (1.2), we find that

$\gamma^{-1}\log N=\frac{\log N}{\frac{N}{M}(p+(M-1)q)}\approx\frac{M\log
N}{Np}\to 0,\ $ (4.5)

as $N\to\infty$, i.e. $\sqrt{\gamma^{-1}\log N}=o(1)$. Here and below for two
sequence $(a_{N}),(b_{N})$ we write $a_{N}\approx b_{N}$, if and only if,
$\frac{a_{N}}{b_{N}}\to 1$ as $N\to\infty$.

Furthermore,

$\frac{N\sigma^{2}}{\gamma}\leq 1\ll\log N,$

hence

$\gamma^{-1}\sqrt{N\sigma^{2}}\ll\sqrt{\gamma^{-1}\log N}=o(1),$

implying that the second $O$-term is negligible compared to the first one.

Since $\gamma^{-1}Nq\approx\frac{Mq}{p}$ and $Mq\ll p$, we further find that

$O(\sqrt{\gamma^{-1}\log N})\ll\gamma^{-1}Nq\approx\frac{Mq}{p}\ll 1.$ (4.6)

due to (1.4), so both $O$-terms are negligible compared to the rest of the
expression.

##  5\. Spectral decomposition of the average starting hitting time and proof
of Theorem 1.1

Using the spectral decomposition of the average starting hitting time
according to [Lov96] (c.f [LT14, LT23]) and Proposition 4.3, we obtain that
with probability converging to 1

$\displaystyle H^{v}$
$\displaystyle=\sum\limits_{k=2}^{N}\frac{1}{1-\lambda_{k}(B)}$
$\displaystyle=\sum\limits_{k=2}^{M}\frac{1}{1-\lambda_{k}(B)}+\sum\limits_{k=M+1}^{N}\frac{1}{1-\lambda_{k}(B)}$
$\displaystyle=(M-1)\frac{1}{\gamma^{-1}Nq+O(\sqrt{\gamma^{-1}\log
N})}+(N-M)(1+o(1))$ $\displaystyle=\frac{(M-1)\gamma}{Nq+O(\sqrt{\gamma\log
N)}}+(N-M)(1+o(1))$

The second term is asymptotically $N$ (up to some lower order terms). For the
first term, we notice that due to (4.6), $Nq\to\infty$ and using that $Mq\ll
p$ together with (1.4),

$\frac{(M-1)\gamma}{Nq+O(\sqrt{\gamma\log N})}=(M-1)\gamma\cdot
o(1)=(M-1)\frac{N}{M}(p+(M-1)q)\cdot o(1)\leq Np\cdot o(1)=o(N),$

therefore the first term is negligible compared to the second. Altogether,

$H^{v}=N(1+o(1))$

asymptotically almost surely, proving the claim.

##  6\. Spectral decomposition of the average target hitting time and proof of
Theorem 1.2

Using the spectral decomposition of the average starting hitting time
according to [Lov96] (c.f [LT14, LT22]), we find

$H_{w}=\frac{2|E|}{d_{w}}\sum\limits_{k=2}^{N}\frac{1}{1-\lambda_{k}}u_{k,w}^{2},$
(6.1)

where $u_{k,w}$ denotes the $w$-th entry of the eigenvector associated with
the eigenvalue $\lambda_{k}(B)$. We will always normalize these eigenvectors
to have length $1$. We immediately notice that since we assume
$p_{1}=p_{2}=\dots=p_{M}$ from (4.2) and a similar Chernoff bound for $|E|$ we
obtain

$\frac{2|E|}{d_{w}}=N(1+o(1)),$ (6.2)

asymptotically almost surely (which can be proved analogous to the same result
in [LT14] for the Erdős-Rényi graph).

In a similar way as in [LT22] and using that that $|\lambda_{k}|<1$ and we can
therefore apply a geometric series, we note that

$\displaystyle Z_{N}\coloneqq$
$\displaystyle\sum\limits_{k=2}^{N}\frac{1}{1-\lambda_{k}}u_{k,w}^{2}=\sum\limits_{k=2}^{N}\sum\limits_{m=0}^{\infty}\lambda_{k}^{m}u_{k,w}^{2}=\sum\limits_{k=2}^{N}\left(1+\lambda_{k}+\lambda_{k}^{2}\sum\limits_{m=0}^{\infty}\lambda_{k}^{m}\right)u_{k,w}^{2}$
$\displaystyle=$
$\displaystyle\sum\limits_{k=2}^{N}\left(1+\lambda_{k}+\lambda_{k}^{2}\frac{1}{1-\lambda_{k}}\right)u_{k,w}^{2}$

Now one immediately checks that eigenvector corresponding to $\lambda_{1}$ is
the componentwise square root of the stationary distribution $\pi$, i.e.
$u_{1,w}^{2}=\pi_{w}$. Moreover, the matrix of the eigenvectors
$\mathcal{U}:=(u_{k,w})_{k,w=1}^{N}$ is unitary, which implies that
$\sum\limits_{k=1}^{N}u_{k,w}^{2}=1$. Since $\mathcal{U}$ is a unitary matrix
we obtain

$\sum\limits_{k=2}^{N}\lambda_{k}u_{k,w}^{2}=\sum\limits_{k=1}^{N}\lambda_{k}u_{k,w}^{2}-\pi_{w}=\sum\limits_{k=1}^{N}\sum\limits_{v=1}^{N}B_{w,v}u_{k,v}u_{k,w}-\pi_{w}=\sum\limits_{v=1}^{N}B_{w,v}\cdot\langle
u_{v},u_{w}\rangle-\pi_{w}=B_{w,w}-\pi_{w}.$

Here we denote the entries of the matrix $B$ by $B_{v,w}$. Thus we arrive at

$\displaystyle Z_{N}=$
$\displaystyle\sum\limits_{k=2}^{N}u_{k,w}^{2}+\sum\limits_{k=2}^{N}\lambda_{k}u_{k,w}^{2}+\sum\limits_{k=2}^{N}\frac{1}{1-\lambda_{k}}\lambda_{k}^{2}u_{k,w}^{2}=1+B_{w,w}-2\pi_{j}+\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}.$
(6.3)

We will rewrite the sum on the right hand side of (6.3) in a separate lemma:

######  Lemma 6.1.

Under the conditions of Theorem 1.2,

$\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}\leq\frac{C}{Nq}\xrightarrow[]{N\to\infty}0$

with probability converging to 1. If additionally $p\leq\bar{p}<1$, then

$\sqrt{\frac{Np}{M(1-p)}}\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}\xrightarrow[]{N\to\infty}0$

with probability converging to 1.

###### Proof.

With Proposition 4.3 and (4.6), we find $\lambda_{k}\leq\lambda_{2}\leq
1-\frac{Nq}{\gamma}(1+o(1))$ for all $k=2,\dots,N$. Thus,

$\displaystyle\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}\leq\frac{1+o(1)}{\gamma^{-1}Nq}\cdot\sum\limits_{k=2}^{N}{\lambda_{k}^{2}}u_{k,w}^{2}.$
(6.4)

and by (4.2)

$\displaystyle\sum\limits_{k=1}^{N}\lambda_{k}^{2}u_{k,w}^{2}$
$\displaystyle=\sum\limits_{k=1}^{N}(\lambda_{k}u_{k,w})^{2}=\sum\limits_{k=1}^{N}\Big{(}\sum\limits_{v=1}^{N}B_{w,v}u_{k,v}\Big{)}^{2}$
$\displaystyle=\sum\limits_{k=1}^{N}\sum\limits_{v=1}^{N}\sum\limits_{v^{\prime}=1}^{N}B_{w,v}B_{w,v^{\prime}}u_{k,v}u_{k,v^{\prime}}=\sum\limits_{v=1}^{N}\sum\limits_{v^{\prime}=1}^{N}B_{w,v}B_{w,v^{\prime}}\sum\limits_{k=1}^{N}u_{k,v}u_{k,v^{\prime}}$
$\displaystyle=\sum\limits_{v=1}^{N}\sum\limits_{v^{\prime}=1}^{N}B_{w,v}B_{w,v^{\prime}}\langle
u_{\lx@ams@boldsymbol@cdot,v},u_{\lx@ams@boldsymbol@cdot,v^{\prime}}\rangle=\sum\limits_{v=1}^{N}\sum\limits_{v^{\prime}=1}^{N}B_{w,v}B_{w,v^{\prime}}\delta_{v,v^{\prime}}=\sum\limits_{v=1}^{N}B_{w,v}^{2}=\sum\limits_{v=1}^{N}\frac{a_{v,w}}{d_{v}d_{w}}$
$\displaystyle\leq\frac{1}{\gamma-\sqrt{\log
N\cdot\gamma}}\cdot\frac{1}{d_{w}}\cdot\sum\limits_{v=1}^{N}a_{v,w}=\frac{1}{\gamma-\sqrt{\log
N\cdot\gamma}}$

with probability converging to 1. Therefore, we find that

$\sum\limits_{k=2}^{N}\lambda_{k}^{2}u_{k,w}^{2}=\sum\limits_{k=1}^{N}\lambda_{k}^{2}u_{k,w}^{2}-u_{1,w}^{2}\leq\frac{1}{\gamma-\sqrt{\log
N\cdot\gamma}}-\pi_{w}=\frac{1}{\gamma}(1+o(1))-\frac{1}{N}(1+o(1))=O(\gamma^{-1})$

with probability converging to 1. Together with (6.4), we find that with
probability converging to 1, there is some constant $C>0$ such that

$\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}\leq\frac{O(\gamma^{-1})}{\gamma^{-1}Nq}\leq\frac{C}{Nq}$

and if $p\leq\bar{p}<1$, then for some constant $C^{\prime}>0$

$\sqrt{\frac{Np}{M(1-p)}}\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}\leq
C^{\prime}\sqrt{\frac{Np}{M}}\cdot\frac{1}{Nq}\leq\frac{C\sqrt{p}}{\sqrt{NMq^{2}}}\xrightarrow[]{N\to\infty}0,$

with probability converging to 1, since $q\gg\sqrt{\frac{p}{NM}}$ due to
(1.4). ∎

With this lemma at hand, we can now simplify $Z_{N}$. Starting from (6.3) and
using again $\gamma^{-1}Nq\approx\frac{Mq}{p}$ we obtain

$\displaystyle Z_{N}$
$\displaystyle=1+B_{w,w}-2\pi_{j}+\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}=1+\frac{a_{w,w}}{d_{w}}-2\pi_{j}+o(1)=1+o(1)$

asymptotically almost surely, using (4.2) and (6.2). Therefore, putting things
together, from (6.1) we see that

$H_{w}=N(1+o(1))(1+o(1))=N(1+o(1))$

asymptotically almost surely, as proposed.

##  7\. Central limit theorem for the target hitting time

As mentioned in the introduction we can extend the law of large numbers type
result for the average target hitting time Theorem 1.2 above to a central
limit theorem, Theorem 1.4. This will be proven in the present section. For
the most part, the proof is similar to that given by us in [LT22] for the
central limit theorem for the target hitting time in an Erdős-Rényi graph. We
will use several techniques from that paper, most notably a particular version
of the Delta method. The original form of this method can e.g. be found in
[vdV98] (see Theorem 3.8 therein). We will use a version that we recently
proved (see the appendix in [LT22]). We will state this version for the
reader’s convenience below.

In order to obtain a central limit theorem for the average target hitting time
$H_{w}$, the same decomposition as previously seen in (6.1) will become
useful. Indeed, we will see that the scaling as well as the centering of the
central limit theorem depends solely on the factor $\frac{2|E|}{d_{w}}$ again
(see also the statement of Theorem 1.4). This means that the statement in
(6.2), has to be enhanced to a convergence in distribution. Similarly,
negligibility of the spectral term has to be made more precise as well to
account for the scaling of the central limit theorem.

The proof of Theorem 1.4 can be split into several parts. More precisely, we
break down the spectral decomposition of the average target hitting time into
its factors. Recall the definitions of $\mu_{\mathrm{in}}$ and
$\mu_{\mathrm{out}}$: with

$\displaystyle\mu_{\mathrm{in}}$
$\displaystyle\coloneqq\bigg{[}(M\\!-\\!1)\binom{N/M+1}{2}+\binom{N/M}{2}\bigg{]}p,\quad$
$\displaystyle\mu_{\mathrm{out}}$
$\displaystyle\coloneqq\bigg{[}\binom{N}{2}-(M-1)\binom{N/M+1}{2}-\binom{N/M}{2}\bigg{]}q$

Then, the following proposition holds true:

######  Proposition 7.1.

If $p\leq\bar{p}<1$ and the conditions of Theorem 1.2 hold, then for all
vertice $w\in V$

$\sqrt{\frac{Np}{M(1-p)}}\left(\log\Big{(}2\frac{|E\Setminus
N_{w}|}{d_{w}}+2\Big{)}-\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\right)\xRightarrow{N\to\infty}\mathcal{N}\left(0,1\right).$
(7.1)

Here $N_{w}\subseteq E$ denotes the set of edges in $E$ that have one end in
the vertex $w$, i.e.

$N_{w}=\\{\\{v,v^{\prime}\\}\in E:w\in\\{v,v^{\prime}\\}\\}.$

The proof of Proposition 7.1 will be given with the help of several lemmas.

Before stating them, let us introduce a few additional notations. We will
enumerate the vertices in such a way that for $i=1,\dots,M$, and $B_{i}$
denoting the $i$-th block, $B_{i}$ contains the vertices
$(i-1)\frac{N}{M}+1$,…,$i\frac{N}{M}$. Without loss of generality, we assume
that the vertex $w$ is $N$ (so the target vertex is the last vertex in the
enumeration, and satisfies $w\in B_{M}$). This can, of course, be achieved by
relabeling the vertices and blocks, if necessary (note that this is possible,
since we assume that all blocks have the same size and the probabilities
$p_{i}$ are identical). We further write $B(v)$ for the block of a vertex
$v\in V$, i.e. if $v\in B_{i}$, $B(v)=B_{i}$.

Now we further decompose the representation (6.1) of the average target
hitting time: Notice that

$E\Setminus N_{w}=E_{\mathrm{in}}\cup E_{\mathrm{out}},$

where $E_{\mathrm{in}}$ denotes the edges between vertices of the same block
(excluding $w$) and $E_{\mathrm{out}}$ denotes the edges between vertices of
different blocks and, of course, none of the edges in $E_{\mathrm{in}}\cup
E_{\mathrm{out}}$ contains the vertex $w$. We further decompose
$E_{\mathrm{in}}$ according to the blocks, i.e.

$E_{\mathrm{in}}=\bigcup\limits_{i=1}^{M}E_{i}\coloneqq\bigcup\limits_{i=1}^{M}\Big{\\{}\\{v,v^{\prime}\\}\subset
B(i):w\notin\\{v,v^{\prime}\\}\Big{\\}}.$

Moreover, note that

$E_{\mathrm{out}}=\Big{\\{}\\{v,v^{\prime}\\}\in E:B(v)\neq
B(v^{\prime})\text{ and }w\notin\\{v,v^{\prime}\\}\Big{\\}}$

Then the decomposition of $E\Setminus N_{w}$ into the $E_{i}$ and
$E_{\mathrm{out}}$ is a disjoint decomposition, so

$|E\Setminus
N_{w}|=|E_{\mathrm{out}}|+|E_{\mathrm{in}}|=|E_{\mathrm{out}}|+\sum\limits_{i=1}^{M}|E_{i}|.$
(7.2)

Note that the summands in 7.2 are random variables and as such they are
independent of each other since edges are realized independently of each
other.

Let us give the asymptotic behaviour for the separate summands:

######  Lemma 7.2.

Under the conditions of Theorem 1.2 the following central limit theorem holds:

$\frac{1}{\sqrt{M\binom{N/M}{2}p(1-p)}}\Big{(}|E_{\mathrm{in}}|-\mu_{\mathrm{in}}\Big{)}\Rightarrow\mathcal{N}(0,1).$

###### Proof.

For $i=1,\dots,M-1$, there are $\frac{N}{M}$ vertices in the block $B_{i}$.
Hence, for each $i=1,\dots,M-1$, there are $\binom{N/M+1}{2}$ potential edges
(including loops) within the block $E_{i}$, implying that for each $i$ the
random variable $|E_{i}|$ is binomially distributed with parameters
$\binom{N/M+1}{2}$ and $p_{i}=p$. For block $B_{M}$, we notice that we only
can consider $\frac{N}{M}-1$ vertices for $E_{M}$, since $w\in E_{M}$.
Therefore, the random variable $|E_{M}|$ is binomially distributed with
parameters $\binom{N/M}{2}$ and $p_{M}=p$. By the Lindeberg-Feller central
limit theorem for schemes of random variables we thus find that

$\frac{1}{\sqrt{\binom{N/M}{2}p_{i}(1-p_{i})}}\Big{(}|E_{i}|-\tbinom{N/M+1}{2}p_{i}\Big{)}\Rightarrow\mathcal{N}(0,1)$

for $i=1,\dots,M-1$, and

$\frac{1}{\sqrt{\binom{N/M}{2}p_{M}(1-p_{M})}}\Big{(}|E_{M}|-\tbinom{N/M}{2}p_{M}\Big{)}\Rightarrow\mathcal{N}(0,1).$

Note that because $\binom{N/M+1}{2}\approx\binom{N/M}{2}$, the adjustment in
the first scaling term is immaterial. Since $|E_{i}|$, $i=1,\dots,M$ are
independent and $p_{1}=\dots=p_{M}=p$ in our specific model, by (7.2)

$\frac{1}{\sqrt{\binom{N/M}{2}p(1-p)}}\Big{(}|E_{\mathrm{in}}|-\Big{[}(M\\!-\\!1)\tbinom{N/M+1}{2}p+\tbinom{N/M}{2}p\Big{]}\Big{)}\Rightarrow\mathcal{N}(0,M).$

Rescaling yields the claim. ∎

######  Lemma 7.3.

Under the assumptions of Theorem 1.4 we have the following central limit
theorem for $E_{\mathrm{out}}$:

$\frac{1}{\sqrt{M\binom{N/M}{2}p(1-p)}}\big{(}|E_{\mathrm{out}}|-\mu_{\mathrm{out}}\big{)}\xrightarrow[N\to\infty]{{\mathbb{P}}}0.$

###### Proof.

Note that the number of potential edges in $E_{\mathrm{out}}$ is the number of
total potential edges (without those edges adjacent to $w$) minus the
potential edges within the blocks. This number is given by

$\displaystyle L$
$\displaystyle\coloneqq\binom{N}{2}-(M-1)\binom{N/M+1}{2}-\binom{N/M}{2}$
$\displaystyle=\left(\frac{N}{M}\right)^{2}\binom{M}{2}-(M-1)\frac{N}{M}.$

Thus, $|E_{\mathrm{out}}|$ is binomially distributed with parameters $L$ and
$q$. Recall that $\mu_{\mathrm{out}}=Lq$. Thus there is a constant $C>0$ such
that

$\displaystyle{\mathbb{E}}$
$\displaystyle\left[\bigg{(}\frac{1}{\sqrt{M\binom{N/M}{2}p(1-p)}}\big{(}|E_{\mathrm{out}}|-\mu_{\mathrm{out}}\big{)}\bigg{)}^{2}\right]$
$\displaystyle=\frac{1}{M\cdot\binom{N/M}{2}p(1-p)}\mathbb{V}\left(|E_{\mathrm{out}}|\right)$
$\displaystyle=\frac{Lq(1-q)}{M\cdot\binom{N/M}{2}p(1-p)}$
$\displaystyle=\frac{\frac{N}{M}\cdot\left(\frac{N}{M}\binom{M}{2}-(M-1)\right)\cdot
q(1-q)}{\frac{N}{M}\cdot M\cdot\frac{1}{2}(\frac{N}{M}-1)\cdot p(1-p)}$
$\displaystyle=\frac{\frac{N-2}{2}(M-1)\cdot q(1-q)}{\frac{1}{2}(N-M)\cdot
p(1-p)}$ $\displaystyle=\frac{(N-2)(M-1)\cdot q(1-q)}{(N-M)\cdot p(1-p)}$
$\displaystyle\leq
C\cdot\frac{N-2}{N-M}\cdot\frac{Mq}{p}\xrightarrow[]{N\to\infty}0,$

since we assumend that $p\leq\bar{p}$ and we have that $N-2\approx N\approx
N-M$ and $Mq\ll p$. Chebychev’s inequality yields the claim. ∎

We are now ready to prove Proposition 7.1:

###### Proof of Proposition 7.1.

By Slutzky’s theorem applied to Lemmas 7.2 and 7.3,

$\frac{1}{\sqrt{M\binom{N/M}{2}p(1-p)}}\Big{(}|E\Setminus
N_{w}|-\big{(}\mu_{\mathrm{in}}+\mu_{\mathrm{out}}\big{)}\Big{)}\Rightarrow\mathcal{N}(0,1)$
(7.3)

Note that the degree $d_{w}$ can be written as

$d_{w}=\sum_{v\in B_{N}}\varepsilon_{v,w}+\sum_{v\notin
B_{N}}\varepsilon_{v,w}$

The first sum has expectation $\frac{N}{M}p$ and variance $\frac{N}{M}p(1-p)$
such that by the classical Lindeberg-Feller central limit theorem

$\frac{\sum_{v\in
B_{N}}\varepsilon_{v,w}-\frac{N}{M}p}{\sqrt{\frac{N}{M}p(1-p)}}\xRightarrow{N\to\infty}\mathcal{N}(0,1).$

On the other hand, similar to the proof of Lemma 7.3

$\displaystyle 0\leq$
$\displaystyle\,{\mathbb{E}}\left[\left(\frac{\sum_{v\notin
B_{N}}\varepsilon_{v,w}-((M-1)\frac{N}{M}q)}{\sqrt{\frac{N}{M}p(1-p)}}\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\,\frac{(M-1)\frac{N}{M}q(1-q)}{\frac{N}{M}p(1-p)}$
$\displaystyle\lesssim$ $\displaystyle\,\frac{Mq(1-q)}{p(1-p)}\to 0$

by the assumptions that $p$ is bounded away from 1 and (1.2). Hence by Slutzky
again we obtain,

$\frac{1}{\xi}(d_{w}-\gamma)\xRightarrow{N\to\infty}\mathcal{N}(0,1),$

with
$\xi^{2}\coloneqq\frac{N}{M}p(1-p)\approx\frac{N}{M}\big{(}p(1-p)+(M-1)q(1-q)\big{)}=\mathbb{V}\left(d_{w}\right)$.
Thus by independence of $d_{w}$ and $E\Setminus N_{w}$ and (7.3):

$\left(\frac{|E\Setminus
N_{w}|}{\sqrt{M\binom{N/M}{2}p(1-p)}},\frac{d_{w}}{\xi}\right)-\left(\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\sqrt{M\binom{N/M}{2}p(1-p)}},\frac{\gamma}{\xi}\right)\xRightarrow{N\to\infty}\mathcal{N}(0,I),$

where $I$ is the $2\times 2$ identity matrix. Consequently

$\rho_{N}\cdot(T_{N}-\theta_{N})\xRightarrow{N\to\infty}\mathcal{N}(0,I)=T$

with

$\rho_{N}:=\sqrt{\tfrac{Np}{M(1-p)}},\text{ }T_{N}:=\bigg{(}\frac{|E\Setminus
N_{w}|}{\sqrt{\binom{N/M}{2}Np^{2}}},\frac{d_{w}}{\frac{N}{M}p}\bigg{)}^{t},\text{
and
}\theta_{N}=\left(\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\sqrt{\binom{N/M}{2}Np^{2}}},\frac{\gamma}{\frac{N}{M}p}\right)^{t}$
(7.4)

For the reader’s convenience we will cite Definition 3.3 from [LT22]:

######  Definition 7.4.

Consider an open set $D\subset{\mathbb{R}}^{k}$, $k\in{\mathbb{N}}$ and a
sequence of vectors $(x_{n})_{n\in{\mathbb{N}}}\subset D$. For
$l\in{\mathbb{N}}$, let $f:D\to{\mathbb{R}}^{l}$ be a continuous function (on
$D$). We call $f$ _uniformly continuous with respect to the sequence
$(x_{n})$_ if for any $\varepsilon>0$ there is a $\delta>0$ and an
$N\in{\mathbb{N}}$, so that for all $z\in{\mathbb{R}}^{k}$ with $\|z\|<\delta$
and $n\geq{\mathbb{N}}$

$\|f(x_{n}+z)-f(x_{n})\|<\varepsilon.$

Here, by $\|\cdot\|$, we denote the Euclidean norm.

In [LT22, Theorem A.2] we showed the following version of the Delta method:

######  Theorem 7.5 (Delta-Method).

Consider an open set $D\subset{\mathbb{R}}^{k}$ and random vectors $T_{n}$
with values in $D$ and satisfying
$\rho_{N}(T_{n}-\theta_{n})\xRightarrow{N\to\infty}T$ for vectors
$\theta_{n}\in D$, scalars $\rho_{N}\to\infty$ and a random vector
$T\in{\mathbb{R}}^{k}$. Consider a continuously differentiable function
$\phi:D\to{\mathbb{R}}$. Furthermore, assume that $\nabla\phi$ is uniformly
continuous with respect to $\theta_{n}$ and that
$\lim\limits_{n\to\infty}\nabla\phi(\theta_{n})$ exists. Then

$\rho_{N}\left(\phi(T_{n})-\phi(\theta_{n})\right)\xRightarrow{N\to\infty}\bigl{(}\lim\limits_{n\to\infty}\nabla\phi(\theta_{n})\bigr{)}^{t}\cdot
T.$

By $\nabla\phi$ we denote the gradient of $\phi$.

We will use Definition 7.4 and Theorem 7.5 with $k=2$ and $D=(0,\infty)^{2}$.
Notice that with the above defintions $\theta_{N}\in D$ for $N\geq 3$. Let us
consider the following (continuously differentiable) function

$\displaystyle\phi:D$
$\displaystyle\to{\mathbb{R}},\quad(x,y)\mapsto\log\tfrac{x}{y}$

We observe that $\nabla\phi(x,y)=\left(\frac{1}{x},-\frac{1}{y}\right)$ is
uniformly continuous on $D^{\prime}=(\frac{1}{2},\infty)^{2}$, and since
$\theta_{N}\in D^{\prime}$ for all $N\geq 3$, $\nabla\phi(x,y)$ is uniformly
continuous with respect to $\theta_{N}$. Finally,
$\lim\limits_{n\to\infty}\nabla\phi(\theta_{n})=(0,-1)^{t}$. Thus, we are in
the situation to apply Theorem 7.5 to obtain

$\rho_{N}(\phi(T_{N})-\phi(\theta_{N}))\xRightarrow{N\to\infty}\left(\lim\limits_{N\to\infty}\nabla\phi(\theta_{N})\right)^{t}\cdot
T.$

Now $T$ is a two-dimensional normal distribution with expectation vector $0$
and identity covariance matrix. Therefore, multiplying it by $(0,-1)^{t}$
gives a one-dimensional standard normal distribution $\mathcal{N}(0,1)$. Thus

$\sqrt{\tfrac{Np}{M(1-p)}}\left[\log\left(\sqrt{\tfrac{2}{N-M}}\cdot\tfrac{|E\Setminus
N_{w}|}{d_{w}}\right)-\log\left(\sqrt{\tfrac{2}{N-M}}\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}\right)\right]\xRightarrow{N\to\infty}\mathcal{N}\left(0,1\right)$

which yields

$\sqrt{\tfrac{Np}{M(1-p)}}\left(\log\Big{(}2\frac{|E\Setminus
N_{w}|}{d_{w}}\Big{)}-\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}\Big{)}\right)\xRightarrow{N\to\infty}\mathcal{N}\left(0,1\right).$

For another application of the Delta method we will consider the one-
dimensional situation, i.e. $k=1$ with

$D=(0,\infty),\,\rho_{N}=\sqrt{\tfrac{Np}{M(1-p)}},\,T_{N}=\log\left(2\tfrac{|E\Setminus
N_{w}|}{d_{w}}\right),\,\theta_{N}=2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma},\,\mbox{and
}\phi(x)=\log(e^{x}+2).$

Note that again $\phi$ is continuously differentiable on $D$ with

$\nabla\phi(x)=\frac{1}{1+\frac{2}{\exp(x)}}$

and

$\lim\limits_{n\to\infty}\nabla\phi(\theta_{n})=1.$

Furthermore, $\nabla\phi$ is uniformly continuous with respect to
$\theta_{n}$. By applying the Delta method again, we obtain

$\sqrt{\frac{Np}{M(1-p)}}\left(\log\Big{(}2\frac{|E\Setminus
N_{w}|}{d_{w}}+2\Big{)}-\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\right)\xRightarrow{N\to\infty}\mathcal{N}\left(0,1\right).$

which was our claim. ∎

A final ingredient is needed to complete the proof of the central limit
theorem for the target hitting time:

######  Proposition 7.6.

Under the assumptions of Theorem 1.4,

$\sqrt{\frac{Np}{M(1-p)}}\log\left(\sum\limits_{k=2}^{N}\frac{1}{1-\lambda_{k}}u_{k,w}^{2}\right)\xrightarrow[N\to\infty]{{\mathbb{P}}}0,$

for every $w\in\\{1,\dots,N\\}$.

###### Proof.

To prove the proposition, let us rewrite the term in the logarithm analogously
as above.

$\displaystyle Z_{N}\coloneqq$
$\displaystyle\sum\limits_{k=2}^{N}\frac{1}{1-\lambda_{k}}u_{k,w}^{2}=1+B_{w,w}-2\pi_{w}+\sum\limits_{k=2}^{N}\frac{\lambda_{k}^{2}}{1-\lambda_{k}}u_{k,w}^{2}.$

As $\pi_{v}=\frac{d_{v}}{2|E|}$ for all $v=1,\ldots,N$ and the $d_{v}$ are
identically distributed it is obvious that the $\pi_{v}$ are identically
distributed for $v=1,\dots,N$. Furthermore, $\sum_{v=1}^{N}d_{v}=2|E|$. Thus
we obtain

$N\mathbb{E}\left[\pi_{w}\right]=\sum\limits_{v=1}^{N}\mathbb{E}\left[\pi_{v}\right]=\frac{1}{2|E|}{\mathbb{E}}\Bigl{[}\sum\limits_{v=1}^{N}d_{v}\Bigr{]}=1.$

Therefore,

${\mathbb{E}}\Bigl{[}\sqrt{\tfrac{Np}{M(1-p)}}\pi_{w}\Bigr{]}=\sqrt{\tfrac{p}{NM(1-p)}}\xrightarrow[]{N\to\infty}0$

and by non-negativity of $\sqrt{\frac{Np}{M(1-p)}}\pi_{w}$ and Markov’s
inequality,

$\sqrt{\tfrac{Np}{M(1-p)}}\pi_{w}\xrightarrow[N\to\infty]{{\mathbb{P}}}0.$

and similarly using (4.2)

$\sqrt{\tfrac{Np}{M(1-p)}}B_{w,w}=\sqrt{\tfrac{Np}{M(1-p)}}\frac{a_{w,w}}{d_{w}}\xrightarrow[N\to\infty]{{\mathbb{P}}}0.$

Combining the last two statements with Lemma 6.1 yields

$\sqrt{\frac{Np}{M(1-p)}}(Z_{N}-1)\xrightarrow[N\to\infty]{{\mathbb{P}}}0.$

Now, if $a_{n}$ is a sequence of non-negative numbers and $X_{n}$ is a
sequence of random variables, with $a_{n}\to\infty$ and $a_{n}X_{n}\to 0$ in
probability, then $a_{n}\log(1+X_{n})$ converges to 0 in probability (see
Lemma A.1 in [LT22]). Therefore,

$\sqrt{\tfrac{Np}{M(1-p)}}\log Z_{N}\xrightarrow[N\to\infty]{{\mathbb{P}}}0,$

proving the claim. ∎

###### Proof of Theorem 1.4.

Recall the decomposition (6.1). Moreover, notice that

$\frac{2|E|}{d_{w}}=\frac{2|E\Setminus N_{w}|}{d_{w}}+2.$

We therefore obtain that

$\displaystyle\sqrt{\frac{Np}{M(1-p)}}$ $\displaystyle\hskip
56.9055pt\left(\log(H_{w})-\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\right)$
$\displaystyle=\sqrt{\frac{Np}{M(1-p)}}\left[\log\left(2\frac{|E\Setminus
N_{w}|}{d_{w}}+2\right)+\log\left(\sum\limits_{k=2}^{n}\frac{1}{1-\lambda_{k}}u_{k,w}^{2}\right)-\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\right]$
$\displaystyle=\sqrt{\frac{Np}{M(1-p)}}\left[\log\left(2\frac{|E\Setminus
N_{w}|}{d_{w}}+2\right)-\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\right]$
$\displaystyle\hskip
241.84842pt{+\sqrt{\frac{Np}{M(1-p)}}\log\left(\sum\limits_{k=2}^{N}\frac{1}{1-\lambda_{k}}v_{k,w}^{2}\right).}$

The first term on the right hand side above converges to a standard Gaussian
random variable in distribution (cf. Proposition 7.1). The second summand on
the right hand side converges to 0 in probability (cf. Proposition 7.6).
Putting things together with the help of Slutzky’s theorem we obtain

$\sqrt{\frac{Np}{M(1-p)}}\left(\log(H_{w})-\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\right)\xRightarrow{N\to\infty}\mathcal{N}(0,1)$
(7.5)

To arrive at our claim we apply the Delta method from Theorem 7.5 one more
time: We choose $k=2$,

$D=({\mathbb{R}}^{+})^{2},\,\rho_{N}=\sqrt{\tfrac{Np}{M(1-p)}},\,T_{N}=(\log{H_{w}},N)^{t},\,\theta_{N}=(\log\big{(}2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\big{)},N)^{t},$

and $\phi(x,y)=\tfrac{1}{y}\exp(x).$ Observe again that we have chosen a
$\phi$ that is continuously differentiable with

$\nabla\phi(x,y)=\left(\tfrac{1}{y}\exp(x),-\tfrac{1}{y^{2}}\exp(x)\right)^{t}$

Moreover, we have that

$\lim\limits_{n\to\infty}\nabla\phi(\theta_{n})=(1,0)^{t}.$

Here and subsequently, a crucial idea is to notice that
$2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N\gamma}\to 1$ as $N\to\infty$
and therefore, the term is bounded by a constant $C>1$.

Furthermore, we can show that $\nabla\phi$ is uniformly continuous with
respect to $\theta_{n}$: Indeed, let $\varepsilon>0$ be arbitrary, but fixed.
Then, we choose $\delta$ as $\delta=\frac{\varepsilon}{2C}+\frac{1}{C}$ and
$z=(z_{1},z_{2})$ with $0<\|z\|<\delta$. Without loss of generality, let
$z_{1},z_{2}>0$ (for negative $z_{1}$ or $z_{2}$, we can proceed in the same
way). We then see that

$\displaystyle\nabla$
$\displaystyle\phi(\theta_{N}\\!+\\!z)-\nabla\phi(\theta_{N})$
$\displaystyle=\Big{(}\tfrac{1}{N\\!+\\!z_{2}}\exp\Big{[}\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\\!+\\!z_{1}\Big{]},-\tfrac{1}{(N\\!+\\!z_{2})^{2}}\exp\Big{[}\log\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{\gamma}+2\Big{)}\\!+\\!z_{1}\Big{]}\Big{)}^{t}$
$\displaystyle\qquad-\Big{(}2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N\gamma}+\frac{2}{N},-2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N^{2}\gamma}-\frac{2}{N^{2}}\Big{)}^{t}$
$\displaystyle=\left(\Big{(}2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{(N\\!+\\!z_{2})\gamma}+\tfrac{2}{N\\!+\\!z_{2}}\Big{)}e^{z_{1}}-\Big{(}2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N\gamma}+\tfrac{2}{N}\Big{)},-\Big{(}2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{(N\\!+\\!z_{2})^{2}\gamma}+\tfrac{2}{(N\\!+\\!z_{2})^{2}}\Big{)}e^{z_{1}}-\Big{(}2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N^{2}\gamma}+\tfrac{2}{N^{2}}\Big{)}\right)^{t}$

Since, both $\mu_{\mathrm{in}}$ and $\mu_{\mathrm{out}}$ are of order $N$, one
readily checks that the second component of the vector on the right hand side
is of order $O\left(\frac{1}{N}\right)$. The same is true for the terms
$\frac{2}{N+z_{2}}$ and $\frac{2}{N}$. Thus,

$\displaystyle\|\nabla\phi(\theta_{N}\\!+\\!z)-\nabla\phi(\theta_{N})\|$
$\displaystyle=\sqrt{\left(2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{(N\\!+\\!z_{2})\gamma}e^{z_{1}}-2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N\gamma}\right)^{2}+O\left(\tfrac{1}{N}\right)^{2}}$
$\displaystyle\leq
2\tfrac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N\gamma}\left|\tfrac{N(e^{z_{1}}-1)-z_{2}}{N+z_{2}}\right|+O\left(\tfrac{1}{N}\right)$
$\displaystyle\leq
C\cdot\left|e^{z_{1}}-1\right|+\tfrac{z_{2}}{N}+O\left(\tfrac{1}{N}\right)$
$\displaystyle=Ce^{z_{1}}-1+O\left(\tfrac{1}{N}\right),$

since we assumed that $z_{1}>0$.

Now due to $z_{1}<\|z\|<\delta$ and our choice of $\delta$ we obtain

$Ce^{z_{1}}<Ce^{\delta}=\frac{\varepsilon}{2}+1.$

Moreover, naturally, there is some $N_{0}\in{\mathbb{N}}$ so that for all
$N\geq N_{0}$, the $O\left(\frac{1}{N}\right)$-term is bounded by
$\frac{\varepsilon}{2}$. Thus, for all $N\geq N_{0}$ and all $z\in D$ with
$\|z\|<\delta$,

$\|\nabla\phi(\theta_{N}\\!+\\!z)-\nabla\phi(\theta_{N})\|<\varepsilon,$

which proves uniform continuity with respect to $\theta_{N}$. By Theorem 7.5
we thus finally get,

$\sqrt{\frac{Np}{M(1-p)}}\left(\frac{H_{w}}{N}-2\frac{\mu_{\mathrm{in}}+\mu_{\mathrm{out}}}{N\gamma}-\frac{2}{N}\right)\xRightarrow{N\to\infty}\mathcal{N}(0,1)$

This completes the proof.∎

##  8\. Example and open questions

In the previous sections we have seen that the hitting times for simple random
walk on (a realization) of the stochastic block model in a certain regime of
parameters behave like those for simple random walk on (a realization) of a
supercritical Erdős-Rényi graph. This is true for their laws of large numbers
and also for the central limit theorem for the target hitting time. However,
the stochastic block model has a variety of parameters and we could not cover
all regimes. In this section we will pose a number of open problems that
basically all concern the parameter regimes we were not able to cover. We also
give an example that makes it plausible that a lower bound on $p_{0}=q$ is
required for our results to hold.

######  Conjectures and Open Problems 8.1.

  1. (1)

How do Theorems 1.1, 1.2 and 1.4 change, if the $p_{1},\ldots,p_{M}$ are not
equal? We conjecture that at least Theorems 1.1, 1.2 remain valid, if the
$p_{i},i=1,\ldots,M$ are different but of the same order, but $p_{i}\gg p_{0}$
for all $i=1,\ldots,M$. One can imagine that even the latter condition can be
relaxed, since Theorems 1.1, 1.2 and 1.4 are also true for random walks on a
supercritical Erdős-Rényi graph.

  2. (2)

In this paper we just consider blocks $V^{(1)}_{N},\dots,V^{(M)}_{N}$ that are
of the same size. Are Theorems 1.1, 1.2 and 1.4 still true, if we have blocks
with different sizes? We conjecture that this is the case as long none of the
blocks is asymptotically negligible compared to the other blocks.

  3. (3)

In the present note we always assume a strongly assortative setting, i.e.
$p_{i}\gg p_{0}$ for all $i=1,\ldots,M$. One could ask the same questions in
the strongly disassortative setting, where $p_{i}\ll p_{0}$ for all
$i=1,\ldots,M$. We would conjecture that also in such models our results
remain true, if there is a lower bound on the $p_{i}$ (e.g.
$p_{i}\gg\log^{\kappa}(N)/N$ for some large enough $\kappa$).

We conclude with an example that shows that in our situation (i.e. equal block
sizes, $p_{1}=p_{2}=\ldots=p_{M}\gg p_{0}$) already Theorems 1.1 and 1.2 are
no longer true without a lower bound on $p_{0}$. Note that our example is a a
deterministic graph, rather than a random graph. However, without a lower
bound on $p_{0}$ of the form $Np_{0}\to\infty$ one can construct realizations
of a stochastic block model with $p_{1}=p_{2}=\ldots=p_{M}=1$ and $p_{0}$ very
small (depending on which variant of the example we consider) where,
conditionally on connectedness of the graph, the hitting time of a random walk
behaves similarly. Even so, the condition on $p_{0}$ in Theorem 1.2 might be
an artifact of our techniques.

######  Example 8.2.

Consider the following graph on $V_{N}=\\{1,\ldots,N\\}$ with $N$ even. Split
$V_{N}$ into $V^{(1)}_{N}=\\{1,\ldots,N/2\\}$ and $V^{(2)}_{N}:=V_{N}\Setminus
V^{(1)}_{N}.$ Within $V^{(1)}_{N}$ and $V^{(2)}_{N}$ we connect every pair of
vertices while between $V^{(1)}_{N}$ and $V^{(2)}_{N}$ there is just one
connection: $\\{1,N/2+1\\}$. Then the degrees of the vertices are all $N/2-1$
with exception of $d_{1}$ and $d_{N/2+1}$ which are $N/2$. Hence also the
invariant distribution $\pi_{v}$ is almost constant $1/N$. We select our
starting point according to this invariant distribution and, say, we pick a
vertex in $V^{(1)}_{N}$. Then the expected hitting time of the vertex $1$ is
$N/2\log(N/2)$. Whenever we are in vertex $1$ we have a $1/N$ probability to
walk to block $V^{(2)}_{N}$. Hence, the average hitting time of block
$V^{(2)}_{N}$ is already of order $N^{2}/2\log^{2}(N)$. The same is true if we
start in block $V^{(2)}_{N}$ and it does not matter whether we consider target
or starting hitting times.

Of course, from a random graph perspective, this example might look a bit
extreme, but even if we connect each point in $V^{(1)}_{N}$ to exactly one
point in $V^{(2)}_{N}$ (mimicking a situation where $p_{0}=2/N$) the hitting
time of $V^{(2)}_{N}$ when starting in $V^{(1)}_{N}$ is of order $N\log N$ and
hence bigger than $N$.

## References

  * [ACK15] Konstantin Avrachenkov, Laura Cottatellucci, and Arun Kadavankandy.  Spectral Properties of Random Matrices for Stochastic Block Model.  Research Report RR-8703, INRIA Sophia-Antipolis, France ; INRIA, April 2015.
  * [AGvdH+22] Luca Avena, Hakan Güldas, Remco van der Hofstad, Frank den Hollander, and Oliver Nagy.  Linking the mixing times of random walks on static and dynamic random graphs.  Stochastic Process. Appl., 153:145–182, 2022.
  * [BLPS18] Nathanaël Berestycki, Eyal Lubetzky, Yuval Peres, and Allan Sly.  Random walks on the random graph.  Ann. Probab., 46(1):456–490, 2018.
  * [CL06] Fan Chung and Linyuan Lu.  Complex graphs and networks, volume 107 of CBMS Regional Conference Series in Mathematics.  Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006.
  * [FKMP18] Alan Frieze, Michael Krivelevich, Peleg Michaeli, and Ron Peled.  On the trace of random walks on random graphs.  Proc. Lond. Math. Soc. (3), 116(4):847–877, 2018.
  * [FR08] N. Fountoulakis and B. A. Reed.  The evolution of the mixing rate of a simple random walk on the giant component of a random graph.  Random Structures Algorithms, 33(1):68–86, 2008.
  * [Gen86] Michel Gendreau.  On the location of eigenvalues of off-diagonal constant matrices.  Linear Algebra and its Applications, 79:99–102, 1986.
  * [HJ13] Roger A. Horn and Charles R. Johnson.  Matrix analysis.  Cambridge University Press, Cambridge, second edition, 2013.
  * [HL19] Amine Helali and Matthias Löwe.  Hitting times, commute times, and cover times for random walks on random hypergraphs.  Statist. Probab. Lett., 154:108535, 6, 2019.
  * [Lov96] L. Lovász.  Random walks on graphs: a survey.  In Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), volume 2 of Bolyai Soc. Math. Stud., pages 353–397. János Bolyai Math. Soc., Budapest, 1996.
  * [LT14] Matthias Löwe and Felipe Torres.  On hitting times for a simple random walk on dense Erdös-Rényi random graphs.  Statist. Probab. Lett., 89:81–88, 2014.
  * [LT22] Matthias Löwe and Sara Terveer.  A central limit theorem for the average target hitting time for a random walk on a random graph, 2022.
  * [LT23] Matthias Löwe and Sara Terveer.  A central limit theorem for the mean starting hitting time for a random walk on a random graph.  J. Theor. Probab., 36:779–810, 2023.
  * [OS23] Andrea Ottolini and Stefan Steinerberger.  Concentration of hitting times in erdös-rényi graphs, 2023.
  * [Par98] Beresford N. Parlett.  The Symmetric Eigenvalue Problem.  Society for Industrial and Applied Mathematics, 1998.
  * [SRbA05] V. Sood, S. Redner, and D. ben Avraham.  First-passage properties of the Erdös-Rényi random graph.  J. Phys. A, 38(1):109–123, 2005.
  * [Syl21] John Sylvester.  Random walk hitting times and effective resistance in sparsely connected Erdös-Rényi random graphs.  J. Graph Theory, 96(1):44–84, 2021.
  * [vdV98] A. W. van der Vaart.  Asymptotic statistics, volume 3 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, Cambridge, 1998.
  * [Vu07] Van H. Vu.  Spectral norm of random matrices.  Combinatorica, 27(6):721–736, 2007.