Mixing times of random walks on dynamic configuration models

Luca Avena, Hakan Guldas, Remco van der Hofstad, Frank den Hollander

Published 2016-06-24Version 1

The mixing time of a simple random walk on a random graph generated according to the configuration model is known to be of order $\log n$ when $n$ is the number of vertices. In this paper we investigate what happens when the random graph becomes dynamic, namely, at each unit of time a fraction $\alpha_n$ of the edges is randomly relocated. For degree distributions that converge and have a second moment that is bounded in $n$, we show that the mixing time is of order $1/\sqrt{\alpha_n}$, provided $\lim_{n\to\infty} \alpha_n(\log n)^2=\infty$. We identify the sharp asymptotics of the mixing time when we additionally require that $\lim_{n\to\infty} \alpha_n=0$, and relate the relevant proportionality constant to the average probability of escape from the root by a simple random walk on an augmented Galton-Watson tree which is obtained by taking a Galton-Watson tree whose offspring distribution is the size-biased version of the limiting degree distribution and attaching to its root another Galton-Watson tree with the same offspring distribution. Our proofs are based on a randomised stopping time argument in combination with coupling estimates.