DISTINGUISHED LECTURE: Better than Random: Quasirandomness for Discrete Stochastic Systems

November 16, 2005
2:50 pm - 4:00 pm
Halligan 111

Abstract

When you're unable (or unwilling) to solve a probabilistic model exactly, you might be inclined to use statistical methods to analyze the model, and to estimate properties of the model by doing N independent (pseudo)random simulations of the model for some large N.

This is the Monte Carlo temptation, and I will argue that in many cases it's a temptation that should be resisted: quasirandom methods, when available, are often much better. Not only does the typical error for quasirandom simulation go down like 1/N or (log N)/N rather than 1/sqrt(N), but a quasirandom error-bound is frequently a deterministic bound rather than a confidence interval. Why settle for being 95% confident that some quantity of interest lies in a large interval when you can be 100% confident that it lies in a small interval?

I'll further argue that if you're doing Monte Carlo simulation using an algorithmic random number generator as your source of (pseudo)random bits, you're already doing a kind of low-accuracy quasirandom simulation that's hard to analyze. Paradoxically, some visibly non-random schemes may both be easier to analyze and give better estimates of the quantities that interest you. I'll support these claims with examples involving random walk, random aggregation, and other stochastic models as time permits.

For a preview of the lecture, see murl.microsoft.com/LectureDetails.asp?1050 (a video of an earlier version of the talk), www.math.wisc.edu/~propp/rotor-router-1.0, (an applet that illustrates some of the ideas of the talk), or www.math.wisc.edu/~propp/quasirandom.html (my web-page on quasirandom simulation of discrete random processes).

This talk is based on joint work with Ander Holroyd and Lionel Levine.