# Theorems on the Geometric Definition
of the Positive Likelihood Ratio (LR+)

Dr. Jacques Balayla MD, MPH, CIP, FRCSC111To whom correspondence should be
addressed: Dr. Jacques Balayla MD, MPH, CIP, FRCSC. Quilligan Scholar. e-mail:
<EMAIL_ADDRESS>Osler Fellow. Department of Obstetrics and
Gynecology. McGill University, Montreal, Quebec, Canada

###### Abstract

From the fundamental theorem of screening (FTS) we obtain the following
mathematical relationship relaying the pre-test probability of disease $\phi$
to the positive predictive value $\rho(\phi)$ of a screening test:

$\displaystyle\lim_{\varepsilon\to
2}{\displaystyle\int_{0}^{1}}{\rho(\phi)d\phi}=1$

where $\varepsilon$ is the screening coefficient - the sum of the sensitivity
($a$) and specificity ($b$) parameters of the test in question. However, given
the invariant points on the screening plane, identical values of $\varepsilon$
may yield different shapes of the screening curve since $\varepsilon$ does not
respect traditional commutative properties. In order to compare the
performance between two screening curves with identical $\varepsilon$ values,
we derive two geometric definitions of the positive likelihood ratio (LR+),
defined as the likelihood of a positive test result in patients with the
disease divided by the likelihood of a positive test result in patients
without the disease, which helps distinguish the performance of both screening
tests. The first definition uses the angle $\beta$ created on the vertical
axis by the line between the origin invariant and the prevalence threshold
$\phi_{e}$ such that $LR+=\frac{a}{1-b}=cot^{2}{(\beta)}$. The second
definition projects two lines $(y_{1},y_{2})$ from any point on the curve to
the invariant points on the plane and defines the LR+ as the ratio of its
derivatives $\frac{dy_{1}}{dx}$ and $\frac{dy_{2}}{dx}$. Using the concepts of
the prevalence threshold and the invariant points on the screening plane, the
work herein presented provides a new geometric definition of the positive
likelihood ratio (LR+) throughout the prevalence spectrum and describes a
formal measure to compare the performance of two screening tests whose
screening coefficients $\varepsilon$ are equal.

##  1 The Fundamental Theorem of Screening

From the fundamental theorem of screening we obtain the following mathematical
relationship relaying the positive predictive value ($\rho$) to the pre-test
probability ($\phi$), which equals the prevalence of disease amongtst
individuals at baseline risk [1]:

$\displaystyle\lim_{\varepsilon\to
2}{\displaystyle\int_{0}^{1}}{\rho(\phi)d\phi}=1$ (1)

where $\varepsilon$ is equal to the sum of the sensitivity ($a$) and
specificity ($b$) parameters of a screening test in question [2]. Equation (1)
holds since the Euclidean plane, henceforth referred to as the screening
plane, which contains the domain and range of the screening curve is a square
of dimensions 1 x 1 and consequently, of area 1.

###  1.1 The Screening Plane

Graphically, the screening plane can be depicted as follows, with the vertical
axis representing the positive predictive value and the horizontal axis
representing the pre-test probability or prevalence of disease:

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$$\phi$$\rho(\phi)$

Figure 1. The Screening Plane

As can be readily observed, the range and domain of the screening curve span
from [0-1], and all curves share $at$ $least$ two invariant points at [0,0]
and [1,1] [2]. While we’re restricting the screening plane to this square in
order to obtain clinically useful information, the screening curve extends
beyond this area.

##  2 Invariant Points

In mathematics, a fixed point (sometimes shortened to fixpoint, also known as
an invariant point) of a function is an element of the function’s domain that
is mapped to itself by the function. That is to say, c is a fixed point of the
function $f$ if $f$(c) = c [3]. In other words, there is a point with
coordinates $\\{c,f(c)\\}$ that equals $\\{c,c\\}$. Invariant points do not
move when a specific transformation is applied. However, points which are
invariant under one transformation may not be invariant under a different
transformation [3]. We can illustrate graphically the invariant points at the
extremes of the screening plane at [0,0] and [1,1], with multiple screening
curves with different sensitivity and specificity parameters in the same plane
as follows:

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$$\phi$$\rho(\phi)$

Figure 2. Screening curves with different $\varepsilon$ values

##  3 Non-Commutative Properties of $\varepsilon$

Two identical values of $\varepsilon$ will yield different screening curves
depending on the individual values of the sensitivity and specificity. In this
sense, the make-up of $\varepsilon$ is non-commutative because the equation
for the positive predictive value isn’t linear. Take as an example two
different tests whose $\varepsilon$ value equal to 1.70. The first case we
have a sensitivity of 95$\%$ and a specificity of 75$\%$. In the second case,
we have the reverse, a sensitivity of 75$\%$ and a specificity of 95$\%$ [4].

Graphically, these scenarios yield the following curves:

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$$\phi$$\rho(\phi)$

Figure 3. Identical values of $\varepsilon$ yield different screening curves

It is clear therefore that despite $\varepsilon_{1}$ = $\varepsilon_{2}$ =
1.70, the areas under the curve are different such that:

${\displaystyle\int_{0}^{1}}{{\rho_{2}}(\phi)d\phi}>{\displaystyle\int_{0}^{1}}{{\rho_{1}}(\phi)d\phi}$

To overcome the non-commutative properties of $\varepsilon$ and determine
which tests performs better under standard conditions, we can take advantage
of the invariant points of the screening curve at the extremes of the domain,
namely the origin [0,0] and the endpoint [1,1].

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$$\phi$$\rho(\phi)$

Figure 4. Invariant points (red) on the screening plane

##  4 The Likelihood Ratio

The likelihood ratio is a computable statistic which provides a direct
estimate of how much a test result will change the odds of having a disease
[5]. In essence, the likelihood ratio (LR) for a dichotomous test is defined
as the likelihood of a test result in patients with the disease divided by the
likelihood of the test result in patients without the disease. Both the
positive and negative likelihood ratios can be calculated depending on the
clinical scenario by simply using the sensitivity and specificity parameters
of a test. A LR close to 1 means that the test result does not change the
likelihood of disease or the outcome of interest appreciably [5]. The more the
likelihood ratio for a positive test (LR+) is greater than 1, the more likely
the disease or outcome [6]. The more a likelihood ratio for a negative test is
less than 1, the less likely the disease or outcome. Thus, LRs correspond to
the clinical concepts of ruling in and ruling out disease [5].

##  5 The Prevalence Threshold

We have previously defined the prevalence threshold as the prevalence level on
the screening curve below which screening tests start to produce an increasing
amount of false positive results [2]. In technical terms, this is equivalent
to the inflection point, also known as point of greatest curvature, on the
screening curve below which the the rate of change of a test’s positive
predictive value drops at a differential pace relative to the prevalence [2].
This value, termed $\phi_{e}$, is defined at the following point on the
prevalence (pre-test probability) axis:

$\phi_{e}=\frac{\sqrt{a\left(-b+1\right)}+b-1}{(\varepsilon-1)}=\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}$
(2)

###### Theorem 1

Let S be the screening plane of area 1 with invariant points [0,0] and [1,1]
where lies the screening curve’s continuous function $0<\rho(\phi)<1$. Then
there is a vertical function $f(a,b)$ which transects the screening curve at
the prevalence threshold, such that the square of the cotangent of the angle
$\beta$ formed between the line $y_{1}$ from the origin to the prevalence
threshold and the vertical axis equals the positive likelihood ratio (LR+).

###  5.1 Proof of Theorem 1

If we take the point [0,0], we can draw a line from the origin to the
intersection of the prevalence threshold with the screening curve. The
coordinates of this intersecting point are
[$\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}$,
$\sqrt{\frac{a}{1-b}}\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}$]. This
intersection allows us to determine the slope $m$ of the line that crosses
that point and the origin at [0,0] (Figure 5).

$m=\frac{\Delta y}{\Delta
x}=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}=\frac{\sqrt{\frac{a}{1-b}}\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}-0}{\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}-0}=\sqrt{\frac{a}{1-b}}$
(3)

Since by definition the point [0,0] falls on the line, the linear equation
from the origin to the prevalence threshold point is therefore simply:

$f(x)=\sqrt{\frac{a}{1-b}}x$ (4)

where $\frac{a}{1-b}$ is the positive likelihood ratio (LR+), defined as the
likelihood of a positive test result in patients $with$ the disease divided by
the likelihood of a positive test result in patients $without$ the disease. To
distinguish between two screening curves with identical $\varepsilon$ values,
we make use of the angle $\beta$ created by the line between the invariant
origin and the prevalence threshold $\phi_{e}$ to make a right-angle triangle
as follows:

