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$.
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?