  The rotor walk is a derandomized version of the random walk on a graph. On
successive visits to any given vertex, the walker is routed to each of the
neighboring vertices in some fixed cyclic order, rather than to a random
sequence of neighbors. The concept generalizes naturally to Markov chains on a
countable state space. Subject to general conditions, we prove that many
natural quantities associated with the rotor walk (including normalized hitting
frequencies, hitting times and occupation frequencies) concentrate around their
expected values for the random walk. Furthermore, the concentration is stronger
than that associated with repeated runs of the random walk, with discrepancy at
most C/n after n runs (for an explicit constant C), rather than c/sqrt n.