Figure 5. Representation of the angle $\beta$ on the screening curve

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$$\phi$$\rho(\phi)$$\beta$$\phi_{e}$$\Delta
y=\sqrt{\frac{a}{1-b}}\frac{\sqrt{a\left(-b+1\right)}+b-1}{(\varepsilon-1)}$$\Delta
x=\frac{\sqrt{a\left(-b+1\right)}+b-1}{(\varepsilon-1)}$

We can determine the value of $\beta$ through the following trigonometric
identities:

$tan(\beta)=\frac{opp}{adj}=\frac{\Delta x}{\Delta
y}=\frac{1}{\sqrt{\frac{a}{1-b}}}=\sqrt{\frac{1-b}{a}}$ (5)

We can therefore isolate $\beta$ such that:

$\beta=arctan\left(\sqrt{\frac{1-b}{a}}\right)$ (6)

For simplicity’s sake we can define the expression $\sqrt{\frac{1-b}{a}}$ as
$\Psi$. From the above relationship we can infer the critical relationship
between a test’s parameters and the angle $\beta$:

$\lim_{\Psi\to 0}\beta=0$ (7)

We now have enough information to distinguish between the shapes of two
different screening curves which have the same $\varepsilon$. Notably, the
test whose angle $\beta$ is lower will take up a greater area in the screening
plane and therefore will offer a greater positive predictive value for a given
risk level. Otherwise stated:

$\beta_{2}<\beta_{1}\leftrightarrow\Psi_{2}<\Psi_{1}\rightarrow\rho_{2}>\rho_{1}$
(8)

The latter follows from the non-commutative properties of $\varepsilon$.

###  5.2 Using the angle $\beta$ to determine the LR+ of a screening curve

From the relationship above in (6), and knowing that the positive likelihood
ratio (LR+) [7] is defined as the ratio of the sensitivity over the compliment
of the specificity ($\frac{a}{1-b}$) we obtain:

$tan(\beta)=\frac{1}{\sqrt{\frac{a}{1-b}}}\Leftrightarrow\sqrt{\frac{a}{1-b}}=\frac{1}{tan(\beta)}=cot(\beta)$
(9)

where $cot(\beta)$ is the cotangent of the angle $\beta$. Thus, a new
geometric formulation for the positive likelihood ratio (LR+) [7] ensues, now
defined as:

$cot^{2}{(\beta)}=\frac{a}{1-b}$ (10)

##  6 Deriving the likelihood ratio LR+ by means of the prevalence threshold

###### Theorem 2

Let S be the screening plane of area 1 with invariant points [0,0] and [1,1]
where lies the screening curve’s continuous function $0<\rho(\phi)<1$. Then
there is a vertical function $f(a,b)$ which transects the screening curve at
the prevalence threshold, such that the ratio $\chi$ between the derivatives
$\frac{dy_{1}}{dx}$ and $\frac{dy_{2}}{dx}$ of the linear equations $y_{1}$,
$y_{2}$ which stem from the invariant points on the plane to the prevalence
threshold equals the positive likelihood ratio (LR+).

###  6.1 Proof of Theorem 2

While the angular definition makes intuitive sense, we can derive the positive
likelihood ratio (LR+) by using the prevalence threshold as a transecting
function that divides the screening curve into two halves. Notably, as stated
in previous work defining the prevalence threshold, the half of the screening
curve below the prevalence threshold represents the risk range where the
reliability of the test in question drops exponentially and the number of
false positive results increases most rapidly. This time, we will use the
second invariant point, namely [1,1], to define the linear equation from the
prevalence threshold [$\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}$,
$\sqrt{\frac{a}{1-b}}\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}$] to this point.
In so doing, we thus obtain:

$m=\frac{\Delta y}{\Delta
x}=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}=\frac{1-\sqrt{\frac{a}{1-b}}\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}}{1-\frac{\sqrt{1-b}}{\sqrt{a}+\sqrt{1-b}}}$
(11)

We can use the invariant point [1,1] to determine the y-intercept and thus
obtain the following final linear equation for this line:

$y=\frac{\left(1-\frac{\sqrt{1-b}}{\sqrt{1-b}+\sqrt{a}}\sqrt{\frac{a}{1-b}}\right)}{1-\frac{\sqrt{1-b}}{\sqrt{1-b}+\sqrt{a}}}x\
+\
\left[1-\frac{\left(1-\frac{\sqrt{1-b}}{\sqrt{1-b}+\sqrt{a}}\sqrt{\frac{a}{1-b}}\right)}{1-\frac{\sqrt{1-b}}{\sqrt{1-b}+\sqrt{a}}}\right]$
(12)

If we take the ratio of the derivatives $\chi$ of both equations in (4) and
(12) we obtain the following:

$\Rightarrow\chi=\frac{\frac{dy_{1}}{dx}}{\frac{dy_{2}}{dx}}=\frac{\sqrt{\frac{a}{1-b}}}{\frac{\left(1-\frac{\sqrt{1-b}}{\sqrt{1-b}+\sqrt{a}}\sqrt{\frac{a}{1-b}}\right)}{1-\frac{\sqrt{1-b}}{\sqrt{1-b}+\sqrt{a}}}}=\frac{a}{1-b}$
(13)

This is the equation for the positive likelihood ratio of a screening test
(LR+). It thus follows that we can re-define the prevalence threshold as the
single dividing point on the screening curve from which only two lines can de
drawn to the invariant points on the screening curve such that the ensuing
ratio of their derivative equals the positive likelihood ratio. Graphically,
we can depict the two linear functions in red and blue as follows:

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$$\phi$$\rho(\phi)$$\phi_{e}$$\Delta
y_{a}=\sqrt{\frac{a}{1-b}}\frac{\sqrt{a\left(-b+1\right)}+b-1}{(\varepsilon-1)}$$\Delta
x_{a}=\frac{\sqrt{a\left(-b+1\right)}+b-1}{(\varepsilon-1)}$$\Delta
y_{b}=1-\sqrt{\frac{a}{1-b}}\frac{\sqrt{a\left(-b+1\right)}+b-1}{(\varepsilon-1)}$$\Delta
x_{b}=1-\frac{\sqrt{a\left(-b+1\right)}+b-1}{(\varepsilon-1)}$

Figure 6. Prevalence threshold transects the screening curve

##  7 Generalized version of the theorem on the Geometric Definition of the
Positive Likelihood Ratio (LR+)

###### Theorem 3

Let S be the screening plane of area 1 with invariant points [0,0] and [1,1]
where lies the screening curve’s continuous function $0<\rho(\phi)<1$. Then
there is a vertical function $f(a,b)$ which transects the screening curve at
any given point, such that the ratio $\chi$ between the derivatives
$\frac{dy_{1}}{dx}$ and $\frac{dy_{2}}{dx}$ of the linear equations $y_{1}$,
$y_{2}$ which stem from the invariant points on the plane to that point on the
curve equals the positive likelihood ratio (LR+).

###  7.1 Proof of Theorem 3

While the use of the prevalence threshold as a transecting function that
divides the screening curve into two halves can yield the LR+, this point is
but a special case of a broader definition. Indeed, drawing a line from each
invariant point to any point on the curve yields linear equations whose ratio
of derivatives yield the LR+. This time, we will use the PPV equation to
obtain the coordinates of any point on the curve as
[$\phi,\frac{a\phi}{a\phi+\left(1-b\right)\left(1-\phi\right)}$]. Determining
the equation of the lines that stem from the invariant origin [0,0] to any
point on the curve we obtain:

$m_{1}=\frac{\Delta y}{\Delta
x}=\frac{\frac{a\phi}{a\phi+(1-b)(1-\phi)}-0}{\phi-0}=\frac{\frac{a\phi}{a\phi+(1-b)(1-\phi)}}{\phi}$
(14)

We can likewise use the invariant point [1,1] to determine the slope of the
second line:

$m_{2}=\frac{\Delta y}{\Delta
x}=\frac{1-\frac{a\phi}{a\phi+(1-b)(1-\phi)}}{1-\phi}$ (15)

If we take the ratio of the derivatives $\chi$ of both equations in (14) and
(15) we obtain the following:

