Skip to main content
main-content
Top

About this book

This book presents broadly applicable methods for the large deviation and moderate deviation analysis of discrete and continuous time stochastic systems. A feature of the book is the systematic use of variational representations for quantities of interest such as normalized logarithms of probabilities and expected values. By characterizing a large deviation principle in terms of Laplace asymptotics, one converts the proof of large deviation limits into the convergence of variational representations. These features are illustrated though their application to a broad range of discrete and continuous time models, including stochastic partial differential equations, processes with discontinuous statistics, occupancy models, and many others. The tools used in the large deviation analysis also turn out to be useful in understanding Monte Carlo schemes for the numerical approximation of the same probabilities and expected values. This connection is illustrated through the design and analysis of importance sampling and splitting schemes for rare event estimation. The book assumes a solid background in weak convergence of probability measures and stochastic analysis, and is suitable for advanced graduate students, postdocs and researchers.

Table of Contents

Frontmatter

Laplace Principle, Relative Entropy, and Elementary Examples

Frontmatter

Chapter 1. General Theory

Abstract
Throughout this chapter \(\{X^{n}\}_{n\in \mathbb {N}}\) is a sequence of random variables defined on a probability space \((\varOmega ,\mathscr {F}, P)\) and taking values in a complete separable metric space \(\mathscr {X}\). As is usual, we will refer to such a space as a Polish space . The metric of \(\mathscr {X}\) is denoted by d(xy), and expectation with respect to P by E. The theory of large deviations focuses on random variables \(\{X^{n}\}\) for which the probabilities \(P\{X^{n}\in A\}\) converge to 0 exponentially fast for a class of Borel sets A.
Amarjit Budhiraja, Paul Dupuis

Chapter 2. Relative Entropy and Tightness of Measures

Abstract
In this chapter we will collect results on relative entropy and tightness of probability measures that will be used many times in this book.
Amarjit Budhiraja, Paul Dupuis

Chapter 3. Examples of Representations and Their Application

Abstract
Our approach to the study of large deviations is based on convenient variational representations for expected values of nonnegative functionals. In this chapter we give three examples of such representations and show how they allow easy proofs of some classical results.
Amarjit Budhiraja, Paul Dupuis

Discrete Time Processes

Frontmatter

Chapter 4. Recursive Markov Systems with Small Noise

Abstract
In Chap. 3 we presented several examples of representations and how they could be used for large deviation analysis.
Amarjit Budhiraja, Paul Dupuis

Chapter 5. Moderate Deviations for Recursive Markov Systems

Abstract
In this chapter we consider \(\mathbb {R}^{d}\)-valued discrete time processes of the same form as in Chap. 4, but instead of analyzing the large deviation behavior, we consider deviations closer to the LLN limit.
Amarjit Budhiraja, Paul Dupuis

Chapter 6. Empirical Measure of a Markov Chain

Abstract
In this chapter we develop the large deviation theory for the empirical measure of a Markov chain, thus generalizing Sanov’s theorem from Chap. 3. The ideas developed here are useful in other contexts, such as proving sample path large deviation properties of processes with multiple time scales as described in Sect. 7.​3.
Amarjit Budhiraja, Paul Dupuis

Chapter 7. Models with Special Features

Abstract
Chapters 4 through 6 considered small noise large deviations of stochastic recursive equations, small noise moderate deviations for processes of the same type, and large deviations for the empirical measure of a Markov chain. These chapters thus consider models that are both standard and fairly general for each setting. In this chapter we consider discrete time models that are somewhat less standard, with the aim being to show how the weak convergence methodology can be adapted.
Amarjit Budhiraja, Paul Dupuis

Continuous Time Processes

Frontmatter

Chapter 8. Representations for Continuous Time Processes

Abstract
In previous chapters we developed and applied representations for the large deviation analysis of discrete time processes. The derivation of useful representations in this setting follows from a straightforward application of the chain rule. The only significant issue is to decide on the ordering used for the underlying “driving noises” when the chain rule is applied, since controls are allowed to depend on the “past,” which is determined by this ordering.
Amarjit Budhiraja, Paul Dupuis

Chapter 9. Abstract Sufficient Conditions for Large and Moderate Deviations in the Small Noise Limit

Abstract
In this chapter we use the representations derived in Chap. 8 to study large and moderate deviations for stochastic systems driven by Brownian and/or Poisson noise, and consider a “small noise” limit, as in Sects. 3.​2 and 3.​3. We will prove general abstract large deviation principles, and in later chapters apply these to models in which the noise enters the system in an additive and independent manner (In our terminology, this includes systems with multiplicative noise, namely settings in which the noise term is multiplied by a state-dependent coefficient). For these systems, one can view the mapping that takes the noise into the state of the system as “nearly” continuous, and it is this property that allows a unified and relatively straightforward treatment.
Amarjit Budhiraja, Paul Dupuis

Chapter 10. Large and Moderate Deviations for Finite Dimensional Systems

