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

2021/02/16 by Luis Fredes, Fredes, Luis, Jean‐François Marckert +1 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Markov Chains and Monte Carlo Methods #Advanced Combinatorial Mathematics

paper · pdf · doi:10.48550/arxiv.2102.08639

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 ∏_e=(e^-,e⁺)∈ \sf 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 )

Citations

• A combinatorial approach to matrix algebra

Cited by

• A combinatorial perspective on the Kemeny constant and more
• Almost triangular Markov chains on ℕ

Related

• A reverse Aldous/Broder algorithm
• Scaling limit of the Aldous-Broder chain on regular graphs: the transient regime
• Projections of the Aldous chain on binary trees: Intertwining and\n consistency
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Rayleigh processes, real trees, and root growth with re-grafting