Spring 2016

Random Walk on Random Directed Graphs

Tuesday, Feb. 23, 2016 11:40 am12:25 pm

Add to Calendar


Calvin Lab

A finite Markov chain exhibits cutoff if its distance from equilibrium remains close to the initial value over a certain number of iterations and then abruptly drops to near zero 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 reversible chains. In this talk we consider the non-reversible case of random walks on sparse random directed graphs, for which even the equilibrium measure is far from being understood. We establish the cutoff phenomenon, determine its precise window and prove that the cutoff profile approaches a simple, universal shape. This is joint work with Charles Bordenave and Pietro Caputo.

PDF icon Random Walk on Random Directed Graphs914.93 KB