IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v56y2008i4p958-975.html
   My bibliography  Save this article

A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains

Author

Listed:
  • Pierre L'Ecuyer

    (GERAD and Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, C.P. 6128, Succ. Centre-Ville, Montréal, Québec, Canada H3C 3J7)

  • Christian Lécot

    (Laboratoire de Mathématiques, Université de Savoie, 73376 Le Bourget-du-Lac Cedex, France)

  • Bruno Tuffin

    (IRISA-INRIA, Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France)

Abstract

We introduce and study a randomized quasi-Monte Carlo method for the simulation of Markov chains up to a random (and possibly unbounded) stopping time. The method simulates n copies of the chain in parallel, using a ( d+1 )-dimensional, highly uniform point set of cardinality n , randomized independently at each step, where d is the number of uniform random numbers required at each transition of the Markov chain. The general idea is to obtain a better approximation of the state distribution, at each step of the chain, than with standard Monte Carlo. The technique can be used in particular to obtain a low-variance unbiased estimator of the expected total cost when state-dependent costs are paid at each step. It is generally more effective when the state space has a natural order related to the cost function.We provide numerical illustrations where the variance reduction with respect to standard Monte Carlo is substantial. The variance can be reduced by factors of several thousands in some cases. We prove bounds on the convergence rate of the worst-case error and of the variance for special situations where the state space of the chain is a subset of the real numbers. In line with what is typically observed in randomized quasi-Monte Carlo contexts, our empirical results indicate much better convergence than what these bounds guarantee.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:oropre:v:56:y:2008:i:4:p:958-975
    DOI: 10.1287/opre.1080.0556
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0556
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.1080.0556?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
    ---><---

    References listed on IDEAS

    as
    1. Pierre L'Ecuyer & Christiane Lemieux, 2000. "Variance Reduction via Lattice Rules," Management Science, INFORMS, vol. 46(9), pages 1214-1235, September.
    2. Paul Glasserman & Philip Heidelberger & Perwez Shahabuddin & Tim Zajic, 1999. "Multilevel Splitting for Estimating Rare Event Probabilities," Operations Research, INFORMS, vol. 47(4), pages 585-600, August.
    3. Hatem Ben-Ameur & Pierre L'Ecuyer & Christiane Lemieux, 2004. "Combination of General Antithetic Transformations and Control Variables," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 946-960, November.
    4. Pierre L’Ecuyer & Christiane Lemieux, 2002. "Recent Advances in Randomized Quasi-Monte Carlo Methods," International Series in Operations Research & Management Science, in: Moshe Dror & Pierre L’Ecuyer & Ferenc Szidarovszky (ed.), Modeling Uncertainty, chapter 0, pages 419-474, Springer.
    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. Nabil Kahalé, 2020. "Randomized Dimension Reduction for Monte Carlo Simulations," Management Science, INFORMS, vol. 66(3), pages 1421-1439, March.
    2. 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.
    3. Dimov, I. & Georgieva, R. & Ostromsky, Tz., 2012. "Monte Carlo sensitivity analysis of an Eulerian large-scale air pollution model," Reliability Engineering and System Safety, Elsevier, vol. 107(C), pages 23-28.
    4. 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.
    5. 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.

    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. Xiaoqun Wang & Ken Seng Tan, 2013. "Pricing and Hedging with Discontinuous Functions: Quasi-Monte Carlo Methods and Dimension Reduction," Management Science, INFORMS, vol. 59(2), pages 376-389, July.
    2. Pierre L’Ecuyer & Florian Puchhammer & Amal Ben Abdellah, 2022. "Monte Carlo and Quasi–Monte Carlo Density Estimation via Conditioning," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1729-1748, May.
    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. Hatem Ben-Ameur & Pierre L'Ecuyer & Christiane Lemieux, 2004. "Combination of General Antithetic Transformations and Control Variables," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 946-960, November.
    5. Fabian Dickmann & Nikolaus Schweizer, 2014. "Faster Comparison of Stopping Times by Nested Conditional Monte Carlo," Papers 1402.0243, arXiv.org.
    6. Brown, Paul T. & Joshi, Chaitanya & Joe, Stephen & Rue, Håvard, 2021. "A novel method of marginalisation using low discrepancy sequences for integrated nested Laplace approximations," Computational Statistics & Data Analysis, Elsevier, vol. 157(C).
    7. Pierre L’Ecuyer, 2009. "Quasi-Monte Carlo methods with applications in finance," Finance and Stochastics, Springer, vol. 13(3), pages 307-349, September.
    8. D.D. Riley & X. Koutsoukos, 2014. "Probabilistic verification of a biodiesel production system using statistical model checking," Mathematical and Computer Modelling of Dynamical Systems, Taylor & Francis Journals, vol. 20(5), pages 452-469, September.
    9. Okten, Giray & Eastman, Warren, 2004. "Randomized quasi-Monte Carlo methods in pricing securities," Journal of Economic Dynamics and Control, Elsevier, vol. 28(12), pages 2399-2426, December.
    10. Kontosakos, Vasileios E. & Mendonca, Keegan & Pantelous, Athanasios A. & Zuev, Konstantin M., 2021. "Pricing discretely-monitored double barrier options with small probabilities of execution," European Journal of Operational Research, Elsevier, vol. 290(1), pages 313-330.
    11. Raimova, Gulnora, 2011. "Variance reduction methods at the pricing of weather options," Applied Econometrics, Russian Presidential Academy of National Economy and Public Administration (RANEPA), vol. 21(1), pages 3-15.
    12. James Hodgson & Adam M. Johansen & Murray Pollock, 2022. "Unbiased Simulation of Rare Events in Continuous Time," Methodology and Computing in Applied Probability, Springer, vol. 24(3), pages 2123-2148, September.
    13. Kleijnen, Jack P.C. & Ridder, A.A.N. & Rubinstein, R.Y., 2010. "Variance Reduction Techniques in Monte Carlo Methods," Discussion Paper 2010-117, Tilburg University, Center for Economic Research.
    14. Jan Baldeaux, 2011. "Exact Simulation of the 3/2 Model," Papers 1105.3297, arXiv.org, revised May 2011.
    15. Xiaoqun Wang & Ian H. Sloan, 2011. "Quasi-Monte Carlo Methods in Financial Engineering: An Equivalence Principle and Dimension Reduction," Operations Research, INFORMS, vol. 59(1), pages 80-95, February.
    16. Lemieux, Christiane & L’Ecuyer, Pierre, 2001. "On selection criteria for lattice rules and other quasi-Monte Carlo point sets," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 55(1), pages 139-148.
    17. Kaynar, Bahar & Ridder, Ad, 2010. "The cross-entropy method with patching for rare-event simulation of large Markov chains," European Journal of Operational Research, Elsevier, vol. 207(3), pages 1380-1397, December.
    18. Yang Huang & Yongdao Zhou, 2022. "Convergence of Uniformity Criteria and the Application in Numerical Integration," Mathematics, MDPI, vol. 10(19), pages 1-20, October.
    19. Vladimir K. Kaishev & Dimitrina S. Dimitrova, 2009. "Dirichlet Bridge Sampling for the Variance Gamma Process: Pricing Path-Dependent Options," Management Science, INFORMS, vol. 55(3), pages 483-496, March.
    20. Zdravko I. Botev & Pierre L'Ecuyer & Gerardo Rubino & Richard Simard & Bruno Tuffin, 2013. "Static Network Reliability Estimation via Generalized Splitting," INFORMS Journal on Computing, INFORMS, vol. 25(1), pages 56-71, February.

    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:inm:oropre:v:56:y:2008:i:4:p:958-975. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.