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 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 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:

Also, there are some web-sites to explore:

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.