Sensitivity of mixing times

Abstract

In this note, we demonstrate an instance of bounded-degree graphs of size $n$, for which the total variation mixing time for the random walk is decreased by a factor of $\log n/\log \log n$ if we multiply the edge-conductances by bounded factors in a certain way.

7pages, 2 figures

References in corpus (1)

• Critical random graphs: Diameter and mixing time