Quasi-random points keep their distance
In contrast to random points that may cluster, quasi-random points keep their distance. These distances are investigated. 1. If N independent random points in the n-dimensional unit hypercube are selected, two of these points may be arbitrarily close. However, if Q(0), Q(1),..., Q(N-1), are quasi-random points, the minimum distance between pairs of these points, d(N), has a positive lower bound. For the Sobol sequence dN >= 1/2 root nN(-1). Numerical experiments suggest that for large N d(N) asymptotic to N-1/n 2. For certain search algorithms, it is important to know points Q(i) and Q(i+1) that are not close, For the Sobol sequence, the distances p(Q(2k), Q(2k+1)) = 1/2 root n, and 1/4 root n <= p(Q(4k+1), Q(4k+2)) <= 1/4 root 5n + c, where c=0 for even n and c=4 for odd n. 3. Numerical estimations of dN for the Halton and Faure sequences were carried out. It is likely that for these sequences, (1) is true also. (C) 2006 IMACS. Published by Elsevier B.V. All rights reserved.
monte carlo method quasi-monte carlo method numerical mathematics