QUASI-RANDOM SEQUENCES AND THEIR DISCREPANCIES

Quasi-random (also called low discrepancy) sequences are a determinist ic alternative to random sequences for use in Monte Carlo methods, suc h as integration and particle simulations of transport processes. The error in uniformity for such a sequence of N points in the s-dimension al unit cube is measured by its discrepancy, which is of size (log N)s N-1 for large N, as opposed to discrepancy of size (log log N)1/2 N-1 /2 for a random sequence (i.e., for almost any randomly chosen sequenc e). Several types of discrepancies, one of which is new, are defined a nd analyzed. A critical discussion of the theoretical bounds on these discrepancies is presented. Computations of discrepancies are presente d for a wide choice of dimensions s, number of points N, and different quasi-random sequences. In particular for moderate or large s, there is an intermediate regime in which the discrepancy of a quasi-random s equence is almost exactly the same as that of a randomly chosen sequen ce. A simplified proof is given for Wozniakowski's result relating dis crepancy and average integration error, and this result is generalized to other measures on function space.