Convergence of the Stochastic Euler Scheme for Locally Lipschitz Coefficients

Stochastic differential equations are often simulated with the Monte Carlo Euler method. Convergence of this method is well understood in the case of globally Lipschitz continuous coefficients of the stochastic differential equation. However, the important case of superlinearly growing coefficients has remained an open question. The main difficulty is that numerically weak convergence fails to hold in many cases of superlinearly growing coefficients. In this paper we overcome this difficulty and establish convergence of the Monte Carlo Euler method for a large class of one-dimensional stochastic differential equations whose drift functions have at most polynomial growth.     

Monte Carlo method via a numerical algorithm to solve a parabolic problem

This paper is intended to provide a numerical algorithm consisted of the combined use of the finite difference method and Monte Carlo method to solve a one-dimensional parabolic partial differential equation. The numerical algorithm is based on the discretize governing equations by finite difference method. Due to the application of the finite difference method, a large sparse system of linear algebraic equations is obtained. An approach of Monte Carlo method is employed to solve the linear system. Numerical tests are performed in order to show the efficiency and accuracy of the present work.     

Parameter estimation in stochastic differential equations with Markov chain Monte Carlo and non-linear Kalman filtering

This paper is concerned with parameter estimation in linear and non-linear Itô type stochastic differential equations using Markov chain Monte Carlo (MCMC) methods. The MCMC methods studied in this paper are the Metropolis–Hastings and Hamiltonian Monte Carlo (HMC) algorithms. In these kind of models, the computation of the energy function gradient needed by HMC and gradient based optimization methods is non-trivial, and here we show how the gradient can be computed with a linear or non-linear Kalman filter-like recursion. We shall also show how in the linear case the differential equations in the gradient recursion equations can be solved using the matrix fraction decomposition. Numerical results for simulated examples are presented and discussed in detail.     

Multi-level Monte Carlo Finite Element method for elliptic PDEs with stochastic coefficients

In Monte Carlo methods quadrupling the sample size halves the error. In simulations of stochastic partial differential equations (SPDEs), the total work is the sample size times the solution cost of an instance of the partial differential equation. A Multi-level Monte Carlo method is introduced which allows, in certain cases, to reduce the overall work to that of the discretization of one instance of the deterministic PDE. The model problem is an elliptic equation with stochastic coefficients. Multi-level Monte Carlo errors and work estimates are given both for the mean of the solutions and for higher moments. The overall complexity of computing mean fields as well as k-point correlations of the random solution is proved to be of log-linear complexity in the number of unknowns of a single Multi-level solve of the deterministic elliptic problem. Numerical examples complete the theoretical analysis.     

Parallel Markov chain Monte Carlo Simulation by Pre-Fetching

In recent years, parallel processing has become widely available to researchers. It can be applied in an obvious way in the context of Monte Carlo simulation, but techniques for “parallelizing” Markov chain Monte Carlo (MCMC) algorithms are not so obvious, apart from the natural approach of generating multiple chains in parallel. Although generation of parallel chains is generally the easiest approach, in cases where burn-in is a serious problem, it is often desirable to use parallelization to speed up generation of a single chain. This article briefly discusses some existing methods for parallelization of MCMC algorithms, and proposes a new “pre-fetching” algorithm to parallelize generation of a single chain.     

Coarse-Grained Langevin Approximations and Spatiotemporal Acceleration for Kinetic Monte Carlo Simulations of Diffusion of Interacting Particles

Kinetic Monte Carlo methods provide a powerful computational tool for the simulation of microscopic processes such as the diffusion of interacting particles on a surface, at a detailed atomistic level. However such algorithms are typically computationatly expensive and are restricted to fairly small spatiotemporal scales. One approach towards overcoming this problem was the development of coarse-grained Monte Carlo algorithms. In recent literature, these methods were shown to be capable of efficiently describing much larger length scales while still incorporating information on microscopic interactions and fluctuations. In this paper, a coarse-grained Langevin system of stochastic differential equations as approximations of diffusion of interacting particles is derived, based on these earlier coarse-grained models. The authors demonstrate the asymptotic equivalence of transient and long time behavior of the Langevin approximation and the underlying microscopic process, using asymptotics methods such as large deviations for interacting particles systems, and furthermore, present corresponding numerical simulations, comparing statistical quantities like mean paths, auto correlations and power spectra of the microscopic and the approximating Langevin processes. Finally, it is shown that the Langevin approximations presented here are much more computationally efficient than conventional Kinetic Monte Carlo methods, since in addition to the reduction in the number of spatial degrees of freedom in coarse-grained Monte Carlo methods, the Langevin system of stochastic differential equations allows for multiple particle moves in a single timestep.     

