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. 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.
    3. 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.
    4. 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.
    5. 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.
    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. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Karamé, Frédéric, 2018. "A new particle filtering approach to estimate stochastic volatility models with Markov-switching," Econometrics and Statistics, Elsevier, vol. 8(C), pages 204-230.
    11. Bertsimas, Dimitris & Van Ryzin, Garrett., 1991. "A stochastic and dynamic vehicle routing problem in the Euclidean plane," Working papers 3286-91., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    12. 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.
    13. Jean-Jacques Forneron, 2019. "A Scrambled Method of Moments," Papers 1911.09128, arXiv.org.
    14. 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.
    15. Gael M. Martin & David T. Frazier & Christian P. Robert, 2021. "Approximating Bayes in the 21st Century," Monash Econometrics and Business Statistics Working Papers 24/21, Monash University, Department of Econometrics and Business Statistics.
    16. 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.
    17. Crucinio, Francesca R. & Johansen, Adam M., 2023. "Properties of marginal sequential Monte Carlo methods," Statistics & Probability Letters, Elsevier, vol. 203(C).
    18. 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.
    19. 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.
    20. Nabil Kahalé, 2020. "Randomized Dimension Reduction for Monte Carlo Simulations," Management Science, INFORMS, vol. 66(3), pages 1421-1439, March.

    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.