test
Search publications, data, projects and authors

Thesis

French

ID: <

10670/1.nmu01o

>

Where these data come from
Stratified Monte Carlo Methods for the simulation of Markov chains

Abstract

Monte Carlo methods are probabilistic schemes that use computers for solving various scientific problems with random numbers. The main disadvantage to this approach is the slow convergence. Many scientists are working hard to find techniques that may accelerate Monte Carlo simulations. This is the aim of some deterministic methods called quasi-Monte Carlo, where random points are replaced with special sets of points with enhanced uniform distribution. These methods do not provide confidence intervals that permit to estimate the errordone. In the present work, we are interested with random methods that reduce the variance of a Monte Carlo estimator : the stratification techniques consist of splitting the sampling area into strata where random samples are chosen. We focus here on applications of stratified methods for approximating Markov chains, simulating diffusion in materials, or solving fragmentationequations.In the first chapter, we present Monte Carlo methods in the framework of numerical quadrature, and we introduce the stratification strategies. We focus on two techniques : the simple stratification (MCS) and the Sudoku stratification (SS), where the points repartitions are similar to Sudoku grids. We also present quasi-Monte Carlo methods, where quasi-random pointsshare common features with stratified points.The second chapter describes the use of stratified algorithms for the simulation of Markov chains. We consider time-homogeneous Markov chains with one-dimensional discrete or continuous state space. We establish theoretical bounds for the variance of some estimator, in the case of a discrete state space, that indicate a variance reduction with respect to usual MonteCarlo. The variance of MCS and SS methods is of order 3/2, instead of 1 for usual MC. The results of numerical experiments, for one-dimensional or multi-dimensional, discrete or continuous state spaces show improved variances ; the order is estimated using linear regression.In the third chapter, we investigate the interest of stratified Monte Carlo methods for simulating diffusion in various non-stationary physical processes. This is done by discretizing time and performing a random walk at every time-step. We propose algorithms for pure diffusion, for convection-diffusion, and reaction-diffusion (Kolmogorov equation or Nagumo equation) ; we finally solve Burgers equation. In each case, the results of numerical tests show an improvement of the variance due to the use of stratified Sudoku sampling.The fourth chapter describes a stratified Monte Carlo scheme for simulating fragmentation phenomena. Through several numerical comparisons, we can see that the stratified Sudoku sampling reduces the variance of Monte Carlo estimates. We finally test a method for solving an inverse problem : knowing the evolution of the mass distribution, it aims to find a fragmentation kernel. In this case quasi-random points are used for solving the direct problem.

Your Feedback

Please give us your feedback and help us make GoTriple better.
Fill in our satisfaction questionnaire and tell us what you like about GoTriple!