nach oben

2013 | Buch

Kapitel lesen Erstes Kapitel lesen

Stochastic Simulation and Monte Carlo Methods

Mathematical Foundations of Stochastic Simulation

verfasst von: Carl Graham, Denis Talay

Verlag: Springer Berlin Heidelberg

Buchreihe : Stochastic Modelling and Applied Probability

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

In various scientific and industrial fields, stochastic simulations are taking on a new importance. This is due to the increasing power of computers and practitioners’ aim to simulate more and more complex systems, and thus use random parameters as well as random noises to model the parametric uncertainties and the lack of knowledge on the physics of these systems. The error analysis of these computations is a highly complex mathematical undertaking. Approaching these issues, the authors present stochastic numerical methods and prove accurate convergence rate estimates in terms of their numerical parameters (number of simulations, time discretization steps). As a result, the book is a self-contained and rigorous study of the numerical methods within a theoretical framework. After briefly reviewing the basics, the authors first introduce fundamental notions in stochastic calculus and continuous-time martingale theory, then develop the analysis of pure-jump Markov processes, Poisson processes, and stochastic differential equations. In particular, they review the essential properties of Itô integrals and prove fundamental results on the probabilistic analysis of parabolic partial differential equations. These results in turn provide the basis for developing stochastic numerical methods, both from an algorithmic and theoretical point of view.

The book combines advanced mathematical tools, theoretical analysis of stochastic numerical methods, and practical issues at a high level, so as to provide optimal results on the accuracy of Monte Carlo simulations of stochastic processes. It is intended for master and Ph.D. students in the field of stochastic processes and their numerical applications, as well as for physicists, biologists, economists and other professionals working with stochastic simulations, who will benefit from the ability to reliably estimate and control the accuracy of their simulations.

Inhaltsverzeichnis

Frontmatter

Principles of Monte Carlo Methods

Frontmatter

Chapter 1. Introduction

Abstract

This introduction starts by describing some motivations for using probabilistic models and stochastic simulations. Some examples are used to illustrate classical objectives of random simulations, and to derive relevant convergence criteria for which error estimates need to be developed. Then the goals and the organization of this monograph are presented.

Carl Graham, Denis Talay

Chapter 2. Strong Law of Large Numbers and Monte Carlo Methods

Abstract

The principles of Monte Carlo methods based on the Strong Law of Large Numbers (SLLN) are detailed. A number of examples are described, some of which correspond to concrete problems in important application fields. This is followed by the discussion and description of various algorithms of simulation, first for uniform random variables, then using these for general random variables. Eventually, the more advanced topic of martingale theory is introduced, and the SLLN is proved using a backward martingale technique and the Kolmogorov zero-one law.

Carl Graham, Denis Talay

Chapter 3. Non-asymptotic Error Estimates for Monte Carlo Methods

Abstract

In order to effectively implement Monte Carlo methods, the random approximation errors must be controlled. For this purpose, theoretical results are provided for the estimation of the number of simulations necessary to obtain a desired accuracy with a prescribed confidence interval. Therefore absolute, i.e., non-asymptotic, versions of the Central Limit Theorem (CLT) are developed: Berry–Esseen’s and Bikelis’ theorems, as well as concentration inequalities obtained from logarithmic Sobolev inequalities. The difficult subject of variance reduction techniques for Monte Carlo methods arises naturally in this context, and is discussed at the end of this chapter.

Carl Graham, Denis Talay

Exact and Approximate Simulation of Markov Processes

Frontmatter

Chapter 4. Poisson Processes as Particular Markov Processes

Abstract

We first introduce some practical and theoretical issues of modeling by means of Markov processes. Point processes are introduced in order to model jump instants. The Poisson process is then characterized as a point process without memory. The rest of the chapter consists in its rather detailed study, including various results concerning its simulation and approximation. This study is essential to understand the abstract constructions and the simulation methods for jump Markov processes developed in the following chapters.