$\Rightarrow\chi=\frac{\frac{dy_{1}}{dx}}{\frac{dy_{2}}{dx}}=\frac{\frac{\frac{a\phi}{a\phi+(1-b)(1-\phi)}}{\phi}}{\frac{1-\frac{a\phi}{a\phi+(1-b)(1-\phi)}}{1-\phi}}=\frac{a}{1-b}$
(16)

Once again, we retrieve the equation for the positive likelihood ratio of a
screening test (LR+). It thus follows that Theorem 3 generalizes the
geometrization of the LR+ from the prevalence threshold point, as in Theorem
2, to any point on the screening curve.

##  8 Discussion

By having a foundational understanding of the interpretation of sensitivity,
specificity, predictive values, and likelihood ratios, healthcare providers
can better understand outputs from current and new diagnostic assessments,
aiding in decision-making and ultimately improving healthcare for patients.
That said, it is important to understand the limitations of the LR. First, and
perhaps most obviously, the accuracy of a LR depends entirely upon the
relevance and quality of the studies that generated the numbers (sensitivity
and specificity) that inform that LR. Even when a LR is used in this fashion
there are definite limits to the accuracy that we can presume underlies the
number, for example the sensitivity and specificity evidence as originally
generated may be flawed and the pre-test probability judgment can vary widely
which mean that there are margins of error that should considered even under
ideal circumstances. In addition, LRs have never been validated for use in
series or in parallel. In other words there is no precedent to suggest that
LRs can be used one after the other (i.e. using one LR to generate a post-test
probability, and then using this as a pre-test probability for application of
a different LR) or simultaneously, to arrive at a more accurate probability or
diagnosis. It is important to keep these limitations in mind when using LRs
because in many ways it is quite counter-intuitive to imagine that only one
question at a time can be addressed when seeing a patient in the clinical
environment with all of its inherent complexity. Despite this seemingly narrow
use, LRs remain an invaluable and unique tool, as there is no other
established method for adjusting a probability of disease based on known
diagnostic test properties.

##  9 Conclusion

Using the concepts of the prevalence threshold and the invariant points on the
screening plane, the work herein presented provides a geometric definition of
the positive likelihood ratio (LR+) and describes a formal measure to compare
the performance of two screening tests whose $\varepsilon$ are equal. Indeed,
when faced with two screening tests whose sensitivity and specificity
parameters add to the same value, the angle $\beta$ and the ratio of
derivatives $\chi$ can help distinguish their performance throughout the
prevalence/risk spectrum.

## References

  * [1] Arjun K Manrai, Gaurav Bhatia, Judith Strymish, Isaac S Kohane, and Sachin H Jain.  Medicine’s uncomfortable relationship with math: calculating positive predictive value.  JAMA internal medicine, 174(6):991–993, 2014.
  * [2] Jacques Balayla.  Prevalence threshold ($\phi$ e) and the geometry of screening curves.  Plos one, 15(10):e0240215, 2020.
  * [3] George David Birkhoff and Oliver Dimon Kellogg.  Invariant points in function space.  Transactions of the American Mathematical Society, 23(1):96–115, 1922.
  * [4] Jacques Balayla.  Derivation of generalized equations for the predictive value of sequential screening tests.  arXiv preprint arXiv:2007.13046, 2020.
  * [5] Stephen R Hayden and Michael D Brown.  Likelihood ratio: a powerful tool for incorporating the results of a diagnostic test into clinical decisionmaking.  Annals of emergency medicine, 33(5):575–580, 1999.
  * [6] Daniel M Grove.  Positive association in a two-way contingency table: likelihood ratio tests.  Communications in Statistics-Theory and Methods, 13(8):931–945, 1984.
  * [7] Jonathan J Deeks and Douglas G Altman.  Diagnostic tests 4: likelihood ratios.  Bmj, 329(7458):168–169, 2004.


# Hitting times in the stochastic block model

Andrea Ottolini  Department of Mathematics, University of Washington, Seattle,
WA 98195, USA<EMAIL_ADDRESS>
###### Abstract.

Given a large connected graph $G=(V,E)$, and two vertices $w,\neq v$, let
$T_{w,v}$ be the first hitting time to $v$ starting from $w$ for the simple
random walk on $G$. We prove a general theorem that guarantees, under some
assumptions on $G$, to approximate $\mathbb{E}[T_{w,v}]$ up to $o(1)$ terms.
As a corollary, we derive explicit formulas for the stochastic block model
with two communities and connectivity parameters $p$ and $q$, and show that
the average hitting times, for fixed $v$ and as $w$ varies, concentrates
around four possible values. The proof is purely probabilistic and make use of
a coupling argument.

######  Mathematics Subject Classification:

60J10, 05C80, 60B20

##  1\. Introduction

###  1.1. The Erdős-Rényi case

Let $G$ be a simple connected graph, equipped with simple random walk. Given
two vertices $w\neq v$, let $T_{w,v}$ be the first time that simple random
walk, starting from $w$, hits $v$. Our goal is to understand
$\mathbb{E}[T_{w,v}]$, which we refer to as the average hitting time from $w$
to $v$. Our motivation comes from a recent joint work with Steinerberger [22],
where we show that if $G$ is sampled according to the Erdős-Rényi model with
parameters $n$ (large) and $p$ (fixed), then there is an almost exact formula:
with high probability, for every pair $w\neq v\in V$

$\mathbb{E}[T_{w,v}]=\frac{2|E|}{\deg v}-1+\frac{1}{p}1_{w\not\sim
v}+\mathcal{O}\left(\sqrt{\frac{\log^{3}n}{n}}\,\right).$ (1)

Here, $E$ denotes the number of edges, $\deg(v)$ the number of neighbors of
$v$, and $1_{w\not\sim v}$ the indicator that $w$ and $v$ are not adjacent.
The implicit constant in the error term depends on $p$, and deteriorates as
$p\rightarrow 0$. One way to interpret this result is that the hitting times
concentrates around two values, and such a concentration can be used to
recover the adjacency structure of the graphs.
Our main result, Theorem 1, allows to derive similar formulas in a variety of
situations. As a first example, we obtain the following corollary that extends
(1) to the case where $p\rightarrow 0$.

######  Corollary 1.

Let $G=(V,E)$ be an Erdős-Rényi random graph with parameters $n$ and $p=p_{n}$
where $\log^{5}n\cdot n^{-1}\cdot p^{-8}\rightarrow 0.$ Then, with high
probability, we have that for every pair $w\neq v$ the hitting time $T_{w,v}$
satisfies

$\mathbb{E}[T_{w,v}]=\frac{2|E|}{\deg v}-1+\frac{X+Y}{X}1_{w\not\sim v}+o(1)$
(2)

where, conditional on $\deg v$, the random variables $X$ and $Y$ are
independent and

$\displaystyle X\sim\emph{Bin}\left(\deg v(n-\deg v-1),p\right)\,\quad
Y\sim\emph{Bin}\left((n-\deg v-1)(n-\deg v-2),p\right).$

The restriction on $p$ is likely an artifex of the proof, though there is a
real obstacle at $p=n^{-1/2}$, which is the regime at which the diameter of a
typical graph changes from $2$ to $3$. In first approximation, we have

$\frac{X+Y}{X}\approx\frac{n}{\deg v}\approx\frac{1}{p}$

thus recovering the result in [22] when $p$ is fixed. In the regime of $p$
where Corollary 1, this is also a refinement of the results in [15, 16, 17].
In fact, they prove a law of large numbers and central limit theorem for
$\mathbb{E}[T_{w,v}]$ in the case where $w$ is distributed according to the
stationary distributed – confirming a prediction from the physics literature
[25]. Provided that $p$ decays according to (1), their result can be recovered
from the leading term in (2) using asymptotic of binomial coefficients.

###  1.2. Stochastic block model

In many situations, the Erdős-Rényi model is unrealistic as it assumes that
each pair of vertices interact with the same probability. A widely used
variation, the stochastic block model [1], takes into account for situations
where vertices can be partitioned into sets that we call communities. We write
$w\simeq v$ to denote that $w$ and $v$ are in the same community. While what
follows can be substantially generalized, we focus here on the case of two
communities of size $n$ each, with each pair of vertices in the same community
being connected with probability $p$, and each pair of vertices in different
communities being connected with probability $q$. We call the resulting
measure on graphs on $2n$ vertices $\mathcal{G}_{n,p,q}$. Notice that the case
$p=q$ corresponds to the Erdős-Rényi model with parameters $2n$ and $p$. An
instance of $\mathbb{E}[T_{w,v}]$ for $G\sim G_{1000,0.8,0.2}$, for fixed $v$
and $w$ that ranges on $w\neq v$, is given in Figure 1.2.

