Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T09:25:00.525Z Has data issue: false hasContentIssue false
  • English
  • Français

Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains

Published online by Cambridge University Press:  14 July 2016

James A Bucklew,
Peter Ney and
John S. Sadowsky
James A Bucklew*
Affiliation:
University of Wisconsin-Madison
Peter Ney*
Affiliation:
University of Wisconsin-Madison
John S. Sadowsky*
Affiliation:
Purdue University
*
∗ Postal address: Department of Electrical and Computer Engineering, University of Wisconsin-Madison, WI 53706, USA.
∗∗ Department of Mathematics, University of Wisconsin-Madison, WI 53706, USA.
∗∗∗ Postal address: School of Electrical Engineering, Purdue University, West Lafayette, IN 47906, USA.
Get accessRights & Permissions [Opens in a new window]

Abstract

Importance sampling is a Monte Carlo simulation technique in which the simulation distribution is different from the true underlying distribution. In order to obtain an unbiased Monte Carlo estimate of the desired parameter, simulated events are weighted to reflect their true relative frequency. In this paper, we consider the estimation via simulation of certain large deviations probabilities for time-homogeneous Markov chains. We first demonstrate that when the simulation distribution is also a homogeneous Markov chain, the estimator variance will vanish exponentially as the sample size n tends to∞. We then prove that the estimator variance is asymptotically minimized by the same exponentially twisted Markov chain which arises in large deviation theory, and furthermore, this optimization is unique among uniformly recurrent homogeneous Markov chain simulation distributions.

Keywords

IMPORTANCE SAMPLING

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 27 , Issue 1 , March 1990, pp. 44 - 59
Copyright
Copyright © Applied Probability Trust 1990 

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.)

Article purchase

Temporarily unavailable

Footnotes

Supported jointly by the Office of Naval Research (N00014-87-K-0155) and the National Science Foundation (ECS-8601071).

References

Bahadur, R. R. and Rao, R. R. (1960) Large deviations of the sample mean. Ann. Math. Statist. 31, 1015–1027.Google Scholar
Bucklew, J. A. and Ney, P. (1988) Large sample optimal memoryless detectors for Markov processes via large deviations theory techniques. Proc. 22nd Ann. Conf. Inform. Sci. & Sys., Princeton University, 1019–1021.Google Scholar
Cottrell, M., Fort, J.-C. and Malgouyres, G. (1983) Large deviations and rare events in the study of stochastic algorithms. IEEE Trans. Autom. Control 28, 907–920.CrossRefGoogle Scholar
Donsker, M. D. and Varadhan, S. R. S. (1975, 1976, 1983) Asymptotic evaluation of certain Markov process expectations for large time I-IV. Comm. Pure Appl. Math. 28, 1–47, 279-301; 29, 389-461; 36, 183-212.CrossRefGoogle Scholar
Ellis, R. S. (1984) Large deviations for a general class of random vectors. Ann. Prob. 12, 1–12.Google Scholar
Ellis, R. S. (1985) Entropy, Large Deviations, and Statistical Mechanics. Springer-Verlag, New York.CrossRefGoogle Scholar
Gärtner, J. (1977) On large deviations from the invariant measure. Theory Prob. Appl. 22, 24–39.Google Scholar
Glynn, P. W. and Iglehart, D. L. (1989) Importance sampling for stochastic simulations. Management Sci. 35, 1367–1392.CrossRefGoogle Scholar
Hammersley, J. M. and Handscomb, D. C. (1964) Monte Carlo Methods. Chapman and Hall, New York.CrossRefGoogle Scholar
Harris, T. (1963) The Theory of Branching Processes. Springer-Verlag, Berlin.Google Scholar
Hunkel, V. and Bucklew, J. A. (1988) Fast simulation for functionals of Markov chains. Proc. 22nd Ann. Conf. Inform. Sci. & Sys., Princeton University, 330–335.Google Scholar
Iscoe, I., Ney, P. and Nummelin, E. (1985) Large deviations of uniformly recurrent Markov additive processes. Adv. Appl. Math. 6, 373–411.Google Scholar
Miller, H. D. (1961) A convexity property in the theory of random variables on a finite Markov chain. Ann. Math. Statist. 32, 1260–1270.Google Scholar
Ney, P. (1983) Dominating points and the asymptotics of large deviations for random walks on Rd. Ann. Prob. 11, 158–167.Google Scholar
Ney, P. (1984) Convexity and large deviations. Ann. Prob. 12, 903–906.CrossRefGoogle Scholar
Ney, P. and Nummelin, E. (1984) Some limit theorems for Markov additive processes. Proc. Symp. Semi-Markov Processes, Brussels: also in Janssen, J., ed. (1986) Semi-Markov Models. Plenum, New York.Google Scholar
Ney, P. and Nummelin, E. (1987a) Markov additive process I: eigenvalue properties and limit theorems. Ann. Prob. 15, 561–592.CrossRefGoogle Scholar
Ney, P. and Nummelin, E. (1987b) Markov additive processes II: Large deviations. Ann. Prob. 15, 593–609.CrossRefGoogle Scholar
Nummelin, E. (1984) General Irreducible Markov Chains and Non-Negative Operators. Cambridge University Press, New York.CrossRefGoogle Scholar
Orsak, G. and Aazhang, B. (1988) A comparison of two importance sampling methods for the analysis of detection systems. Proc. 1988 Conf. Inform. Sci. & Sys., Princeton University, 314–318.Google Scholar
Rubinstein, R. Y. (1981) Simulation and the Monte Carlo Method. Wiley, New York.Google Scholar
Sadowsky, J. S. (1987) An asymptotically least-favorable Chernoff bound for a large class of dependent data processes. IEEE Trans. Inf. Theory 33, 52–61.Google Scholar
Sadowsky, J. S. (1989) A dependent data extension of Wald's identity and its application to sequential test performance computations. IEEE Trans. Inf. Theory 35, 834–842.Google Scholar
Siegmund, D. (1976) Importance sampling in the Monte Carlo study of sequential tests. Ann. Statist. 4, 673–684.Google Scholar
Stroock, D. (1984) An Introduction to the Theory of Large Deviations. Springer-Verlag, New York.CrossRefGoogle Scholar
Wessel, A. E., Hall, E. B. and Wise, G. L. (1988) Some comments on importance sampling. Proc. 1988 Conf. Inform. Sci. & Sys., Princeton University, 325–329.Google Scholar