Faster random walk via infrequent steering

Random walks on graphs can mix slowly. To speed it up, imagine that at each step instead of choosing the neighbor at random, there is a small probability eps>0 that we can choose it. We show that in this case, at least for graphs of bounded degree, there is a way to steer the walk so that we visit every vertex in n^{1+o(1)} many steps. The key to this result is a way to decompose arbitrary graphs into small-diameter pieces. Joint work with Quentin Dubroff.