Rotor Walks and Markov Chains

Details Rotor Walks and Markov Chains Rotor Walks and Markov Chains

2009-04-28

arxiv.org/abs/0904.4507v3

Mathematics

Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Rotor Walks and Markov Chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Rotor Walks and Markov Chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rotor Walks and Markov Chains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-511015