More Web Proxy on the site http://driver.im/

article

Variance with alternative scramblings of digital nets

Author:

Art B. OwenAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 13, Issue 4

Pages 363 - 378

https://doi.org/10.1145/945511.945518

Published: 01 October 2003 Publication History

Abstract

There have been many proposals for randomizations of digital nets. Some of those proposals greatly reduce the computational burden of random scrambling. This article compares the sampling variance under different scrambling methods. Some scrambling methods adversely affect the variance, even to the extent of deteriorating the rate at which variance converges to zero. Surprisingly, a new scramble proposed here, has the effect of improving the rate at which the variance converges to zero, but so far, only for one dimensional integrands. The mean squared L² discrepancy is commonly used to study scrambling schemes. In this case, it does not distinguish among some scrambles with different convergence rates for the variance.

References

[1]

Bakhvalov, N. S. 1959. On approximate calculation of multiple integrals. Vestnik Moskovskogo Universiteta, Seriya Matematiki, Mehaniki, Astronomi, Fiziki, Himii 4, 3--18. (In Russian).

[2]

Cochran, W. G. 1977. Sampling Techniques (3rd Ed). Wiley, New York.

[3]

Cranley, R. and Patterson, T. 1976. Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 13, 904--914.

Digital Library

[4]

de Boor, C. 1978. A Practical Guide to Splines. Springer, New York.

[5]

Faure, H. 1982. Discrépance de suites associées à un systéme de numération (en dimension s). Acta Arithmet. 41, 337--351.

[6]

Faure, H. 1992. Good permutations for extreme discrepancy. J. Numb. Theory 42, 47--56.

[7]

Faure, H. 2001. Variations on (0,s)-sequences. J. Complex. 17, 741--753.

Digital Library

[8]

Faure, H. and Tezuka, S. 2002. Another random scrambling of digital (t,s)--sequences. In Monte Carlo and Quasi-Monte Carlo Methods 2000, K. T. Fang, F. J. Hickernell, and H. Niederreiter, Eds. Springer-Verlag, Berlin, Germany, 242--256.

[9]

Fox, B. L. 1999. Strategies for quasi-Monte Carlo. Kluwer Academic, Boston, Mass.

[10]

Friedel, I. and Keller, A. 2002. Fast generation of randomized low-discrepancy point sets. In Monte Carlo and Quasi-Monte Carlo Methods 2000, K. T. Fang, F. J. Hickernell, and H. Niederreiter, Eds. Springer-Verlag, Berlin, Germany, 257--273.

[11]

Haber, S. 1967. A modified Monte Carlo quadrature, II. Math. Computat. 21, 388--397.

[12]

Heinrich, S. 1993. Random approximation in numerical analysis. In Functional analysis. Proceedings of the Essen Conference (Essen, Germany, Nov. 24--30). K. D. Bierstedt, A. Pietsch, W. M. Ruess, and D. Vogt, Eds. Marcel Dekker, New York, 123--171.

[13]

Hickernell, F. J. 1996a. The mean square discrepancy of randomized nets. ACM Trans. Model. Comput. Simul. 6, 274--296.

Digital Library

[14]

Hickernell, F. J. 1996b. Quadrature error bounds and figures of merit for quasi-random points. SIAM J. Numer. Anal. 33, 1995--2016. Corrected printing of Sections 3-6 in ibid., 34 (1997), 853--866.

Digital Library

[15]

Hickernell, F. J. 1998a. A generalized discrepancy and quadrature error bound. Math. Comput. 67, 299--322.

Digital Library

[16]

Hickernell, F. J. 1998b. Lattice rules: how well do they measure up? In Random and Quasi-Random Point Sets, P. Hellekalek and G. Larcher, Eds. Springer, New York, 109--168.

[17]

Hickernell, F. J. and Yue, R. X. 2000. The mean square discrepancy of scrambled (t,s)-sequences. SIAM J. Numer. Anal. 38, 1089--1112.

Digital Library

[18]

Hlawka, E. 1961. Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Ann. Mate. Pura Appl. 54, 325--333.

[19]

Hong, H. S. and Hickernell, F. J. 1999. The asymptotic efficiency of randomized nets for quadrature. Math. Comput. 68, 767--791.

Digital Library

[20]

Hong, H. S. and Hickernell, F. J. 2003. Implementing scrambled digital sequences. AMS Trans. Math/Softw. 29, 95--109.

Digital Library

[21]

L'Ecuyer, P. and Lemieux, C. 2002. A survey of randomized quasi-Monte Carlo methods. In Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, M. Dror, P. L'Ecuyer, and F. Szidarovszki, Eds. Kluwer Academic Publishers, New York, 419--474.

[22]

Matoušek, J. 1998a. Geometric Discrepancy : An Illustrated Guide. Springer-Verlag, Heidelberg.

[23]

Matoušek, J. 1998b. On the L2--discrepancy for anchored boxes. J. Complex. 14, 527--556.

Digital Library

[24]

Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, PA.

Digital Library

[25]

Owen, A. B. 1995. Randomly permuted (t, m, s)-nets and (t, s)-sequences. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, H. Niederreiter and P. J.-S. Shiue, Eds. Springer-Verlag, New York, 299--317.

[26]

Owen, A. B. 1997a. Monte Carlo variance of scrambled equidistribution quadrature. SIAM J. Numer. Anal. 34, 5, 1884--1910.

Digital Library

[27]

Owen, A. B. 1997b. Scrambled net variance for integrals of smooth functions. Ann. Stat. 25, 4, 1541--1562.

[28]

Owen, A. B. 1998. Latin supercube sampling for very high dimensional simulations. ACM Trans. Model. Comput. Simul. 8, 2, 71--102.

