# Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

### Rotor-routing, smoothing kernels, and reduction of variance: breaking the O(1/n) barrier

**Mathematical Physics & Probability**

Speaker: | James Propp, UMass Lowell (currently visiting MSRI and UC Berkeley) |

Location: | 1147 MSB |

Start time: | Wed, Mar 14 2012, 4:10PM |

If a random variableXis easier to simulate than to analyze, one way to estimate its expected valueE(X)is to generatensamples that are distributed according to the law ofXand take their average. If the samples are independent, then (assumingXhas finite variance) the estimate will have typical error O(1/n^{1/2}). But often one can do better by introducing appropriate forms of negative dependence. In the toy context of simulating Markov chains to estimate their absorption probabilities, I'll describe a scheme that uses maximally anticorrelated identically distributed Bernoulli random variables (aka rotor routers) and has typical error O(1/n). This might seem to be optimal, and indeed one cannot expect the average (X_{1}+...+X_{n})/nto differ from its expected valueE(X)by less than O(1/n). However, by using weighted averages that assignXless weight when_{i}iis near 1 ornand greater weight wheniis nearn/2, one can get estimators forE(X)with typical error significantly smaller than O(1/n).

The methods and ideas are mostly probabilistic and combinatorial. No prior knowledge of rotor-routing or smoothing kernels, and no familiarity with (or fondness for) statistics, will be assumed.