×

Computational investigations of scrambled Faure sequences. (English) Zbl 1207.65010

Summary: The Faure sequence is one of the well-known quasi-random sequences used in quasi-Monte Carlo applications. In its original and most basic form, the Faure sequence suffers from correlations between different dimensions. These correlations result in poorly distributed two-dimensional projections. A standard solution to this problem is to use a randomly scrambled version of the Faure sequence. We analyze various scrambling methods and propose a new nonlinear scrambling method, which has similarities with inversive congruential methods for pseudo-random number generation. We demonstrate the usefulness of our scrambling by means of two-dimensional projections and integration problems.

MSC:

65C05 Monte Carlo methods
11K38 Irregularities of distribution, discrepancy

Software:

Algorithm 647
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bratley, P.; Fox, B.; Niederreiter, H., Implementation and tests of low-discrepancy sequences, ACM Transactions on Modelling and Computer Simulation, 2, 3, 195-213 (1992) · Zbl 0846.11044
[2] H. Chi, Scrambled quasirandom sequences and their applications, PhD Dissertation, Florida State University, 2004.; H. Chi, Scrambled quasirandom sequences and their applications, PhD Dissertation, Florida State University, 2004.
[3] Chi, H.; Mascagni, M.; Warnock, T., On the optimal Halton sequences, Mathematics and Computers in Simulation, 70, 1, 9-21 (2005) · Zbl 1119.65301
[4] Cohen, H., A Course in Computational Algebraic Number Theory (2000), Springer
[5] Eichenauer, J.; Lehn, J., A non-linear congruential pseudo random number generator, Statistical Papers, 27, 315-326 (1986) · Zbl 0607.65001
[6] Eichenauer-Hermann, J.; Herrmann, E.; Stefan, W., A survey of quadratic and inversive congruential pseudorandom numbers, (Proceedings of the Second International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Salzburg, July 9-12, 1996, volume 127 (1997), Springer-Verlag: Springer-Verlag New York), 66-97 · Zbl 0885.65003
[7] Faure, H., Discrépance de suites associées a un système de numération (en dimension \(s)\), Acta Arithmetica, 41, 337-351 (1982) · Zbl 0442.10035
[8] Faure, H., Variations on \((0,s)\)-sequences, Journal of Complexity, 17, 4, 741-753 (2001) · Zbl 0997.11060
[9] Faure, H., Selection criteria for (random) generation of digital \((0,s)\)-sequences, (Monte Carlo and Quasi-Monte Carlo Methods 2004 (2006)), 113-126 · Zbl 1096.11028
[10] Fox, L. B., Algorithm 647: Implementation and relative efficiency of quasirandom sequence generators, ACM Transactions on Mathematical Software, 12, December (4), 362-376 (1986) · Zbl 0615.65003
[11] Friedel, I.; Keller, A., Fast generation of randomized low-discrepancy point sets, (Niederreiter, H.; Fang, K.-T.; Hickernell, F. J., Monte Carlo and Quasi-Monte Carlo Methods 2000 (2002), Springer-Verlag: Springer-Verlag Berlin Heidelberg), 257-273 · Zbl 1055.11049
[12] Hickernell, F. J., The mean square discrepancy of randomized nets, ACM Transactions on Modeling and Computer Simulation, 6, October (4), 274-296 (1996) · Zbl 0887.65030
[13] Hickernell, F. J., A generalized discrepancy and quadrature error bound, Mathematics of Computation, 67, 221, 299-322 (1998) · Zbl 0889.41025
[14] L’Ecuyer, P.; Lemieux, C., Recent Advances in Randomized quasi-Monte Carlo Methods, (Modelling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications (2002), Kluwer Academic Publishers), 419-474
[15] Lehmer, D. H., Mathematical methods in large-scale computing units, (Proceedings of the 2nd Symposium on Large-Scale Digital Calculating Machinery. Proceedings of the 2nd Symposium on Large-Scale Digital Calculating Machinery, Cambridge, MA (1949)), 141-146 · Zbl 0045.40001
[16] Loh, W. L., On the asymptotic distribution of scrambled net quadrature, Annals of Statistics, 31, 1282-1324 (2003) · Zbl 1105.62304
[17] Matoušek, J., On the \(L_2\)-discrepancy for anchored boxes, Journal of Complexity, 14, 527-556 (1998) · Zbl 0942.65021
[18] Niederreiter, H., Quasi-Monte Carlo methods and pseudo-random numbers, Bulletin of the American Mathematical Society, 84, November (6), 957-1041 (1978) · Zbl 0404.65003
[19] Niederreiter, H., Recent trends in random number and random vector generation, Annals of Operations Research, 31, December (1), 323-346 (1991) · Zbl 0737.65001
[20] Niederreiter, H., Nonlinear methods for pseudorandom number and vector generation, 374, 145-153 (1992) · Zbl 0849.11055
[21] Niederreiter, H., Random number generation and quasi-Monte Carlo methods, vol. 63, (SIAM CBMS-NSF Regional Conference Series in Applied Mathematics (1992), SIAM: SIAM Philadelphia), 31
[22] Owen, A. B., Randomly permuted (t,m,s)-nets and (t,s)-sequences, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, 106 in Lecture Notes in Statistics, 299-317 (1995) · Zbl 0831.65024
[23] Owen, A. B., Monte Carlo, quasi-Monte Carlo, and randomized quasi-Monte Carlo, (Niederreiter, H.; Spanier, J., Monte Carlo and Quasi-Monte Carlo Methods, 1998 (2000), Springer-Verlag: Springer-Verlag Berlin Heidelberg), 86-97 · Zbl 0942.65024
[24] Owen, A. B., Variance with alternative scramblings of digital nets, ACM Transactions on Modeling and Computer Simulation, 13, 363-378 (2003) · Zbl 1390.65037
[25] Sobol’, I. M., Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates, Mathematics and Computers in Simulation, 55, 271-280 (2001) · Zbl 1005.65004
[26] Tan, K. S.; Boyle, P. B., Applications of randomized low discrepancy sequences to the valuation of complex securities, Journal of Economic Dynamics and Control, 24, 1747-1782 (2000) · Zbl 0967.91059
[27] S. Tezuka, A generalization of Faure sequences and its efficient implementation, Technical Report RT0105, IBM, 1994.; S. Tezuka, A generalization of Faure sequences and its efficient implementation, Technical Report RT0105, IBM, 1994.
[28] Tezuka, S., Uniform Random Numbers: Theory and Practice (1995), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0841.65004
[29] Tezuka, S.; Faure, H., I-binomial scrambling of digital nets and sequences, Journal of Complexity, 19, 6, 744-757 (2003), Dec. · Zbl 1073.68033
[30] Vandewoestyne, B.; Cools, R., Good permutations for deterministic scrambled Halton sequences in terms of \(L_2\)-discrepancy, Journal of Computational and Applied Mathematics, 189, 1, 341-361 (2006) · Zbl 1086.65003
[31] Wang, X.; Fang, K.-T., The effective dimension and quasi-Monte Carlo, Journal of Complexity, 19, 2, 101-124 (2003) · Zbl 1021.65002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.