Numerical comparison of three stochastic methods for nonlinear PN junction problems

We apply the Monte Carlo, stochastic Galerkin, and stochastic collocation methods to solving the drift-diffusion equations coupled with the Poisson equation arising in semiconductor devices with random rough surfaces. Instead of dividing the rough surface into slices, we use stochastic mapping to transform the original deterministic equations in a random domain into stochastic equations in the corresponding deterministic domain. A finite element discretization with the help of AFEPack is applied to the physical space, and the equations obtained are solved by the approximate Newton iterative method. Comparison of the three stochastic methods through numerical experiment on different PN junctions are given. The numerical results show that, for such a complicated nonlinear problem, the stochastic Galerkin method has no obvious advantages on efficiency except accuracy over the other two methods, and the stochastic collocation method combines the accuracy of the stochastic Galerkin method and the easy implementation of the Monte Carlo method.     

Numerical simulation of a strongly nonlinear Ait-Sahalia-type interest rate model

We are interested in the strong convergence of Euler-Maruyama type approximations to the solution of a class of stochastic differential equations models with highly nonlinear coefficients, arising in mathematical finance. Results in this area can be used to justify Monte Carlo simulations for calibration and valuation. The equations that we study include the Ait-Sahalia type model of the spot interest rate, which has a polynomial drift term that blows up at the origin and a diffusion term with superlinear growth. After establishing existence and uniqueness for the solution, we show that an appropriate implicit numerical method preserves positivity and boundedness of moments, and converges strongly to the true solution.     

Pricing and hedging of financial derivatives using a posteriori error estimates and adaptive methods for stochastic differential equations

The efficient and accurate calculation of sensitivities of the price of financial derivatives with respect to perturbations of the parameters in the underlying model, the so-called ‘Greeks’, remains a great practical challenge in the derivative industry. This is true regardless of whether methods for partial differential equations or stochastic differential equations (Monte Carlo techniques) are being used. The computation of the ‘Greeks’ is essential to risk management and to the hedging of financial derivatives and typically requires substantially more computing time as compared to simply pricing the derivatives. Any numerical algorithm (Monte Carlo algorithm) for stochastic differential equations produces a time-discretization error and a statistical error in the process of pricing financial derivatives and calculating the associated ‘Greeks’. In this article we show how a posteriori error estimates and adaptive methods for stochastic differential equations can be used to control both these errors in the context of pricing and hedging of financial derivatives. In particular, we derive expansions, with leading order terms which are computable in a posteriori form, of the time-discretization errors for the price and the associated ‘Greeks’. These expansions allow the user to simultaneously first control the time-discretization errors in an adaptive fashion, when calculating the price, sensitivities and hedging parameters with respect to a large number of parameters, and then subsequently to ensure that the total errors are, with prescribed probability, within tolerance.     

A random differential transform method: Theory and applications

In this article, a Differential Transform Method (DTM) based on the mean fourth calculus is developed to solve random differential equations. An analytical mean fourth convergent series solution is found for a nonlinear random Riccati differential equation by using the random DTM. Besides obtaining the series solution of the Riccati equation, we provide approximations of the main statistical functions of the stochastic solution process such as the mean and variance. These approximations are compared to those obtained by the Euler and Monte Carlo methods. It is shown that this method applied to the random Riccati differential equation is more efficient than the two above mentioned methods.     

Artificial Monte Carlo interactions for solving some linear problems

A method of artificial interaction for Monte Carlo solution of ordinary differential equations with respect to probability measures is proposed. Under some conditions this method is advantageous over the standard method. A theoretical comparison of the complexity of the corresponding algorithms is provided. Also, results of numerical experiments are discussed.     

Optimization of the quasi-Monte Carlo algorithm for solving systems of linear algebraic equations

An interesting conclusion about error reduction of the modified quasi-Monte Carlo method for solving systems of linear algebraic equations is suggested. The Monte Carlo method is compared with the quasi-Monte Carlo method and its modification. The optimal choice of the parameters of the Markov chain for the modified Monte Carlo method applied to solving systems of linear equations is substantiated.     

New Monte Carlo Algorithms for Estimating Probability Moments of Criticality Parameters for a Scattering Process with Multiplication in Stochastic Media

By analogy with Kellogg’s method, a Monte Carlo algorithm well suited for parallelization was constructed for estimating probability moments of the leading eigenvalue of the particle transport equation with multiplication in a random medium. For this purpose, a randomized homogenization method was developed by applying the theory of small perturbations and the diffusion approximation. Test computations were performed for a one-group spherically symmetric model system. They revealed that the results produced by two methods are in satisfactory agreement.     

