Expected hitting time estimates on finite graphs.

(Joint work with Laurent Saloff-Coste)

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

Motivation: other connections

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.

Preliminaries

Our random process of interest is an 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, relying on the fact that the torus is vertex transitive.

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:

$p(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$, trees with polynomial growth, other Harnack graphs up to rough isometries

We will use the finite version of this definition.

Main result:

(Saloff-Coste, W. 2023) If $G$ is a finite $\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/2. \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 \max \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: $$ 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), $$



When $d(x,y) = 0$, the exponential term disappears. 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. \]

When $n \geq D^\theta$, the volume term disappears and remaining exponential terms sum to a constant. When $d(x,y)^\theta \leq n \leq D^\theta$, the exponential term is bounded above by 1. 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})}\]

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.

Thanks for your attention! Questions?