This thesis examines the quantification of uncertainty in real-world engineering systems using the multilevel Monte Carlo method. It is often infeasible to use the traditional Monte Carlo method to investigate the impact of uncertainty because computationally it can be prohibitively expensive for complex systems. Therefore, the newer multilevel method is investigated and the cost of this method is analysed in the finite element framework. The Monte Carlo and multilevel Monte Carlo methods are compared for two prototypical examples: structural vibrations and buoyancy driven flows through porous media. In the first example, the impact of random mass density is quantified for structural vibration problems in several dimensions using the multilevel Monte Carlo method. Comparable eigenvalues and energy density approximations are found for the traditional Monte Carlo method and the multilevel Monte Carlo method, but for certain problems the expectation and variance of the quantities of interest can be computed over 100 times faster using the multilevel Monte Carlo method. It is also tractable to use the multilevel method for three dimensional structures, where the traditional Monte Carlo method is often prohibitively expensive. In the second example, the impact of uncertainty in buoyancy driven flows through porous media is quantified using the multilevel Monte Carlo method. Again, comparable results are obtained from the two methods for diffusion dominated flows and the multilevel method is orders of magnitude cheaper. The finite element models for this investigation are formulated carefully to ensure that spurious numerical artefacts are not added to the solution and are compared to an analytical model describing the long term sequestration of CO2 in the presence of a background flow. Additional cost reductions are achieved by solving the individual independent samples in parallel using the new podS library. This library schedules the Monte Carlo and multilevel Monte Carlo methods in parallel across different computer architectures for the two examples considered in this thesis. Nearly linear cost reductions are obtained as the number of processes is increased.

In biochemical systems, stochastic e↵ects can be caused by the presence of small numbers of certain reactant molecules. In this setting, discrete state-space and stochastic simulation approaches were proved to be more relevant than continuous state-space and deterministic ones. These stochastic models constitute the theory of stochastic reaction networks (SRNs). Furthermore, in some cases, the dynamics of fast and slow time scales can be well separated and this is characterized by what is called sti↵ness. For such problems, the existing discrete space-state stochastic path simulation methods, such as the stochastic simulation algorithm (SSA) and the explicit tau-leap method, can be very slow. Therefore, implicit tau-leap approxima- tions were developed to improve the numerical stability and provide more e cient simulation algorithms for these systems. One of the interesting tasks for SRNs is to approximate the expected values of some observables of the process at a certain fixed time T. This is can be achieved using Monte Carlo (MC) techniques. However, in a recent work, Anderson and Higham in 2013, proposed a more computationally e cient method which combines multi-level Monte Carlo (MLMC) technique with explicit tau-leap schemes. In this MSc thesis, we propose new fast stochastic algorithm, particularly designed 5 to address sti↵ systems, for approximating the expected values of some observables of SRNs. In fact, we take advantage of the idea of MLMC techniques and drift-implicit tau-leap approximation to construct a drift-implicit MLMC tau-leap estimator. In addition to accurately estimating the expected values of a given observable of SRNs at a final time T , our proposed estimator ensures the numerical stability with a lower cost than the MLMC explicit tau-leap algorithm, for systems including simultane- ously fast and slow species. The key contribution of our work is the coupling of two drift-implicit tau-leap paths, which is the basic brick for constructing our proposed drift-implicit MLMC tau-leap estimator. As an example of sti↵ problem, we used the decaying-dimerizing reaction as a test example to show the advantage of our drift-implicit method over the explicit one. Through our numerical experiments, we checked the convergence properties of our coupling algorithm and showed that our proposed estimator is outperforming the explicit MLMC estimator about three times in terms of computational work. We also illustrated in a second example how our drift-implicit MLMC tau-leap estimator can be forty times faster than the explicit MLMC.

