A combinatorial proof of Aldous–Broder theorem for general Markov chains. Issue 2 (19th June 2022)

• Record Type: Journal Article
• Authors: Fredes, Luis; Marckert, Jean‐François
• Is Part Of: Random structures & algorithms. Volume 62:Issue 2(2023)
• Page Start: 430
• Page End: 449
• Publication Date: 2022-06-19
• Subjects: matrix tree theorem -- random spanning tree; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21101
• Languages: English
• ISSNs: 1042-9832

Abstract

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.