Optimal Generation of Scrambled Low-Discrepancy Sequences
Emanouil I. Atanassov (Uni Saarbrücken)
Several families of sequences have upper bounds on their discrepancy of
order O(N-1log1/2N), and are the most popular
candidates for usage in quasi-Monte Carlo methods.
They are called low-discrepancy sequences, and the Sobol and the Halton family
are two of the most popular among them.
Two problems exist before the widespread adoption of quasi-Monte Carlo methods.
The first one is that the quality of distribution of the quasi-random sequence
usually depends on the choice of a certain set of generation parameters, and
finding the optimal choice is not easy.
The second one is that the generation of these sequences requires thorough
understanding of their theory, and thus the low-level computer hardware issues
are usually neglected.
The idea of scrambling the low-discrepancy sequences was introduced with the
purpose to add some automatic statistical error estimation, and even to improve
the equidistribution of the sequence, in the case of Owen type scrambling.
Our results in selecting the best parameters for the modified Halton sequences
so that the upper limits on their discrepancy is reduced, will be shown.
We will also show how our improved generation algorithms can substantially reduce
the generation time, even when Owen-type scrambling is applied.