Cutoff on trees is rare
Preprint
Abstract
We study the simple random walk on trees and give estimates on the mixing and relaxation time. Relying on a recent characterization by Basu, Hermon and Peres, we give geometric criteria, which are easy to verify and allow to determine whether the cutoff phenomenon occurs. We thoroughly discuss families of trees with cutoff, and show how our criteria can be used to prove the absence of cutoff for several classes of trees, including spherically symmetric trees, Galton-Watson trees of a fixed height, and sequences of random trees converging to the Brownian CRT.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Spectral gap, isoperimetry and concentration on treesScience China Mathematics, 2015
- Mixing Times are Hitting Times of Large SetsJournal of Theoretical Probability, 2013
- Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered treesThe Annals of Probability, 2012
- The CRT is the scaling limit of unordered binary treesRandom Structures & Algorithms, 2011
- Centers for Random Walks on TreesSIAM Journal on Discrete Mathematics, 2009
- Total variation cutoff in birth-and-death chainsProbability Theory and Related Fields, 2008
- On eigenfunctions of Markov processes on treesProbability Theory and Related Fields, 2007
- Weighted Hardy and Poincaré Inequalities on TreesJournal of the London Mathematical Society, 1995
- Some Inequalities for Reversible Markov ChainsJournal of the London Mathematical Society, 1982
- Generating a random permutation with random transpositionsProbability Theory and Related Fields, 1981