Probability Seminar: Anna Ben-Hamou

  • Date: 10/14/2015
  • Time: 15:00
Anna Ben-Hamou, Université Paris Diderot

University of British Columbia


Cutoff for non-backtracking random walks on sparse random graphs


A finite ergodic Markov chain exhibits cutoff if its distance to stationarity remains close to 1 over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Here we consider non-backtracking random walks on random graphs with a given degree sequence. Under a general sparsity condition, we establish the cutoff phenomenon, determine its precise window, and prove that the cutoff profile approaches a remarkably simple, universal shape. This is a joint work with Justin Salez (Paris-Diderot).

Other Information: 

Location: ESB 2012