A reverse Aldous-Broder algorithm

DOI10.1214/20-AIHP1101zbMath1468.05281arXiv1907.10196OpenAlexW3163390376MaRDI QIDQ2041828

Pengfei Tang, Russell Lyons, Yiping Hu

Publication date: 23 July 2021

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

zbMATH Keywords

BEST theoremspanning treesloop-erased random walk

Mathematics Subject Classification ID

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

Related Items

A combinatorial proof of Aldous–Broder theorem for general Markov chains ⋮ Almost triangular Markov chains on \(\mathbb{N}\) ⋮ Models of random subtrees of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Urn models for Markov exchangeability
• Choosing a spanning tree for the integer lattice uniformly
• Interlacements and the wired uniform spanning forest
• Uniform spanning forests
• Probability on Trees and Networks
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Statistical Methods in Markov Chains
• A connective constant for loop-erased self-avoiding random walk
• How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph

This page was built for publication: A reverse Aldous-Broder algorithm