A Random Walk on Rectangles Algorithm

In this article, we introduce an algorithm that simulates efficiently the first exit time and position from a rectangle (or a parallelepiped) for a Brownian motion that starts at any point inside. This method provides an exact way to simulate the first exit time and position from any polygonal domain and then to solve some Dirichlet problems, whatever the dimension. This method can be used as a replacement or complement of the method of the random walk on spheres and can be easily adapted to deal with Neumann boundary conditions or Brownian motion with a constant drift. AMS 2000 Subject Classification 60C05, 65N     

New Brownian bridge construction in quasi-Monte Carlo methods for computational finance

Quasi-Monte Carlo (QMC) methods have been playing an important role for high-dimensional problems in computational finance. Several techniques, such as the Brownian bridge (BB) and the principal component analysis, are often used in QMC as possible ways to improve the performance of QMC. This paper proposes a new BB construction, which enjoys some interesting properties that appear useful in QMC methods. The basic idea is to choose the new step of a Brownian path in a certain criterion such that it maximizes the variance explained by the new variable while holding all previously chosen steps fixed. It turns out that using this new construction, the first few variables are more “important” (in the sense of explained variance) than those in the ordinary BB construction, while the cost of the generation is still linear in dimension. We present empirical studies of the proposed algorithm for pricing high-dimensional Asian options and American options, and demonstrate the usefulness of the new BB.     

Global optimization by multilevel search

A new approach to the global optimization of functions with extremely rugged graphs is introduced. This multilevel search method is both an algorithm and a meta-algorithm, a logic for regulating optimization done by other algorithms. First, it is examined in the one-dimensional case theoretically and through simple examples. Then, to deal with higher dimensions, multilevel search is combined with the Monte Carlo method; this hybrid algorithm is tested on standard problems and is found to perform extremely well for a derivative-free method.     

Efficiently pricing barrier options in a Markov-switching framework

An efficient Monte Carlo simulation for the pricing of barrier options in a Markov-switching model is presented. Compared to a brute-force approach, relying on the simulation of discretized trajectories, the presented algorithm simulates the underlying stock price process only at state changes and at maturity. Given these pieces of information, option prices are evaluated using the probability of Brownian bridges not to fall below some threshold level. It is illustrated how two methods of variance reduction, control variates and antithetic variates, further improve the algorithm. In a small case study, the algorithm is applied to the pricing of options with the EuroStoxx 50 as underlying.     

Asymptotics of an Efficient Monte Carlo Estimation for the Transition Density of Diffusion Processes

Discretized simulation is widely used to approximate the transition density of discretely observed diffusions. A recently proposed importance sampler, namely modified Brownian bridge, has gained much attention for its high efficiency relative to other samplers. It is unclear for this sampler, however, how to balance the trade-off between the number of imputed values and the number of Monte Carlo simulations under a given computing resource. This paper provides an asymptotically efficient allocation of computing resource to the importance sampling approach with a modified Brownian bridge as importance sampler. The optimal trade-off is established by investigating two types of errors: Euler discretization error and Monte Carlo error. The main results are illustrated with two simulated examples.      

Adaptive Sequential Monte Carlo for Multiple Changepoint Analysis

Process monitoring and control requires the detection of structural changes in a data stream in real time. This article introduces an efficient sequential Monte Carlo algorithm designed for learning unknown changepoints in continuous time. The method is intuitively simple: new changepoints for the latest window of data are proposed by conditioning only on data observed since the most recent estimated changepoint, as these observations carry most of the information about the current state of the process. The proposed method shows improved performance over the current state of the art. Another advantage of the proposed algorithm is that it can be made adaptive, varying the number of particles according to the apparent local complexity of the target changepoint probability distribution. This saves valuable computing time when changes in the changepoint distribution are negligible, and enables rebalancing of the importance weights of existing particles when a significant change in the target distribution is encountered. The plain and adaptive versions of the method are illustrated using the canonical continuous time changepoint problem of inferring the intensity of an inhomogeneous Poisson process, although the method is generally applicable to any changepoint problem. Performance is demonstrated using both conjugate and nonconjugate Bayesian models for the intensity. Appendices to the article are available online, illustrating the method on other models and applications.     

Global optimization by random perturbation of the gradient method with a fixed parameter

The paper deals with the global minimization of a differentiable cost function mapping a ball of a finite dimensional Euclidean space into an interval of real numbers. It is established that a suitable random perturbation of the gradient method with a fixed parameter generates a bounded minimizing sequence and leads to a global minimum: the perturbation avoids convergence to local minima. The stated results suggest an algorithm for the numerical approximation of global minima: experiments are performed for the problem of fitting a sum of exponentials to discrete data and to a nonlinear system involving about 5000 variables. The effect of the random perturbation is examined by comparison with the purely deterministic gradient method.     

A Monte Carlo study of old and new frontier methods for efficiency measurement