Dans ce travail, nous nous intéressons aux estimateurs Multilevel Monte Carlo. Ces estimateurs vont apparaître sous leur forme standard, avec des poids et dans une forme randomisée. Nous allons rappeler leurs définitions et les résultats existants concernant ces estimateurs en termes de minimisation du coût de simulation. Nous allons ensuite montrer une loi forte des grands nombres et un théorème central limite. Après cela nous allons étudier deux cadres d'applications. Le premier est celui des diffusions avec schémas de discrétisation antithétiques, où nous allons étendre les estimateurs Multilevel aux estimateurs Multilevel avec poids. Le deuxième est le cadre nested, où nous allons nous concentrer sur les hypothèses d'erreur forte et faible. Nous allons conclure par l'implémentation de la forme randomisée des estimateurs Multilevel, en la comparant aux estimateurs Multilevel avec et sans poids. / In this work, we will focus on the Multilevel Monte Carlo estimators. These estimators will appear in their standard form, with weights and in their randomized form. We will recall the previous existing results concerning these estimators, in terms of minimization of the simulation cost. We will then show a strong law of large numbers and a central limit theorem.After that, we will focus on two application frameworks.The first one is the diffusions framework with antithetic discretization schemes, where we will extend the Multilevel estimators to Multilevel estimators with weights, and the second is the nested framework, where we will analyze the weak and the strong error assumptions. We will conclude by implementing the randomized form of the Multilevel estimators, comparing this to the Multilevel estimators with and without weights.

The Monte Carlo forward Euler method with uniform time stepping is the standard technique to compute an approximation of the expected payoff of a solution of an Itô SDE. For a given accuracy requirement TOL, the complexity of this technique for well behaved problems, that is the amount of computational work to solve the problem, is O(TOL-3). A new hybrid adaptive Monte Carlo forward Euler algorithm for SDEs with non-smooth coefficients and low regular observables is developed in this thesis. This adaptive method is based on the derivation of a new error expansion with computable leading-order terms. The basic idea of the new expansion is the use of a mixture of prior information to determine the weight functions and posterior information to compute the local error. In a number of numerical examples the superior efficiency of the hybrid adaptive algorithm over the standard uniform time stepping technique is verified. When a non-smooth binary payoff with either GBM or drift singularity type of SDEs is considered, the new adaptive method achieves the same complexity as the uniform discretization with smooth problems. Moreover, the new developed algorithm is extended to the MLMC forward Euler setting which reduces the complexity from O(TOL-3) to O(TOL-2(log(TOL))2). For the binary option case with the same type of Itô SDEs, the hybrid adaptive MLMC forward Euler recovers the standard multilevel computational cost O(TOL-2(log(TOL))2). When considering a higher order Milstein scheme, a similar complexity result was obtained by Giles using the uniform time stepping for one dimensional SDEs. The difficulty to extend Giles' Milstein MLMC method to the multidimensional case is an argument for the flexibility of our new constructed adaptive MLMC forward Euler method which can be easily adapted to this setting. Similarly, the expected complexity O(TOL-2(log(TOL))2) is reached for the multidimensional case and verified numerically.

A standard problem in the field of computational finance is that of pricing derivative securities. This is often accomplished by estimating an expected value of a functional of a stochastic process, defined by a stochastic differential equation (SDE). In such a setting the random sampling algorithm Monte Carlo (MC) is useful, where paths of the process are sampled. However, MC in its standard form (SMC) is inherently slow. Additionally, if the analytical solution to the underlying SDE is not available, a numerical approximation of the process is necessary, adding another layer of computational complexity to the SMC algorithm. Thus, the computational cost of achieving a certain level of accuracy of the estimation using SMC may be relatively high. In this thesis we introduce and review the theory of the SMC method, with and without the need of numerical approximation for path simulation. Two numerical methods for path approximation are introduced: the Euler–Maruyama method and Milstein's method. Moreover, we also introduce and review the theory of a relatively new (2008) MC method – the multilevel Monte Carlo (MLMC) method – which is only applicable when paths are approximated. This method boldly claims that it can – under certain conditions – eradicate the additional complexity stemming from the approximation of paths. With this in mind, we wish to see whether this claim holds when pricing a European call option, where the underlying stock process is modelled by geometric Brownian motion. We also want to compare the performance of MLMC in this scenario to that of SMC, with and without path approximation. Two numerical experiments are performed. The first to determine the optimal implementation of MLMC, a static or adaptive approach. The second to illustrate the difference in performance of adaptive MLMC and SMC – depending on the used numerical method and whether the analytical solution is available. The results show that SMC is inferior to adaptive MLMC if numerical approximation of paths is needed, and that adaptive MLMC seems to meet the complexity of SMC with an analytical solution. However, while the complexity of adaptive MLMC is impressive, it cannot quite compensate for the additional cost of approximating paths, ending up roughly ten times slower than SMC with an analytical solution.