Solution of partial differential equations by a modified random walk

A new Monte Carlo technique is applied to solve difference equations of elliptic and parabolic partial differential equations with given boundary values. Fixed random walk is extended to modified random walk, whereby a random walk is made on a maximum square. The average number of steps and the computational time in a modified random walk is much less than in a fixed random walk. Numerical examples support the utility of this method.     

Moment equation methods for nonlinear stochastic systems

One method of approaching models represented by systems of stochastic ordinary differential equations is to consider the moment equations. This approach can be far more efficient than a Monte Carlo simulation or a finite-difference solution of the associated Fokker-Plank equation. However, a nonlinear system generates an infinite hierarchy of moment equations, which requires the adoption of some hierarchy truncation technique to facilitate solution. This paper considers a method of hierarchy truncation, based on the quasi-moments of the state-variables.     

Playdoh: A lightweight Python library for distributed computing and optimisation

Parallel computing is now an essential paradigm for high performance scientific computing. Most existing hardware and software solutions are expensive or difficult to use. We developed Playdoh, a Python library for distributing computations across the free computing units available in a small network of multicore computers. Playdoh supports independent and loosely coupled parallel problems such as global optimisations, Monte Carlo simulations and numerical integration of partial differential equations. It is designed to be lightweight and easy to use and should be of interest to scientists wanting to turn their lab computers into a small cluster at no cost.     

Quasi-Monte Carlo Sampling for Solving Partial Differential Equations by Deep Neural Networks

Solving partial differential equations in high dimensions by deep neural networks has brought significant attentions in recent years. In many scenarios, the loss function is defined as an integral over a high-dimensional domain. Monte-Carlo method, together with a deep neural network, is used to overcome the curse of dimensionality, while classical methods fail. Often, a neural network outperforms classical numerical methods in terms of both accuracy and efficiency. In this paper, we propose to use quasi-Monte Carlo sampling, instead of Monte-Carlo method to approximate the loss function. To demonstrate the idea, we conduct numerical experiments in the framework of deep Ritz method. For the same accuracy requirement, it is observed that quasi-Monte Carlo sampling reduces the size of training data set by more than two orders of magnitude compared to that of Monte-Carlo method. Under some assumptions, we can prove that quasi-Monte Carlo sampling together with the deep neural network generates a convergent series with rate proportional to the approximation accuracy of quasi-Monte Carlo method for numerical integration. Numerically the fitted convergence rate is a bit smaller, but the proposed approach always outperforms Monte Carlo method.     

A Monte Carlo method for the Broadwell model with relaxation

A Monte Carlo method is proposed for numerical solution of the Broadwell model. Developing a probabilistic interpretation of the equations, the transport and collision parts are treated separately in the method. Particles are advected according to their velocities and collisions are performed between randomly chosen particles. We numerically test the algorithm for a variety of examples. In particular we are interested in situations which generate structures that have nonsmooth fronts. Our simulations show that this Monte Carlo method is capable of capturing the nonlinear regime in presence of shocks and interactions. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Multicanonical MCMC for sampling rare events: an illustrative review

Multicanonical MCMC (Multicanonical Markov Chain Monte Carlo; Multicanonical Monte Carlo) is discussed as a method of rare event sampling. Starting from a review of the generic framework of importance sampling, multicanonical MCMC is introduced, followed by applications in random matrices, random graphs, and chaotic dynamical systems. Replica exchange MCMC (also known as parallel tempering or Metropolis-coupled MCMC) is also explained as an alternative to multicanonical MCMC. In the last section, multicanonical MCMC is applied to data surrogation; a successful implementation in surrogating time series is shown. In the appendix, calculation of averages and normalizing constant in an exponential family, phase coexistence, simulated tempering, parallelization, and multivariate extensions are discussed.     

An efficient alternating direction method of multipliers for optimal control problems constrained by random Helmholtz equations

Based on the alternating direction method of multipliers (ADMM), we develop three numerical algorithms incrementally for solving the optimal control problems constrained by random Helmholtz equations. First, we apply the standard Monte Carlo technique and finite element method for the random and spatial discretization, respectively, and then ADMM is used to solve the resulting system. Next, combining the multi-modes expansion, Monte Carlo technique, finite element method, and ADMM, we propose the second algorithm. In the third algorithm, we preprocess certain quantities before the ADMM iteration, so that nearly no random variable is in the inner iteration. This algorithm is the most efficient one and is easy to implement. The error estimates of these three algorithms are established. The numerical experiments verify the efficiency of our algorithms.