Digital Library

[29]

Owen, A. B. 1999. Monte Carlo, quasi-Monte Carlo, and randomized quasi-Monte Carlo. In Monte Carlo and quasi-Monte Carlo Methods 1998, H. Niederreiter and J. Spanier, Eds. Springer-Verlag, Berlin, 86--97.

[30]

Roth, K. F. 1980. On irregularities of distribution IV. Acta Arithmet. 37, 67--75.

[31]

Tan, K. S. and Boyle, P. P. 2000. Applications of randomized low discrepancy sequences to the valuation of complex securities. J. Econ. Dynam. Cont. 24, 1747--1782.

[32]

Tezuka, S. 1995. Uniform random numbers: theory and practice. Kluwer Academic Publishers, Boston, Mass.

[33]

Tezuka, S. 2002. On randomization of generalized faure sequences. Tech. Rep. RT0494, IBM Tokyo Research Laboratory.

[34]

Tezuka, S. and Faure, H. 2002. I-binomial scrambling of digital nets and sequences. Tech. Rep., IBM Tokyo Research Laboratory.

[35]

van der Corput, J. G. 1935a. Verteilungsfunktionen I. Nederl. Akad. Wetensch. Proc. 38, 813--821.

[36]

van der Corput, J. G. 1935b. Verteilungsfunktionen II. Nederl. Akad. Wetensch. Proc. 38, 1058--1066.

[37]

Zaremba, S. K. 1968. Some applications of multidimensional integration by parts. Ann. Pol. Math. 21, 85--96.

Cited By

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Goda TSuzuki KMatsumoto M(2024)A Universal Median Quasi-Monte Carlo IntegrationSIAM Journal on Numerical Analysis10.1137/22M152507762:1(533-566)Online publication date: 16-Feb-2024
https://doi.org/10.1137/22M1525077
L'Ecuyer PCherkanihassani YEl Amine Derkaoui M(2024)Pre-Scrambled Digital Nets for Randomized Quasi-Monte Carlo2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838945(443-454)Online publication date: 15-Dec-2024
https://doi.org/10.1109/WSC63780.2024.10838945
Show More Cited By

Index Terms

Variance with alternative scramblings of digital nets
1. Mathematics of computing
  1. Mathematical analysis
    1. Quadrature

Recommendations

Monte Carlo Variance of Scrambled Net Quadrature

Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. This paper studies the variance of one such hybrid, scrambled nets, by ...
New approach in steganography by integrating different LSB algorithms and applying randomization concept to enhance security
ICCCS '11: Proceedings of the 2011 International Conference on Communication, Computing & Security

In this paper we propose a new technique in steganography to hide the information to be hidden with digital image. Here we take BMP image to hide the data. We take most common Steganography algorithm LSB as base and made some changes in it based upon ...
Watermarking via optimization algorithms for quantizing randomized semi-global image statistics

We introduce a novel approach for blind and semi-blind watermarking and apply it to images. We derive randomized robust semi-global statistics of images in a suitable transform domain (wavelets in case of images) and quantize them in order to embed the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 13, Issue 4

October 2003

84 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/945511

Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2003

Published in TOMACS Volume 13, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
645
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Doignies BCoeurjolly DBonneel NDigne JIehl JOstromoukhov V(2024)Differentiable Owen ScramblingACM Transactions on Graphics10.1145/368776443:6(1-12)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687764
Goda TSuzuki KMatsumoto M(2024)A Universal Median Quasi-Monte Carlo IntegrationSIAM Journal on Numerical Analysis10.1137/22M152507762:1(533-566)Online publication date: 16-Feb-2024
https://doi.org/10.1137/22M1525077
L'Ecuyer PCherkanihassani YEl Amine Derkaoui M(2024)Pre-Scrambled Digital Nets for Randomized Quasi-Monte Carlo2024 Winter Simulation Conference (WSC)10.1109/WSC63780.2024.10838945(443-454)Online publication date: 15-Dec-2024
https://doi.org/10.1109/WSC63780.2024.10838945
Dong GHintz EHofert MLemieux C(2024)Randomized Quasi-Monte Carlo Methods on Triangles: Extensible Lattices and SequencesMethodology and Computing in Applied Probability10.1007/s11009-024-10084-z26:2Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s11009-024-10084-z
L'Ecuyer PNakayama MOwen ATuffin B(2023)Confidence Intervals for Randomized Quasi-Monte Carlo EstimatorsProceedings of the Winter Simulation Conference10.5555/3643142.3643179(445-456)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3643142.3643179
Ahmed APharr MWonka P(2023)ART-Owen ScramblingACM Transactions on Graphics10.1145/361830742:6(1-11)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618307
L’Ecuyer PNakayama MOwen ATuffin B(2023)Confidence Intervals for Randomized Quasi-Monte Carlo Estimators2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10408613(445-456)Online publication date: 10-Dec-2023
https://doi.org/10.1109/WSC60868.2023.10408613
L’Ecuyer PPuchhammer FBen Abdellah A(2022)Monte Carlo and Quasi–Monte Carlo Density Estimation via ConditioningINFORMS Journal on Computing10.1287/ijoc.2021.113534:3(1729-1748)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1135
Pan ZOwen A(2022)Super-polynomial accuracy of one dimensional randomized nets using the median of meansMathematics of Computation10.1090/mcom/3791Online publication date: 7-Oct-2022
https://doi.org/10.1090/mcom/3791
Dong GLemieux C(2022)Dependence properties of scrambled Halton sequencesMathematics and Computers in Simulation10.1016/j.matcom.2022.04.016200(240-262)Online publication date: Oct-2022
https://doi.org/10.1016/j.matcom.2022.04.016
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents