Stochastic simulation and Monte Carlo methods. Mathematical foundations of stochastic simulation (Q2392069): Difference between revisions

The stochastic simulations and Monte Carlo methods are useful approaches for solving a number of problems of numerical integration, financial mathematics, physics and another branches of science. This monograph is organized as follows: Its contains three parts, Part one -- principles of Monte Carlo methods, Part two -- exact and approximate simulation of Markov processes and Part three -- variance reduction, Girsanov' s theorem and stochastic algorithms. On the other hand, the monograph is divided into nine chapters. The purposes of the monograph are to present: - examples of probability distributions on the space of continuous or piecewise continuous functions; - examples of sampling methods for these probability distributions, and theoretical estimates describing sampling errors; - a selection of applications which justify the examples and the need for theoretical sampling error estimation. Chapter 1 ``Introduction'', begins with 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. In Section 1.1, a review and examples of applications of these models in different scientific areas are given. In Section 1.2, the authors give a short description of the content of the monograph. Chapter 2 deals with the principles of Monte Carlo methods, based on the strong law of large numbers (SLLN). Various examples are described, some coming from concrete important applications. The description of algorithms of the simulation of random variables follows: they are involved in the probabilistic numerical techniques which will be developed. The SLLN is proved using martingale techniques. In Section 2.1 the SLLN is presented. This is the content of Theorem 2.1. The concept of the Monte Carlo algorithm is presented. The geometric concept of Buffon's needle is given. The neutron transport simulations are considered as a tool to solve the differential equation, describing the evolution of the position of a neutron. Stochastic numerical methods for partial differential equations are applied. In Section 2.2, a number of distributions -- a uniform distribution, a discrete distribution, a Gaussian distribution, and exponential distributions are described. The rejection method is used to simulate a random vector with given density. In Section 2.3, the important notion of martingale processes is introduced. At the end of this section the SLLN is proved. In Section 2.4 problems are proposed as a final presentation of different kinds of distributions. Chapter 3 deals with the convergence rates for Monte Carlo methods. Here, theoretical results, allowing to estimate the number of Monte Carlo simulations, which are necessary to obtain a desired accuracy, are provided. A non-asymptotic version of the central limit theorem is developed. Also, variance reduction techniques for Monte Carlo methods are presented. In Section 3.1 few reminders on the probability laws of random variables are presented. In Section 3.2 the central limit theorem is given. By using this result, asymptotic confidence intervals are provided. In Section 3.3 Berry-Esseen's theorem, which provides non-asymptotic error estimation, is given. In Section 3.4 Bikelis' theorem is presented and applied to establish absolute or non-asymptotic convergence. An algorithm to estimate the number of samples is described. In Section 3.5, in order to estimate the probability that the Monte Carlo method error exceeds, the following inequalities are presented -- the logarithmic Sobolev inequality and concentration inequalities for the SLLN. In Section 3.6 some variance reduction techniques are described. The idea of the control variance reduction method is developed. The importance sampling variance reduction technique is presented. The situation of a Bermuda European option is developed. In Section 3.7 problems, related to the theoretic base of Section 3, are presented. Chapter 4 introduces some theoretical and practical issues of modelling by means of Markov processes. Point processes are introduced in order to model jump instants. The Poisson process is 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. In Section 4.1, a quick introduction to Markov processes for the modelling of randomly evolving systems is given. In Section 4.2, the Poisson process is characterized as a memoryless point process. The law of the Poisson process is determined, also some extensions are developed. The strong Markov property for stopping times is given. The superposition and decomposition of the Poisson process is proved. An application to exponential random variables is realized. In Section 4.3, an exact and an approximate simulation of Poisson processes are described as well as some statistical and computational issues. Simulations of independent Poisson processes, the simulation of renewal processes and an intermediate method are presented. The asymptotic behavior of Poisson processes in long times, or with large intensities is shown. In Section 4.4 problems, related to Poisson processes, are presented. They supplement the theory and applications of this chapter. In Chapter 5, a rather detailed study of Markov processes with discrete state space is provided. It focuses on simple path techniques in a perspective inspired by simulation needs. The relationship of these processes with Poisson processes and with discrete-time Markov chain is shown. Rigorous constructions and results are provided for Markov processes with uniformly bounded jump rates. The elements of the theory of the bounded operations are introduced, which explain the relation between generators and semigroups, and provide a useful framework for the forward and backward Kolmogorov equations and the Feynman-Kac formula. In Section 5.1, some general properties of a Markov process are shown. A presentation of a Markov process in matrix form is realized. The stopping times and the strong Markov property are discussed. In Section 5.2, an effective construction and simulation techniques for a Markov process are provided. The random evolution of a Markov process is characterized and described in terms of its generator and its rates. Two constructions of Markov processes are presented. The explosion or existence for a Markov process is proved. It is proved that the Kolmogorov equation or Fokker-Planck equation under presented conditions has a unique solution. The notions of a measure-function duality, a total variation norm, bounded operator algebras, generators with bounded jump rates are presented. Examples, which are a concrete realization of Markov processes, as \(M/M / \infty\) queue, pure birth, birth and death process, are developed. In Section 5.3 problems, related to Markov process, are provided. In Chapter 6, the strong similarity between such Markov processes with constant trajectories between isolated jumps and a discrete space are emphasized. A Markov process with sample path is introduced. The Kolmogorov equations and Feynman-Kac formula are established. This is applied to kinetic equations. To construct continuous-space Markov processes, in Section 6.1, necessary notions and facts, measures, functions, integrals of functions, transition kernels, semigroups, and infinitesimal generators are presented. In Section 6.2, Markov processes which evolve only by isolated jumps are considered. The hypothesis of ``isolated jumps'' is discussed. The fundamental construction, then the fundamental simulation and a fictitious jump method, the Kolmogorov equations and Feynman-Kac formula of this Markov process are developed. In Section 6.3, a more general class of Markov process, the so-called piecewise deterministic Markov processes, is introduced. Probabilistic representations for kinetic equations, arising in statistical mechanics, is obtained. Kolmogorov equations and Feynman-Kac formula are adapted to this framework. The using of the Monte Carlo method vs. the curse of dimensionality is discussed. In Section 6.4 problems, related to the jump method, are provided. In Chapter 7, discretization schemes for stochastic differential equations and their applications to the probabilistic resolution of deterministic parabolic partial differential equations are developed. Some important properties of Itô's Brownian stochastic calculus and the existence and uniqueness theorem for stochastic differential equations with Lipschitz coefficients are given. The obtained results are applied to prove the existence, the uniqueness and the smoothness properties of the solutions of parabolic partial differential equations. It is shown that the stochastic partial differential equations with smooth coefficients define stochastic flows, and some properties of such flows are proved. In Section 7.1, a few reviews to stochastic integrals and Itô's stochastic calculations is given. In Section 7.2, Euler and Milstein schemes for convergence rate in \(L^p(\Omega)\) norm are presented. In Section 7.3, the moments of the solution of a stochastic differential with Lipschitz coefficients and applications to the Euler scheme are studied. In Section 7.4, the convergence in \(L^p(\Omega)\) norm of the error of the results of the Euler or Milstein schemes is studied. In Section 7.5, a Monte Carlo method is applied to solve a class of parabolic partial differential equations. In Section 7.6, the theorem of Talay and Tubaro is proved. In Section 7.7, the Romberg-Richardson exploration methods are developed. This chapter is finished with problems. In Chapter 8, the variance reduction subject and focuses on the Monte Carlo methods for deterministic parabolic partial differential equations are deepened. For this study, in Section 8.1, advanced notions in stochastic calculus, particularly the Girsanov theorem are presented. In Section 8.2, a control variates method is developed. In Section 8.3 it is shown how to compute both the solution, and some of its partial derivatives with respect to some of its parameters. In Section 8.4, some applications of the Girsanov theorem to variance reduction are shown. In Section 8.5, the principles of the statistical Romberg method to reduce the variance of the simulation are developed. This chapter finishes with problems. Chapter 9 introduces a few theoretical and practical issues, raised by stochastic optimization algorithms. In Section 9.2, a wide variety of situations and techniques is given, also a framework sufficiently simple to remain accessible and sufficiently wide to illustrate the main ideas. In Section 9.3, by using stochastic algorithms, a variance reduction of Monte Carlo method is obtained. This chapter finishes with problems. In a special appendix the solutions of some selected problems are presented. The References of the monograph contain 47 items.