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 + _e=(e^-, e^+)Edges(t, r)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.