A combinatorial proof of Aldous-Broder theorem for general Markov chains

Abstract

Aldous-Broder algorithm is a famous algorithm used to sample a uniform spanning tree of any finite connected graph $G$, but it is more general: given an irreducible and reversible Markov chain $M$ on $G$ started at $r$, the tree rooted at $r$ formed by the first entrance steps in each node (different from the root) has a probability proportional to ${\prod }_{e=(e^{-},e^{+})\in \mathsf{Edges}(t,r)}{M}_{e^{-},e^{+}}$, where the edges are directed toward $r$. In this paper we give proofs of Aldous-Broder theorem in the general case, where the kernel $M$ is irreducible but not assumed to be reversible (this generalized version appeared recently in Hu, Lyons and Tang )