Cutoff on Trees is Rare

Nina Gantert, Evita Nestoridi, Dominik Schmid

Research output: Contribution to journalArticlepeer-review

Abstract

We study the simple random walk on trees and give estimates on the mixing and relaxation times. Relying on a seminal result by Basu, Hermon and Peres characterizing cutoff on trees, we give geometric criteria that are easy to verify and allow to determine whether the cutoff phenomenon occurs. We provide a general characterization of 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 continuum random tree.

Original languageEnglish (US)
Pages (from-to)1417-1444
Number of pages28
JournalJournal of Theoretical Probability
Volume37
Issue number2
DOIs
StatePublished - Jun 2024
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • General Mathematics
  • Statistics, Probability and Uncertainty

Keywords

  • Cutoff phenomenon
  • Mixing time
  • Random walk
  • Spectral gap

Fingerprint

Dive into the research topics of 'Cutoff on Trees is Rare'. Together they form a unique fingerprint.

Cite this