Skip to main content
SpringerLink
Log in

Quasi-Monte Carlo Methods for Estimating Transient Measures of Discrete Time Markov Chains

  • Conference paper
Monte Carlo and Quasi-Monte Carlo Methods 2002

Summary

We describe a new method for the transient simulation of discrete time Markov chains. It is a quasi-Monte Carlo method where different paths are simulated in parallel, but reordered at each step. We prove the convergence of the method, when the number of simulated paths increases. Using some numerical experiments, we illustrate that the error of the new algorithm is smaller than the error of standard Monte Carlo algorithms. Finally, we propose to analyze continuous time Markov chains by transforming them into a discrete time problem by using the uniformization technique.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 189.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 249.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Coulibaly, I., Lécot, C. (1998) Simulation of diffusion using quasi-random walk methods. Math. Comput. Simul. 47, 153–163

    Article  Google Scholar 

  2. Fang, K.-T., Hickernell, F.J., and Niederreiter, H. (Eds.) (2002) Monte Carlo and Quasi-Monte Carlo Methods 2000. Springer, Berlin

    MATH  Google Scholar 

  3. Fishman, G.S. (1996) Monte Carlo: Concepts, Algorithms, and Applications. Springer, New York

    MATH  Google Scholar 

  4. Lécot, C. (1996) Error bounds for quasi-Monte Carlo integration with nets. Math. Comp. 65, 179–187

    Article  MathSciNet  MATH  Google Scholar 

  5. Morokoff, W. J. (1998) Generating quasi-random paths for stochastic processes. SIAM Rev. 40, 765–788

    Article  MathSciNet  MATH  Google Scholar 

  6. Morokoff, W. J., Caflisch, R. E. (1993) A quasi-Monte Carlo approach to particle simulation of the heat equation. SIAM J. Numer. Anal. 30, 1558–1573

    Article  MathSciNet  MATH  Google Scholar 

  7. Moskowitz, B. (1995) Quasirandom diffusion Monte Carlo. In Niederreiter, H., Shiue, P.J.-S. (Eds.) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Springer, New York, 278-298

    Google Scholar 

  8. Nananukul, S., Gong, W.B. (1995) The quasi-Monte Carlo method for regenerative simulation. Proceedings of the 34th Conference on Decision and Control, New Orleans, 1964-1969

    Google Scholar 

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

    Book  MATH  Google Scholar 

  10. Niederreiter, H., Shiue, P.J.-S. (Eds.) (1995) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing. Springer, New York

    MATH  Google Scholar 

  11. Niederreiter, H., Hellekalek, P., Larcher, G., and Zinterhof, P. (Eds.) (1998) Monte Carlo and Quasi-Monte Carlo Methods 1996. Springer, New York

    Google Scholar 

  12. Niederreiter, H., Spanier, J. (Eds.) (2000) Monte Carlo and Quasi-Monte Carlo Methods 1998. Springer, Berlin

    MATH  Google Scholar 

  13. Ökten, G. (1996) A probabilistic result on the discrepancy of a hybridMonte Carlo sequence and applications. Monte Carlo Methods and Appl. 2, 255–270

    MathSciNet  MATH  Google Scholar 

  14. Owen, A.B. (2000) Monte Carlo, quasi-Monte Carlo, and randomized quasiMonte Carlo. In Niederreiter, H., Spanier, J. (Eds.) Monte Carlo and QuasiMonte Carlo Methods 1998, Springer, Berlin, 86-97

    Google Scholar 

  15. Spanier, J. (1995) Quasi-Monte Carlo methods for particle transport problems. In Niederreiter, H., Shiue, P.J.-S. (Eds.) Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Springer, New York, 121-148

    Google Scholar 

  16. Spanier, J., Li, L. (1998) Quasi-Monte Carlo methods for integral equations. In Niederreiter, H., Hellekalek, P., Larcher, G., and Zinterhof, P. (Eds.) Monte Carlo and Quasi-Monte Carlo Methods 1996, Springer, New York, 398-414

    Google Scholar 

  17. Takagi, H. (1993) Queueing Analysis. A Foundation of Performance Evaluation. Volume 3: Discrete-Time Systems. North-Holland, Amsterdam

    Google Scholar 

  18. Trivedi, K.S. (2002) Probability and Statistics with Reliability, Queuing, and Computer Science Applications. John Wiley & Sons, 2nd ed., New York

    Google Scholar 

  19. Zaremba, S.K. (1968) Some applications of multidimensional integration by parts. Ann. Pol. Math. 21, 85–96

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Christian Lécot

  2. IRISA-INRIA, Campus universitaire de Beaulieu, 35042, Rennes Cedex, France

    Bruno Tuffin

Authors
  1. Christian Lécot
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bruno Tuffin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543, Republic of Singapore

    Harald Niederreiter

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lécot, C., Tuffin, B. (2004). Quasi-Monte Carlo Methods for Estimating Transient Measures of Discrete Time Markov Chains. In: Niederreiter, H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2002. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18743-8_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-18743-8_20

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-20466-4

  • Online ISBN: 978-3-642-18743-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation