Speeding up random walk mixing by starting from a uniform vertex

Zoom Link

The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small poorly connected set significantly slows down the diffusion of the walk in the first steps of the process. The average mixing time is defined to be the mixing time starting at a uniformly random vertex and hence is not sensitive to these bottlenecks when there are few of them. We provide a general framework to show logarithmic average mixing time for random walks on graphs with few small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models whose mixing time is known to be $\Theta(\log^2 n)$. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. 

This is joint work with Alberto Espuny Díaz, Patrick Morris and Oriol Serra.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.