Discrete Quasirandomness
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
a_{0}/2 + a_{1}/4 + a_{2}/8 + ..., where n =
a_{0} + 2a_{1} + 4a_{2}+ ...,
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
previously.
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
expanded
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
holds.
- Lionel Levine's article
The
Rotor-Router Model (his undergraduate thesis while at Harvard).
- The grant
proposal I submitted to NSF's
Division of
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
Erdos
Lecture Series in Spring 2006.
- Michael Kleber's article
Goldbug
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
buy
this book!)
Also, there are some web-sites to explore:
- 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
web-page for
the video also has links to various memos, documents, and emails
I've written or received on the topic of quasirandomness and
rotor-routers.
- Matt Cook has a
web
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
applet
(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"
web-site.
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.
My main collaborators on this project so far have been
Lionel Levine
and
Ander Holroyd,
though I've also gotten lots of useful feedback from other people.
(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
James Propp,
propp@math.wisc.edu.