Scrambled Sobol Sequences via Permutation

摘要

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.