<p>In a recent <a href="https://arxiv.org/pdf/1611.01647v1.pdf" rel="nofollow noreferrer">paper</a>, 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 ...</p>

CC BY-SA 3.0
2016-11-26T20:55:55.700Z
2016-11-26T20:55:55.700Z
Heng Guo
<p>I have decided to ask David Wilson himself, soon thereafter got a reply:</p>

<blockquote>
  <p>For undirected graphs on $n$ vertices, the worst case mean hitting time is $\Theta(n^3)$. The example is the <a href="http://mathworld.wolfram.com/BarbellGraph.html" rel="noreferrer">barbell graph</a>, 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 <a href="https://www.stat.berkeley.edu/~aldous/RWG/book.html" rel="noreferrer" title="Reversible Markov Chains and Random Walks on Graphs">Aldous-Fill book</a>, which is unfinished but on the web.</p>
</blockquote>

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

<p>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 $.</p>

<p>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.</p>

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

<p>Admittedly, I'm lost at the point they state:</p>

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

<p>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}$.</p>

<p>However, comments on the informal proof are still welcome.</p>

CC BY-SA 3.0
2015-10-20T16:40:40.220Z
2015-10-24T09:19:17.500Z
2015-10-24T09:19:17.500Z
arekolek
<p>Let $G=(V,E)$ be a simple undirected graph on $n$ vertices and $m$ edges.</p>

<p>I'm trying to determine the expected running time of <a href="http://www.cs.cmu.edu/~15859n/RelatedWork/RandomTrees-Wilson.pdf" rel="nofollow noreferrer" title="David Wilson. &quot;Generating random spanning trees more quickly than the cover time.&quot; (1996)">Wilson's algorithm</a> for generating a random spanning tree of $G$. There, it is shown to be $O(\tau)$, where $\tau$ is the <em>mean hitting time</em>: $$\tau = \sum_{v \in V} \pi(v) \cdot H(u, v), $$ where:</p>

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

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

<hr>

<p>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.</p>

<p>The paper mentions another <a href="https://www.cs.cmu.edu/~15859n/RelatedWork/Broder-GenRanSpanningTrees.pdf" rel="nofollow noreferrer" title="Andrei Broder. &quot;Generating random spanning trees.&quot; (1989)">algorithm by Broder</a> that works in expected <em>cover time</em> (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 <em>most graphs</em> (i.e., <em>expander graphs</em>) to contrast it with $\Theta(n \log n)$ by Broder for most graphs (with a somewhat more inclusive definition of <em>most</em>).</p>

<p>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)$.</p>

<p>There are two publicly available implementations of Wilson's algorithm that I'm aware of. One is in the <a href="http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/random_spanning_tree.html" rel="nofollow noreferrer">Boost Graph Library</a>, while second is in <a href="https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.random_spanning_tree" rel="nofollow noreferrer">graph-tool</a>. Documentation of the former does not mention running time, while the latter states:</p>

<blockquote>
  <p>The typical running time for random graphs is $O(n \log n)$.</p>
</blockquote>

<p>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.</p>

<p>I had initially hoped that the worst case might be attained by a graph constructed by attaching a path to a clique, due to <a href="http://www.cs.elte.hu/~lovasz/erdos.pdf" rel="nofollow noreferrer" title="László Lovász. &quot;Random walks on graphs: A survey.&quot; (1993): p. 7">Lovász</a>, 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.</p>

<p>A paper by <a href="https://math.dartmouth.edu/~pw/papers/maxhit.pdf" rel="nofollow noreferrer" title="Graham Brightwell and Peter Winkler. &quot;Maximum hitting time for random walks on graphs.&quot; (1990)">Brightwell and Winkler</a> shows that a subset of <a href="http://mathworld.wolfram.com/LollipopGraph.html" rel="nofollow noreferrer">lollipop graphs</a> 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.</p>

CC BY-SA 3.0
2015-10-21T10:28:05.003Z
Thanks for spotting this error in graph-tool's documentation! Indeed for typical random graphs the mean hitting time is $O(n)$ (see e.g. http://arxiv.org/abs/1003.1266), not $O(n \log n)$. This will be corrected in the next version. (Note also that graph-tool uses the Boost Graph Library underneath, so they are not really distinct implementations.)
Tiago Peixoto
CC BY-SA 3.0
2015-10-21T11:31:59.623Z
@Tiago I'm happy to contribute! Thank you for your comment. You may also be interested in mentioning expected time in the worst case (however unlikely), since I've now updated my answer with a reply from David Wilson.
arekolek
<graph-theory><graph-algorithms><co.combinatorics><random-walks><analysis-of-algorithms>
Random walk and mean hitting time in a simple undirected graph
arekolek
# Random walk and mean hitting time in a simple undirected graph

(Asked by: username_0 on 2015-10-18)

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](http://www.cs.cmu.edu/~15859n/RelatedWork/RandomTrees-Wilson.pdf "David Wilson. ") 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](https://www.cs.cmu.edu/~15859n/RelatedWork/Broder-GenRanSpanningTrees.pdf "Andrei 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](http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/random_spanning_tree.html), while second is in [graph-tool](https://graph-tool.skewed.de/static/doc/topology.html#graph_tool.topology.random_spanning_tree). 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](http://www.cs.elte.hu/~lovasz/erdos.pdf "László 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](https://math.dartmouth.edu/~pw/papers/maxhit.pdf "Graham Brightwell and Peter Winkler. ") shows that a subset of [lollipop graphs](http://mathworld.wolfram.com/LollipopGraph.html) 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.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, random-walks, analysis-of-algorithms
> **Comments:**
> **username_1**: Thanks for spotting this error in graph-tool's documentation! Indeed for typical random graphs the mean hitting time is $O(n)$ (see e.g. http://arxiv.org/abs/1003.1266), not $O(n \log n)$. This will be corrected in the next version. (Note also that graph-tool uses the Boost Graph Library underneath, so they are not really distinct implementations.)  
> **username_0**: @Tiago I'm happy to contribute! Thank you for your comment. You may also be interested in mentioning expected time in the worst case (however unlikely), since I've now updated my answer with a reply from David Wilson.  

---

## 2 answers

### Answer by username_0 on 2015-10-20. Score: 11 | Accepted answer

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](http://mathworld.wolfram.com/BarbellGraph.html), 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](https://www.stat.berkeley.edu/~aldous/RWG/book.html "Reversible Markov Chains and Random Walks on Graphs"), 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 by username_2 on 2016-11-26. Score: 3

In a recent [paper](https://arxiv.org/pdf/1611.01647v1.pdf), 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 ...


---

