0

Suppose that we want to apply Wilson's algorithm on $\mathbb{Z}^d$, by taking a root $v_0$ and labelling the vertices of $\mathbb{Z}^d = \{ v_1 ,\ldots, v_n ,\ldots \}$ arbitrarily (using a bijection between $\mathbb{N} $ and $\mathbb{Z}^d$), thus defining (if the algorithm works) a growing sequence of trees $ \{ v_0\} = T_0 \subset T_1 \subset \ldots $. Will the algorithm work and will any finite box be included in some $T_k$ tree for large enough $k$ ?

I recall that Wilson's algorithm is the following. Labelling vertices of a graph $G$ arbitrarily an choosing a root $v_0$ we construct a growing sequence of trees such that $T_{i+1} \setminus T_i $ is a loop-erased random walk from an arbitrary vertex $x_i \in G\setminus T_i $ and stopped upon hitting $T_i$ and stopped when we get a spanning tree.

In $ \mathbb{Z} $ I think it works because if wlog $v_0=0$ and $x_1$ is wlog positive then since we run a LERW (loop-erased random walk) then eventually we reach $x_0$ since random walk on $\mathbb{Z} $ are recurrent. I think same argument works on $\mathbb{Z}^2$, but actually I'm not sure. However on $\mathbb{Z}^{d} $ with $d \geq 3$ I think that the algorithm doesn't work since random walks on $ \mathbb{Z}^d $ are transient so there is a probability strictly bigger than zero that the random walk never visits $v_0$ and there is a probability strictly than zero that we never create a loop, so I think that already at the first step, starting from $v_1$ and trying to construct $T_1$ it is possible that the algorithm run forever without reaching $T_0$. But for $\mathbb{Z}$ or $\mathbb{Z}^2$ I can't show or disprove that the algorithm work (in the sense that any box is included in some $T_k$ for large enough $k$).

3m0o
  • 783
  • 1
    The probability that we never create a loop is zero. Every pair of steps has a non-zero probability to create a loop, and the probability that none of them ever do is zero. (That doesn't invalidate your entire argument, it's just a small correction about that one statement.) – joriki Jan 18 '23 at 21:48
  • You are right! What I wanted to say is that there is a probability strictly bigger than zero that the random walks never return to the starting point, and hence a strictly positive probability that the random walks never visit the root. – 3m0o Jan 19 '23 at 12:27

0 Answers0