2304.04289v2
Model: nemotron-free
# Concentration of Hitting Times in Erdős-Rényi graphs
**Authors**: Andrea Ottolini, Stefan Steinerberger
> Department of Mathematics, University of Washington, Seattle, WA 98195, USAottolini@uw.edusteinerb@uw.edu
Abstract.
We consider Erdős-Rényi graphs $G(n,p)$ for $0<p<1$ fixed and $n→∞$ and study the expected number of steps, $H_{wv}$ , that a random walk started in $w$ needs to first arrive in $v$ . A natural guess is that an Erdős-Rényi random graph is so homogeneous that it does not really distinguish between vertices and $H_{wv}=(1+o(1))n$ . Löwe-Terveer established a CLT for the Mean Starting Hitting Time suggesting $H_{wv}=n±\mathcal{O}(\sqrt{n})$ . We prove the existence of a strong concentration phenomenon: $H_{wv}$ is given, up to a very small error of size $\lesssim(\log{n})^{3/2}/\sqrt{n}$ , by an explicit simple formula involving only the total number of edges $|E|$ , the degree $\deg(v)$ and the distance $d(v,w)$ .
Key words and phrases: Erdős-Rényi graphs, hitting time, random walk.
Mathematics Subject Classification: 60J10, 05C80, 60B20
S.S. was supported by the NSF (DMS-2123224) and the Alfred P. Sloan Foundation.
1. Introduction and Results
1.1. The Phenomenon.
The purpose of this paper is to demonstrate a very strong concentration phenomenon for hitting times on Erdős-Rényi random graphs. Given a realization of the graph, the hitting time $H_{wv}$ is the expected time that a simple random walk started in vertex $w$ needs to reach the vertex $v$ for the first time. We consider the distribution of hitting times $H_{wv}$ when the graph $G=G(n,p)$ is an Erdős-Rényi random graph for $0<p<1$ fixed and $n→∞$ . The phenomenon we are interested in can be illustrated with a simple example, see Fig. 1. {tikzpicture}
[scale=1] \node at (0,0)
<details>
<summary>2304.04289v2/x1.png Details</summary>
### Visual Description
# Technical Document Extraction: Histogram Analysis
## 1. Labels and Axis Information
- **Title**: "Distribution of Values"
- **Vertical Axis (Y-axis)**:
- Label: "Frequency"
- Range: 0 to 30,000
- Increment: 5,000
- **Horizontal Axis (X-axis)**:
- Label: "Value"
- Range: 950 to 1100
- Increment: 50
## 2. Key Trends and Data Points
- **Peak Frequency**:
- Highest bar at **Value = 1000**
- Frequency: **25,000**
- **Distribution Shape**:
- Symmetric, bell-shaped curve with a **flat peak** centered at 1000.
- Frequency decreases symmetrically on both sides of the peak.
- **Notable Observations**:
- Bars taper gradually toward the edges (950 and 1100).
- No outliers or anomalies detected in the distribution.
## 3. Chart Components
- **Bars**:
- Color: Black
- Uniform width across all bins.
- **Axes**:
- No gridlines or annotations beyond axis labels and increments.
- **Legend**:
- **Absent**: No legend present in the chart.
## 4. Spatial Grounding and Verification
- **Legend Placement**: Not applicable (no legend exists).
- **Trend Verification**:
- Visual confirmation: Bars increase to 1000, peak at 25,000, then decrease symmetrically.
- No discrepancies between visual trends and axis markers.
## 5. Additional Notes
- The chart represents a **frequency distribution** of values, likely from a dataset with a central tendency around 1000.
- The flat peak suggests a uniform distribution of values near the mode (1000).
- No textual annotations or embedded data tables present.
## 6. Language and Transcription
- **Primary Language**: English
- **Transcribed Text**:
- Axis labels: "Frequency," "Value"
- Title: "Distribution of Values"
- Numerical increments: 5,000 (Y-axis), 50 (X-axis)
</details>
; \node at (6.2,0)
<details>
<summary>2304.04289v2/x2.png Details</summary>
### Visual Description
# Technical Document Analysis: Bar Chart
## Image Description
The image is a **bar chart** with a white background. It features two distinct peaks in data distribution, with no intermediate values between them. The chart lacks a legend, title, or additional textual annotations beyond axis labels.
---
## Axis Labels and Markers
- **X-Axis**:
- Labeled with numerical values: `989.0`, `989.5`, `990.0`, `990.5`, `991.0`.
- No units or categorical labels provided.
- **Y-Axis**:
- Labeled with numerical values: `0`, `20`, `40`, `60`, `80`, `100`, `120`.
- No units specified.
---
## Key Trends and Data Points
1. **First Peak**:
- Located at **x = 989.0**.
- Height: Approximately **60** on the y-axis.
- Structure: A cluster of bars forming a triangular distribution, peaking at the center of the bin.
2. **Second Peak**:
- Located at **x = 991.0**.
- Height: Approximately **120** on the y-axis.
- Structure: A single tall bar with a sharp peak, followed by a gradual decline in adjacent bins.
3. **Intermediate Region**:
- No data points between **x = 989.5** and **x = 990.5**.
- Y-axis values remain at **0** for all bins in this range.
---
## Spatial Grounding and Component Isolation
- **Legend**: Absent in the image.
- **Regions**:
- **Header**: No title or subtitle present.
- **Main Chart**: Dominated by the two peaks and empty intermediate region.
- **Footer**: No additional annotations or source information.
---
## Trend Verification
- **First Peak (989.0)**:
- Visual trend: Symmetrical triangular distribution, peaking at the center of the bin.
- Confirmed data point: Height ≈ 60.
- **Second Peak (991.0)**:
- Visual trend: Sharp upward spike followed by a gradual decline.
- Confirmed data point: Height ≈ 120.
---
## Data Table Reconstruction
| X-Axis Value | Y-Axis Height | Notes |
|--------------|---------------|---------------------------|
| 989.0 | ~60 | Triangular distribution |
| 989.5 | 0 | No data |
| 990.0 | 0 | No data |
| 990.5 | 0 | No data |
| 991.0 | ~120 | Sharp peak |
---
## Additional Notes
- The chart lacks contextual information (e.g., units, units of measurement, or categorical labels).
- The absence of data between 989.5 and 990.5 suggests a bimodal distribution or discrete sampling.
- No textual elements (e.g., titles, legends) are present to clarify the chart's purpose or data source.
---
## Conclusion
The chart depicts two isolated data clusters at **x = 989.0** and **x = 991.0**, with no intermediate values. The second peak is significantly taller than the first, indicating a higher frequency or magnitude at the latter value. Further context is required to interpret the data's real-world significance.
</details>
;
Figure 1. Left: the distribution of all hitting times $H_{ij}$ for a realization of $G(1000,1/2)$ . Right: the distribution of hitting times $H_{wv}$ for $w≠v$ for a fixed vertex $v$ . This quantity is tightly concentrated in two very short intervals.
A natural first guess is that such a random walk is rapidly mixing and should spend roughly equal amounts of time in each vertex and all the vertices should, at least to leading order, be indistinguishable. This would suggest that $H_{wv}\sim n$ whenever $w≠v$ and this was also suggested in the physics literature [14]. A version of this scaling result was rigorously proven by Löwe & Torres [9]. If we denote by $H_{\mu v}:=\sum\mu(w)H_{wv}$ the hitting time starting from a point distributed according to a probability measure $\mu$ , then $H_{\pi v}=(1+o(1))n$ where $\pi(w):=\deg(w)/(2|E|)$ is the (random) stationary distribution. We also refer to subsequent results of Helali & Löwe [5], von Luxburg, Radl & Hein [11] and Sylvester [15]. A look at some numerical examples (see Fig. 1) suggests that the typical deviation of $H_{wv}$ from the mean appears to be on the order of $\sqrt{n}$ . One would naturally expect the existence of a central limit theorem. Such a result was recently established by Löwe & Terveer [10], who showed that $H_{\pi v}-n$ , suitably rescaled, converges to a Gaussian (in distribution). This, while not a statement about $H_{wv}$ in itself, does indicate that averaged hitting times have Gaussian fluctuations.
1.2. Main Result.
We provide what is essentially an explicit formula for $H_{wv}$ up to a very small error term that tends to 0 as $n→∞$ .
**Theorem**
*Let $G(n,p)$ be an Erdős-Rényi random graph with $0<p<1$ . Then, as $n→∞$ , we have with high probability that for any vertex $v$ and all vertices $w≠v$
$$
H_{wv}=\frac{2|E|}{\deg(v)}+\begin{cases}-1\quad&\mbox{if}~{}(w,v)\in E\\
-1+1/p\quad&\mbox{if}~{}(w,v)\notin E\end{cases}\quad+\mathcal{O}\left(\frac{(%
\log{n})^{3/2}}{\sqrt{n}}\right)
$$
where the implicit constant in the error term depends only on $p$ .*
This explains the second picture in Fig. 1, we refer to Fig. 2 for more examples. We also prove (Lemma 1) that the average hitting time starting from vertices $w$ that are adjacent to $v$ is exactly $2|E|/\deg(v)-1$ . The Theorem implies that the central limit theorem obtained by Löwe-Terveer [10] for $H_{\pi·}$ , the hitting time from a stationary initial point, holds for $H_{\mu v}$ for any starting measure $\mu$ , and in particular it also holds for the hitting times $H_{wv}$ themselves, see §2.8. {tikzpicture} \node
at (0,0)
<details>
<summary>2304.04289v2/x3.png Details</summary>
### Visual Description
# Technical Document Analysis: Bar Chart
## Chart Type
- **Bar Chart** with vertical bars representing data points.
## Axes
- **X-Axis (Horizontal)**:
- **Label**: Not explicitly labeled.
- **Categories**: Years `3965`, `3966`, `3967`, `3968`, `3969`, `3970`.
- **Spacing**: Evenly distributed across the axis.
- **Y-Axis (Vertical)**:
- **Label**: Not explicitly labeled.
- **Range**: `0` to `800`, with increments of `200`.
- **Units**: Numerical values (no explicit units provided).
## Data Points
1. **Bar at `3965`**:
- **Height**: Approximately `100` on the Y-axis.
- **Position**: Leftmost bar, centered over `3965`.
2. **Bar at `3970`**:
- **Height**: Approximately `900` on the Y-axis.
- **Position**: Rightmost bar, centered over `3970`.
3. **Years `3966`–`3969`**:
- **Bars**: No visible bars; no data represented.
## Trends
- **Primary Trend**: A significant increase in the data value from `3965` to `3970`.
- Value rises from ~`100` to ~`900`, a **800-unit increase**.
- **Secondary Trend**: No data points for intermediate years (`3966`–`3969`).
## Visual Details
- **Bars**: Black, rectangular, with no shading or gradients.
- **Background**: White, with no gridlines or annotations.
- **Spacing**: Consistent gaps between bars and axis labels.
## Notes
- No legend, text blocks, or additional annotations present.
- The chart focuses on two discrete data points with a stark contrast in magnitude.
</details>
; \node at (6,0)
<details>
<summary>2304.04289v2/x4.png Details</summary>
### Visual Description
# Technical Document Extraction: Bar Chart Analysis
## Chart Overview
The image depicts a **bar chart** with two vertical bars. The chart lacks a title, legend, gridlines, or annotations. The x-axis and y-axis are labeled numerically, but no units or categorical labels are provided.
---
## Axis Labels and Markers
- **X-Axis**:
- Range: `3995.0` to `3996.2` (increments of `0.2`).
- Key data points:
- Left bar at `3995.0`.
- Right bar at `3996.1`.
- **Y-Axis**:
- Range: `0` to `1000` (increments of `200`).
- No explicit unit or label provided.
---
## Data Points and Trends
1. **Left Bar** (`x = 3995.0`):
- Height: Approximately `1000` (y-axis).
- Trend: Dominant peak, significantly taller than the right bar.
2. **Right Bar** (`x = 3996.1`):
- Height: Approximately `600` (y-axis).
- Trend: Secondary peak, shorter than the left bar.
**Visual Verification**:
- The left bar slopes upward sharply to `1000`, while the right bar rises more gradually to `600`. No overlapping or intersecting data series observed.
---
## Structural Components
- **Legend**: Absent.
- **Gridlines**: Absent.
- **Annotations**: None.
- **Color Scheme**: Monochromatic (black bars on white background).
---
## Missing Elements
- No textual labels, legends, or categorical identifiers.
- No contextual information (e.g., units, data source, or purpose).
---
## Conclusion
The chart represents two discrete data points at `x = 3995.0` and `x = 3996.1`, with values of `1000` and `600`, respectively. The absence of legends or labels limits interpretability. Further context is required to determine the chart's purpose or domain.
</details>
;
Figure 2. Left: $G(4000,0.2)$ with predicted localization at $2|E|/\deg(v)-1=3965.3$ and $2|E|/\deg(v)+4=3970.3$ . Right: $G(4000,0.8)$ with predicted localization at $3994.9$ and $3996.16$ .
One interpretation, which also informs the structure of the proof, is that an Erdős-Rényi random graph has diameter 2 (with high probability) and can be understood as behaving a little bit like a three-state Markov chain: the vertex $v$ under consideration, the vertices at distance 1 from $v$ , and the vertices at distance 2 from $v$ . Note that transitions to $v$ are rare, given that a typical vertex has an high degree. During that time, the mixing properties of the graph are of sufficiently high quality that they essentially lead to near-deterministic behavior. However, it is important whether one starts at distance 1 or 2 from the target vertex $v$ (not surprising since we aim to determine the hitting term up to an error of $o(1)$ ). In fact, since transitions from most vertices at distance $2$ to the set of vertices at distance $1$ happen at rate roughly $\sim p$ , the correction $1/p$ can be understood as a geometric hitting time. It is conceivable that the result has an extension when $p$ decays with $n$ , generalizing accordingly the number of possible states since the diameter will increase with high probability (see, e.g., [1] for a variety of regimes). Moreover, while some features of our proof rely on the Erdős-Rényi structure, a similar approach may lead to less refined results (e.g., a law of large number or a central limit theorem) for other models of random graphs, provided that the mixing time is sufficiently small compared to the hitting time, bypassing a spectral approach. This seems like a promising avenue for further research.
1.3. Implications.
The result has a number of implications in terms of known results. Löwe & Torres [9] prove, using a spectral theory approach, that the averaged hitting time $H_{\pi v}$ satisfies
$$
H_{\pi v}\geq\frac{2|E|}{\deg(v)}-2
$$
which can now be seen to be almost optimal. Our Theorem implies
| | $\displaystyle H_{\pi v}=\sum_{w}\pi(w)H_{wv}=\frac{2|E|}{\deg(v)}-3+\frac{1}{p%
}+\mathcal{O}\left(\frac{(\log{n})^{3/2}}{\sqrt{n}}\right).$ | |
| --- | --- | --- |
The result also has immediate implications for the commute time $\kappa_{wv}=H_{wv}+H_{vw}$ and the effective resistance
$$
\sigma_{wv}=\frac{\kappa_{wv}}{2|E|}.
$$
For example, we can deduce a very precise asymptotic expansion
$$
\sigma_{wv}=\frac{1}{\deg(v)}+\frac{1}{\deg(w)}+\frac{2}{n^{2}p}\begin{cases}-%
1\quad&\mbox{if}~{}(v,w)\in E\\
-1+1/p\quad&\mbox{if}~{}(v,w)\notin E\end{cases}+\mathcal{O}\left(\frac{(\log{%
n})^{3/2}}{n^{5/2}}\right).
$$
We remark that the effective resistance is intimately connected to a number of classical objects in probability, such as uniform spanning trees (a result dating back to Kirchhoff [6]), and it is easy to rephrase the asymptotic above correspondingly (see, e.g., Chapter $4$ in [12]). Comparing to arbitrary graphs, a result of Lovász [8] shows that the commute time always satisfies
$$
|E|\left(\frac{1}{\deg(v)}+\frac{1}{\deg(w)}\right)\leq\kappa_{wv}\leq\frac{2|%
E|}{1-\lambda_{2}}\left(\frac{1}{\deg(v)}+\frac{1}{\deg(w)}\right),
$$
where $\lambda_{2}$ is the second eigenvalue of the transition matrix. For a typical Erdős-Rényi random graph, our result says that the lower bound is almost saturated. We conclude with some spectral implication (see Löwe & Torres [9] or Lovász [8] for additional details). Let $A∈\left\{0,1\right\}^{n× n}$ denote the adjacency matrix of the graph and $D$ denote the degree matrix of the graph, we can introduce $B=D^{-1/2}AD^{-1/2}$ . $B$ has largest eigenvalue $\lambda_{1}=1$ and has eigenvalues $\lambda_{1}≥\lambda_{2}≥...≥\lambda_{n}$ . We use $\sigma_{k}$ to denote the eigenvectors of length 1 associate to the $k-$ th eigenvalue. Then, see Löwe & Torres [9] or Lovász [8], we have
$$
H_{\pi v}=\frac{2|E|}{\deg(v)}\sum_{w=2}^{n}\frac{\sigma_{wv}^{2}}{1-\lambda_{%
k}}.
$$
Since $H_{\pi v}$ is nearly constant in $v$ , this can be understood as a type of weighted equidistribution result for the eigenvectors of $B$ . Finally, our result allows for estimates related to the quasi-stationary distribution $\tilde{\pi}_{v}$ associated to a vertex $v$ , that is to say, the Perron-Frobenius eigenvector of the sub-stochastic matrix obtained by neglecting the row and column corresponding to $v$ in the transition matrix (see [3] and references therein for a discussion on its use). It is a classical fact that its eigenvalue $\lambda_{v}$ satisfies
| | $\displaystyle H_{\tilde{\pi}_{v}v}=\frac{1}{1-\lambda_{v}},$ | |
| --- | --- | --- |
and so our result gives two-sided bounds on $\lambda_{v}$ that are uniform in $v∈ V$ (w.h.p.).
2. Proof
2.1. Outline
It is a classical result (see, for example, [7]) that with high probability the diameter of $G(n,p)$ for fixed $p$ is 2. From now on, we will work on the event that this occurs. We fix a vertex $v∈ V$ and consider from now on only the (first) hitting time of $v$ of a random walk starting in any vertex $w∈ V$ . Naturally, $H_{vv}=0$ . For any other vertex $w≠v$ , we have
$$
\displaystyle H_{wv}=1+\frac{1}{\deg(w)}\sum_{(w,u)\in E}H_{uv}. \tag{1}
$$
Having fixed $v∈ V$ , we denote the set of all vertices at distance 1 from $v$ by $A$ ,
$$
A=\left\{w\in V:d(v,w)=1\right\}
$$
and the set of all vertices at distance 2 from $v$ by $B=V\setminus\left(\left\{v\right\}\cup A\right)$ . We first establish concentration of the hitting times in $A$ and $B$ and then use the concentration to deduce everything else. The proof works as follows.
1. We first recall some basic facts from probability theory (in §2.2) that will be used throughout to argument: concentration of the degrees, a technical result on the convergence rate, and an exact computation for the hitting time when the starting distribution is uniform in $A$ .
1. In §2.3 we derive a combinatorial formula for the hitting time. It is then shown that many of the terms in the formula are tightly concentrated, conditional on a certain a priori bound to be established.
1. §2.4 shows the a priori bound
$$
H_{wv}=n+\mathcal{O}(\sqrt{n\log{n}})
$$
with high probability. This result is not as good as the main result but shows that certain terms that arise in the formula from §2.3 are more tightly concentrated than one might expect from $H_{wv}=(1+o(1))· n$ .
1. §2.5 uses all the preceeding arguments to show strong concentration of the hitting time in the set $B$ ,
$$
\max_{w_{1},w_{2}\in B}|H_{w_{1}v}-H_{w_{2}v}|\lesssim\frac{(\log{n})^{3/2}}{%
\sqrt{n}}.
$$
1. In §2.6 a similar argument is repeated for vertices in $A$ and
$$
\max_{w_{1},w_{2}\in A}|H_{w_{1}v}-H_{w_{2}v}|\lesssim\frac{(\log{n})^{3/2}}{%
\sqrt{n}}.
$$
1. Having shown concentration in both $A$ and $B$ , it is shown in §2.7 that the difference in expectation between the hitting times in $A$ and $B$ is $1/p+\mathcal{O}(\sqrt{\log{n}}/\sqrt{n})$ . Since we already know (Lemma 1) the expected hitting time for vertices in $A$ , the result follows.
1. §2.8 observes an associated Central Limit Theorem immediately follows, §2.9 proves the technical Proposition introduced in §2.2.
2.2. Preliminary facts
We first collect a couple of elementary facts that will be used several times. We will often omit w.h.p. (with high probability) in what follows: every time we invoke a property of Erdős-Rényi random graphs it is to be understood as being valid with high probability. The sequence of degrees are Bernoulli random variables $\deg(v)\sim B(n,p)$ , with $\mathbb{E}\deg(v)=(n-1)p$ . While they are not independent, a union bound, together with a Chernoff bound for binomial random variables, gives
$$
np-c_{p}\sqrt{n}\sqrt{\log{n}}\leq\min_{v\in V}\deg(v)\leq\max_{v\in V}\deg(v)%
\leq np+c_{p}\sqrt{n}\sqrt{\log{n}}
$$
We note that more precise results, in particular about the size of $c_{p}$ , are known (see, e.g., [2]), though we will not try to optimize over that as they are not required for the remainder of the argument. In particular, this gives
$$
\max_{v\in V}\left|\deg(v)-np\right|\lesssim\sqrt{n\log{n}} \tag{2}
$$
with high likelihood and with an implicit constant depending on $p$ only.
Another ingredient that we will use several times is the following technical proposition about the behavior of a random walk on an Erdős-Renyi graph.
**Proposition**
*Let $G=G(n,p)$ be an Erdős-Renyi graph with $0<p<1$ fixed and $n→∞$ . Let $v$ be an arbitrary vertex, $\mu_{0}=\delta_{v}$ and $\mu_{k+1}=\mu_{k}D^{-1}A$ be the probability distribution after $k$ steps of the random walk. Using $\pi$ to denote the stationary distribution, for $k≥ 1$ ,
$$
\|\mu_{k}-\pi\|_{\ell^{2}}\lesssim_{k,p}\frac{(\log n)^{\frac{k-1}{2}}}{n^{k/2%
}}.
$$*
The Cauchy-Schwarz inequality implies that
$$
\displaystyle\|\mu_{k}-\pi\|_{1} \displaystyle\leq\sqrt{n}\cdot\|\mu_{k}-\pi\|_{2}\lesssim_{k,p}\left(\frac{%
\log{n}}{n}\right)^{\frac{k-1}{2}}. \tag{3}
$$
We will only use his argument for $k=3$ . The argument is self-contained and presented at the end of the paper. Our argument will benefit from having at least one probability measure $\nu$ for which we can obtain explicit estimates on the expected hitting time. There is a particularly simple choice.
**Lemma 1**
*Let $v∈ V$ be arbitrary and let $A$ be the set of neighbors of $v$ . Consider the probability measure $\nu=1_{A}/\deg(v)$ . Then, we have
| | $\displaystyle H_{\nu v}=\frac{2|E|}{\deg(v)}-1.$ | |
| --- | --- | --- |*
* Proof*
Consider a random walker starting from the stationary distribution $\pi$ given by $\pi(w)=\deg(w)/(2|E|)$ . There are two cases: either the initial vertex is already $v$ (and then the hitting time is 0) or it is not, in which case the new probability distribution after one step is distributed according to some new measure $\mu$ . On the other hand, conditional on the starting point being $v$ , the distribution after one step would be exactly $\nu$ . Therefore, we have
| | $\displaystyle\mu=\frac{\pi-\pi(v)\nu}{1-\pi(v)}.$ | |
| --- | --- | --- |
In particular, we obtain
| | $\displaystyle H_{\pi v}=(1-\pi(v))\left(1+H_{\mu v}\right)=1-\pi(v)+H_{\pi v}-%
\pi(v)H_{\nu v}.$ | |
| --- | --- | --- |
Rearranging, this gives
| | $\displaystyle H_{\nu v}=\frac{1}{\pi(v)}-1=\frac{2|E|}{\deg(v)}-1.$ | |
| --- | --- | --- |
∎
The result has an electrical network interpretation, which can be turned into a proof when $A=\{w\}$ is a single vertex connected to $v$ through $\deg(v)$ edges. The effective resistance $\kappa_{wv}$ is that of $\deg(v)$ resistances in parallel. Then,
| | $\displaystyle\frac{H_{wv}+H_{vw}}{2E}=\kappa_{vw}=\frac{1}{\deg(v)},$ | |
| --- | --- | --- |
and the result follows since $H_{vw}=1$ .
2.3. A formula for the Hitting time for $w∈ B$ .
Let us now fix a vertex $w∈ B$ . As an initial motivation, we consider the distribution of a random walk started in $w∈ B$ with a length of 2 steps. We start with the basic fact (introduced above as (1)) that for a vertex $w≠v$
| | $\displaystyle H_{wv}=1+\frac{1}{\deg(w)}\sum_{(w,u)∈ E}H_{uv}.$ | |
| --- | --- | --- |
Since $w∈ B$ and $d(w,v)=2$ , we can apply the identity twice. If we denote the arising distribution after 2 steps by $\nu_{w}$ , then this implies the exact equation
$$
H_{wv}=2+H_{\nu_{w}v}.
$$
For the remainder of the argument, we will consider the distribution of random walks started in $w∈ B$ after 3 steps and this probability distribution will be denoted by $\mu_{w}$ . The analogous equation
$$
\displaystyle H_{wv}=3+H_{\mu_{w}v}\qquad\mbox{is false} \tag{4}
$$
because (1) is only valid in vertices $w≠v$ but a random walk started in $w$ might end up in $v$ after 2 steps. We also note that this is the only source of error. If the random walk ends up in $v$ after 2 steps, then it is uniformly distributed in $A$ after 3 steps and the equation (4) mistakenly contributes
$$
\mathbb{P}\left(\mbox{random walk is in}~{}v~{}\mbox{after 2 steps}\right)%
\cdot\frac{1}{|A|}\sum_{w\in A}H_{wv}
$$
while the true hitting time would have been 2. We note that the sum, the average hitting time for a starting vertex in $A$ , has already been computed above in Lemma 1 but we will not actually need its precise value at this point in the argument. Correcting for this, we arrive at
$$
\displaystyle H_{wv} \displaystyle=3+\sum_{a\in V}\mu_{w}(a)\cdot H_{av} \displaystyle+\mathbb{P}\left(\mbox{random walk is in}~{}v~{}\mbox{after 2 %
steps}\right)\cdot\left(-1-\frac{1}{|A|}\sum_{a\in A}H_{av}\right). \tag{5}
$$
We will now argue that (5) can be used to show that the hitting time is tightly concentrated by showing that each of its terms is tightly concentrated. We start by noting that Lemma 1 implies that
$$
\left(-1-\frac{1}{|A|}\sum_{a\in A}H_{av}\right)=-\frac{2|E|}{\deg(v)}
$$
is independent of $w$ . We continue by computing the probability of a random walk started in $w$ hitting $v$ within 2 steps. For this to happen, the first step of the random walk has to lead to $A$ and the second step has to lead from $A$ to $v$ . The likelihood of moving from $w$ to $A$ is simply the number of neighbors that $w$ has in $A$ compared to its total degree. Introducing the abbreviation
$$
N_{A}(w)=\left\{a\in A:(a,w)\in E\right\}
$$
for the number of neighbors a vertex has in $A$ , we have that the likelihood of moving from $w$ to $A$ is given by
$$
\frac{\#N_{A}(w)}{\deg(w)}=\frac{|A|}{n}+\mathcal{O}\left(\frac{\sqrt{\log{n}}%
}{\sqrt{n}}\right)\qquad\mbox{with high probability.}
$$
owing to (2). The second ingredient is the likelihood of moving from $A$ to $v$ in the second step which, conditioned on the first step leading from $w$ to $A$ , happens with likelihood
$$
\frac{1}{\#N_{A}(w)}\sum_{z\in N_{A}(w)}\frac{1}{\deg(z)}.
$$
This is an average over inverse degrees over the set of neighbors of $w$ that are in $A$ . Abbreviating
$$
X=\left|\frac{1}{\#N_{A}(w)}\sum_{z\in N_{A}(w)}\frac{1}{\deg(z)}-\frac{1}{(n-%
1)p}\right|
$$
we obtain, appealing (2) that (w.h.p.)
| | $\displaystyle X$ | $\displaystyle≤\max_{v∈ V}\left|\frac{1}{\deg(v)}-\frac{1}{(n-1)p}\right|$ | |
| --- | --- | --- | --- |
We see that $\mathbb{P}=\mathbb{P}\left(\mbox{random walk in}~{}v~{}\mbox{after 2 steps}\right)$ satisfies
$$
\displaystyle\mathbb{P} \displaystyle=\left(\frac{|A|}{n}+\mathcal{O}\left(\frac{\sqrt{\log{n}}}{\sqrt%
{n}}\right)\right)\left(\frac{1}{np}+\mathcal{O}\left(\frac{\sqrt{\log{n}}}{n^%
{3/2}}\right)\right) \displaystyle=\frac{|A|}{n^{2}p}+\mathcal{O}\left(\frac{\sqrt{\log{n}}}{n^{3/2%
}}\right). \tag{6}
$$
Therefore, (5) can be simplified as
$$
H_{wv}=3+\sum_{a\in V}\mu_{w}(a)\cdot H_{av}+\mbox{Error}(w)
$$
where
$$
\mbox{Error}(w)=-\frac{2|E|}{n^{2}p}\pm\mathcal{O}\left(\frac{\sqrt{\log{n}}}{%
\sqrt{n}}\right)
$$
and the error term is uniform over all choices of $w∈ B$ .
2.4. A Cheap Uniform Bound
The purpose of this short section is to deduce a cheap uniform bound. This estimate will then be bootstrapped in the subsequent sections to obtain the main result.
**Lemma 2**
*Let $G=G(n,p)$ with $0<p<1$ . Then, as $n→∞$ , with high probability
$$
\max_{v\neq w\in V}~{}\left|H_{wv}-n\right|\lesssim\sqrt{n\log{n}}.
$$
and also
$$
\max_{v\in V,w_{1},w_{2}\in V\setminus\{v\}}|H_{w_{1}v}-H_{w_{2}v}|\lesssim 1.
$$
In both results, the implicit constants depend on $p$ only.*
* Proof*
We know from (2) that, with high likelihood,
$$
\max_{w\in V}\left|\deg(w)-np\right|\lesssim\sqrt{n\log{n}}.
$$
We first argue that $H_{wv}≤ C_{p}n$ for some constant $0<C_{p}<∞$ . Let $X_{0},X_{1},...,$ denote the simple random walk on the graph. We note that there are $|A|=np±\mathcal{O}(\sqrt{n\log{n}})$ vertices where the likelihood of hitting $v$ in the next step is at least
$$
\mathbb{P}\left(X_{k+1}=v\big{|}X_{k}\in A\right)=\frac{1}{\deg(X_{k})}=\frac{%
1}{np}\pm\mathcal{O}\left(\frac{\sqrt{\log{n}}}{n^{3/2}}\right).
$$
If the random walk $X_{k}∈ B$ , then
$$
\mathbb{P}\left(X_{k+1}\in A\big{|}X_{k}\in B\right)\geq p+o(1). \tag{1}
$$
We can now do a simple case distinction: either $X_{k}∈ A$ in which case $X_{k+1}=v$ with likelihood at least $1/(np)$ or $x_{k}∈ B$ in which case $X_{k+2}=v$ with likelihood at least $1/n$ . Using a geometric probability distribution for stochastic domination, we see that $H_{wv}≤ C_{p}n$ . We can now consider an arbitrary starting vertex $w∈ V$ together with a random walk of 3 steps started in $w$ . Let $T_{wv}$ be the time that it takes to hit $v$ starting from $w$ , so that $\mathbb{E}[T_{wv}]=H_{wv}$ . There are two cases: the random walk happens to hit $v$ within the first $3$ steps or it does not. Therefore, if $\mu_{3}$ denotes the distribution after $3$ steps,
$$
\displaystyle H_{wv} \displaystyle=\mathcal{O}(1)+\sum_{u\in V}\mu_{3}(u)\cdot\mathbb{E}[T_{uv}%
\cdot\mathbb{E}[1_{T_{wv}>3}|X_{3}=u]]. \tag{1}
$$
Note that
$$
\mathbb{E}[T_{uv}\cdot\mathbb{E}[1_{T_{wv}>3}|X_{3}=u]]\leq H_{uv}\leq C_{p}n.
$$
The same bound holds if we replace $w$ with the stationary distribution. Using
| | $\displaystyle\|\mu_{3}-\pi\|_{1}\lesssim\frac{\log{n}}{n},$ | |
| --- | --- | --- |
which follows from (3) with $k=3$ we deduce that with high probability and uniformly over all $v∈ V$ and $w_{1},w_{2}∈ V\setminus\{v\}$
$$
|H_{w_{1}v}-H_{w_{2}v}|\lesssim\log{n}.
$$
Note that, by convexity, the result remains true if $w_{2}$ is replaced by an arbitrary probability measure. If we choose $\nu$ from Lemma 1, we deduce
| | $\displaystyle\left|H_{wv}-\frac{2E}{\deg v}+1\right|\lesssim\log{n},$ | |
| --- | --- | --- |
and thus we deduce since, using (2), that
| | $\displaystyle\left|\frac{2E}{\deg v}-n\right|=\mathcal{O}\left(\sqrt{n\log n}\right)$ | |
| --- | --- | --- |
with high probability. ∎
2.5. Concentration of Hitting Times in $B$ .
We can now use these results to establish concentration of the hitting times in $B$ . For this purpose, let us keep our original arbitrary vertex $w∈ B$ considered above and let us additionally consider another vertex $w_{2}∈ B$ . The distribution of a random walk started in $w_{2}$ after 3 steps will be denoted by $\mu_{2}$ . Using (5) once in $w$ and once in $w_{2}$ and invoking the uniform asymptotics (2.3) we arrive at
| | $\displaystyle H_{wv}-H_{w_{2}v}$ | $\displaystyle=\mathcal{O}\left(\frac{\sqrt{\log{n}}}{\sqrt{n}}\right)+\sum_{c%
∈ V}(\mu(c)-\mu_{2}(c))· H_{cv}$ | |
| --- | --- | --- | --- |
Lemma 2, the fact that two probability distributions $\mu$ and $\mu_{2}$ have equal $\ell^{1}-$ norm and the Cauchy-Schwarz inequality allow us to rewrite this as
| | $\displaystyle\left|H_{wv}-H_{w_{2}v}\right|$ | $\displaystyle=\left|\mathcal{O}\left(\frac{\sqrt{\log{n}}}{\sqrt{n}}\right)+%
\sum_{c∈ V}(\mu(c)-\mu_{2}(c))·(n+(H_{cv}-n))\right|$ | |
| --- | --- | --- | --- |
Using a triangular inequality and (3) with $k=3$ , we obtain
$$
\|\mu-\mu_{2}\|_{\ell^{1}}\lesssim\frac{\log{n}}{n},
$$
leading to
$$
\displaystyle\left|H_{wv}-H_{w_{2}v}\right| \displaystyle\lesssim\frac{(\log{n})^{3/2}}{\sqrt{n}}. \tag{7}
$$
2.6. Concentration for vertices in $A$ .
We will now adapt the argument for vertices in $A$ . Let $w∈ A$ and consider the usual random walk in $A$ after 3 steps. We would like to argue analogously as before to obtain a combinatorial formula for the hitting time. There are now two types of mistakes that can happen: those that arise if the random walk already ends up in $v$ after 1 step or after 2 steps.
1. Scenario 1. The random walk moves from $w$ to $v$ in the first step. In that case the true hitting time is 1 where as the naive formula (4) produces an error given by the average hitting time in a point after 2 random steps started in $v$ (as before, this quantity is $\mathcal{O}(n)$ and independent of $w$ ).
1. Scenario 2. The random walk arrives in $v$ at the second step (but not the first). In that case, we deduce that the first random step has to lead from $w$ to another vertex in $A$ and then from that vertex to $v$ . The error made in the naive formula is that it produces the average hitting time in $A$ as opposed to the true hitting time, which equals to $2$ .
We deduce that there are two numbers $O_{1},O_{2}=\mathcal{O}(n)$ , independent of $w∈ A$ , with
$$
\displaystyle H_{wv} \displaystyle=3+\sum_{a\in V}\mu(a)\cdot H_{av} \displaystyle+\mathbb{P}\left(\mbox{Scenario 1}\right)\cdot O_{1}+\mathbb{P}%
\left(\mbox{Scenario 2}\right)\cdot O_{2}. \tag{8}
$$
Note that $O_{1}$ is simply the expected hitting time weighted by the outcome of a random walk of length 2 started in $v$ and $O_{2}$ is the expected hitting time weighted by the distribution of a random walk of length 1 started in $v$ (which, as above, is merely the average hitting time in $A$ ). It remains to show that, just as above, the likelihoods of the two scenarios depend on $w$ in a weak sense. We start with Scenario 1. We have, using (2),
$$
\mathbb{P}\left(\mbox{Scenario 1}\right)=\frac{1}{\deg(w)}=\frac{1}{np\pm%
\mathcal{O}(\sqrt{n\log{n}})}=\frac{1}{np}+\mathcal{O}\left(\frac{\sqrt{\log{n%
}}}{n^{3/2}}\right).
$$
The likelihood of Scenario 2 was already implicitly computed above: there we computed the likelihood of having a random walk from a vertex in $B$ travel to a vertex in $A$ and then to $v$ . However, that likelihood is independent of whether one starts in $A$ or in $B$ and the very same argument as above (see (2.3)) gives
| | $\displaystyle\mathbb{P}\left(\mbox{Scenario 2}\right)=\frac{|A|}{n^{2}p}+%
\mathcal{O}\left(\frac{\sqrt{\log{n}}}{n^{3/2}}\right)$ | |
| --- | --- | --- |
The remainder of the argument is exactly the same as above and we deduce that
$$
\displaystyle\max_{w_{1},w_{2}\in A}|H_{w_{1}v}-H_{w_{2}v}|\lesssim\frac{(\log%
{n})^{3/2}}{\sqrt{n}}. \tag{9}
$$
2.7. Proof of the Theorem
At this point, we know that the expected hitting time in both $A$ and $B$ is essentially constant, owing to (9) and (7), up to an error of size $\lesssim(\log n)^{3/2}/\sqrt{n}$ . We define the average hitting times in $A$ and in $B$
| | $\displaystyle H_{A}=\frac{1}{|A|}\sum_{w∈ A}H_{wv},\quad H_{B}=\frac{1}{|B|}%
\sum_{w∈ B}H_{wv}.$ | |
| --- | --- | --- |
From Lemma (1), we know
$$
H_{A}=\frac{2E}{\deg v}-1, \tag{10}
$$
and, appealing to (9), we obtain that for $w∈ A$
| | $\displaystyle H_{wv}=\frac{2E}{\deg v}-1+\mathcal{O}\left(\frac{(\log n)^{3/2}%
}{\sqrt{n}}\right).$ | |
| --- | --- | --- |
It remains to show that
$$
H_{B}-H_{A}=\frac{1}{p}+\mathcal{O}\left(\frac{(\log{n})^{3/2}}{\sqrt{n}}%
\right),
$$
for the result will follow from (7) and (10). Let now $w∈ B$ be an arbitrary vertex. Performing one step of a random walk in $w$ , we deduce that
| | $\displaystyle H_{B}$ | $\displaystyle=H_{wv}+\mathcal{O}\left(\frac{(\log{n})^{3/2}}{\sqrt{n}}\right)$ | |
| --- | --- | --- | --- |
At this point we can invoke the strong concentration of hitting times in $A$ and $B$ once more to deduce that
| | $\displaystyle H_{B}$ | $\displaystyle=\mathcal{O}\left(\frac{(\log{n})^{3/2}}{\sqrt{n}}\right)+1+\frac%
{1}{\deg(w)}\sum_{z∈ N_{A}(w)}H_{A}+\frac{1}{\deg(w)}\sum_{z∈ N_{B}(w)}H_{B}$ | |
| --- | --- | --- | --- |
Vertices in $B$ only have neighbors in $A$ and in $B$ and therefore, for $w∈ B$ ,
$$
1=\frac{\#N_{A}(w)+\#N_{B}(w)}{\deg(w)}
$$
from which we deduce
$$
\frac{\#N_{A}(w)}{\deg(w)}H_{B}=\mathcal{O}\left(\frac{(\log{n})^{3/2}}{\sqrt{%
n}}\right)+1+\frac{\#N_{A}(w)}{\deg(w)}H_{A}
$$
and thus
$$
H_{B}=\mathcal{O}\left(\frac{(\log{n})^{3/2}}{\sqrt{n}}\right)+\frac{\deg(w)}{%
\#N_{A}(w)}+H_{A}.
$$
We also note that, from (2),
| | $\displaystyle\frac{\deg(w)}{\#N_{A}(w)}$ | $\displaystyle=\frac{np+\mathcal{O}(\sqrt{n\log{n}})}{p|A|+\mathcal{O}(\sqrt{n%
\log{n}})}$ | |
| --- | --- | --- | --- |
Thus
| | $\displaystyle H_{B}-H_{A}=\frac{1}{p}+\mathcal{O}\left(\frac{(\log{n})^{3/2}}{%
\sqrt{n}}\right).$ | |
| --- | --- | --- |
2.8. A Central Limit Theorem
We conclude by showing how the Theorem immediately implies a central limit theorem for the hitting times starting from any point. It can be easily generalized to an arbitrary initial configuration that does not include the target point. This follows from the Theorem and the fact that the main fluctuation comes from the fluctuation of the degree of the target vertex while being virtually independent (up to fluctuations of size $\mathcal{O}(1)$ ) of everything else.
**Corollary**
*Fix two vertices $1,2$ . Then, the distribution of $H_{12}$ over all Erdős-Rényi random graphs satisfies, as $n→∞$ ,
| | $\displaystyle\sqrt{\frac{p}{n(1-p)}}\left(H_{12}-n\right)\Rightarrow\mathcal{N%
}(0,1)$ | |
| --- | --- | --- |*
* Proof*
The central limit theorem for a binomial random variable says that
$$
\displaystyle\deg(2)=np\left(1-\sqrt{\frac{1-p}{pn}}Z_{n}\right), \tag{2}
$$
where $Z_{n}$ converges in distribution to a normal random variable. A standard concentration bound for the number of edges gives
| | $\displaystyle 2|E|=n^{2}p\left(1+\mathcal{O}\left(\frac{\sqrt{\log n}}{n}%
\right)\right)$ | |
| --- | --- | --- |
with high probability. Combining with our main theorem, we obtain
$$
H_{12}=n\frac{1+\mathcal{O}\left(\frac{\sqrt{\log n}}{n}\right)}{1-\sqrt{\frac%
{1-p}{np}}Z_{n}}+\mathcal{O}\left(1\right), \tag{1}
$$
where the error terms are uniform with respect to the measures $\mu_{n}$ . Therefore
| | $\displaystyle\sqrt{\frac{p}{n(1-p)}}\left(H_{12}-n\right)$ | $\displaystyle=\sqrt{\frac{np}{1-p}}\left[\frac{1+\mathcal{O}\left(\frac{\sqrt{%
\log n}}{n}\right)}{1-\sqrt{\frac{1-p}{np}}Z_{n}}-1+\mathcal{O}\left(\frac{1}{%
n}\right)\right]$ | |
| --- | --- | --- | --- |
The result then follows from Slutsky’s theorem. ∎
2.9. Proof of the Proposition
The Proposition will be proven by induction. The statement is very easy to prove when $k=1$ . For the induction step $k→ k+1$ , we make use of a technical Lemma.
**Lemma 3**
*Let $v∈\mathbb{R}^{n}$ be a row vector whose entries sum to 0. Then
$$
\|vD^{-1}A\|_{\ell^{2}}\leq c_{p}\frac{\sqrt{\log{n}}}{\sqrt{n}}\|v\|_{\ell^{2%
}}.
$$*
* Proof*
We use two different ingredients. The first is to write the diagonal matrix $D^{-1}$ as the sum of two diagonal matrices $D^{-1}=D_{1}+D_{2}$ using
$$
\frac{1}{\deg(v)}=\frac{1}{np}+\left(\frac{1}{\deg(v)}-\frac{1}{np}\right).
$$
$D_{1}$ is a matrix with entries $1/(np)$ on the diagonal and $D_{2}=D^{-1}-D_{1}$ . Note that $D_{1}$ is a multiple of the identity and $\|D_{1}\|=1/(np)$ . Since
$$
\deg(v)=np\pm\mathcal{O}(\sqrt{n\log{n}}),
$$
we have
$$
\left|\frac{1}{\deg(v)}-\frac{1}{np}\right|\lesssim\frac{\sqrt{\log{n}}}{n^{3/%
2}}\qquad\mbox{and thus}\qquad\|D_{2}\|\lesssim\frac{\sqrt{\log{n}}}{n^{3/2}}.
$$
The second ingredient are the spectral properties of $A$ . $A$ has one eigenvalue at scale $\lambda_{1}\sim np$ while the second largest eigenvalue of $A$ satisfies $|\lambda_{2}(A)|\lesssim_{p}\sqrt{n}$ with probability tending to 1 (see Füredi-Komlos [4]). This allows us to write, using that $D_{1}$ is a multiple of the identity matrix and thus commutes with all other matrices,
| | $\displaystyle\|vD^{-1}A\|$ | $\displaystyle=\|v(D_{1}+D_{2})Av\|$ | |
| --- | --- | --- | --- |
It remains to analyze the first term. Since $A$ is symmetric, the spectral theorem applies. Using $\phi$ to denote the $\ell^{2}-$ normalized eigenvector of $A$ associated to the eigenvalue $\lambda_{1}$ (and $\lambda_{2}$ the second largest eigenvalue in absolute value), we have
$$
\|vA\|^{2}\leq\lambda_{1}(A)^{2}\left\langle\phi,v\right\rangle^{2}+\lambda_{2%
}(A)^{2}\|v\|^{2}.
$$
Now we use a result of Mitra [13] telling us that the eigenvector associated to the adjacency matrix of an Erdős-Renyi random graph $G(n,p)$ and $0<p<1$ fixed is nearly constant and
$$
\max_{1\leq i\leq n}\left|\phi_{i}-\frac{1}{\sqrt{n}}\right|\leq c_{p}\frac{%
\sqrt{\log{n}}}{n}.
$$
This allows us to write
| | $\displaystyle\left\langle\phi,v\right\rangle=\sum_{i=1}^{n}\phi_{i}v_{i}=\sum_%
{i=1}^{n}\frac{1}{\sqrt{n}}v_{i}+\sum_{i=1}^{n}\left(\phi_{i}-\frac{1}{\sqrt{n%
}}\right)v_{i}.$ | |
| --- | --- | --- |
The first sum vanishes because $v$ , by assumption, has mean value 0. Using the Cauchy-Schwarz inequality
$$
\left\langle\phi,v\right\rangle^{2}=\left(\sum_{i=1}^{n}\left(\phi_{i}-\frac{1%
}{\sqrt{n}}\right)v_{i}\right)^{2}\lesssim_{p}\frac{\log{n}}{n}\cdot\|v\|_{%
\ell^{2}}^{2}.
$$
Therefore
| | $\displaystyle\frac{\|vA\|_{\ell^{2}}}{n}$ | $\displaystyle\lesssim\frac{1}{n}\sqrt{\lambda_{1}(A)^{2}\left\langle\phi,v%
\right\rangle^{2}+\lambda_{2}(A)^{2}\|v\|^{2}}$ | |
| --- | --- | --- | --- |
This establishes the desired result. ∎
* Proof of the Proposition*
$\mu_{1}$ is easy to describe, it assumes values $1/\deg(v)$ in the neighbors of $v$ and value 0 everywhere else. Thus
$$
\|\mu_{1}-\pi\|_{\ell^{2}}\leq\|\mu_{1}\|_{\ell^{2}}+\|\pi\|_{\ell^{2}}%
\lesssim\frac{1}{\sqrt{n}}+\|\pi\|_{\ell^{2}}\lesssim\frac{1}{\sqrt{n}}.
$$
We can now argue via induction. Suppose the desired statement holds for $\mu_{k}$ . Then, using the fact that $\pi D^{-1}A=\pi$ , we have
$$
\mu_{k+1}-\pi=\mu_{k}D^{-1}A-\pi=\left(\mu_{k}-\pi\right)D^{-1}A.
$$
We observe that $\mu_{k}$ and $\pi$ are probability measures, all the arising vectors always have mean value 0. Then
$$
\|\mu_{k+1}-\pi\|_{\ell^{2}}=\|\left(\mu_{k}D^{-1}A-\pi\right)\|_{\ell^{2}}.
$$
Since both $\mu_{k}$ and $\pi$ are probability distributions, we have that $\mu_{k}-\pi$ has mean value 0 and Lemma 3 applies to give
$$
\|\left(\mu_{k}-\pi\right)D^{-1}A\|_{\ell^{2}}\lesssim c_{p}\frac{\sqrt{\log{n%
}}}{\sqrt{n}}\|\mu_{k}-\pi\|_{\ell^{2}}
$$
from which the result follows. ∎
Acknowledgment. The authors are grateful for discussions with Karel Devriendt and grateful to Felix Joos, Jonathan Schrodt and Tom Stalljohann for spotting a gap in a previous version of the manuscript.
References
- [1] F. Chung, L. Linyuan, The diameter of sparse random graphs. Advances in Applied Mathematics 26.4 (2001): 257-279.
- [2] A. Desolneux, L. Moisan, and J. Morel. From gestalt theory to image analysis: a probabilistic approach. Vol. 34. Springer Science & Business Media, 2007.
- [3] P. Diaconis, L. Miclo. On quantitative convergence to quasi-stationarity. Annales de la Faculte des sciences de Toulouse: Mathematiques. Vol. 24. No. 4. 2015.
- [4] Z. Füredi and J. Komlos, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), p. 233–241.
- [5] 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.
- [6] 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
- [7] V. Klee and D. Larman, Diameters of random graphs, Canadian Journal of Mathematics 33.3 (1981): 618-640.
- [8] 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.
- [9] 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.
- [10] 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.
- [11] 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.
- [12] R. Lyons, Y. Peres, Probability on trees and networks. Cambridge University Press, 2017.
- [13] P. Mitra, Entrywise bounds for eigenvectors of random graphs. the electronic journal of combinatorics, R131 (2009).
- [14] 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.
- [15] J. Sylvester, John 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.