Scrambled Soboĺ sequences via permutation

Mascagni Michael and Yu Haohai
Additional contact information
Mascagni Michael: Departments of Computer Science, Mathematics and Scientific Computing, Florida State University, Tallahassee, FL 32306-4530, USA. Email: mascagni@fsu.edu
Yu Haohai: Department of Computer Science, Florida State University, Tallahassee, FL 32306-4530, USA. Email: hy06@fsu.edu

Monte Carlo Methods and Applications, 2009, vol. 15, issue 4, 311-332

Abstract: The Soboĺ sequence [USSR Comput. Math. and Phy. 7: 86–112, 1967, USSR Comput. Math. and Phy. 16: 236–242, 1976] 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) [Caflisch, Acta Numerica 7: 1–49, 1998]. The error of MC methods is asymptotically , where N is the number of samples, while QMC methods can have an error bound which behaves as well as O((logN)sN–1), for s-dimensional problems. The common practice in MC of using a predetermined error criterion as a deterministic termination condition, is almost impossible to achieve in QMC without extra technology. In order to provide such dynamic error estimates for QMC methods, several researchers [Owen, Randomly permuted (t, m, s)-nets and (t, s)-sequences, 1995, Tezuka, Uniform Random Numbers, Theory and Practice, Kluwer Academic Publishers, 1995] 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 [Chi and Lorenzo, A Parallel Cellular Automata Model to Forecast the Effects of Urban Growth in North Florida, 2007, Chi and Mascagni, Efficient Generation of Parallel Quasirandom Sequences via Scrambling, 2007, Vandewoestyne, Chi, Mascagni and Cools, An Empirical Investigation of Different Scrambling Methods for Faure Sequences, 2007]. Besides providing practical error estimates, another byproduct of scrambled quasirandom numbers is that they furnish a natural way to generate quasirandom numbers in parallel and distributed applications. In this paper, we propose a new algorithm for scrambling the Soboĺ sequence based on the permutation (scrambling) of several groups of binary digits from the individual Soboĺ 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 Soboĺ scrambling algorithm in the software context of the well-known Scalable Parallel Random Number Generators (SPRNG) library [Mascagni and Srinivasan, ACM Transactions on Mathematical Software 26: 436–461, 2000, Mascagni, Scalable Parallel Random Number Gernerators Library (SPRNG)] library.

Keywords: quasirandom number generation; scrambling; digit permutation; software (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/MCMA.2009.017 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:15:y:2009:i:4:p:311-332:n:2

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/MCMA.2009.017

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().