Discrete Quasirandomness

(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₀/2 + a₁/4 + a₂/8 + ..., where n = a₀ + 2a₁ + 4a₂+ ..., 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):

• Simulating a random walk with constant error by Joshua Cooper and Joel Spencer (arXiv:math.CO/0402323).
• Spherical asymptotics for the rotor-router model in Z^d by Lionel Levine and Yuval Peres.
• Deterministic random walks on the integers by Joshua Cooper, Benjamin Doerr, Joel Spencer, Gabor Tardos (arXiv:math.CO/0602300).

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

(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!