Expected hitting time estimates on finite graphs.

(Joint work with Laurent Saloff-Coste)

Yuwen Wang
$\global\def \R{\mathbb R}$ $\global\def \E{\mathbb E}$


Hitting times are of interest in many probability-adjacent fields. Here are just a few examples:

  • economics & computer science: Understanding the running times of explore-exploit processes. If the explore process is a random walk, how long would it take to find somewhere we want to exploit?
  • physics: (Doyle, Snell 1984) Associate the random walk with an electric network: if we imagine the path taken by a single electron, then conductance ~ transition probability.
    There are many papers written about estimating the effective resistances $\mathcal R (x \leftrightarrow y)$ on various graphs (frequently referred to as resistance problems).
  • probability: Recent work (Dautenhahn, Saloff-Coste 2023) studies random walks on graphs that a "glued" together.
    Here, it is important to know the hitting probabilities of where the graphs are glued.


Our random process of interest is a aperiodic, irreducible, and reversible random walk, $\{X_n\}_{n \geq 0},$ with transition probabilities $K$:

$K(x,y) = \mathbb P \left(X_{n+1} = y | X_n = x\right).$

Under these assumptions, the random walks converges to a unique stationary measure $\pi$.

We are interested in the expected hitting time $H(a,b) = \mathbb E_a[\tau_b] = \mathbb E \left[\tau_b| X_0=a \right]$, where

$\tau_b = \min\{n\geq 0: X_n =b\}.$

Note that laziness (which implies aperiodicity) only contributes to a constant slow-down factor to $H(a,b).$

Related works:

(J. Cox 1989) Coalescing Random Walks and Voter Model Consensus Times on the Torus.

For $G = \Z_N^d$ and $a,b \in G$ such that $d(a,b)$$ \asymp N$, we have the estimates

$H(a,b)=\mathbb E_a[\tau_{b}] \asymp \begin{cases} N^2 &\text{if } d=1 \\ N^2 \log N &\text{if } d=2 \\ N^d &\text{if } d \geq 3. \end{cases}$

$d(a,b)$ $=$ the graph distance between $a$ and $b$.

Proof in Cox '89 requires very good estimates for the eigenvectors and eigenvalues of $K$.
Markov Chains and Mixing Times (Levin, Peres 2017) provide a proof using effective resistance of the corresponding electric network.

What if we make small pertubations to the transition probabilites or to the graph?

What is the heat kernel?

In $\R^d$, the heat kernel is a fundamental object that is both the transition density of Brownian motion and the fundamental solution of the heat equation.

For example, if $\{B_t\}_{t\geq 0}$ by a Brownian motion in $\R$ starting at $0$, then the random variable $B_t$ is Gaussian with variance $t$.

As the fundamental solution of the heat equation:

$k(t, x, y)=\frac{1}{\sqrt{4 \pi t}} \exp \left(-\frac{|x-y|^2}{4 t}\right).$

With $y=0$, this is just the formula for a Gaussian with mean zero and variance $2 t$.

Heat kernels and $\theta$-Harnack graphs

