A new proof of Aldous-Broder theorem.

Resumen:  The 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: it states that given a reversible M Markov chain on G started at r and up to the cover time, the tree rooted at r formed by the steps of successive first entrance in each node (different from the root) has a probability proportional to the product of these edges according to M, where the edges are directed toward r. In this talk I will present an extension to the non-reversible case and a new combinatorial proof of this theorem. Based on a joint work with Jean-François Marckert.

Posted on Apr 12, 2021 in Seminario Probabilidades CMM, Seminars