Speeding up random walk mixing by starting from a uniform vertex

Alberto Espuny Díaz, Patrick Morris, Guillem Perarnau +1

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 initia…