Large deviations theory techniques in Monte Carlo simulation

ABSTRACT

This paper considers the estimation via importance sampling simulation of large deviation probabilities. These are probabilities P_n which vanish with an exponential rate as n ∞. Let L_n denote the number of simulations required to obtain a specified relative precision. Since P_n vanishes exponentially fast, it turns out that for most practical importance sampling simulation schemes L_n will grow exponentially as n ∞. We say that a simulation scheme is asymptotically efficient if L_n grows less than exponentially fast. Identification of efficient importance sampling simulation schemes is the primary goal of this paper.There are several problems of interest which can be couched in the framework of large deviations theory. For the purpose of developing intuition and presenting of our results with minimal mathematical preliminaries we shall concentrate on the problem of i.i.d. sums crossing a threshold. In this setting we shall show that there is precisely one i.i.d. simulation scheme that is efficient. Generalization and related problems are also overviewed. We assume the reader has no previous knowledge of large deviations theory.

REFERENCES

• 1: Bucklew, J. A., Ney, P. and Sadowsky, J. S. (1990). Monte Carlo simulation and large deviations theory for uniformly recurrent Markov chains. To appear in the Journal of Applied Probability.
• 2: Cottrell, M., Fort, J. C. and Malgouyres, G. (1983). Large deviations and rare events in the study of stochastic algorithms. IEEE Transactions on Automatic Control., AC-28, 907--920.
• 3: Dupuis, P. and Kushner, J. (1987). Stochastic systems with small noise, analysis and simulation; A phase licked loop example. SIAM Journal of Appplied Mathematics, 47, 643--661.
• 4: Ellis, R. S. (1984). Large deviations for a general class of random vectors. Annals of Probability, 12, 1--12, 1984.
• 5: Ellis, R. S. (1985). Entropy, Large Deviations and Statistical Mechanics. Springer-Verlag, New York.
• 6: Hammersley, J. M. and Handscomb, D. C. (1964). Monte Carlo Methods. Chapman and Hall, New York.
• 7: Hunkel, V. M. F. and Bucklew, J. A. (1990). Fast simulation for functionals of Markov chains. To appear in IEEE Transactions on Information Theory.
• 8: Ney, P. (1983). Dominating points and the asymptotics of large deviations for random walks on R^d. Annals of Probabability, 11, 158--167.
• 9: Parekh, S. and Walrand, J. (1989). A quick simulation method for excessive backlogs in networks of queues. IEEE Transactions on Automatic Control, AC-34, 54--66.
• 10: Sadowsky, J. S. and Bucklew, J. A. (1990). On large deviations theory and asymptotically efficient Monte Carlo estimation. To appear in IEEE Transactions on Information Theory.
• 11: Siegmund, D. (1976). Importance sampling in the Monte Carlo study of sequential tests. Annals of Statistics, 4, 673--684.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Performance, Theory