Random walk and mean hitting time in a simple undirected graph
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.