Figure 1. Average hitting times for an instance of the stochastic block model
from different starting points. They cluster around four values that are
predicted by our result (Theorem 2). The clusters reflect the adjacency and
community structure of the graph.

Recently, Löwe and Terveer [18] have shown a law of large numbers and a
central limit theorem for $\mathbb{E}[T_{w,v}]$, when $w$ is stationary
distributed. Their result is applicable in a wide regime – allowing for
multiple communities and $p,q$ that vary with $n$ – but fails to capture the
phenomenon in Figure (1.2). An explanation if instead given by a corollary of
our main Theorem 1.

######  Corollary 2.

Let $(V,E)=G\sim\mathcal{G}_{n,p,q}$ be a graph sampled according to the
stochastic block model with $0<p,q<1$ fixed. Then, with high probability, we
have that for every pair $w\neq v$ the hitting time $T_{w,v}$ satisfies

$\mathbb{E}[T_{w,v}]=\frac{2|E|}{\deg v}-1+\frac{2}{p+q}1_{w\not\sim
v}+\begin{cases}-\frac{(q-p)^{2}}{(p+q)^{2}}\quad&\mbox{if}~{}w\simeq v\\\
+\frac{p(q-p)^{2}}{q(p+q)^{2}}\quad&\mbox{if}~{}w\not\simeq
v\end{cases}\quad+\mathcal{O}_{p,q}\left(\sqrt{\frac{\log^{5}n}{n}}\,\right)$

While some of the logarthmic factors may be a byproduct of the proof, we
believe that the $\sqrt{n}$ behavior in the error term cannot be removed. One
could also allow to vary $p,q$ with $n$, along the lines of Corollary 1,
though we will not pursue this direction. The case of more communities can
also be handled using our main result. An illustration of the case with three
communities is given in (1.2).

Figure 2. The average hitting times to a given vertex $v$ for an instance of
the stochastic block model on three communities of a $1000$ individuals each.
The hitting times cluster around six values.

As discussed in [22], hitting times are closely related to other relevant
quantities for the graph $G$, including spectral data [8, 14], effective
resistances [11], and the uniform measure on the set of spanning tree[20].
There is also a neat connection with the problem of community detection, that
has attracted a lot of interest in the last two decades with a large body of
literature in mathematics, physics, biology, computer science, see [1, 2, 4,
3, 6, 9, 24] and references therein. Classical approaches require an
understanding of the spectrum of the adjacency matrix [24], or are based on
curvature methods [9]. Our Corollary 2 illustrate a simple way to perform
community detection in a stochastic block model by means of observing random
messages travelling among individuals.

##  2\. Main result

###  2.1. Set-up

We consider a connected weighted graph $G$ with vertex set $V$ and non-
negative edge weights $c_{w,w^{\prime}}$ for each pair $1\leq w,w^{\prime}\leq
n$. We assume that the vertex set $V$ can be partitioned into $m+1$ disjoint
parts

$\mathcal{V}=\\{\\{v\\}=V_{0},V_{1},\ldots,V_{m}\\},$

which we use to define a new weighted graph with vertex set $\mathcal{V}$.
Given the symmetric weights $c_{w,w^{\prime}}$ on the original graph, we
define for $1\leq i,j\leq m$

$C_{ij}:=\sum_{w\in V_{i},w^{\prime}\in V_{j}}c_{w,w^{\prime}}.$

This gives a weighted graph structure $\mathcal{G}$ on $\mathcal{V}$. We
define

$c_{w}:=\sum_{w^{\prime}\in V}c_{w,w^{\prime}},\quad C_{i}:=\sum_{0\leq j\leq
m}C_{i,j}=\sum_{w^{\prime}\in V_{i}}c_{w^{\prime}}$

for the total weights at each vertex. We then introduce the random walks
$X_{k}$ on $G$ and $Y_{k}$ on $\mathcal{G}$ with transition probabilities,
respectively,

$p_{w,w^{\prime}}:=\frac{c_{w,w^{\prime}}}{c_{w}},\quad
q_{i,j}:=\frac{C_{i,j}}{C_{i}}.$

In particular, the $q_{i,j}s$ are a convex combination of the
$p_{w,w^{\prime}}$ and

$\min_{w\in V_{i},w^{\prime}\in V_{j}}p_{w,w^{\prime}}\leq
q_{i,j}\leq\max_{w\in V_{i},w^{\prime}\in V_{j}}p_{w,w^{\prime}}$ (3)

We write $\mu(k,w)$ for the probability distribution of the random walk
$X_{k}$ after $k$ steps, starting from $w$. Similarly, we denote by $\nu(k,i)$
the probability distribution of the random walk $Y_{k}$ after $k$ steps,
starting from $V_{i}$. We will abuse notation and write $Y_{k}=i$ for
$Y_{k}=V_{i}$. Owing to the connectedness assumption, the stationary
distributions are unique and given by $\mu$ and $\nu$, where

$\mu_{w}:=\frac{c_{w}}{\sum_{w^{\prime}\in
V}c_{w^{\prime}}},\quad\nu_{i}:=\frac{C_{i}}{\sum_{0\leq j\leq m}C_{j}}$ (4)

We now define the hitting times

$T_{w,v}=\\{\min k\geq 0:X_{k}=v,X_{0}=w\\},\quad T^{\prime}_{i,0}=\\{\min
k\geq 0:Y_{k}=0,Y_{0}=i\\},$

Our goal is to show that we can approximate $T_{w,v}$ with $T_{i,0}$ whenever
$w\in V_{i}$. To do so, we will make the following assumption.

######  Assumption 1.

The graph $G$ satisfies the following bounds.

  1. (1)

There exists $\varepsilon\in[0,1)$ such that for all $0\leq i,j\leq m$ and all
$w\in V_{i}$,

$\left|\sum_{w^{\prime}\in
V_{j}}p_{w,w^{\prime}}-q_{i,j}\right|\leq\varepsilon\min_{w^{\prime\prime}\in
V_{i}}\sum_{w^{\prime}\in V_{j}}p_{w^{\prime\prime},w^{\prime}}.$ (5)

  2. (2)

There exists $K_{1},K_{2}>0$ such that

$\max_{w^{\prime}\in V,0\leq j\leq
m}\left(\mathbb{E}[T_{w^{\prime},v}],\mathbb{E}[T^{\prime}_{j,0}]\right)\leq
K_{1}|V|,\quad\max_{w^{\prime}\sim v}p_{w,v}\leq\frac{K_{2}}{|V|}$ (6)

  3. (3)

If $d_{\emph{TV}}$ denote the total variation distance between two probability
measures, then we have for some $\lambda\in[0,1)$

$\max_{w\in V}d_{\emph{TV}}(\mu(1,w),\mu)\leq\lambda.$ (7)

In many situations, that include the stochastic block model
$\mathcal{G}_{n,p,q}$ with general parameters $0<p,q<1$ fixed, we can choose
$\mathcal{V}$ to be small, the parameters in the assumptions are easy to
estimate, and to do so does not require any knowledge about spectral data.
Some generic conditions are shown in Lemma (1). In fact, one can also allow
$p$ and/or $q$, to vary with $n$, as we show in the proof of Corollary (1). We
now proceed with a brief discussion of the meaning of the parameters.
The first assumption allows to conclude that

$(1-\varepsilon)\mathbb{P}(X_{k}\in
V_{j}|X_{k-1}=w)\leq\mathbb{P}(Y_{k}=j|Y_{k-1}=i)$ (8)

for all $i,j\in\\{0,\ldots,m\\}$ and $w\in V_{i}$. In particular, if we define
$\Gamma$ via

$\Gamma:V\rightarrow\\{0,1\ldots,m\\},\qquad\Gamma(w)=i\quad\Leftrightarrow\quad
w\in V_{i},$

we deduce that we can couple $\Gamma(X_{k})$ and $Y_{k}$ so that if
$\Gamma(X_{k-1})=Y_{k-1}$, then they will remain equal with probability at
least $1-\varepsilon$.
The second assumption is an a priori bound on the hitting of vertex $v$ and on
the chance of hitting $v$ from its neighbor. Notice that if $K_{1}$ and
$K_{2}$ are of the same order, it implies that in first approximation the
average hitting times have the same size, regardless of the starting position.
This is the case for the stochastic block model with arbitrary number of
communities, as long as the connectivity parameters are bounded away from
zero.
The third assumption is a mixing condition, that guarantees that $X_{k}$ can
be coupled with a stationary walker with probability at least $\lambda$ at
each step. It is referred to as a Dobrushin-type of condition in the
statistical physics community [23]. It is also closely related to the optimal
transport-based notion of curvature for the Markov chain $X_{k}$ known as
Ollivier-Ricci curvature [21].

