Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-27T08:53:47.652Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient Simulation via Coupling

Published online by Cambridge University Press:  27 July 2009

Peter W. Glynn  and
Eugene W. Wong
Peter W. Glynn
Affiliation:
Department of Operations Research, Stanford University, Stanford, California 94305-4022
Eugene W. Wong
Affiliation:
Department of Operations Research, Stanford University, Stanford, California 94305-4022
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper is concerned with how coupling can be used to enhance the efficiency of a certain class of terminating simulations, in Markov process settings in which the stationary distribution is known. We are able to theoretically establish that our coupling-based estimator is often more efficient than the naive estimator. In addition, we discuss extensions of our methodology to Markov process settings in which conventional coupling fails and show (for Doeblin chains) that knowledge of the stationary distribution is sometimes unnecessary.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 10 , Issue 2 , April 1996 , pp. 165 - 186
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Aldous, D. & Diaconis, P. (1987). Strong uniform times and finite random walks. Advances in Applied Mathematics 8: 69–97.CrossRefGoogle Scholar
2.Aldous, D. & Thorisson, H. (1993). Shift-coupling. Stochastic Processes and Their Applications 1: 1–14.CrossRefGoogle Scholar
3.Asmussen, S. (1992). Coupling and weak convergence. Annals of Applied Probability 2: 739–751.CrossRefGoogle Scholar
4.Asmussen, S., Glynn, P.W., & Thorisson, H. (1992). Stationary detection in the initial transient problem. ACM Transactions on Modeling and Computer Simulation 3: 130–157.CrossRefGoogle Scholar
5.Athreya, K.B. & Ney, P. (1978). A new approach to the limit theory of recurrent Markov chains. Transactions of the American Mathematical Society 245: 493–501.CrossRefGoogle Scholar
6.Baskett, F., Chandy, K.M., Muntz, R.R., & Palacios, F. (1975). Open, closed, and mixed networks of queues with different classes of customers. Journal of the Association for Computing Machines 22: 248–260.CrossRefGoogle Scholar
7.Billingsley, P. (1968). Convergence of probability measures. New York: John Wiley.Google Scholar
8.Bratley, P., Fox, B.L., & Schrage, L. (1987). A guide to simulation. New York: Springer-Verlag.CrossRefGoogle Scholar
9.Fox, B.L. & Glynn, P.W. (1989). Estimating discounted costs. Management Science 35: 1297–1325.CrossRefGoogle Scholar
10.Glynn, J.E. (1989). A discrete-time storage process with a general release rule. Journal of Applied Probability 26: 566–583.CrossRefGoogle Scholar
11.Glynn, P.W. (1994). Some topics in regenerative steady-state simulation. Acta Applicandae Mathematica 34: 225–236.CrossRefGoogle Scholar
12.Glynn, P.W. & L'Ecuyer, P. (1994). Likelihood ratio gradient estimation for stochastic recursions. Advances in Applied Probability (to appear).Google Scholar
13.Glynn, P.W. & Whitt, W. (1992). The asymptotic efficiency of simulation estimators. Operations Research 40: 505–520.CrossRefGoogle Scholar
14.Kalashnikov, V. (1994). Topics on regenerative processes. Boca Raton, FL: CRC Press.CrossRefGoogle Scholar
15.Kelly, F.P. (1979). Reversibility and stochastic networks. New York: John Wiley.Google Scholar
16.Kelly, F.P. (1986). Blocking probabilities in large circuit-switched networks. Advances in Applied Probability 18: 473–505.CrossRefGoogle Scholar
17.Kielson, J. (1979). Markov Chain models—Rarity and exponentiality. New York: Springer-Verlag.CrossRefGoogle Scholar
18.Lindvall, T. (1992). Lectures on the coupling method. New York: John Wiley.Google Scholar
19.Meyn, S.P. & Tweedie, R.L. (1993). Markov Chains and stochastic stability. New York: Springer-Verlag.CrossRefGoogle Scholar
20.Nummelin, E. (1978). A splitting technique for Harris recurrent Markov chains. Zeitschrift für Wahrscheinlichkeitstheorie und Vervwunde Gebiete 43: 309–318.CrossRefGoogle Scholar
21.Sigman, K. (1990). One-dependent regenerative processes and queues in continuous time. Mathematics of Operations Research 15: 175–189.CrossRefGoogle Scholar
22.Whittle, P. (1986). Systems in stochastic equilibrium. New York: John Wiley.Google Scholar