Total variation cutoff in a tree

DOI10.5802/AFST.1463MaRDI QIDQ5963352zbMATH OpenOpenAlexWikidataFDO

Authors Yuval Peres, Perla Sousi

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)

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

zbMATH Keywords

treesmixing timerelaxation timesimple random walkcutoff windowtotal variation cutoff

Mathematics Subject Classification ID

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

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.

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

Cites work

• Comparison of cutoffs between lazy walks and Markovian semigroups
• Entropy-driven cutoff phenomena
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Surprise probabilities in Markov chains
• Total variation cutoff in birth-and-death chains

Cited in

(3)

• Cutoff on trees is rare
• No cutoff in spherically symmetric trees
• Surprise probabilities in Markov chains

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)