In September of 2004, I visited the statistics department at U.C. Berkeley and gave three lectures:
Better than random: Quasirandomness for discrete stochastic systems (presented at the Interdisciplinary Stochastic Processes Colloquium). 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 empirically using some sort of Monte Carlo simulation. In some cases, one can also get good estimates by using well-chosen deterministic simulations. When they exist, such quasirandom simulation schemes often are just as fast as random simulation, give smaller error, and give deterministic error-bounds rather than confidence-intervals. For a preview of the talk, see http://murl.microsoft.com/LectureDetails.asp?1050 or http://jamespropp.org/rotor-router-1.0. This talk is based on joint work with Ander Holroyd.
Quasirandom walk with rotor-routers (presented at the UC Berkeley Probability Seminar). Abstract: For random walk on a graph, one is frequently interested in quantities such as the expected time until a particle started at X arrives at Y, or the probability that a particle started at X arrives at Y before it arrives at Z (or arrives at Y at all without wandering off to infinity). These problems can be studied using quasirandom walk with "rotor-routers". In many cases, one can show that N stages of quasirandom walk allow one to estimate the desired probability to within error O(1/N) (unlike true random walk, for which the error is O(1/sqrt(N)) in expected magnitude). Even in cases where no rigorous results are available, rotor-router walk appears to do an extremely good job of shadowing the first-order behavior of random walk. For a preview of the talk, see http://murl.microsoft.com/LectureDetails.asp?1050 or http://jamespropp.org/rotor-router-1.0. This talk is based on joint work with Ander Holroyd.
Quasirandom growth with rotor-routers (presented at the UC Berkeley Probability Seminar). Abstract: Internal Diffusion-Limited Aggregation (IDLA) is a discrete stochastic process for growing random subsets of a graph. As time goes to infinity, one can ask for the limiting shape of the normalized IDLA blob. In one dimension, it can be shown that the error in estimating the limit-shape can be reduced from O(1/sqrt(N)) to O(1/N) if one drives the growth model using quasirandom walk with rotor-routers instead of true random walk. Very little is known in higher dimensions, but the agreement between quasirandom growth and the first-order law for random growth is striking: see http://jamespropp.org/million.gif. This talk is based on joint work with Lionel Levine.