“Rotor walks and Markov chains”: a talk presented on April 7, 2009 at the MIT Probability Seminar, reporting work by Alexander Holroyd and James Propp described in their article-in-progress of the same name.

Abstract: For any locally finite Markov chain one can construct deterministic “rotor-router” analogues. Such an analogue typically has many of the same properties as the random process it mimics but is more sharply concentrated around its average-case behavior. I will discuss the general theory of derandomization of Markov chains via rotor-routers, as well as the particular example of walk in Z². Let p be the probability that a random walk in Z² that walks from source vertex (0,0) until it hits the finite target set B stops at a particular vertex b in B. If one performs N successive runs of a suitable rotor-router walk in Z² from (0,0) to B, the number of runs that stop at b is Np plus or minus O(log n). This is joint work with Ander Holroyd.

Slides from the talk are available, as is the paper on which the talk is based.