Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-24T14:04:41.088Z Has data issue: false hasContentIssue false
  • English
  • Français

Exact estimation for Markov chain equilibrium expectations

Part of: Markov processes Probabilistic methods, simulation and stochastic differential equations

Published online by Cambridge University Press:  30 March 2016

Peter W. Glynn  and
Chang-Han Rhee
Peter W. Glynn
Affiliation:
Management Science and Engineering, Stanford University, Stanford, CA 94305-4121, USA. Email address: [email protected].
Chang-Han Rhee
Affiliation:
Biomedical Engineering, Georgia Institute of Technology, U. A. Whitaker Building, 313 Ferst Drive, Atlanta, GA 30332, USA. Email address: [email protected].
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We introduce a new class of Monte Carlo methods, which we call exact estimation algorithms. Such algorithms provide unbiased estimators for equilibrium expectations associated with real-valued functionals defined on a Markov chain. We provide easily implemented algorithms for the class of positive Harris recurrent Markov chains, and for chains that are contracting on average. We further argue that exact estimation in the Markov chain setting provides a significant theoretical relaxation relative to exact simulation methods.

Keywords

Unbiased estimationMarkov chain equilibrium expectationMarkov chain stationary expectationexact estimationexact samplingexact simulationperfect samplingperfect simulation

MSC classification

Primary: 65C05: Monte Carlo methods
Secondary: 60J05: Discrete-time Markov processes on general state spaces
Type
Part 8. Markov processes and renewal theory
Information
Journal of Applied Probability , Volume 51 , Issue A: Celebrating 50 Years of The Applied Probability Trust , December 2014 , pp. 377 - 389
Copyright
Copyright © Applied Probability Trust 2014 

References

Asmussen, S., and Glynn, P. W. (2007). Stochastic Simulation: Algorithms and Analysis (Stoch. Modelling Appl. Prob. 57). Springer, New York.Google Scholar
Asmussen, S., Glynn, P. W., and Thorisson, H. (1992). Stationarity detection in the initial transient problem. ACM Trans. Model. Comput. Simul. 2, 130–157.CrossRefGoogle Scholar
Athreya, K. B., and Ney, P. (1978). A new approach to the limit theory of recurrent Markov chains. Trans. Amer. Math. Soc. 245, 493–501.Google Scholar
Blanchet, J., and Wallwater, A. (2014). Exact sampling for the steady-state waiting time of a heavy-tailed single server queue. Submitted.Google Scholar
Borovkov, A. A., and Foss, S. G. (1992). Stochastically recursive sequences and their generalizations. Siberian Adv. Math. 2, 16–81.Google Scholar
Chung, K. L. (2001). A Course in Probability Theory, 3rd edn. Academic Press, San Diego, CA.Google Scholar
Connor, S. B., and Kendall, W. S. (2007). Perfect simulation for a class of positive recurrent Markov chains. Ann. Appl. Prob. 17, 781–808.Google Scholar
Corcoran, J. N., and Tweedie, R. L. (2001). Perfect sampling of ergodic Harris chains. Ann. Appl. Prob. 11, 438–451.CrossRefGoogle Scholar
Diaconis, P., and Freedman, D. (1999). Iterated random functions. SIAM Rev. 41, 45–76.Google Scholar
Ensor, K. B., and Glynn, P. W. (2000). Simulating the maximum of a random walk. J. Statist. Planning Infer. 85, 127–135.Google Scholar
Giles, M. B. (2008). Multilevel Monte Carlo path simulation. Operat. Res. 56, 607–617.CrossRefGoogle Scholar
Glynn, P. W., and Whitt, W. (1992). The asymptotic efficiency of simulation estimators. Operat. Res. 40, 505–520.Google Scholar
Kendall, W. S. (2004). Geometric ergodicity and perfect simulation. Electron. Commun. Prob. 9, 140–151.CrossRefGoogle Scholar
Lindvall, T. (2002). Lectures on the Coupling Method. Dover Publications, Mineola, NY.Google Scholar
McLeish, D. (2011). A general method for debiasing a Monte Carlo estimator. Monte Carlo Meth. Appl. 17, 301–315.Google Scholar
Meyn, S., and Tweedie, R. L. (2009). Markov Chains and Stochastic Stability, 2nd edn. Cambridge University Press.Google Scholar
Propp, J. G., and Wilson, D. B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures Algorithms 9, 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
Rhee, C.-H., and Glynn, P. W. (2012). A new approach to unbiased estimation for SDE's. In Proc. 2012 Winter Simulation Conference, eds. Laroque, C. et al., 7 pp.Google Scholar
Rhee, C.-H., and Glynn, P. W. (2013). Unbiased estimation with square root convergence for SDE models. Submitted.Google Scholar
Rychlik, T. (1990). Unbiased nonparametric estimation of the derivative of the mean. Statist. Prob. Lett. 10, 329–333.Google Scholar
Rychlik, T. (1995). A class of unbiased kernel estimates of a probability density function. Appl. Math. 22, 485–497.Google Scholar
Thorisson, H. (2000). Coupling, Stationarity, and Regeneration. Springer, New York.CrossRefGoogle Scholar