Condensed Matter and Statistical Physics Journal Club
Date:  Oct 27, 2009 
Title: 
"Rotor walks and Markov Chains" 

Speaker: 
Tridib Sadhu 

Reference: 
"http://arxiv.org/abs/0904.4507" 
Abstract: 
Many problems in discrete probability theory and its applications involve probabilities of events, or expected values of random variables, that are hard to determine analytically but can be estimated using some sort of Monte Carlo simulation. In some cases, one can get good estimates of these quantities by using wellchosen deterministic algorithm. One such process is rotorrouter walk on the state space. One can show that many quantities associated with the rotor walk concentrates around their expected values for the random walk. Further more N steps of rotor walk allow one to estimate the desired probability to within error O(1/N) (unlike random walk, for which the error is O(1/sqrt(N))). In my talk I will discuss some of these examples.
