Variance reduction through smoothing and control variates for Markov chain simulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Variance reduction through smoothing and control variates for Markov chain simulations

Full text

Pdf (1.11 MB)

Source

ACM Transactions on Modeling and Computer Simulation (TOMACS) archive
Volume 3 , Issue 3 (July 1993) table of contents

Pages: 167 - 189

Year of Publication: 1993

ISSN:1049-3301

Authors

Sigrún Andradóttir	Univ. of Wisconsin–Madison, Madison
Daniel P. Heyman	Bellcore, Morristown, NJ
Teunis J. Ott	Bellcore, Morristown, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 22, Citation Count: 3

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174153.174154 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sigrún Andradóttir , Daniel P. Heyman , Teunis J. Ott, Smoothing methods for variance reduction in simulation of Markov chains, Proceedings of the 24th conference on Winter simulation, p.453-457, December 13-16, 1992, Arlington, Virginia, United States [doi>10.1145/167293.167401]
	2	BILLINGSLEY, P. 1968. Convergence of Probabthty Measures. John Wiley, New York
	3	Paul Bratley , Bennett L. Fox , Linus E. Schrage, A guide to simulation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1987
	4	P W. Glynn , D. L. Iglehart, Importance sampling for stochastic simulations, Management Science, v.35 n.11, p.1367-1392, Nov. 1989 [doi>10.1287/mnsc.35.11.1367]
	5	GREENBERG~ h. G., AND VANDERBEI, a.J. 1990. Qmcker convergence for iterat~ve numerical solutions to stochastic problems: Probablhstic interpretations, ordering heuristics, and parallel processing. Prob. Eng'. Inf Scl. 4, 4, 493-521.
	6	HEIDELBERGER, P. 1980a. Variance reduction techmques for the sunulat~on of Markov processes, I: Multiple estunates. IBM J. Res. Devel. 24, 5, 1367 1392.
	7	HEIDELBERGER, P. 1980b. Variance reduction techmques for the simulation of Markov processes, II Matrix iterative methods. Acta Informatlca 13, 1, 21 37.
	8	Daniel P. Heyman, A performance model of the credit manager algorithm, Computer Networks and ISDN Systems, v.24 n.1, p.81-91, March 1992 [doi>10.1016/0169-7552(92)90105-Y]
	9	HEYMAN, D. P., AND SOBEL, M.J. 1984 Stochastic Models in OperatLons Research. Vol. 2. McGraw-Hill, New Delhi.
	10	KEILSON, J., AND WISHART, D. M.G. 1964. A central limit theorem for processes defined on a fimte Markov chain. Proc. Cambrzdge Philos. Soc. 60, 547-567.
	11	KEILSON, J., AND SUBBA RAO, S. 1970. A process with chain dependent growth rate. J Appl. Prob. 7, 3, 699-711.
	12	KEMENY, J. G., AND SNELL, J.L. 1960. Finite Markov Chains. Van Nostrand, Toronto.
	13	KLEIJNEN, J. P.C. 1978. Communication: Reply to Fox and Schruben. Manage. Sci. 24, 16, 1772 1774.
	14	NOBLE, B. 1969. Applied Linear Algebra. Prentice-Hall, Englewood Cliffs, N.J.
	15	Andrew T. Ogielski , William Aiello, Sparse matrix computations on parallel processor arrays, SIAM Journal on Scientific Computing, v.14 n.3, p.519-530, May 1993 [doi>10.1137/0914033]
	16	SADOWSKI, J.S. 1991. Large deviations theory and efficient simulation of excessive backlogs in a GI/G/m queue. IEEE Trans. Autom. Contr. 36, 1383-1394.
	17	Perwez Shahabuddin , Victor F. Nicola , Philip Heidelberger , Ambuj Goyal , Peter W. Glynn, Variance reduction in mean time to failure simulations, Proceedings of the 20th conference on Winter simulation, p.491-499, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318239]
	18	SMITH, W.L. 1955. Regenerative stochastic processes. Proc. Royal Soc. Ser. A 232, 6 31.

CITED BY 3

	Pierre L'Ecuyer, Efficiency improvement and variance reduction, Proceedings of the 26th conference on Winter simulation, p.122-132, December 11-14, 1994, Orlando, Florida, United States
	Shane G. Henderson , Sean P. Meyn, Efficient simulation of multiclass queueing networks, Proceedings of the 29th conference on Winter simulation, p.216-223, December 07-10, 1997, Atlanta, Georgia, United States
	R. S. Randhawa , S. Juneja, Combining importance sampling and temporal difference control variates to simulate Markov Chains, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.14 n.1, p.1-30, January 2004

INDEX TERMS

Primary Classification:
I. Computing Methodologies
I.6 SIMULATION AND MODELING

General Terms:
Algorithms

Keywords:
Poisson's equation, conditional Monte Carlo

REVIEW

"Anthony Joseph Duben : Reviewer"

The objective of this paper is to describe how one may calculate the long-run average cost for transitions in a Markov chain with reduced variance. As a special case, the costs of making specific transitions (for example, less likely but poten more...

Collaborative Colleagues:

Sigrún Andradóttir: colleagues

Daniel P. Heyman: colleagues

Teunis J. Ott: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player