nach oben

2004 | Buch

Kapitel lesen Erstes Kapitel lesen

Introduction to Rare Event Simulation

verfasst von: James Antonio Bucklew

Verlag: Springer New York

Buchreihe : Springer Series in Statistics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book is an attempt to present a unified theory of rare event simulation and the variance reduction technique known as importance sampling from the point of view of the probabilistic theory of large deviations. This framework allows us to view a vast assortment of simulation problems from a single unified perspective. It gives a great deal of insight into the fundamental nature of rare event simulation. Unfortunately, this area has a reputation among simulation practitioners of requiring a great deal of technical and probabilistic expertise. In this text, I have tried to keep the mathematical preliminaries to a minimum; the only prerequisite is a single large deviation theorem dealing with sequences of Rd valued random variables. (This theorem and a proof are given in the text.) Large deviation theory is a burgeoning area of probability theory and many of the results in it can be applied to simulation problems. Rather than try to be as complete as possible in the exposition of all possible aspects of the available theory, I have tried to concentrate on demonstrating the methodology and the principal ideas in a fairly simple setting. Madison, Wisconsin 2003 James Antonio Bucklew Contents 1. Random Number Generation . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . . . 1.1 Uniform Generators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Nonuniform Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 The Inversion Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 The Acceptance---Rejection Method . . . . . . . . . . . . 10 . . . . . 1.3 Discrete Distributions . . . . . . . . . . . . . . . . . . . . . . . . 13 . . . . . . . . . . . 1.3.1 Inversion by Truncation of a Continuous Analog. . . . . . 14 1.3.2 Acceptance---Rejection . . . . . . . . . . . . . . . . . . . . 15 . . . . . . . . .

Inhaltsverzeichnis

Frontmatter

1. Random Number Generation

Abstract

In this chapter, we give a quick overview and discussion of some of the principal methods for generating good random numbers with a specified distribution on a computer.

James Antonio Bucklew

2. Stochastic Models

Abstract

In the previous chapter, we were concerned almost exclusively with the problem of how to generate independent random variables with a specified distribution. In the simplest settings, this is the underlying statistical model and we need go no further. In many other situations, we have to simulate some sort of dependent data or noise process to act as inputs to our simulation model. Many dependent stochastic models can be simulated in an obvious way from their definitions. Nevertheless, some tricks sometimes are useful and we present a few of the more common ones below.

James Antonio Bucklew

3. Large Deviation Theory

Abstract

We will find that many of the rare events that we wish to simulate are the result of the occurrence of a large deviation event. In order to develop good simulation strategies for these events, we need to understand something of the probability theory associated with them. In this chapter, we provide an introduction to two of the basic concepts of this important area: Cramér’s Theorem and the Gärtner-Ellis Theorem.

James Antonio Bucklew

4. Importance Sampling

Abstract

Large and/or nonlinear stochastic systems, due to analytic intractability, must often be simulated in order to obtain estimates of the key performance parameters. Typical situations of interest could be a buffer overload in a queueing network or an error event in a digital communication system. In many system designs or analyses a low probability event is a key parameter of the system’s efficacy.

James Antonio Bucklew

5. The Large Deviation Theory of Importance Sampling Estimators

Abstract

In this section we first prove a very general theorem regarding the variance rate of importance sampling estimators. At first sight the setting may appear to be fairly abstract but we argue that the level of generality presented here will pay dividends later on. We encourage the reader to follow the problem setup given here with some care and then compare it with the first example given below to see how this framework is actually used.

James Antonio Bucklew

6. Variance Rate Theory of Conditional Importance Sampling Estimators

Abstract

We consider again our usual framework: for every integer n, let Z _p _,n be a random variable taking values in some complete separable metric space S _n. Let P _n be the probability measure induced by Z _p,n on S _n. We suppose that for each random variable Z _p,n we have access to some information about it contained in an information random variable Z _pi,n taking values in some other probability space I _n. Let P _i,n denote the probability measure induced by Z _pi,n on I _n. Let f _n be an R ^d-valued measurable function on the space S _n; that is, f _n: S _n → R _d, and we suppose we are interested in ρ _n = P(f _n(Z _p,n) Є nE), for some Borel set E ⊂ R ^d.

James Antonio Bucklew

7. The Large Deviations of Bias Point Selection

Abstract

Suppose the inputs to the system are i.i.d. random variables {X _i}, which have the scalar density function p(·). We are interested in \( \rho = P\left( {\sum\nolimits_{j = 1}^n {{X_i} > na} } \right)\). We simulate with i.i.d. {S _i} whose individual density functions are q(·). In the light of Theorem 5.1.1, let us compute the variance rates for the input and output estimators, respectively.

James Antonio Bucklew

8. Chernoff’s Bound and Asymptotic Expansions

Abstract

