Uniform Distribution, Discrepancy and Low-Discrepancy Sequences

A sequence of points is uniformly distributed in the -dimensional unit cube , if in the limit the fraction of points lying in any measurable set of is equal to the area of that set. The star-discrepancy of the first points of a sequence measures its deviation from the uniform distribution in the way that

,     

where denotes the set of all rectangles in with one corner at the origin., the -dimensional Lebesgue measure and the characteristic function of .
The Law of Iterated Logarithm for the discrepancy shows that the discrepancy of pseudo-random numbers is of the order . A lower bound for the discrepancy of any sequence in the s-dimensional unit cube is , where is a constant depending on the dimension. Low-discrepancy sequences are sequences whose discrepancy is less than .

Converted by Mathematica November 18, 1998