Abstract. Generating random spanning trees

This paper describes a probabilistic algorithm that, given a connected, undirected graph G with n vertices, produces a spanning tree of G chosen uniformly at random among the spanning trees of G. The expected running time is O(n log n) per generated tree for almost all graphs, and O(n3) for the worst graphs. Previously known deterministic algorithms and much more complicated and require O(n3) time per generated tree. A Markov chain is called rapidly mixing if it gets close to the limit distribution in time polynomial in the log of the number of states. Starting from the analysis of the algorithm above we show that the Markov chain on the space of all spanning trees of a given a graph where the basic step is an edge swap is rapidly mixing. 1. Introduction. Puzzle: A particle moves on a cycle graph. At each step the particle goes from the current vertex to one of the two adjacent vertices chosen with equal probability. Clearly, the first time when the particle has visited all the vertices, it has gone over all the edges in the cycle, except one. The question is, how is the “left-out ” edge distributed, relative to the starting point? It i