Abstract
In this chapter we use the abstract sufficient conditions from Chap. 9 to prove large and moderate deviation principles for small noise finite dimensional jump-diffusions. We will consider only Laplace principles rather than uniform Laplace principles, since, as was noted in Chap. 9, the extension from the nonuniform to the uniform case is straightforward. The first general results on large deviation principles for jump-diffusions of the form considered in this chapter are due to Wentzell [245–248] and Freidlin and Wentzell [140]. The conditions for an LDP identified in the current chapter relax some of the assumptions made in these works. Results on moderate deviation principles in this chapter are based on the recent work [41]. We do not aim for maximal generality, and from the proofs it is clear that many other models (e.g., time inhomogeneous jump diffusions, SDEs with delay) can be treated in an analogous fashion.
Amarjit Budhiraja, Paul Dupuis

Chapter 11. Systems Driven by an Infinite Dimensional Brownian Noise

Abstract
In Chap. 8 we gave a representation for positive functionals of a Hilbert space valued Brownian motion. This chapter will apply the representation to study the large deviation properties of infinite dimensional small noise stochastic dynamical systems. In the application, the driving noise is given by a Brownian sheet, and so in this chapter we will present a sufficient condition analogous to Condition 9.​1 (but there will be no Poisson noise in this chapter) that covers the setting of such noise processes (see Condition 11.​15). Another formulation of an infinite dimensional Brownian motion that will be needed in Chap. 12 is as a sequence of independent Brownian motions regarded as a \(\mathscr {C}([0,T]:\mathbb {R}^{\infty })\)-valued random variable. We also present the analogous sufficient condition (Condition 11.12) for an LDP to hold for this type of driving noise.
Amarjit Budhiraja, Paul Dupuis

Chapter 12. Stochastic Flows of Diffeomorphisms and Image Matching

Abstract
The previous chapter considered in detail an example driven by a Brownian sheet, namely a stochastic reaction–diffusion equation. In this chapter we consider an application of one of the other formulations of infinite dimensional Brownian motion, which is the infinite sequence of independent one-dimensional Brownian motions. Such a collection will be used to define a general class of Brownian flows of diffeomorphisms [178], which are a special case of the stochastic flows of diffeomorphisms studied in [16, 25, 124, 178]. We will consider small noise asymptotics, prove the corresponding LDP, and then use it to give a Bayesian interpretation of an estimator used for image matching.
Amarjit Budhiraja, Paul Dupuis

Chapter 13. Models with Special Features

Abstract
Chapters 8 through 12 considered representations in continuous time and their application to large and moderate deviation analyses of finite and infinite dimensional systems described by stochastic differential equations. In this chapter we complete our study of continuous time processes by considering additional problems with features that benefit from a somewhat different use of the representations and/or weak convergence arguments.
Amarjit Budhiraja, Paul Dupuis

Accelerated Monte Carlo for Rare Events

Frontmatter

Chapter 14. Rare Event Monte Carlo and Importance Sampling

Abstract
Suppose that in the analysis of some system, the value of a probability or expected value that is largely determined by one or a few events is important. Examples include the data loss in a communication network; depletion of capital reserves in a model for insurance; motion between metastable states in a chemical reaction network; and exceedance of a regulatory threshold in a model for pollution in a waterway. In previous chapters we have described how large deviation theory gives approximations for such quantities. The approximations take the form of logarithmic asymptotics, i.e., exponential decay rates.
Amarjit Budhiraja, Paul Dupuis

Chapter 15. Performance of an IS Scheme Based on a Subsolution

Abstract
In Chap. 14 we considered the problem of rare event simulation associated with small noise discrete time Markov processes of the form analyzed in Chap. 4. Two types of events were emphasized: those that are described by process behavior on a bounded time interval (finite-time problems) and those that concern properties of the process over unbounded time horizons (e.g., exit probability problems).
Amarjit Budhiraja, Paul Dupuis

Chapter 16. Multilevel Splitting

Abstract
An alternative to importance sampling in estimating rare events and related functionals is multilevel splitting. In the context of estimating probabilities of a set \(\mathscr {C}\) in path space, the multilevel splitting philosophy is to simulate particles that evolve according to the law of \(\left\{ X_{i}\right\} \), and at certain times split those particles considered more likely to lead to a trajectory that belongs to the set \(\mathscr {C}\). For example, \(\mathscr {C}\) might be the trajectories that reach some unlikely set B before hitting a likely set A, after starting in neither A nor B. In this case, the splitting will favor migration toward B. Splitting can also be used to enhance the sampling of regions that are important for a given integral. In all cases, particles which are split are given an appropriate weighting to ensure that the algorithm remains unbiased.
Amarjit Budhiraja, Paul Dupuis

Chapter 17. Examples of Subsolutions and Their Application

Abstract
In this chapter we present examples to illustrate the importance sampling and splitting techniques developed in Chaps. 14, 15, and 16. There are many different types of problems one might consider, and the interested reader can find additional examples in the references [76, 77, 101, 103, 105, 110, 112, 113, 116, 117]. As mentioned in Chaps. 14 and 16, an important distinction is that in the case of importance sampling, we use a smooth classical-sense subsolution, while in the case of splitting, we use a continuous but not necessarily smooth weak-sense solution. For many of the examples presented, the construction of subsolutions can be carried out in arbitrary dimension.
Amarjit Budhiraja, Paul Dupuis

Backmatter

Additional information

Premium Partner

    Image Credits