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

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