(Grigor'yan, Saloff-Coste, Coulhon, Delmott, Barlow, etc.)

These "lattice-like" graphs are those on which we have double-sided Gaussian bounds: $$ k^n(x,y) = \frac{K^n(x,y)}{\pi(y)} \asymp \frac{1}{V\left(x, n^{1/\theta}\right)} \exp \left(- \left( \frac{d(x, y)^\theta}{n}\right)^{\frac{1}{\theta-1}}\right), $$ for $\theta \geq 2$ and $V(x,r) = \sum_{y \in B(x,r)} \pi(y)$.

Non-Examples: Expanders and other 'fast-mixing' graphs, Cayley graphs of $S_n$ wrt transpositions

Examples: $\Z^d$, Cayley graphs of nilpotent groups, fractal graphs, infinite clusters of percolation in $\mathbb Z^d$, other Harnack graphs up to rough isometries
For more (Barlow 2017) Random Walks and Heat Kernels on Graphs

Main result:

(Saloff-Coste, W. 2023) If $G$ is a $\theta$-Harnack graph and $d(a,b) \asymp$ $D$, $$H(a,b) \asymp \sum_{n= 0}^{2D^\theta} \frac{1}{V(b,n^{1/\theta})} $$
  • $\theta$ is the walk-dimension of the graph
  • $D$ is the diameter of the graph
  • $V(x,r) = \sum_{y \in B(x,r)} \pi(y)$, where $B(x,r)$ is the ball of radius $r$ centered at $x$

For lazy simple random walk on a regular graphs, $$H(a,b) \asymp |G| \sum\limits_{n=0}^{2D^\theta} \frac{1}{\#B(b,n^{1/\theta})}.$$

Example: Rectangular torus

Consider a rectangular $2$-dimensional torus, $G = \Z_a \times \Z_b$, where $a \geq b$.
This is a $2$-Harnack graph. Let $x,y \in G$ be such that $d(x,y) \asymp D$.

$\# B(x,r) \asymp \begin{cases} r^2 &\text{if } r \leq b/2 \\ b^2 + b(r-b) &\text{if } b/2 \leq r \leq a. \end{cases}$

\[ \begin{align*} H(x,y) &\asymp |G| \sum\limits_{n=0}^{2D^2} \frac{1}{\#B(y,n^{1/2})} &\asymp ab \left( \sum_{n=1}^{b^2} \frac{1}{n} + \frac{1}{b} (a-b) + \text{smaller terms}\right) \end{align*} \]

Example: Rectangular torus

Consider a rectangular $2$-dimensional torus, $G = \Z_a \times \Z_b$, where $a \geq b$.
Let $x,y \in G$ be such that $d(x,y) \asymp D$. We computed that for the simple random walk:

$H(x,y) \asymp ab \left(\log(b) + \frac 1 b (a-b)\right) \asymp \max( a b \log b, a^2).$

Recall from (Cox '89) for $\Z_N$ and $\Z_N^2$, we know \[ H(x,y) \asymp \begin{cases} N^2 &\text{if } d=1 \\ N^2 \log N &\text{if } d=2 \end{cases}\]

In general: $N$-torus with uneven side lengths

Consider a simple random walk on the torus $$\Z_{a_1} \times \Z_{a_2} \times \cdots \times \Z_{a_N},$$ where $1 \leq a_1 \leq a_2 \leq \cdots \leq a_N.$ For two points $x,y$ such that $d(x,y) \asymp a_N$, $$H(x,y) \asymp_N \left\{ \prod_{i=1}^N a_i, a_N a_{N-1} \log \left(\frac{a_{N-1}}{a_{N-2}}\right), a_N^2\right\}.$$

Example: Birth-death chains

The state space is $\{0,1,\dotsc,N\}$ and transition probabilities can be specified by the information $\{(p_k, r_k, q_k)\}_{k=0}^N$. Consider a chain such that $\pi(k) \asymp (1 + k)^\alpha$.

With a fixed $\pi$, it is straightforward to reverse engineer the transition probabilities so that the chain is reversible and converges to $\pi$. In our case, we expect $p_k$'s to be bigger than $q_k$'s.
\[ H(0,N) \asymp N^2 \]
\[ H(N,0) \asymp \begin{cases} N^{\alpha+1} &\text{if $\alpha>1$},\\ N^2 \log N &\text{if $\alpha = 1$},\\ N^2 &\text{if $0\le \alpha<1$}. \end{cases} \]
Note that $H(x,y)$ is not symmetric when $\alpha \geq 1$.

Example: Fractal graphs (Sierpinski Gasket)

In the work of (Barlow, Coulhon, Kumagai 2005), the authors show that a large class of fractal graphs is $\theta$-Harnack, with $\theta$ being the walk dimension of the fractal.
For the Sierpinski graph, the diameter is $2^k$, the walk dimension is $\theta=\frac{\log 5}{\log 2}$ and \[ \# B(x,r) \asymp r^\alpha, \qquad \alpha = \log 3 /\log 2. \]
\[ H(x,y) \asymp |G| \sum_{n=0}^{2 (2^k)^\theta} \frac{1}{n^{\alpha/\theta}} \asymp 3^k \sum_{n = 1}^{2^{k \theta}} n ^{-\frac{\log 3}{\log 5}} \asymp 5^k = D^\theta \]

In general, for Ahlfors-regular graphs

These are graphs where $\#B(y,r) \asymp r^\alpha$, which implies that $|G| \asymp D^\alpha$. Using our theorem, we have that for $x,y$ such that $d(x,y) \asymp D$, $$H(x,y) \asymp \begin{cases} D^{\alpha} &\text{if $\alpha> \theta$},\\ D^\theta \log D &\text{if $\alpha = \theta$},\\ D^\theta &\text{if $0\le \alpha<\theta$}. \end{cases}$$ In the context of $\theta$-Harnack graphs, this behavior is analogous to the transition in $\Z^d$ from recurrent to barely recurrent to transient.

The behavior at the transition can be more complex!

Consider the subgraph of $\Z^3$ enclosed by this graph:
Then phase transition from "recurrent" to "transient" occurs at $\alpha = 1/2$.
Fix $\alpha = 1/2$ and $\beta > 0$. The points $o = (0,0,0)$ and $p = (N,0,0)$ are roughly diameter apart. $$H(p,o) \asymp \sum_{n=0}^{N} \frac{1}{V(o,\sqrt{n})} \asymp \begin{cases} N^2(\log N)^{2\beta} &\text{if } \beta \in (1/2,+\infty) \\ N^{2} (\log N)(\log\log N) &\text{if } \beta = 1/2 \\ N^{2} \log N &\text{if } \beta \in (-\infty, 1/2). \end{cases} $$ In general, $H(x,y)$ can involve arbitrary slowly varying functions.

Proof sketch

The (normalized) discrete Green's function is a function $\mathcal G: G \times G \to \R$, where \[ \mathcal G (x,y) = \sum_{n = 0}^\infty (k^n(x,y) - 1), \] and $k^n(x,y) = K^n(x,y)/\pi(y)$.

Main Lemma: For all $x, y \in G$, \[H(x,y) = \mathcal G (y,y) - \mathcal G(x,y)\]

We first obtain bounds on the discrete Green's function using heat kernel bounds:

  • For all $x,y \in V$, \[|\mathcal G(x,y)| \lesssim \sum_{d(x,y)^\theta \leq n \leq 2D^\theta} \frac{C}{V(x,n^{1/\theta})}\]
  • There exists $C_1, C_2 > 0$ such that for all $x \in G$, \[ \mathcal G(x,x) \geq C_1 \sum_{0 \leq n \leq 2D^\theta} \frac{1}{V(x,n^{1/\theta})} - C_2 D^\theta. \]

These bounds with the Main Lemma, is almost what we need!
The last ingredient is a lower bound on $H(x,y)$: $H(x,y) \gtrsim D^\theta$ which we obtain by using exit time estimates.

What's next?

  • What about when $d(a,b) $ is not of order $D$? Currently, we believe that for "transient graphs", i.e. $$ \frac{1}{\pi(b)} \asymp \sum_{n= 0}^{2D^\theta} \frac{1}{V(b,n^{1/\theta})}. $$ Then, $H(a,b) \asymp \frac{1}{\pi(b)}$. What about for "recurrent" graphs?
  • Can these techniques also be useful for studying cover times?