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

DOI10.1002/RSA.21101MaRDI QIDQ6074870zbMATH OpenOpenAlexWikidataFDO

Authors Luis Fredes, Jean-François Marckert

Publication date 19 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.08639

zbMATH Keywords

golf sequencesmatrix tree theoremrandom spanning tree

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

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 $pro{d}_{e=(e^{-},e^{+})insfEdges(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 )

Recommendations

• A reverse Aldous-Broder algorithm
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• Choosing a random spanning subtree: A case study
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs

Cites work

• A combinatorial approach to matrix algebra
• A reverse Aldous-Broder algorithm
• Combinatorial problems of commutation and rearrangements
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
• scientific article; zbMATH DE number 4002104 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• scientific article; zbMATH DE number 218327 (Why is no real title available?)
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

Cited in

(7)

• The Perron-Frobenius theorem -- a proof with the use of Markov chains
• A reverse Aldous-Broder algorithm
• scientific article; zbMATH DE number 3995885 (Why is no real title available?)
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Cycling in the forest with Wilson's algorithm
• Markov chains on trees: almost lower and upper directed cases
• Exact sampling of spanning trees via fast-forwarded random walks

This page was built for publication: A combinatorial proof of Aldous–Broder theorem for general Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074870)