This thesis focuses on the development and analysis of efficient simulation and inference techniques for Markovian pure jump processes with a view towards applications in dense communication networks. These techniques are especially relevant for modeling networks of smart devices —tiny, abundant microprocessors with integrated sensors and wireless communication abilities— that form highly complex and diverse communication networks. During 2010, the number of devices connected to the Internet exceeded the number of people on Earth: over 12.5 billion devices. By 2015, Cisco’s Internet Business Solutions Group predicts that this number will exceed 25 billion. The first part of this work proposes novel numerical methods to estimate, in an efficient and accurate way, observables from realizations of Markovian jump processes. In particular, hybrid Monte Carlo type methods are developed that combine the exact and approximate simulation algorithms to exploit their respective advantages. These methods are tailored to keep a global computational error below a prescribed global error tolerance and within a given statistical confidence level. Indeed, the computational work of these methods is similar to the one of an exact method, but with a smaller constant. Finally, the methods are extended to systems with a disparity of time scales. The second part develops novel inference methods to estimate the parameters of Markovian pure jump process. First, an indirect inference approach is presented, which is based on upscaled representations and does not require sampling. This method is simpler than dealing directly with the likelihood of the process, which, in general, cannot be expressed in closed form and whose maximization requires computationally intensive sampling techniques. Second, a forward-reverse Monte Carlo Expectation-Maximization algorithm is provided to approximate a local maximum or saddle point of the likelihood function of the parameters given a set of observations. The third part is devoted to applications in communication networks where also mean field or fluid approximations techniques, to substantially reduce the computational work of simulating large communication networks are explored. These methods aim to capture the global behaviour of systems with large state spaces by using an aggregate approximation, which is often described by means of a non-linear dynamical system.

Experimental design can be vital when experiments are resource-exhaustive and time-consuming. In this work, we carry out experimental design in the Bayesian framework. To measure the amount of information that can be extracted from the data in an experiment, we use the expected information gain as the utility function, which specifically is the expected logarithmic ratio between the posterior and prior distributions. Optimizing this utility function enables us to design experiments that yield the most informative data about the model parameters. One of the major difficulties in evaluating the expected information gain is that it naturally involves nested integration over a possibly high dimensional domain. We use the Multilevel Monte Carlo (MLMC) method to accelerate the computation of the nested high dimensional integral. The advantages are twofold. First, MLMC can significantly reduce the cost of the nested integral for a given tolerance, by using an optimal sample distribution among different sample averages of the inner integrals. Second, the MLMC method imposes fewer assumptions, such as the asymptotic concentration of posterior measures, required for instance by the Laplace approximation (LA). We test the MLMC method using two numerical examples. The first example is the design of sensor deployment for a Darcy flow problem governed by a one-dimensional Poisson equation. We place the sensors in the locations where the pressure is measured, and we model the conductivity field as a piecewise constant random vector with two parameters. The second one is chemical Enhanced Oil Recovery (EOR) core flooding experiment assuming homogeneous permeability. We measure the cumulative oil recovery, from a horizontal core flooded by water, surfactant and polymer, for different injection rates. The model parameters consist of the endpoint relative permeabilities, the residual saturations and the relative permeability exponents for the three phases: water, oil and microemulsions. We also compare the performance of the MLMC to the LA and the direct Double Loop Monte Carlo (DLMC). In fact, we show that, in the case of the aforementioned examples, MLMC combined with LA turns to be the best method in terms of computational cost.

