A sharp analysis of the mixing time for random walk on rooted trees

2009/08/08 by Jason Fulman, Fulman, Jason · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.0908.1141

13 pages

arxiv created 2009/08/08 · openalex publication_date 2009/08/08 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We define an analog of Plancherel measure for the set of rooted unlabeled trees on n vertices, and a Markov chain which has this measure as its stationary distribution. Using the combinatorics of commutation relations, we show that order n² steps are necessary and suffice for convergence to the stationary distribution.

Cited by

• sl(2) Operators and Markov Processes on Branching Graphs

Related

• The Best Mixing Time for Random Walks on Trees
• The Exact Mixing Time for Trees with Fixed Diameter
• Extremal process of the local time of simple random walk on a regular tree
• Random Walks and the Meeting Time for Trees
• Sensitivity of mixing times, an example