Carl Graham, Denis Talay

Chapter 5. Discrete-Space Markov Processes

Abstract

A rather detailed study of Markov processes with discrete state space is provided. It focuses on sample path techniques in a perspective inspired by simulation needs. The relationship of these processes with Poisson processes and with discrete-time Markov chains is shown. Rigorous constructions and results are provided for Markov process with uniformly bounded jump rates. To this end, elements of the theory of bounded operators are introduced, which explain the relation between generator and semigroup, and provide a useful framework for the forward and backward Kolmogorov equations and the Feynman–Kac formula.

Carl Graham, Denis Talay

Chapter 6. Continuous-Space Markov Processes with Jumps

Abstract

From now on, Markov processes with continuous state space (\(\mathbb{R}^{d}\) for some or one of its closed subsets) are considered. Their rigorous study requires advanced measure-theoretic tools, but we limit ourselves to developing the reader’s intuition, notably by pathwise constructions leading to simulations. We first emphasize the strong similarity between such Markov processes with constant trajectories between isolated jumps and discrete space ones. We then introduce Markov processes with sample paths following an ordinary differential equation between isolated jumps. In both cases, the Kolmogorov equations and Feynman–Kac formula are established. This is applied to kinetic equations coming from statistical Mechanics. These describe the time evolution of the instantaneous distribution of particles in phase space (position-velocity), when the particle velocity jumps at random instants in function of the particle position and velocity.

Carl Graham, Denis Talay

Chapter 7. Discretization of Stochastic Differential Equations

Abstract

This chapter develops discretization schemes for stochastic differential equations and their applications to the probabilistic numerical resolution of deterministic parabolic partial differential equations. It starts with some important properties of Itô’s Brownian stochastic calculus, and the existence and uniqueness theorem for stochastic differential equations with Lipschitz coefficients. Then, using probabilistic techniques only, existence, uniqueness, and smoothness properties are proved for solutions of parabolic partial differential equations. To this end, we show that stochastic differential equations with smooth coefficients define stochastic flows, and we prove some properties of such flows. We are then in a position to prove an optimal convergence rate result for the discretization schemes.

Carl Graham, Denis Talay

Variance Reduction, Girsanov’s Theorem, and Stochastic Algorithms

Frontmatter

Chapter 8. Variance Reduction and Stochastic Differential Equations

Abstract

This chapter deepens the variance reduction subject, and focuses on the Monte Carlo methods for deterministic parabolic partial differential equations. This topic requires advanced notions in stochastic calculus, particularly the Girsanov theorem, which we state and discuss first. We strongly emphasize that universal techniques do not exist: most often, effective variance reduction methods depend on the numerical analyst’s knowledge and experience. We will see that it is rather easy to construct perfect variance reduction methods which are irrelevant from a numerical point of view; a contrario, the construction of an effective method often lies on the approximation of a perfect method, the approximation method needing to be adapted to each particular case. Interesting examples can be found in Duffie and Glynn (Ann. Appl. Probab. 5(4), 897–905, 1995).

Carl Graham, Denis Talay

Chapter 9. Stochastic Algorithms

Abstract

This chapter addresses a few theoretical and practical issues raised by a class of stochastic optimization or approximation algorithms. These algorithms are efficient numerical tools in various applications and they are at the basis of the variance reduction techniques studied in the preceding chapter. We limit ourselves to a simple framework which allows us to get convergence results by means of dynamical systems and martingales theories without too many technical details. In this, we follow the very pedagogical approach in Benaïm and El Karoui (Chaînes de Markov et simulations; Martingales et stratégies, 2004).

Carl Graham, Denis Talay

Backmatter

Titel: Stochastic Simulation and Monte Carlo Methods
verfasst von: Carl Graham
Denis Talay
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-39363-1
Print ISBN: 978-3-642-39362-4
DOI: https://doi.org/10.1007/978-3-642-39363-1