The large deviation theory of Chapter 3 tells us what the asymptotic rates to zero are of various sequences of rare event probabilities. The very reason for this book is that in almost all applications, this knowledge is not sufficient. We actually need to know what the probability is (or at least have a good estimate of it) in order to complete an engineering system analysis or design. The philosophy of this book is that we are going to simulate in order to obtain that number.

James Antonio Bucklew

9. Gaussian Systems

Abstract

The design of information systems operating in and being corrupted by Gaussian (thermal) noise is a keystone subject area. The application areas are as numerous as are the uses of the radio spectrum. In this chapter we give a very general overview and explicitly present a theoretical framework from which a vast array of practical simulation problems can be viewed and solved.

James Antonio Bucklew

10. Universal Simulation Distributions

Abstract

In the previous chapter, we saw that in the Gaussian setting we could describe completely a sequence of simulation distributions that was efficient and depended on only one scalar parameter, the minimum rate point of the set. In this chapter we consider carrying out these techniques in the general non-Gaussian setting. Due to the special form of the multidimensional Gaussian distribution and its level sets, we could perform a closed form integration of the exponentially shifted distributions over the boundary of the level set. In general, this sort of attack which obtains a closed form solution for the sequence of simulation distributions will not be easily available. In this chapter we present an alternate methodology leading to a new class of simulation distributions, which we call universal distributions. We discuss their use and propose and debate some numerical techniques needed for employing them.

James Antonio Bucklew

11. Rare Event Simulation for Level Crossing and Queueing Models

Abstract

For every integer n, let Z _p,n be a random variable taking values in some complete separable metric space S _n. Let P _n be the probability measure induced by Z _p,n on S _n. Instead of directly simulating Z _p,n, we choose to simulate with another S _n-valued random variable Z _q,n which in turn induces a probability measure on S _n, Q _n. Let f _n be an R-valued measurable function on the space S _n; that is f _n : S _n → R.

James Antonio Bucklew

12. Blind Simulation

Abstract

Consider the following problem. One is allowed to observe the output of a very complicated system. The system could be a computer model whose internal workings would contain many random number generators and various interacting subsystems. Alternatively one could have a physical device consisting of complicated possible nonlinear electronics from which one can sample data. It may even just be a string of numbers taken as data from some experiment. The simulation problem is to estimate the probability of some output sequence event. Because of the system’s complexity, it is not known nor would it be feasible analytically to derive the underlying probability law of the experiment. This is what we call a blind simulation problem: we have to estimate the probability of an event without complete knowledge of the underlying probability law. A very large class of practical simulation problems is blind.

James Antonio Bucklew

13. The (Over-Under) Biasing Problem in Importance Sampling

Abstract

In the previous chapters we have said a lot about how to choose good importance sampling biasing distributions. We have found that in many interesting situations easily computable efficient choices exist. All in all we have painted quite a rosy picture of the problem of rare event simulation. In this chapter, we indicate some of the (dangerous) problems that can face the importance sampling practitioner and how one might go about guarding against these dangers.

James Antonio Bucklew

14. Tools and Techniques for Importance Sampling

Abstract

All of the simulation distribution families that we have seen and worked with in this book are some sort of parametric family parameterized by some vector parameter θ. The mean shift method can be thought of as a family of distributions parameterized by the mean shift. The same is true for the variance scaling method. Of course the exponential shifts have the exponential shift parameter. A mixture of m exponential shifts can be thought of as a parametric class where we have the parameters θ ₁, θ ₂,..., θ _m, p ₁, p ₂,..., p _m, where the {θ _i} are the (vector) exponential shifts for each element of the mixture and the {p _i} are the scalar mixture weights (they must sum to one which implies there are really only m — 1 free mixture weight parameters). The universal simulation distributions (once we select the “covering measure” 7) are characterized by a single scalar parameter. In fact this is their major selling point.

James Antonio Bucklew

Backmatter

Titel: Introduction to Rare Event Simulation
verfasst von: James Antonio Bucklew
Verlag: Springer New York
Electronic ISBN: 978-1-4757-4078-3
Print ISBN: 978-1-4419-1893-2
DOI: https://doi.org/10.1007/978-1-4757-4078-3

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

1. Random Number Generation

2. Stochastic Models

3. Large Deviation Theory

4. Importance Sampling

5. The Large Deviation Theory of Importance Sampling Estimators

6. Variance Rate Theory of Conditional Importance Sampling Estimators

7. The Large Deviations of Bias Point Selection

8. Chernoff’s Bound and Asymptotic Expansions

9. Gaussian Systems

10. Universal Simulation Distributions

11. Rare Event Simulation for Level Crossing and Queueing Models

12. Blind Simulation

13. The (Over-Under) Biasing Problem in Importance Sampling

14. Tools and Techniques for Importance Sampling

Backmatter