This study presents the results of an extensive Monte Carlo experiment to compare different methods of efficiency analysis. In addition to traditional parametric–stochastic and nonparametric–deterministic methods recently developed robust nonparametric–stochastic methods are considered. The experimental design comprises a wide variety of situations with different returns-to-scale regimes, substitution elasticities and outlying observations. As the results show, the new robust nonparametric–stochastic methods should not be used without cross-checking by other methods like stochastic frontier analysis or data envelopment analysis. These latter methods appear quite robust in the experiments.     

水滴清除气溶胶过程的随机算法和数值模拟

气溶胶尺度分布的时间演变可量化气溶胶的湿沉降过程,它在数学上可由考虑湿沉降的通用动力学方程来描述．该方程为一典型的部分积分微分方程,与气溶胶尺度分布和雨滴尺度分布均相关,且由于需要考虑Brown扩散、拦截和惯性碰撞等湿沉降机制而使得清除系数模型非常复杂,普通的数值方法难以求解．为此发展了一种新的多重Monte Carlo算法,以求解考虑湿沉降的通用动力学方程,并用于模拟实际环境中气溶胶的湿沉降．对于对数正态分布的气溶胶尺度分布和雨滴尺度分布, 多重Monte Carlo算法进行的数值模拟表明, 雨滴几何平均尺度越小, 雨滴几何标准偏差越小,越有利于小尺度和中等尺度气溶胶的湿去除,而稍微不利于大尺度气溶胶的湿去除．     

A Monte Carlo Method for the Simulation of First Passage Times of Diffusion Processes

A reliable Monte Carlo method for the evaluation of first passage times of diffusion processes through boundaries is proposed. A nested algorithm that simulates the first passage time of a suitable tied-down process is introduced to account for undetected crossings that may occur inside each discretization interval of the stochastic differential equation associated to the diffusion. A detailed analysis of the performances of the algorithm is then carried on both via analytical proofs and by means of some numerical examples. The advantages of the new method with respect to a previously proposed numerical-simulative method for the evaluation of first passage times are discussed. Analytical results on the distribution of tied-down diffusion processes are proved in order to provide a theoretical justification of the Monte Carlo method.     

应用结构异质性阈值模型定位阈值性状基因位点 : 仿真研究(英文)

蒙特卡罗仿真研究表明 :对处理在基因定位阈值性状中出现的超离中趋势现象 (结构异质性 ) ,我们提出的结构异质性模型是一个高效的统计方法 .它表现在高效率的统计检验、准确的参数估计和基因定位等方面 .病态或奇异费歇信息矩阵是在基因连锁定位分析中的一个突出的算法问题 ,仿真数据显示它们的发生率可以达到 2 8% .我们提出的应用奇异根分解方法可以有效地解决这一算法问题 .对比常规阈值模型 ,结构异质性阈值模型有较高的算法稳定性 .     

Derivative-free Greeks for the Barndorff-Nielsen and Shephard stochastic volatility model

We derive derivative-free formulas for the Delta and other Greeks of options written on an asset modelled by a geometric Brownian motion with stochastic volatility of Barndorff-Nielsen and Shephard type. The method applies the Malliavin calculus in Wiener space which moves differentiation of the payoff function of the option to a random weight function. Our method paves the way for simple Monte Carlo approaches, illustrated by several numerical examples.     

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.     

How do path generation methods affect the accuracy of quasi-Monte Carlo methods for problems in finance?

Quasi-Monte Carlo (QMC) methods are important numerical tools in computational finance. Path generation methods (PGMs), such as Brownian bridge and principal component analysis, play a crucial role in QMC methods. Their effectiveness, however, is problem-dependent. This paper attempts to understand how a PGM interacts with the underlying function and affects the accuracy of QMC methods. To achieve this objective, we develop efficient methods to assess the impact of PGMs. The first method is to exploit a quadratic approximation of the underlying function and to analyze the effective dimension and dimension distribution (which can be done analytically). The second method is to carry out a QMC error analysis on the quadratic approximation, establishing an explicit relationship between the QMC error and the PGM. Equalities and bounds on the QMC errors are established, in which the effect of the PGM is separated from the effect of the point set (in a similar way to the Koksma–Hlawka inequality). New measures for quantifying the accuracy of QMC methods combining with PGMs are introduced. The usefulness of the proposed methods is demonstrated on two typical high-dimensional finance problems, namely, the pricing of mortgage-backed securities and Asian options (with zero strike price). It is found that the success or failure of PGMs that do not take into account the underlying functions (such as the standard method, Brownian bridge and principal component analysis) strongly depends on the problem and the model parameters. On the other hand, the PGMs that take into account the underlying function are robust and powerful. The investigation presents new insight on PGMs and provides constructive guidance on the implementation and the design of new PGMs and new QMC rules.     

Bayesian Monte Carlo estimation for profile hidden Markov models

