Total variation cutoff in a tree

DOI10.5802/AFST.1463zbMATH Open1333.60089arXiv1307.2887OpenAlexW1845539321WikidataQ105584897 ScholiaQ105584897MaRDI QIDQ5963352FDOQ5963352

Perla Sousi, Yuval Peres

Publication date: 19 February 2016

Published in: Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI (Search for Journal in Brave)

Abstract: We construct a family of trees on which a lazy simple random walk exhibits total variation cutoff. The main idea behind the construction is that hitting times of large sets should be concentrated around their means. For this sequence of trees we compute the mixing time, the relaxation time and the cutoff window.

Full work available at URL: https://arxiv.org/abs/1307.2887

Recommendations

• No cutoff in spherically symmetric trees
• Characterization of cutoff for reversible Markov chains
• Characterization of cutoff for reversible Markov chains
• Comparison of cutoffs between lazy walks and Markovian semigroups
• Total variation and separation cutoffs are not equivalent and neither one implies the other

zbMATH Keywords

treesmixing timerelaxation timesimple random walkcutoff windowtotal variation cutoff

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Comparison of Cutoffs Between Lazy Walks and Markovian Semigroups
• Entropy-driven cutoff phenomena
• Total variation cutoff in birth-and-death chains
• Surprise probabilities in Markov chains

Cited In (3)

• No cutoff in spherically symmetric trees
• Surprise Probabilities in Markov Chains
• Cutoff on trees is rare

This page was built for publication: Total variation cutoff in a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963352)