Since the pioneering work of Diaconis and Shahshahani, much research has been devoted to the study of the cutoff phenomenon, which describes how a random walk on a finite graph reaches its equilibrium distribution over a dramatically short period of time. However, much less is known about how a random walk behaves before it has reached this equilibrium distribution. The purpose of this talk is to study aspects of this question, with an emphasis on the way a random walk gets away from its starting point. In some interesting cases, the growth of the distance exhibits a phase transition from linear to sublinear behaviour. In other examples, there are different regimes with different scalings but no phase transition. While we do not have a theory at the moment, I will discuss some results which relate this phenomenon to the local geometry of the graph (as perceived by a random walker) and state some conjectures.
Partly joint with Rick Durrett.
view more