Faster random walks via infrequent steering

Boris Bukh, Quentin Dubroff

Random walks on graphs can be slow. To speed them up, imagine that at each step instead of choosing the neighbor at random, there is a small probability $\epsilon >0$ that we can…