We provide new upper bounds for mixing times of general finite Markov chains. We use these bounds to show that the total variation mixing time is robust under rough isometry for bounded degree graphs that are roughly isometric to trees.
However, a construction of Ding and Peres @cite_10 shows that cannot hold in general if the underlying graph is not a tree, even if it has bounded degree. The message that we take from this is that the total variation mixing time is geometrically robust in general. One of the main aims of this article is to show that there is robustness amongst a wider class than just trees: indeed, holds if the graph has bounded degree and is roughly isometric to a tree. We will explain Ding and Peres' construction in more detail in Section .
@cite_10
2063224062
In this note, we demonstrate an instance of bounded-degree graphs of size @math , for which the total variation mixing time for the random walk is decreased by a factor of @math if we multiply the edge-conductances by bounded factors in a certain way.