Cutoff for random walks on covered expander graphs

Cutoff for random walks on covered expander graphs

-
Charles Bordenave, Toulouse
Fine Hall 214

A finite ergodic Markov chain exhibits cutoff if its distance to equilibrium remains close to its initial value over a certain number of iterations and then abruptly drops to near 0 on a much shorter time scale. Originally discovered in the context of card shuffling (Aldous-Diaconis, 1986), this remarkable phenomenon is now rigorously established for many Markov chains. There is however a lack of general theory for proving this phenomenon. In this talk,  we will consider a sequence of finite Markov chains which are the images by group actions of a random walk on a non-amenable group. We will give sufficient conditions for the cutoff in terms of spectral  properties of the group actions. This is a joint work with Hubert Lacoin (IMPA).