###  2.2. Main result

We are now ready to state our main result. In a nutshell, it shows that
$T_{w,v}$ and $T^{\prime}_{i,0}$ behave similarly up to an error term governed
by Assumption 1. The bound is explicit, and allows for neat formulas for
$T_{w,v}$ for large structured graphs.

######  Theorem 1.

Let $G$ be a connected weighted graph satisfying Assumption 1. Then, for all
$1\leq i\leq m$ and $w\in V_{i}$, we have

$\left|\mathbb{E}[T_{w,v}]-\mathbb{E}[T^{\prime}_{i,0}]\right|\leq\frac{16K_{1}K_{2}\varepsilon}{\log^{2}\lambda}\log^{2}\left(\varepsilon\cdot\frac{K_{2}}{|V|}\cdot(1-\sqrt{\lambda})\right)$

In fact, the result is stronger, as the proof provides a coupling between the
hitting times that is small in the $L^{1}$ sense, thus providing convergence
in distribution whenever the right side vanishes. In many applications,
$K_{1},K_{2}$ and $\lambda$ are positive constants, while
$\varepsilon\rightarrow 0$ sufficiently fast. In such cases, the expectations
of $T_{w,v}$ and $T^{\prime}_{i,0}$ coincide up to $o(1)$ factors. The latter
is typically much easier to estimate, as we will see in the proofs of
Corollaries 1 and 2.

##  3\. Main ingredients

###  3.1. A useful lemma

In order to apply Theorem (1) in concrete settings, we need good and practical
bounds for $\lambda$ and $K_{1},K_{2}$ given by Assumption (1). The following
lemma will suffice for our purposes. Versions of them are known in the
literature, but we report them with proofs for the sake of completeness and to
tailor them with an eye to our applications.

######  Lemma 1.

Consider a connected graph $G$ on $n$ vertices satisfying Assumption (1).
Assume that there exists $0\leq\delta<1$ and $0<D<1$ such that

$(1-\delta)D\leq\frac{\deg(w)}{n}\leq(1+\delta)D,\quad\frac{(1+\delta)^{2}}{(1-\delta)}D\leq
1.$

for all $w\in V$, and that for $w\neq v$ we can bound for some $\alpha>0$

$\frac{|w^{\prime}:w^{\prime}\sim w,w\sim v|}{\deg w}\geq\alpha.$

Then, we have the bounds

$K_{1}\leq\frac{2D}{\alpha}(1+\delta),\quad
K_{2}\leq\frac{1}{D(1-\delta)},\quad\lambda\leq 1-D+o(\delta).$

###### Proof.

The statement regarding $K_{2}$ follows at once from the assumption on the
degree. As for the bound on the hitting time, start from any $w^{\prime}\in
V$. We have by assumption that there is a likelihood of at least $\alpha$ of
reaching a neighbor of $v$ in one step, and a chance of at least
$D^{-1}(1+\delta)^{-1}$ of hitting $v$ at the next step. In other words,

$\mathbb{P}(T_{w^{\prime},v}>2)\leq 1-\frac{\alpha}{D(1-\delta)}$

Using the Markov property, this gives

$\mathbb{P}(T_{w^{\prime},v}>2k)\leq\left(1-\frac{\alpha}{nD(1+\delta)}\right)^{k}$

and thus summing over $k$

$\mathbb{E}[T_{w^{\prime},v}]\leq 2\frac{nD(1+\delta)}{\alpha}.$

as desired. Following the remark in (3), the same bounds hold for the graph
$\mathcal{G}$ with the same quantities $D$, $\delta$ and $\alpha$.
We move now to the bound on $\lambda$. Given the bounds on the degree, we can
estimate

$(1-\delta)Dn^{2}\leq\sum_{w}\deg(w)\leq(1+\delta)Dn^{2}$

and thus we deduce that the stationary distribution $\mu$ satisfy

$\frac{1}{n}\frac{1-\delta}{1+\delta}\leq\mu_{w}\leq\frac{1+\delta}{1-\delta}\frac{1}{n}.$

for all $w$. Given any other vertex $w^{\prime}\sim w$, we have

$\mu_{w^{\prime}}\leq\frac{1+\delta}{1-\delta}\frac{1}{n}\leq\frac{D(1+\delta)^{2}}{1-\delta}\frac{1}{\deg
w}\leq\mu_{w^{\prime}}(1,w)$

In particular, this implies that $\mu\leq\mu(1,w)$ for all $w^{\prime}\sim w$.
Therefore, by definition of total variation distance

$\displaystyle\lambda$
$\displaystyle=d_{\emph{TV}}(\mu,\mu(1,w^{\prime}))=\sum_{w\not\sim
w^{\prime}}\mu_{w}\leq(n-\deg(w^{\prime}))\max_{w}\mu_{w}$ $\displaystyle\leq
n\left(1-D(1-\delta)\right)\frac{1}{n}\frac{1+\delta}{1-\delta}=1-D+o(\delta).$

∎

###  3.2. Relationship between the stationary distributions

We now show a connection between the stationary distributions $\mu$ and $\nu$
for $X_{k}$ and $Y_{k}$, introduced in (4). In what follows, we recall that
$\Gamma$ denotes the map sending $w\in V_{i}$ to $i$. In most cases, the
transition rates of $\Gamma(X_{k})$ depend on the specific location $X_{k}$ we
are at, though our Assumption 1 suggests that the dependence is mild. For
stationary starting configurations we can say even more.

######  Lemma 2.

Let $X_{0}\sim\mu$ and $Y_{0}\sim\nu$. Then, the pair
$(\Gamma(X_{k}),\Gamma(X_{k+1}))$ is equal in distribution to
$(Y_{k},Y_{k+1})$ for all $k$. Moreover,

$\max_{i}d_{\emph{TV}}(\nu(1,i),\nu)\leq\max_{w}d_{\emph{TV}}(\mu(1,w),\mu)$

###### Proof.

Since both chains are stationary, it suffices to show the statement for $k=0$.
In this case, we notice that for every $i$ we have

$\mathbb{P}(\Gamma(X_{0})=i)=\sum_{w\in V_{i}}\mu_{w}=\sum_{w\in
V_{i}}\frac{c_{w}}{\sum_{w^{\prime}\in
V}c_{w^{\prime}}}=\frac{C_{i}}{\sum_{0\leq j\leq
m}C_{j}}=\nu_{i}=\mathbb{P}(Y_{0}=i)$

To check the distribution of pairs are the same, it suffices to show that the
transition probabilities coincide, i.e., we need to show

$\mathbb{P}(\Gamma(X_{k+1})=j|\Gamma(X_{k})=i)=q_{i,j}.$

This is just an easy computation.

$P(\Gamma(X_{k+1})=j|\Gamma(X_{k})=i)=\sum_{w\in V_{i},w^{\prime}\in
V_{j}}\frac{c_{w,w^{\prime}}}{c_{w}}\frac{c_{w}}{\sum_{a\in
V_{i}}c_{a}}=\frac{C_{i,j}}{C_{i}}=q_{i,j}.$

It remains to prove the total variation bound. Fix $1\leq i\leq m$ and
consider $\tilde{X}_{0}$ that is distributed according to the measure
$\tilde{\mu}$

$\tilde{\mu}(w)=\frac{\mu_{w}1_{w\in V_{i}}}{\mu(V_{i})},$

i.e. Our previous computation shows that the pair
$(\Gamma(X_{0}),\Gamma(X_{1}))$ has the same law of $(Y_{0},Y_{1})$, where
$Y_{0}=i$. Therefore, we have

$d_{\emph{TV}}(\nu(1,i),\nu)\leq d_{\emph{TV}}(\tilde{\mu},\mu)\leq\max_{w\in
V}d_{\emph{TV}}(\mu(1,w),\mu)$

where we used the convexity of total variation distance in the last
inequality. ∎

The lemma does not extend to triples, in the following sense: if we condition
on $X_{0}=i$ and $X_{1}=j$, the distribution of $X_{2}$ is typically not
identical to that of $Y_{2}$ conditioned on $Y_{0}=i$ and $Y_{1}=j$.

###  3.3. Construction of the coupling

