Scrambled Sobol Sequences via Permutation
FLORIDA STATE UNIV TALLAHASSEE
Pagination or Media Count:
The Sobol sequence is one of the standard quasirandom sequences, and is widely used in Quasi- Monte Carlo QMC applications. QMC methods are a variant of ordinary Monte Carlo MC methods that employ highly uniform quasirandom numbers in place of the pseudorandom numbers used in ordinary Monte Carlo MC. QMC methods are now widely used in scientific computation, especially in estimating integrals over multidimensional domains and in many different financial computations. In order to provide such dynamic error estimates for QMC methods, several researchers proposed the use of Randomized QMC RQMC methods, where randomness can be brought to bear on quasirandom sequences through scrambling and other related randomization techniques. The core of RQMC is to find fast and effective algorithms to randomize scramble quasirandom sequences. In this paper, we propose a new Sobol scrambling algorithm based on the permutation of several groups of bits from the individual Sobol numbers. Most of the current scrambling methods either randomize a single digit at each iteration, or randomize a group of digits through linear operations. In contrast, our multiple-digit scrambling is efficient and fast because it permutes small groups of digits. We implemented this new Sobol scrambling algorithm in the software context of the SPRNG library, because SPRNG not only generates parallel pseudorandom numbers, but it also provides an extensible object-orient interfaces for merging scrambled Sobol sequences.
- Statistics and Probability
- Operations Research