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**^{2}. Let *p*
be the probability that a random walk in **Z**^{2} 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**^{2} 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.