Displaying similar documents to “Mixing time for a random walk on rooted trees.”

Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs

Johannes Fehrenbach, Ludger Rüschendorf (2005)

Applicationes Mathematicae

Similarity:

We analyse a natural edge exchange Markov chain on the set of spanning trees of an undirected graph by the method of multicommodity flows. The analysis is then refined to obtain a canonical path analysis. The construction of the flow and of the canonical paths is based on related path constructions in a paper of Cordovil and Moreira (1993) on block matroids. The estimates of the congestion measure imply a polynomial bound on the mixing time. The canonical paths for spanning trees also...

Exponential inequalities for VLMC empirical trees

Antonio Galves, Véronique Maume-Deschamps, Bernard Schmitt (2008)

ESAIM: Probability and Statistics

Similarity:

A seminal paper by Rissanen, published in 1983, introduced the class of Variable Length Markov Chains and the algorithm Context which estimates the probabilistic tree generating the chain. Even if the subject was recently considered in several papers, the central question of the rate of convergence of the algorithm remained open. This is the question we address here. We provide an exponential upper bound for the probability of incorrect estimation of the probabilistic tree,...