Tutte seminar - Roberto Imbuzeiro Oliveira

Late points for random walks and the fluctuations of cover times

Abstract:

How long does it take for a random walk to visit all vertices of a finite graph G? What is the distribution of this so-called cover time? And what do the last k vertices to be covered look like? Little is known about the last two questions, in spite of great interest in cover times (eg. in the CS community) since the early 90's.

The general theme of this talk is that, under certain conditions, the late stages of coverage of a large graph G look like what one sees in a large complete graph. In particular, we obtain that, after a time rescaling:

1. the law of the cover time is approximately the Gumbel law;
2. for any constant k, the last k points to be covered are essentially uniformly distributed; and
3. uncovered points at a time t0 later become covered at times that are approximatelly independent exponential random variables.

Our results apply to all examples where 1 was previously known, including tori with d≥ 3 dimensions (a very recent result by Belius). They also apply to other graphs and digraphs which are "locally recurrent" such as large-girth expanders and random regular graphs. Our techniques include new general results about the joint distribution of hitting time and of the point hit of a "nice" subset of vertices.

(Joint work with Alan Prata.)