IDEAS home Printed from https://ideas.repec.org/a/eee/matcom/v143y2018icp191-201.html
   My bibliography  Save this article

Sorting methods and convergence rates for Array-RQMC: Some empirical comparisons

Author

Listed:
  • L’Ecuyer, Pierre
  • Munger, David
  • Lécot, Christian
  • Tuffin, Bruno

Abstract

We review the Array-RQMC method, its variants, sorting strategies, and convergence results. We are interested in the convergence rate of measures of discrepancy of the states at a given step of the chain, as a function of the sample size n, and also the convergence rate of the variance of the sample average of a (cost) function of the state at a given step, viewed as an estimator of the expected cost. We summarize known convergence rate results and show empirical results that suggest much better convergence rates than those that are proved. We also compare different types of multivariate sorts to match the chains with the RQMC points, including a sort based on a Hilbert curve.

Suggested Citation

  • L’Ecuyer, Pierre & Munger, David & Lécot, Christian & Tuffin, Bruno, 2018. "Sorting methods and convergence rates for Array-RQMC: Some empirical comparisons," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 143(C), pages 191-201.
    • Handle: RePEc:eee:matcom:v:143:y:2018:i:c:p:191-201
    DOI: 10.1016/j.matcom.2016.07.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378475416301203
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.matcom.2016.07.010?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. El Haddad, R. & Lécot, C. & L’Ecuyer, P. & Nassif, N., 2010. "Quasi-Monte Carlo methods for Markov chains with continuous multi-dimensional state space," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 81(3), pages 560-567.
    2. Zhijian He & Art B. Owen, 2016. "Extensible grids: uniform sampling on a space filling curve," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 78(4), pages 917-931, September.
    3. L’Ecuyer, P. & Sanvido, C., 2010. "Coupling from the past with randomized quasi-Monte Carlo," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 81(3), pages 476-489.
    4. Pierre L'Ecuyer & Christian Lécot & Bruno Tuffin, 2008. "A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains," Operations Research, INFORMS, vol. 56(4), pages 958-975, August.
    5. Mathieu Gerber & Nicolas Chopin, 2015. "Sequential quasi Monte Carlo," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 77(3), pages 509-579, June.
    6. John J. Bartholdi, III & Loren K. Platzman, 1988. "Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space," Management Science, INFORMS, vol. 34(3), pages 291-305, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Lécot, Christian & L’Ecuyer, Pierre & El Haddad, Rami & Tarhini, Ali, 2019. "Quasi-Monte Carlo simulation of coagulation–fragmentation," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 161(C), pages 113-124.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bhattacharya, Arnab & Wilson, Simon P., 2018. "Sequential Bayesian inference for static parameters in dynamic state space models," Computational Statistics & Data Analysis, Elsevier, vol. 127(C), pages 187-203.
    2. Mathieu GERBER & Nicolas CHOPIN & Nick WHITELEY, 2017. "Negative association, ordering and convergence of resampling methods," Working Papers 2017-36, Center for Research in Economics and Statistics.
    3. Jeanne Demgne & Sophie Mercier & William Lair & Jérôme Lonchampt, 2017. "Modelling and numerical assessment of a maintenance strategy with stock through piecewise deterministic Markov processes and quasi Monte Carlo methods," Journal of Risk and Reliability, , vol. 231(4), pages 429-445, August.
    4. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    5. Bowerman, Robert & Hall, Brent & Calamai, Paul, 1995. "A multi-objective optimization approach to urban school bus routing: Formulation and solution method," Transportation Research Part A: Policy and Practice, Elsevier, vol. 29(2), pages 107-123, March.
    6. Nicolas Chopin & Mathieu Gerber, 2017. "Sequential quasi-Monte Carlo: Introduction for Non-Experts, Dimension Reduction, Application to Partly Observed Diffusion Processes," Working Papers 2017-35, Center for Research in Economics and Statistics.
    7. Chris Clifton & Ananth Iyer & Richard Cho & Wei Jiang & Murat Kantarc{i}ou{g}lu & Jaideep Vaidya, 2008. "An Approach to Securely Identifying Beneficial Collaboration in Decentralized Logistics Systems," Manufacturing & Service Operations Management, INFORMS, vol. 10(1), pages 108-125, January.
    8. Jean-Jacques Forneron, 2019. "A Scrambled Method of Moments," Papers 1911.09128, arXiv.org.
    9. Lécot, Christian & L’Ecuyer, Pierre & El Haddad, Rami & Tarhini, Ali, 2019. "Quasi-Monte Carlo simulation of coagulation–fragmentation," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 161(C), pages 113-124.
    10. Dick, Josef & Rudolf, Daniel & Zhu, Houying, 2019. "A weighted discrepancy bound of quasi-Monte Carlo importance sampling," Statistics & Probability Letters, Elsevier, vol. 149(C), pages 100-106.
    11. Golightly, Andrew & Bradley, Emma & Lowe, Tom & Gillespie, Colin S., 2019. "Correlated pseudo-marginal schemes for time-discretised stochastic kinetic models," Computational Statistics & Data Analysis, Elsevier, vol. 136(C), pages 92-107.
    12. Fakhereddine, Rana & Haddad, Rami El & Lécot, Christian & Maalouf, Joseph El, 2017. "Stratified Monte Carlo simulation of Markov chains," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 135(C), pages 51-62.
    13. Dellaportas, Petros & Titsias, Michalis K. & Petrova, Katerina & Plataniotis, Anastasios, 2023. "Scalable inference for a full multivariate stochastic volatility model," Journal of Econometrics, Elsevier, vol. 232(2), pages 501-520.
    14. Pan, C-H. & Liu, S-Y., 1995. "A comparative study of order batching algorithms," Omega, Elsevier, vol. 23(6), pages 691-700, December.
    15. Karol Gellert & Erik Schlögl, 2021. "Parameter Learning and Change Detection Using a Particle Filter with Accelerated Adaptation," Risks, MDPI, vol. 9(12), pages 1-18, December.
    16. Pierre E. Jacob & John O’Leary & Yves F. Atchadé, 2020. "Unbiased Markov chain Monte Carlo methods with couplings," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 82(3), pages 543-600, July.
    17. Chopin, Nicolas & Gadat, Sébastien & Guedj, Benjamin & Guyader, Arnaud & Vernet, Elodie, 2015. "On some recent advances in high dimensional Bayesian Statistics," TSE Working Papers 15-557, Toulouse School of Economics (TSE).
    18. Gael M. Martin & David T. Frazier & Christian P. Robert, 2020. "Computing Bayes: Bayesian Computation from 1763 to the 21st Century," Monash Econometrics and Business Statistics Working Papers 14/20, Monash University, Department of Econometrics and Business Statistics.
    19. Z. I. Botev, 2017. "The normal law under linear restrictions: simulation and estimation via minimax tilting," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 79(1), pages 125-148, January.
    20. Zhijian He & Art B. Owen, 2016. "Extensible grids: uniform sampling on a space filling curve," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 78(4), pages 917-931, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:matcom:v:143:y:2018:i:c:p:191-201. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/mathematics-and-computers-in-simulation/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.