Start with $X_{0}=w\in V_{i}$ and $Y_{0}=i$, so that in particular
$\Gamma(X_{0})=Y_{0}$. Heuristically, we want to construct a coupling such
that $\Gamma(X_{k})$ and $Y_{k}$ agree for as long as possible. In case things
go wrong, we want to re-couple them as quick as possible, and we will do so by
guaranteeing that both the chains reach their stationary states as fast as
they can.

Let $w=X_{0},X_{1},\ldots$ be a realization of the Markov chain $X_{k}$. To
describe the coupling, we introduce the independent random variables

$\tau_{d}\sim\text{Geo}(\varepsilon),\quad\tau_{c},\tau^{\prime}_{c}\sim\text{Geo}(1-\lambda).$

First we notice that by definition of $\lambda$ and the coupling
interpretation of total variation distance (see, e.g., Theorem $5.2$ in [13]),
we can construct a stationary walker $\tilde{X}_{k}$ so that

$X_{k}=\tilde{X}_{k},\quad k\geq\tau_{c}.$

On the other hand, owing to (8) we can guarantee that

$Y_{k}=\Gamma(X_{k}),\quad k<\tau_{d}$

By means of Lemma 2, if $\tau_{c}<\tau_{d}$ we can then set
$Y_{k}=\Gamma(X_{k})$ for all $k$. If, instead, $\tau_{d}\leq\tau_{c}$, we
define $Y_{k}$ for $k>\tau_{d}$ as follows.

  1. (1)

For $\tau_{d}<k\leq\tau_{c}$, move the two chains independently. If only one
of the events $\\{T=k\\}$ or $\\{T^{\prime}=k\\}$ occurs in this range, then
move the two chains independently after that.

  2. (2)

For $\tau_{c}<k\leq\tau_{c}+\tau^{\prime}_{c}$, use Lemma 2 to couple $Y_{k}$
with $X_{k}=\tilde{X}_{k}$ so that
$\Gamma(X_{\tau_{c}+\tau^{\prime}_{c}})=Y_{\tau_{c}+\tau^{\prime}_{c}}$. If
only one of the events $\\{T=k\\}$ or $\\{T^{\prime}=k\\}$ occurs in this
range, then move the two chains independently after that.

  3. (3)

If $k>\tau_{c}+\tau_{c}^{\prime}$ and neither $T$ nor $T^{\prime}$ occurred by
time $k$, set $Y_{k}=\Gamma(X_{k})=\Gamma(\tilde{X}_{k})$, which is possible
owing to Lemma 2.

In particular, our coupling guarantees that the inclusion of events

$\\{T\neq T^{\prime}\\}\subset\\{T\neq
T^{\prime},\tau_{d}\leq\min(T,T^{\prime})<\tau_{c}+\tau^{\prime}_{c}\\}.$ (9)

Moreover, if we write

$T-T^{\prime}=\left(\max(T,T^{\prime})-\min(T,T^{\prime})\right)1_{T\neq
T^{\prime}},$ (10)

we see that, because of the construction of the coupling and the Markov
property, $\max(T,T^{\prime})-\min(T,T^{\prime})$ depends on
$\min(T,T^{\prime})$ only through
$X_{\min(T,T^{\prime})},Y_{\min(T,T^{\prime})}$.

##  4\. Proofs

###  4.1. Proof of Theorem 1

###### Proof.

We start by estimating $\mathbb{P}(T\neq T^{\prime})$. Using the inclusion of
events in (9), we can write

$\mathbb{P}(T\neq T^{\prime})\leq\sum_{k=1}^{\infty}\mathbb{P}(T\neq
T^{\prime},\tau_{d}\leq k<\tau_{c}+\tau^{\prime}_{c},\min(T,T^{\prime})=k)$

For $k$ small (to be decided), we will estimate using a union bound

$\mathbb{P}(\min(T,T^{\prime})=k,T\neq T^{\prime},\tau_{d}\leq k)\leq
k\varepsilon\max_{1\leq s\leq k}\mathbb{P}(\min(T,T^{\prime})=k,T\neq
T^{\prime}|\tau_{d}=s)$

For each $1\leq s\leq k-1$, we can further condition on $X_{k-1}$ and
$Y_{k-1}$ and use a union bound to deduce

$\mathbb{P}(\min(T,T^{\prime})=k|\tau_{d}=s)\leq\max_{w^{\prime}\sim
v}p_{w^{\prime},v}+\max_{j\sim 0}q_{j,0}\leq 2\frac{K_{2}}{|V|}$

where the last inequality follows from (3) and the definition (6) of $K_{2}$.
If, instead, $\tau_{d}=k$, we can write

$\displaystyle\mathbb{P}(\min(T,T^{\prime})=k,T\neq T^{\prime}|\tau_{d}=k)$
$\displaystyle\leq\mathbb{P}(\Gamma(X_{k})=0|\tau_{d}=k,\Gamma(X_{k-1})\neq
0)$ $\displaystyle+\mathbb{P}(Y_{k}=0|\tau_{d}=k,Y_{k-1}\neq 0)$

The first term can be handled using the fact that $\tau_{d}$ is independent of
$X_{k}$, and thus

$\mathbb{P}(\Gamma(X_{k})=0|\tau_{d}=k,\Gamma(X_{k-1})\neq
0)\leq\max_{w^{\prime}\sim v}p_{w^{\prime},w}\leq\frac{K_{2}}{|V|}$

As for the second term, we can use (5) and (8) to write

$\mathbb{P}(Y_{k}=0|\tau_{d}=k,Y_{k-1}\neq
0)\leq\mathbb{P}(\Gamma(X_{k})=0|\Gamma(X_{k-1})\neq
0)\leq\max_{w^{\prime}\sim v}p_{w^{\prime},w}\leq\frac{K_{2}}{|V|}.$

Overall, we have deduced the bound

$\mathbb{P}(\min(T,T^{\prime})=k,T\neq T^{\prime},\tau_{d}\leq k)\leq
2k\varepsilon\frac{K_{2}}{|V|}.$

that will be useful for small $k$. As for large $k$, we use the bound

$\displaystyle\mathbb{P}(\min(T,T^{\prime})=k,T\neq
T^{\prime},k<\tau_{c}+\tau_{c}^{\prime})\leq\mathbb{P}(k<\tau_{c}+\tau_{c}^{\prime})\leq
2\mathbb{P}(\tau_{c}>\frac{k}{2})\leq 2(\sqrt{\lambda})^{k}$

Collecting all bounds, we obtain that for every positive integer $z$ we can
bound

$\displaystyle\mathbb{P}(T\neq T^{\prime})$
$\displaystyle\leq\sum_{k=1}^{\infty}\mathbb{P}(\min(T,T^{\prime})=k,T\neq
T^{\prime},\tau_{d}\leq k<\tau_{c}+\tau_{c}^{\prime})$
$\displaystyle\leq\sum_{k=1}^{z-1}\mathbb{P}(\min(T,T^{\prime})=k,T\neq
T^{\prime},\tau_{d}\leq
k)+\sum_{k=z}^{\infty}\mathbb{P}(\tau_{c}+\tau^{\prime}_{c}>k)$
$\displaystyle\leq
2z^{2}\varepsilon\frac{K_{2}}{|V|}+2\frac{(\sqrt{\lambda})^{z}}{1-\sqrt{\lambda}}$

The choice of

$z=\frac{2}{\log\lambda}\cdot\log\left(\varepsilon\frac{K_{2}}{|V|}(1-\sqrt{\lambda})\right)$

gives

$\mathbb{P}(T\neq
T^{\prime})\leq\frac{16\varepsilon}{\log^{2}\lambda}\cdot\frac{K_{2}}{|V|}\cdot\log^{2}\left(\varepsilon\frac{K_{2}}{|V|}(1-\sqrt{\lambda})\right)$

Using the identity in (10) and the definition of $K_{1}$ from (6), we conclude

$\displaystyle|\mathbb{E}[T]-\mathbb{E}[T^{\prime}]|$
$\displaystyle\leq\mathbb{E}|T-T^{\prime}|\leq\max_{w^{\prime}\in V,0\leq
j\leq
m}\left(\mathbb{E}[T_{w^{\prime},v}],\mathbb{E}[\tilde{T}_{j,0}]\right)\mathbb{P}(T\neq
T^{\prime})$ $\displaystyle\leq K_{1}|V|\mathbb{P}(T\neq
T^{\prime})\leq\frac{16K_{1}K_{2}\varepsilon}{\log^{2}\lambda}\log^{2}\left(\varepsilon\cdot\frac{K_{2}}{|V|}\cdot(1-\sqrt{\lambda})\right).$

∎

###  4.2. Proofs of Corollaries 2 and 1

In the proofs of both Corollaries, we will make heavy use of the classical
Chernoff bound for binomial random variables. We have that for any $N$ and
$0<r<1$ (possibly depending on $N$) a random variable $X\sim\text{Bin}(N,r)$
satisfies

$\mathbb{P}\left(|X-Nr|\geq\sqrt{3cNr\log N}\right)\leq\frac{1}{N^{c}}.$

for every $c$ (while this is not optimal for $r$ close to $1$, it will suffice
for our purposes). In particular, if we have a family of random variables of
size at most polynomially in $N$, by taking $c$ sufficiently large we can
ensure that, with high probability, they all lie in a neighbor of $Nr$ of size
at most $\mathcal{O}\left(\sqrt{Nr\log N}\right)$, uniformly in $r$.

###### Proof of Corollary 2.

Given $G\sim G_{n,p,q}$ and a vertex $v$, let $A$ denote the set of vertices
distinct from $v$ in the same community of $v$, and let $B$ denote the set of
vertices that are not in the same community of $v$ (thus $|A|=n-1$, $|B|=n$).
Notice that, for parameters $p,q$ that are bounded away from zero, we are
guaranteed that the graph have diameter $2$ with high probability [5]. Now,
define $\mathcal{V}=\\{V_{0},V_{1},V_{2},V_{3},V_{4}\\}$ where

$\displaystyle V_{0}=\\{v\\},$ $\displaystyle V_{1}=\\{w\in A:w\sim v\\},$
$\displaystyle V_{2}=\\{w\in B:w\sim v\\}$ $\displaystyle V_{1}=\\{w\in
A:w\not\sim v\\},$ $\displaystyle V_{2}=\\{w\in B:w\not\sim v\\}$

In particular, this gives

$|V_{1}|=\text{Bin}(n-1,p),\quad|V_{2}|=\text{Bin}(n,q),\quad|V_{3}|=n-1-|V_{1}|,\quad|V_{4}|=n-|V_{2}|.$

and obviously $|V_{0}|=1$. We now proceed to show that Theorem 1 is in force
with $\lambda,K_{1},K_{2}$ that are independent of $n$, and
$\varepsilon\rightarrow 0$. In what follows, the implicit constant in
$\mathcal{O}$ may depend on $p$ and $q$. First, notice that for every vertex
$w$

$\deg(w)=\text{Bin}(n-1,p)+\text{Bin}(n,q),$

and thus a Chernoff bound gives with high probability

$\frac{\deg(w)}{2n}=\frac{p+q}{2}\left(1+\mathcal{O}\left(\sqrt{\frac{\log
n}{n}}\,\right)\right)$ (11)

for all $w\in V$. A similar argument implies that with high probability $w\in
V_{1}$ the fraction of edges leading to $V_{2}$, whose size is

$|V_{2}|=nq\left(1+\mathcal{O}\left(\sqrt{\frac{\log n}{n}}\,\right)\right)$

satisfies the uniform bound

$\frac{|w^{\prime}:w^{\prime}\in V_{2},w^{\prime}\sim w|}{\deg
w}=\frac{\text{Bin}(|V_{2}|,q)}{\text{Bin}(n-1,p)+\text{Bin}(n,q)}=\frac{q^{2}}{p+q}\left(1+\mathcal{O}\left(\sqrt{\frac{\log
n}{n}}\right)\right),$

which is independent of $w\in V_{1}$. A similar argument for each pair $0\leq
i,j\leq 4$ shows that Assumption 1 holds with

$\varepsilon=\mathcal{O}\left(\sqrt{\frac{\log n}{n}}\right).$

We now proceed to bound $\lambda,K_{1},K_{2}$, and we do so by applying Lemma
1. In fact, we have from (11) that

$D=\frac{p+q}{2},\quad\delta=\mathcal{O}\left(\sqrt{\frac{\log n}{n}}\right).$

Moreover, we also have

$\alpha=\frac{|w^{\prime}:w^{\prime}\sim v,w\sim w|}{\deg
w}\geq\min(p,q)\left(1+\mathcal{O}\left(\sqrt{\frac{\log n}{n}}\right)\right)$

Applying Lemma (1), we deduce the bounds

$\quad K_{1}\leq\frac{p+q}{pq}+o(1),\quad
K_{2}\leq\frac{2}{p+q}+o(1),\quad\lambda\leq 1-\frac{p+q}{2}+o(1).$

Using Theorem 1, we conclude

$\mathbb{E}[T_{w,v}]-\mathbb{E}[T^{\prime}_{i,0}]=\mathcal{O}\left(\varepsilon\left(\log\left(\frac{\varepsilon}{n}\right)\right)^{2}\right)=\mathcal{O}\left(\sqrt{\frac{\log^{5}n}{n}}\right)$

It remains to compute $T^{\prime}_{i,0}$ for $1\leq i\leq 4$. These are just
the hitting times for a weighted graph with explicit transition probabilities.

$Q=\begin{pmatrix}0&\frac{p}{(p+q)}&\frac{q}{(p+q)}&0&0&\\\
\frac{1}{(p+q)n}&\frac{p^{2}}{p+q}&\frac{q^{2}}{p+q}&\frac{p(1-p)}{p+q}&\frac{q(1-q)}{p+q}\\\
\frac{1}{(p+q)n}&\frac{pq}{p+q}&\frac{pq}{p+q}&\frac{q(1-p)}{p+q}&\frac{p(1-q)}{p+q}\\\
0&\frac{p^{2}}{p+q}&\frac{q^{2}}{p+q}&\frac{p(1-p)}{p+q}&\frac{q(1-q)}{p+q}\\\
0&\frac{pq}{p+q}&\frac{pq}{p+q}&\frac{q(1-p)}{p+q}&\frac{p(1-q)}{p+q}\\\
\end{pmatrix}+\mathcal{O}\left(\sqrt{\frac{\log n}{n}}\right)$

where the error term is uniform over all entries. In addition to that, we
notice that the return time is exactly the inverse of the stationary
distribution at $v$. Therefore, we have

$\frac{2|E|}{\deg v}=1+q_{01}T^{\prime}_{1,0}+q_{02}T^{\prime}_{2,0}.$

This suggests writing $T_{i,0}^{\prime}=\frac{2|E|}{\deg v}-1+\tilde{T}_{i}$
and, using the bound

$\left(\frac{2|E|}{\deg
v}-1\right)\frac{1}{(p+q)n}=\frac{2}{p+q}+\mathcal{O}\left(\sqrt{\frac{\log
n}{n}}\right)$

we deduce

$\begin{pmatrix}\tilde{T}_{1}\\\ \tilde{T}_{2}\\\ \tilde{T}_{3}\\\
\tilde{T}_{4}\end{pmatrix}=\begin{pmatrix}1-\frac{2}{p+q}\\\
1-\frac{2}{p+q}\\\ 1\\\ 1\end{pmatrix}+B_{p,q}\begin{pmatrix}\tilde{T}_{1}\\\
\tilde{T}_{2}\\\ \tilde{T}_{3}\\\
\tilde{T}_{4}\end{pmatrix}+\mathcal{O}\left(\sqrt{\frac{\log n}{n}}\right)$

where the matrix $B_{p,q}$ is given by

$B_{p,q}:=\begin{pmatrix}\frac{p^{2}}{p+q}&\frac{q^{2}}{p+q}&\frac{p(1-p)}{p+q}&\frac{q(1-q)}{p+q}\\\
\frac{pq}{p+q}&\frac{pq}{p+q}&\frac{q(1-p)}{p+q}&\frac{p(1-q)}{p+q}\\\
\frac{p^{2}}{p+q}&\frac{q^{2}}{p+q}&\frac{p(1-p)}{p+q}&\frac{q(1-q)}{p+q}\\\
\frac{pq}{p+q}&\frac{pq}{p+q}&\frac{q(1-p)}{p+q}&\frac{p(1-q)}{p+q}\\\
\end{pmatrix}$

The linear system can be solved explicitly, leading to

$\begin{pmatrix}\tilde{T}_{1}\\\ \tilde{T}_{2}\\\ \tilde{T}_{3}\\\
\tilde{T}_{4}\end{pmatrix}=\begin{pmatrix}-\frac{(p-q)^{2}}{(p+q)^{2}}\\\
\frac{p(p-q)^{2}}{q(p+q)^{2}}\\\ -\frac{(p-q)^{2}}{(p+q)^{2}}+\frac{2}{p+q}\\\
\frac{q(p-q)^{2}}{p(p+q)^{2}}+\frac{2}{p+q}\end{pmatrix}+\mathcal{O}\left(\sqrt{\frac{\log
n}{n}}\right)$

∎

###### Proof of Corollary 1.

First, we observe that in this regime for $n$ and $p$ the graph has diameter
$2$ with high probability [5]. The proof now is similar to that of Theorem 2,
but we need to be more careful in keeping track of the various parameters. We
have

$V_{0}=\\{v\\},\quad V_{1}=\\{w:w\sim v\\}\quad V_{2}=V\setminus(V_{1}\cup
V_{0}).$

In the following, all statement follows from a Chernoff bound, and thus holds
with high probability. For all vertices $w$, including $v$, we have

$\deg(w)=pn\left(1+\mathcal{O}\left(\sqrt{\frac{\log n}{np}}\right)\right).$

In particular,

$|V_{1}|=\deg(v)=pn\left(1+\mathcal{O}\left(\sqrt{\frac{\log
n}{np}}\right)\right).$

The same argument shows that for every $w\neq v$ we have

$\displaystyle\sum_{w^{\prime}\in
V_{1}}p_{w,w^{\prime}}=\frac{\text{Bin}(|V_{1}|-1_{w\in
V_{1}},p)}{\deg(w)}=p\left(1+\mathcal{O}\left(\sqrt{\frac{\log
n}{np^{2}}}\right)\right)$ $\displaystyle\sum_{w^{\prime}\in
V_{2}}p_{w,w^{\prime}}=\frac{\text{Bin}(|V_{2}|-1_{w\in
V_{2}},p)}{\deg(w)}=(1-p)\left(1+\mathcal{O}\left(\sqrt{\frac{\log
n}{np}}\right)\right)$

and for $w\in V_{1}$

$p_{w,v}=\frac{1}{\deg
w}=\frac{1}{np}\left(1+\mathcal{O}\left(\sqrt{\frac{\log
n}{np}}\right)\right)$

In particular, we obtain that Assumption 5 holds with

$\varepsilon=\mathcal{O}\left(\sqrt{\frac{\log n}{np^{2}}}\right)$

Similarly, we can apply Lemma 1 with

$D=p,\quad\alpha=p,\quad\delta=\mathcal{O}\left(\sqrt{\frac{\log
n}{np}}\right),$

Our assumption on $p$ guarantees that $\delta=o(p)$ and thus we deduce

$K_{1}\leq 2+o(1),\quad K_{2}\leq\frac{1+o(1)}{p},\quad\lambda=1-p+o(p)$

and thus

$K_{1}K_{2}\varepsilon=\mathcal{O}\left(\sqrt{\frac{\log n}{np^{4}}}\right)$

On the other hand, we also have

$\frac{\log(\varepsilon\frac{K_{2}}{|V|}(1-\sqrt{\lambda}))}{\log\lambda}=\mathcal{O}\left(\frac{\log
n}{p}\right)$

Combining all the ingredients, Theorem (1) is in force and gives a bound

$\mathbb{E}[T_{w,v}]-\mathbb{E}[T^{\prime}_{i,0}]=\mathcal{O}\left(\sqrt{\frac{\log
n}{np^{4}}}\frac{(\log n)^{2}}{p^{2}}\right)=\mathcal{O}\left(\sqrt{\frac{\log
n^{5}}{np^{8}}}\right)$

that goes to zero by our assumption. It remains to compute the hitting times
for $T_{1,0}$ and $T_{2,0}$. From the return time to $0$, we can deduce

$\frac{2|E|}{\deg(v)}=1+T_{1,0},$

while from

$T_{2,0}=1+q_{2,1}T_{1,0}+(1-q_{2,1})T_{2,0}$

we obtain that the difference of the hitting times is

$T_{2,0}-T_{1,0}=\frac{1}{q_{2,1}}.$

It remains to compute $q_{2,1}$. If we let $X$ denote the number of edges
between $V_{1}$ and $V_{2}$, and by $Y$ denote the number of edges between
$V_{2}$ and itself, we obtain $q_{2,1}=\frac{X}{X+Y}$. By the very definition
of the model, $X$ and $Y$ are independent and

$\displaystyle X\sim\text{Bin}\left(\deg v(n-\deg v-1),p\right)\,\quad
Y\sim\text{Bin}\left((n-\deg v-1)(n-\deg v-2),p\right).$

∎

## Acknowledgments

We warmly thank Stefan Steinerberger for many useful discussions. We were also
supported by an AMS-Simons travel grant.

## References

  * [1] E. Abbe. Community detection and stochastic block models: recent developments. Journal of Machine Learning Research 18.177 (2018): 1-86.
  * [2] C. T. Bergstrom, M. Rosvall. Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. USA 105, 1118–1123 (2008).
  * [3] S. S. Bhowmick, B. S. Seah. Clustering and summarizing protein-protein interaction networks: A survey. IEEE Trans. Knowl. Data Eng. 28, 638–658 (2015).
  * [4] S. Chatterjee, K. Rohe, B. Yu, Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Statist. 39(4): 1878-1915 (2011).
  * [5] F. Chung, L. Linyuan, The diameter of sparse random graphs. Advances in Applied Mathematics 26.4 (2001): 257-279.
  * [6] A. Clauset, M. E. Newman, C. Moore. Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004).
  * [7] A. Desolneux, L. Moisan, and J. Morel. From gestalt theory to image analysis: a probabilistic approach. Vol. 34. Springer Science & Business Media, 2007.
  * [8] P. Diaconis, L. Miclo. On quantitative convergence to quasi-stationarity. Annales de la Faculte des sciences de Toulouse: Mathematiques. Vol. 24. No. 4. 2015.
  * [9] J. Gao, CC. YY. Lin, F. Luo, CC. Ni, Community Detection on Networks with Ricci Flow, Sci Rep 9, 9984 (2019)
  * [10] A. Helali and M. Löwe, Hitting times, commute times, and cover times for random walks on random hypergraphs. Statist. Probab. Lett. 154 (2019), 108535, 6 pp.
  * [11] G. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 72 (1847), 497–508
  * [12] V. Klee and D. Larman, Diameters of random graphs, Canadian Journal of Mathematics 33.3 (1981): 618-640.
  * [13] D. Levin, Y. Peres. Markov chains and mixing times. Vol. 107. American Mathematical Soc., 2017.
  * [14] L. Lovász, Random walks on graphs: a survey. (English summary) Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), 353–397, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996.
  * [15] M. Löwe and F. Torres, On hitting times for a simple random walk on dense Erdős-Rényi random graphs. Statistics & Probability Letters 89 (2014), p. 81–88.
  * [16] M. Löwe and S. Terveer, A Central Limit Theorem for the average target hitting time for a random walk on a random graph. arXiv preprint arXiv:2104.01053.
  * [17] M. Löwe and S. Terveer, A central limit theorem for the mean starting hitting time for a random walk on a random graph. Journal of Theoretical Probability, 36(2), 779-810.
  * [18] M. Löwe and S. Terveer, Spectral properties of the strongly assortative stochastic block model and their application to hitting times of random walks, arXiv preprint arXiv:2104.01053
  * [19] U. von Luxburg, A. Radl and M. Hein, Hitting and commute times in large random neighborhood graphs. The Journal of Machine Learning Research, 15 (2014), 1751–1798.
  * [20] R. Lyons, Y. Peres, Probability on trees and networks. Cambridge University Press, 2017.
  * [21] Y. Ollivier, Ricci curvature of metric spaces.” Comptes Rendus Mathematique 345.11 (2007): 643-646.
  * [22] A. Ottolini, S. Steinerberger. Concentration of Hitting Times in Erdős-Rényi graphs, to appear on Journal of Graph Theory.
  * [23] D. Ruelle. Statistical mechanics: rigorous results. World Scientific, 1999.
  * [24] A. Saxena et al, A review of clustering techniques and developments, Neurocomputing 267 (2017): 664-681.
  * [25] V. Sood, S. Redner and D. ben-Avraham, First-passage properties of the Erdős-Renyi random graph. J. Phys. A 38 (2005), no. 1, 109–123.
  * [26] J. Sylvester, Random walk hitting times and effective resistance in sparsely connected Erdős-Rényi random graphs. J. Graph Theory 96 (2021), no. 1, 44–84.