Hidden Markov models are used as tools for pattern recognition in a number of areas, ranging from speech processing to biological sequence analysis. Profile hidden Markov models represent a class of so-called “left–right” models that have an architecture that is specifically relevant to classification of proteins into structural families based on their amino acid sequences. Standard learning methods for such models employ a variety of heuristics applied to the expectation-maximization implementation of the maximum likelihood estimation procedure in order to find the global maximum of the likelihood function. Here, we compare maximum likelihood estimation to fully Bayesian estimation of parameters for profile hidden Markov models with a small number of parameters. We find that, relative to maximum likelihood methods, Bayesian methods assign higher scores to data sequences that are distantly related to the pattern consensus, show better performance in classifying these sequences correctly, and continue to perform robustly with regard to misspecification of the number of model parameters. Though our study is limited in scope, we expect our results to remain relevant for models with a large number of parameters and other types of left–right hidden Markov models.     

Second order probabilistic parametrix method for unbiased simulation of stochastic differential equations

In this article, following the paradigm of bias–variance trade-off philosophy, we derive parametrix expansions of order two, based on the Euler–Maruyama scheme with random partitions, for the purpose of constructing an unbiased simulation method for multidimensional stochastic differential equations. These formulas lead to Monte Carlo simulation methods which can be easily parallelized. The second order method proposed here requires further regularity of coefficients in comparison with the first order method but achieves finite moments even when Poisson sampling is used for the partitions, in contrast to Andersson and Kohatsu-Higa (2017). Moreover, using an exponential scaling technique one achieves an unbiased simulation method which resembles a space importance sampling technique which significantly improves the efficiency of the proposed method. A hint of how to derive higher order expansions is also presented.     

Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints

In this paper, we consider a class of stochastic mathematical programs with equilibrium constraints introduced by Birbil et al. (Math Oper Res 31:739–760, 2006). Firstly, by means of a Monte Carlo method, we obtain a nonsmooth discrete approximation of the original problem. Then, we propose a smoothing method together with a penalty technique to get a standard nonlinear programming problem. Some convergence results are established. Moreover, since quasi-Monte Carlo methods are generally faster than Monte Carlo methods, we discuss a quasi-Monte Carlo sampling approach as well. Furthermore, we give an example in economics to illustrate the model and show some numerical results with this example. The first author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science and SRF for ROCS, SEM. The second author’s work was supported in part by the United Kingdom Engineering and Physical Sciences Research Council grant. The third author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

Brownian Processes for Monte Carlo Integration on Compact Lie Groups

This article proposes a Monte Carlo approach for the evaluation of integrals of smooth functions defined on compact Lie groups. The approach is based on the ergodic property of Brownian processes in compact Lie groups. The article provides an elementary proof of this property and obtains the following results. It gives the rate of almost sure convergence of time averages along with a “large deviations” type upper bound and a central limit theorem. It derives probability of error bounds for uniform approximation of the paths of Brownian processes using two numerical schemes. Finally, it describes generalization to compact Riemannian manifolds.     

Study and modelling of two apple quality attributes: the soluble solids content and the firmness

Recently, the basic dynamics of fruit characteristics have been modelled using a stochastic approach. The time evolution of apple quality attributes was represented by means of a system of differential equations in which the initial conditions and model parameters are both random. In this work, a complete study of two apple quality attributes, the soluble solids content and the firmness, is carried out. For each of these characteristics, the system of differential equations is linear and the state variables and the parameters are represented as random variables with their statistical properties (mean values, variances, covariances, joint probability density function) known at the initial time. The dynamic behaviour of these statistical properties is analysed. The variance propagation algorithm is used to obtain an analytical expression of the dynamic behaviour of the mean value, the variance, the covariance and the probability density function. A Monte Carlo method and the Latin hypercube method were developed to obtain a numerical expression of the dynamic behaviour of these statistical quantities and particularly to follow the time evolution of joint probability density function which represents one but the best mean to characterize random phenomena linked with fruit quality attributes.     

Stochastic Domain Decomposition for Time Dependent Adaptive Mesh Generation

The efficient generation of meshes is an important component in the numerical solution of problems in physics and engineering. Of interest are situations where global mesh quality and a tight coupling to the solution of the physical partial differential equation (PDE) is important. We consider parabolic PDE mesh generation and present a method for the construction of adaptive meshes in two spatial dimensions using stochastic domain decomposition that is suitable for an implementation in a multi- or many-core environment. Methods for mesh generation on periodic domains are also provided. The mesh generator is coupled to a time dependent physical PDE and the system is evolved using an alternating solution procedure. The method uses the stochastic representation of the exact solution of a parabolic linear mesh generator to find the location of an adaptive mesh along the (artificial) subdomain interfaces. The deterministic evaluation of the mesh over each subdomain can then be obtained completely independently using the probabilistically computed solutions as boundary conditions. A small scaling study is provided to demonstrate the parallel performance of this stochastic domain decomposition approach to mesh generation. We demonstrate the approach numerically and compare the mesh obtained with the corresponding single domain mesh using a representative mesh quality measure.