Monte-Carlo methods and stochastic processes. From linear to non-linear (Q2803233)

The book is divided into three parts with theoretical results, namely -- Part A -- toolbox for stochastic simulation, Part B -- simulation of linear processes and Part C -- simulation of nonlinear processes.NEWLINENEWLINEIn the introduction, some historical notices are presented. Three typical problems in the theory of random simulations are defined. Problem 1 is the numerical integration. Here, the problem of numerical computation of multidimensional integrals is considered. The concept of the Monte Carlo estimator is given. The convergence rate of this method is described. The notion of the discrepancy as a measure for the irregularity of an arbitrary \(d\)-dimensional sequence is given. The constructive principles of two important low discrepancy sequences -- Van der Corput sequence and Halton sequence, are presented. The important Koksma-Hlawka inequality is given. Problem 2 is the simulation of complex distributions. Here, the Metropolis-Hastings algorithm and the algorithm of random Gibbs sampler are presented. Problem 3 is the stochastic optimization. Here, two algorithms are presented -- the simulated annealing algorithm and Robbins-Monro algorithm, which show how stochastic simulation allows us to resolve optimization problems.NEWLINENEWLINEChapter 1 is devoted to the practice of random simulation, it requires the ability to simulate appropriate random variables. In Section 1.1, a general presentation of the idea for construction of random variables is given. The concept of the classical generator -- the linear congruential generator is given. In Section 1.2, the concept of the inversion method of the comulated distribution function is presented. Many concrete distributions as exponential distribution, discrete distribution, geometric distribution, Cauchy distribution and Gaussian distribution are discussed. In Section 1.3, the concept of the conditional distribution is presented. The simulations of the beta distribution and the gamma distribution are realized. In Section 1.4, techniques for generating random vectors are developed. Some usual examples of copulas are given. In Section 1.5, some exercises are presented.NEWLINENEWLINEThe aim of Chapter 2 is to review the asymptotic tools as the law of large numbers, the central limit theorem and the nonasymptotic ones as concentration inequalities, in a pointwise or uniform version. The technique for the numerical evaluation of the expectation by using Monte Carlo methods is developed. In Section 2.1, the law of large numbers is proved. In Section 2.2, the concept of the central limit theorem and some its consequences are presented. The substitution method to calculate certain functions of the expectation is presented. The convergence rate and the bias of this method are given. The pathwise differentiation method is presented. In Section 2.3, some asymptotic convergence results are presented. Here, the main results are Berry-Essen bounds and Edgeworth expansions. The law of the iterated logarithm is presented. In Section 2.4, some statistical error estimates are investigated. The Hoeffding inequality, which depends only on the bound of the random variables, is proved. The uniform law of large numbers is studied. The notion of entropy is introduced and discussed. It is proved that the Gaussian distribution in arbitrary dimension satisfies the logarithmic Sobolev inequality. In Section 2.5, many exercises are presented.NEWLINENEWLINEIn Chapter 3, the question of acceleration of convergence is considered. The method of importance sampling, whose application to the evaluation of rare events is emphasized. In Section 3.1, the method of antithetic sampling is applied to describe the antithetic function. In Section 3.2, the idea to approximate the expectation by Monte Carlo methods is further developed. Here, the stratification technique as an alternative approach based on the conditioning is developed. The form of the stratification estimator is presented and the variance of this estimator is calculated. The stratification of the Gaussian vectors is discussed. In Section 3.3, the concept of the control variates is presented. The problems of the choice of the optimal parameters for the uniform distribution and the standard Gaussian variables are considered. In Section 3.4, the technique of the importance sampling for variance reduction is developed. The effects of the change of the probability measure are analysed. The changes of the probability measure by affine transformation are presented. The change of the probability measure by the Esscher transform is given. Also the concept of the adaptive methods by change of the probability measure is considered. In Section 3.5, examples, connected with applications of the antithetic sampling to the Cauchy distribution, Gaussian vectors, are given. Also the Esscher transform is applied to the Gaussian and the exponential distributions.NEWLINENEWLINEChapter 4 presents a very minimal background in stochastic calculus, the stochastic differential equations (SDE) and their simulation. The link with partial differential equations (PDE) is given via the Feynman-Kac formula, representing the solution to the PDE as an expectation of a functional of stochastic processes. Brief historical information about the Brownian motion is presented. In Section 4.1, the definition of the Brownian motion in dimension 1 is given. The technique of the iterative construction of the Brownian motion by the Brownian bridge is presented. The heat equation in dimension \(d=1\) and its multi-dimensional case are considered. In Section 4.2, the concepts of the stochastic integrals and Itô formula are given. Mathematical results related to stochastic calculus and the simulation of the SDE are presented. The concept of the Itô process and Itô formula are given. In Section 4.3, some preliminary definitions, existence and uniqueness related to the SDE are presented. The concept of the Ornstein-Uhlenbeck process is given. In Section 4.4, the probabilistic representations of the PDE are realized. The concept of the infinitesimal generator is presented. The technique of the localization procedure is developed. Some applications to linear elliptic PDEs and to linear parabolic PDEs are presented. In Section 4.5, some probabilistic formulas for the gradients are presented. In Section 4.6, some examples related with stochastic processes are given.NEWLINENEWLINEChapter 5 tackles the question of simulating SDEs. The Euler scheme for SDEs is developed. In Section 5.1, the concept of the Euler scheme associated with a SDE is given. It is proved that the Euler scheme is an Itô process. Some applications to computation of the diffusion expectation, the discretization error and the statistical error are presented. In Section 5.2, the strong convergence of the Euler approximation to the corresponding SDE in the sense of the \(L_p\)-norm is shown. In Section 5.3, the weak convergence at order 1 of the evaluation of the expectation by the Monte Carlo method using the Euler scheme is proved. Also the weak convergence for measurable functions is proved. In Section 5.4, an approximation by the Euler scheme of the expectation is developed. In Section 5.5, examples related with the strong and weak convergence are given.NEWLINENEWLINEChapter 6 studies the related statistical errors, the methods of variance reduction and the multi-level Monte Carlo methods. The statistical error that appears in the simulation of SDEs, in connection with the discretization step that is chosen for the process of approximation, is discussed. In Section 6.1, an asymptotic analysis of the number of simulations and time step is given. In Section 6.2 it is shown how the concentration inequalities for the Gaussian random variables can be applied to the Euler scheme. In Section 6.3, the so-called multi-level method is applied to the computation of the expectation for functionals of diffusion processes. The computational cost of this method is obtained. In Section 6.4, the randomized multi-level method to construct estimators of expectation of path functionals associated with SDEs is applied. In Section 6.5, variance reduction methods as the control variates and the importance sampling to reduce the size of confidence intervals are presented. In Section 6.6 some exercises are given.NEWLINENEWLINEIn Chapter 7, the notion of a solution to the backward SDE is defined. The link with semi-linear PDEs is established. Another interpretation of certain equations using branching diffusion is developed. The concepts of informal definition of forward and backward SDEs are presented. In Section 7.1, several examples coming from either deterministic or stochastic equations are described. In Section 7.2, the Feynman-Kac formulas are proved. In Section 7.3, the dynamic programming principles is applied to solve problems of the discretization of backward SDEs. In Sections 7.4 and 7.5, some probabilistic representations via branching processes are considered. In Section 7.6, some exercises are presented.NEWLINENEWLINEChapter 8 is devoted to study the resolution by the method of empirical regression. The error analysis is fully carried out, displaying the adjustment of the convergence parameters. Tools for efficient numerical solutions of the dynamic programming equation are developed and analysed. In Section 8.1, the difficulties of a naive approach are discussed. In Section 8.2, an approximation of conditional expectations by least squares methods is presented. In Section 8.3, an application to the resolution of the dynamic programming equation by empirical regression is shown. The chapter finishes with a section with exercises.NEWLINENEWLINEChapter 9 introduces the McKean-Vlasov stochastic equation. This equation is presented in Section 9.1. In Section 9.2, the existence and the uniqueness of the solution of the nonlinear diffusion equation is proved. In Section 9.3, the convergence in the \(L_1\)-norm of each SDE to the SDE, where the empirical measure is replaced by the distribution of the process, is proved.NEWLINENEWLINEIn the appendix, several useful inequalities are presented.