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 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. |