In this thesis, we center our research around the analytical approximation of American put options with the Multilevel Monte Carlo simulation approach. The focus lies on reducing the computational complexity of estimating an expected value arising from a stochastic differential equation. Numerical results showcase that the simulations are consistent with the theoretical order of convergence of Monte Carlo simulations. The approximations are accurate and considerately more computationally efficient than the standard Monte Carlo simulation method.

Recent debiasing techniques are incorporated into the Ensemble Kalman-Bucy Filter (EnKBF). Specifically, a novel double randomization is applied. The EnKBF is a Monte Carlo (MC) method that approximates the Kalman-Bucy Filter (KBF), which in turn can be seen as the continuous-time version of the celebrated discrete-time Kalman Filter (KF). The KF is a method that combines sequential observations with an underlying dynamics model to predict the state of the quantity of interest. Our interest in the EnKBF comes from its relevance in high dimensions, where it overcomes the curse of dimensionality and outperforms other standard methods like the Particle Filter. We will consider debiasing techniques (also termed unbiased estimators) in order to improve the error-to-cost rate. Unbiased estimators are variance reduction techniques that produce unbiased and finite variance estimators. Applications of the EnKBF are numerous, from atmospheric sciences, numerical weather prediction, finance, machine learning, among others. Thus, improving the EnKBF is of interest. Numerical tests are done in order to evaluate the cost and the error-to-cost rate of the algorithm, where we consider Ornstein-Uhlenbeck processes. Specifically, a numerical comparison with the Multilevel Ensemble Kalman-Bucy Filter (MLEnKBF) is made using two different unbiased estimators, the coupled sum and the single term estimators. Additionally, we test two variants of the EnKBF, the Vanilla EnKBF, and the Deterministic EnKBF. We find that the error-to-cost rate is virtually the same, although the cost of the unbiased EnKBF is much higher.

This thesis studies novel and efficient computational sampling methods for appli- cations in three types of stochastic inversion problems: seismic waveform inversion, filtering problems, and static parameter estimation. A primary goal of a large class of seismic inverse problems is to detect parameters that characterize an earthquake. We are interested to solve this task by analyzing the full displacement time series at a given set of seismographs, but approaching the full waveform inversion with the standard Monte Carlo (MC) method is prohibitively expensive. So we study tools that can make this computation feasible. As part of the inversion problem, we must evaluate the misfit between recorded and synthetic seismograms efficiently. We employ as misfit function the Wasserstein metric origi- nally suggested to measure the distance between probability distributions, which is becoming increasingly popular in seismic inversion. To compute the expected values of the misfits, we use a sampling algorithm called Multi-Level Monte Carlo (MLMC). MLMC performs most of the sampling at a coarse space-time resolution, with only a few corrections at finer scales, without compromising the overall accuracy. We further investigate the Wasserstein metric and MLMC method in the context of filtering problems for partially observed diffusions with observations at periodic time intervals. Particle filters can be enhanced by considering hierarchies of discretizations to reduce the computational effort to achieve a given tolerance. This methodology is called Multi-Level Particle Filter (MLPF). However, particle filters, and consequently MLPFs, suffer from particle ensemble collapse, which requires the implementation of a resampling step. We suggest for one-dimensional processes a resampling procedure based on optimal Wasserstein coupling. We show that it is beneficial in terms of computational costs compared to standard resampling procedures. Finally, we consider static parameter estimation for a class of continuous-time state-space models. Unbiasedness of the gradient of the log-likelihood is an important property for gradient ascent (descent) methods to ensure their convergence. We propose a novel unbiased estimator of the gradient of the log-likelihood based on a double-randomization scheme. We use this estimator in the stochastic gradient ascent method to recover unknown parameters of the dynamics.