Note: Random-to-front shuffles on trees

2009/01/27 by Anders Björner, Björner, Anders
Mathematics · #05E99 #60C05 #60J10 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05E99 #msc:60C05 #msc:60J10

paper · pdf · doi:10.48550/arxiv.0901.4278

6 pages, 4 figures; to appear in Electronic Communications in Probability

arxiv created 2009/01/27 · arxiv updated 2009/12/01

Abstract

A Markov chain is considered whose states are orderings of an underlying fixed tree and whose transitions are local "random-to-front" reorderings, driven by a probability distribution on subsets of the leaves. The eigenvalues of the transition matrix are determined using Brown's theory of random walk on semigroups.

Related

• A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle
• A sharp analysis of the mixing time for random walk on rooted trees
• Random spanning forests, Markov matrix spectra and well distributed points
• A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle
• Top to random shuffles on colored permutations