logo AFST
Total variation cutoff in a tree
;
Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 24 (2015) no. 4, pp. 763-779.

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.

Published online : 2016-01-21
@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},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 24},
     number = {4},
     year = {2015},
     pages = {763-779},
     language = {en},
     url={afst.centre-mersenne.org/item/AFST_2015_6_24_4_763_0/}
}
Peres, Yuval; Sousi, Perla. Total variation cutoff in a tree. Annales de la Faculté des sciences de Toulouse : Mathématiques, Serie 6, Volume 24 (2015) no. 4, pp. 763-779. https://afst.centre-mersenne.org/item/AFST_2015_6_24_4_763_0/

[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 3083928 | Zbl 1297.60049

[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 3161366 | Zbl 1288.60088

[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 2550359 | Zbl 1190.60005

[4] Lancia (C.), Nardi (F. A.), and Scoppola (B.).— Entropy-driven cutoff phenomena. J. Stat. Phys., 149(1), p. 108-141 (2012). | MR 2981642 | Zbl 1263.82026

[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 2466937 | Zbl 1160.60001

[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).