Random walk and mean hitting time in a simple undirected graph

Question

Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges.

I'm trying to determine the expected running time of Wilson's algorithm for generating a random spanning tree of $G$. There, it is shown to be $O(\tau)$, where $\tau$ is the mean hitting time: $$\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), $$ where:

• $\pi$ is the stationary distribution $\pi(v)=\frac{d(v)}{2m}$,
• $u$ is an arbitrary vertex, and
• $H(u,v)$ is the hitting time (AKA access time), i.e., the expected number of steps before vertex $v$ is visited, starting from vertex $u$.

What is the general upper bound for the mean hitting time? And what is the worst case graph $G$ that maximizes mean hitting time?

---

To make my question clear, I don't require calculations or a detailed proof (although they may be useful to other people encountering this question in the future). For me personally, a citation would be sufficient.

The paper mentions another algorithm by Broder that works in expected cover time (first time when all vertices have been visited). Then it is said, that mean hitting time is always less than cover time. However it only gives an asymptotic bound of $\Theta(n)$ for most graphs (i.e., expander graphs) to contrast it with $\Theta(n \log n)$ by Broder for most graphs (with a somewhat more inclusive definition of most).

It does give an example of a graph where mean hitting time is $\Theta(n^2)$ and cover time is $\Theta(n^3)$. While this is known to be the worst case for the latter, he does not specifically say anything about the worst case of the former. This would mean that the worst case for Wilson's algorithm may fall anywhere between $O(n^2)$ and $O(n^3)$.

There are two publicly available implementations of Wilson's algorithm that I'm aware of. One is in the Boost Graph Library, while second is in graph-tool. Documentation of the former does not mention running time, while the latter states:

The typical running time for random graphs is $O(n \log n)$.

Which does not answer the question, and actually seems to be inconsistent with Wilson's paper. But I report this just in case, to save time of anybody with the same idea of consulting implementation documentation.

I had initially hoped that the worst case might be attained by a graph constructed by attaching a path to a clique, due to Lovász, where the hitting time can be as high as $\Omega(n^3)$. However, the probability of this event is about $\frac{1}{n}$ when picking vertices from stationary distribution. Consequently yielding an $O(n^2)$ bound for the mean hitting time in this graph.

A paper by Brightwell and Winkler shows that a subset of lollipop graphs maximizes the expected hitting time, reaching $4n^3/27$. Graph by Lovász is also a lollipop graph, but in this case the clique size is $\frac{2}{3} n$, rather than half. However, care must be taken not to confuse expected hitting time with mean hitting time. This result, like the previous one, refers to expected hitting time for two specific vertices chosen beforehand.

Answer 1

I have decided to ask David Wilson himself, soon thereafter got a reply:

For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the barbell graph, which consists of two cliques of size $n/3$ connected by a path of length $n/3$. I don’t know what the worst constant is. The [Brightwell-Winkler] paper looks at (expected) hitting times $H(x,y)$ started at $x$ and ending at $y$. The mean hitting time is the average of $H(x,y)$ for fixed $x$ and random choices of $y$ from the stationary distribution of a random walk. It’s a nice fact that this doesn’t depend on $x$. I learned about hitting times from the Aldous-Fill book, which is unfinished but on the web.

There is even a proof of this fact in the abovementioned book, which goes like this:

To construct a graph on $n=2n_1+n_2$ vertices, start with two complete graphs on $n_1$ vertices. Distinguish vertices $v_l \neq v_L$ in one graph ("the left bell") and vertices $v_R \neq v_r$ in the other graph ("the right bell"). Then connect the graphs via a path $v_L - w_1 - \cdots w_{n_2} - v_R $.

Then it is informally argued that it takes mean time about $n_1$ to hit $v_L$ and from there, there's chance $\frac{1}{n_1}$ to hit $w_1$, so it takes mean time about $n_1^2$ to hit $w_1$. From $w_1$ there is chance about $\frac{1}{n_2}$ to hit the right bell before returning into the left bell, so it takes mean time about $n_1^2 n_2$ to enter the right bell.

Setting $n_1 = n_2 = n/3$ gives us mean time $O(n^3)$.

Admittedly, I'm lost at the point they state:

From $w_1$ there is chance about $\frac{1}{n_2}$ to hit the right bell before returning into the left bell.

But to ease my mind, I ran a simulation of random walks on barbell graphs constructed this way, between vertices picked from the stationary distribution. Indeed, the mean hitting time fitted very nicely to a curve $\frac{(n+1)^3}{54}$.

However, comments on the informal proof are still welcome.

Answer 2

In a recent paper, we found an mn upper bound (no big O) on the expected number of "cycles popped" by Wilson's algorithm and it is tight up to constants. It doesn't directly answer the question of Wilson's algorithms' running time as the average size of popped cycles does not seem obvious. On the other hand, I don't have enough "reputation" to leave a comment ...