A quasirandom analogue of a random process is a deterministic process
specifically designed so that simulation of the quasirandom process gives the
same limiting behavior (of some quantities of interest) as the random process,
but with faster convergence.
(Quasirandomness is not to be confused with pseudorandomness. A pseudorandom
process is supposed to be statistically indistinguishable from the truly
random process it imitates. In contrast, a quasirandom process will typically
have many regularities that mark it as non-random. Quasirandom processes only
need to be irregular enough for the desired application.)
Most work on quasirandomness (also sometimes called subrandomness)
has been motivated by Monte Carlo integration, and involves well-distributed
sequences of points in some continuous space (e.g., the sequence of
points in the interval [0,1] whose nth element is
a0/2 + a1/4 + a2/8 + ..., where n =
a0 + 2a1 + 4a2+ ...,
or the sequence whose
nth element is the fractional part of n times the golden ratio).
Recently I and others have been attempting to develop very simple forms
of quasirandom simulation suitable for the study of random walk, random
aggregation, particle processes, and the like. There has been a large
amount of related work (see e.g. the
Monte Carlo and Quasi-Monte Carlo Methods website), but this new
work proposes radically simpler mechanisms than those introduced
So far, the following articles are available (with more to come soon):
There are a number of other places from which one can find out
what's been done and what's in the offing:
- A first
draft of a write-up of one of the basic results in the subject
(joint work of Ander Holroyd and Jim Propp)
showing that simple devices called rotor-routers achieve
quasirandomness, at least in simple cases.
- A still extremely rough
version of the preceding draft
- An preliminary
write-up of a theorem of Oded Schramm's, showing that under
weaker hypotheses, a weaker version of the preceding result still
- Lionel Levine's article
Rotor-Router Model (his undergraduate thesis while at Harvard).
- The grant
proposal I submitted to NSF's
Mathematical Sciences in Fall 2005, describing the work on
discrete quasirandomness that I plan to do in 2006-2009.
- The slides
from a talk on quasirandomness that I gave
at the Harvard
statistics department in Spring 2005.
- The slides
from three talks on quasirandomness that I gave at faculty seminars
at the UC Berkeley
statistics department in Fall 2004.
- The slides
from a talk on quasirandomness that I gave to undergraduates at
Wellesley, Smith, and Mount Holyoke Colleges in Fall 2004.
- The slides
from a talk I gave at the
Lecture Series in Spring 2006.
- Michael Kleber's article
Variations, in the Winter 2005 issue of
The Mathematical Intelligencer.
- Peter Winkler's book Mathematical Puzzles: A Connoissuer's
Collection; in particular, the bugs-on-a-line problem on page 82
and the solution on pages 91-93. (If you like math puzzles, you should
Also, there are some web-sites to explore:
My main collaborators on this project so far have been
though I've also gotten lots of useful feedback from other people.
- In Fall 2003, I gave a talk on quasirandomness at Microsoft. They made
a video of my talk, and have kindly made it available via the web. The
the video also has links to various memos, documents, and emails
I've written or received on the topic of quasirandomness and
- Matt Cook has a
site with some amazing pictures of simulations he's done, relating
to rotor-router aggregation. (You may need to own a copy of
Mathematica to run some of Matt's simulations.)
- Hal Canary and Francis Wong, working under my supervision at
UW Madison, created an
(still under development) that will let you see for yourself
some of the properties of quasirandom simulation based on rotors.
- Tobias Friedrich, under the supervision of Benjamin Doerr, has
created a "Propp machine"
I especially liked the leftmost of the three pictures at the
bottom of the page. I've known for years that the NESW version
of the machine created interesting large-scale structures
reminiscent of conformal geometry, but I had no idea till now
that the same was true for the NSEW version.
(It should also be mentioned that Fan Chung, Ron Graham, Josh Cooper,
and others have done work on quasirandom graphs, quasirandom hypergraphs,
quasirandom tournaments, quasirandom permutations, etc. But they are
using the term "quasirandom" in a slightly different way, and so far,
I have not found that much overlap with what I'm studying.)
Comments, corrections and other contributions are welcome!
This page was last modified March 26, 2006 by