Postal address
Department of Theoretical Physics, Tata Institute of Fundamental Research, Homi Bhabha Road, Mumbai 400005, India.
Secretariat phones
+91-22-2278 2244 +91-22-2278 2777
+91-22-2280 4611 +91-22-2280 4610
Secretariat email
"theophys" The mailhost for DTP is


Condensed Matter and Statistical Physics Journal Club

Date: Oct 27, 2009
Title: "Rotor walks and Markov Chains"
Speaker: Tridib Sadhu
Reference: ""
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 well-chosen deterministic algorithm. One such process is rotor-router 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.