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.
On construit une famille d’arbres sur laquelle la marche aléatoire paresseuse présente un phénomène de transition abrupte à l’équilibre au sens de la variation totale. L’idée principale de la construction est le fait que les temps d’atteinte de grands sous-ensembles doivent se concentrer autour de leurs moyennes. Pour cette famille d’arbres, nous calculons le temps de mélange, le temps de relaxation et la fenêtre de transition abrupte.
@article{AFST_2015_6_24_4_763_0,
author = {Yuval Peres and Perla Sousi},
title = {Total variation cutoff in a tree},
journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
pages = {763--779},
publisher = {Universit\'e Paul Sabatier, Institut de Math\'ematiques},
address = {Toulouse},
volume = {Ser. 6, 24},
number = {4},
year = {2015},
doi = {10.5802/afst.1463},
language = {en},
url = {https://afst.centre-mersenne.org/articles/10.5802/afst.1463/}
}
TY - JOUR AU - Yuval Peres AU - Perla Sousi TI - Total variation cutoff in a tree JO - Annales de la Faculté des sciences de Toulouse : Mathématiques PY - 2015 SP - 763 EP - 779 VL - 24 IS - 4 PB - Université Paul Sabatier, Institut de Mathématiques PP - Toulouse UR - https://afst.centre-mersenne.org/articles/10.5802/afst.1463/ DO - 10.5802/afst.1463 LA - en ID - AFST_2015_6_24_4_763_0 ER -
%0 Journal Article %A Yuval Peres %A Perla Sousi %T Total variation cutoff in a tree %J Annales de la Faculté des sciences de Toulouse : Mathématiques %D 2015 %P 763-779 %V 24 %N 4 %I Université Paul Sabatier, Institut de Mathématiques %C Toulouse %U https://afst.centre-mersenne.org/articles/10.5802/afst.1463/ %R 10.5802/afst.1463 %G en %F AFST_2015_6_24_4_763_0
Yuval Peres; Perla Sousi. Total variation cutoff in a tree. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Numéro Spécial : Conférence “Talking Across Fields” du 24 au 28 mars 2014 à l’Institut de Mathématiques de Toulouse, Volume 24 (2015) no. 4, pp. 763-779. doi : 10.5802/afst.1463. https://afst.centre-mersenne.org/articles/10.5802/afst.1463/
[1] Chen (G.-Y.) and Saloff-Coste (L.).— On the mixing time and spectral gap for birth and death chains, 2013. arXiv:1304.4346. | MR | Zbl
[2] Chen (G.-Y.) and Saloff-Coste (L.).— Comparison of cutoffs between lazy walks and Markovian semigroups. J. Appl. Probab., 50(4), p. 943-959 (2013). | MR | Zbl
[3] Ding (J.), Lubetzky (E.), and Peres (Y.).— Total variation cutoff in birth-and-death chains. Probab. Theory Related Fields, 146(1-2), p. 61-85 (2010). | MR | Zbl
[4] Lancia (C.), Nardi (F. A.), and Scoppola (B.).— Entropy-driven cutoff phenomena. J. Stat. Phys., 149(1), p. 108-141 (2012). | MR | Zbl
[5] Levin (D. A.), Peres (Y.), and Wilmer (E. L.).— Markov chains and mixing times. American Mathematical Society, Providence, RI (2009). With a chapter by James G. Propp and David B. Wilson. | MR | Zbl
[6] Norris (J.), Peres (Y.), and Zhai (A.).— Surprise probabilities in Markov chains. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, p. 1759-1773 (2015).
[7] Peres (Y.) and Sousi (P.).— Mixing times are hitting times of large sets. Journal of Theoretical Probability, p. 1-32 (2013).
Cited by Sources: