Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

If a random variable X is easier to simulate than to analyze, one way to estimate its expected value E(X) is to generate n samples that are distributed according to the law of X and take their average. If the samples are independent, then (assuming X has 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₁+...+X_n)/n to differ from its expected value E(X) by less than O(1/n). However, by using weighted averages that assign X_i less weight when i is near 1 or n and greater weight when i is near n/2, one can get estimators for E(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.