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.

DOI: 10.5802/afst.1463

Yuval Peres 1; Perla Sousi 2

1 Microsoft Research, Redmond, Washington, USA
2 University of Cambridge, Cambridge, UK
@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, 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: