A combinatorial proof of Aldous–Broder theorem for general Markov chains. Issue 2 (19th June 2022) - Fredes, Luis; Marckert, Jean‐François
Abstract: Aldous–Broder algorithm is a famous algorithm used to sample a uniform spanning tree of any finite connected graph G $$ G $$, but it is more general: given an irreducible and reversible Markov chain M $$ M $$ on G $$ G $$ started at r $$ r $$, the tree rooted at r $$ r $$ formed by the first entrance steps in each node (different from the root) has a probability proportional to ∏ e = ( e −, e + ) ∈ Edges ( t, r ) M e −, e + $$ {\prod}_{e=\left({e}^{-}, {e}^{+}\right)\in \mathsf{Edges}\left(t, r\right)}{M}_{e^{-}, {e}^{+}} $$, where the edges are directed toward r $$ r $$ . In this article we give proofs of Aldous–Broder theorem in the general case, where the kernel M $$ M $$ is irreducible but not assumed to be reversible (this generalized version appeared recently in Hu, Lyons, and Tang [5]). We provide two new proofs: an adaptation of the classical argument, which is purely probabilistic, and a new proof based on combinatorial arguments. On the way we introduce a new combinatorial object that we call the golf sequences.