4 papers
Cutoff for permuted Markov chains
Anna Ben-Hamou, Yuval Peres
Let be a bistochastic matrix of size , and let be a permutation matrix of size . In this paper, we are interested in the mixing time of the Markov chain whose transit…
A threshold for cutoff in two-community random graphs
Anna Ben-Hamou
In this paper, we are interested in the impact of communities on the mixing behavior of the non-backtracking random walk. We consider sequences of sparse random graphs of size …
Weighted sampling without replacement
Anna Ben-Hamou, Yuval Peres, Justin Salez
Comparing concentration properties of uniform sampling with and without replacement has a long history which can be traced back to the pioneer work of Hoeffding (1963). The goal of…
Cutoff for non-backtracking random walks on sparse random graphs
Anna Ben-Hamou, Justin Salez
A finite ergodic Markov chain is said to exhibit cutoff if its distance to stationarity remains close to 1 over a certain number of iterations and then abruptly drops to near 0 on…