×

Quasi-random sequences and their discrepancies. (English) Zbl 0815.65002

Authors’ summary: Quasi-random (also called low discrepancy) sequences are a deterministic alternative to random sequences for use in Monte Carlo methods, such as integration and particle simulations of transport processes. The error in uniformity for such a sequence of \(N\) points in the \(s\)-dimensional 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 sequence). Several types of discrepancies, one of which is new, are defined and analyzed. A critical discussion of the theoretical bounds on these discrepancies is presented. Computations of discrepancies are presented for a wide choice of dimension \(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 sequence is almost exactly the same as that of a randomly chosen sequence. A simplified proof is given for Woźniakowski’s result [Bull. Am. Math. Soc., New Ser. 24, No. 1, 185- 194 (1991; Zbl 0729.65010)] relating discrepancy and average integration error, and this result is generalized to other measures on function space.
Reviewer: W.Grecksch (Halle)

MSC:

65C05 Monte Carlo methods
11K45 Pseudo-random numbers; Monte Carlo methods
11K38 Irregularities of distribution, discrepancy

Citations:

Zbl 0729.65010
PDFBibTeX XMLCite
Full Text: DOI