Search

This paper analyses a novel two-step Monte Carlo simulation algorithm to estimate the weighted volume of a polytope of the form A ⁢ z ≤ T {Az\leq T} . The essential idea is to partition the columns of A into two categories – a lightweight category and a heavyweight category. Simulation is done in a two-step manner where, for every sample of the lightweight category variables we use multiple samples of the heavyweight category variables. Thus, the heavyweight category variables are oversampled with respect to the lightweight category variables and increasing samples of the heavyweight variables at the expense of the lightweight variables will lead to a more efficient Monte Carlo method. In this paper we present a fast heuristic approximate for estimating the optimal oversampling ratio and substantiate with experimental results which confirm the effectiveness of the method. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new algorithm for estimating the lower bounds for the star discrepancy of any arbitrary point sets in [ 0 , 1 ] s . Computing the exact star discrepancy is known to be an NP-hard problem, so we have been looking for effective approximation algorithms. The star discrepancy can be thought of as the maximum of a function called the local discrepancy, and we will develop approximation algorithms to maximize this function. Our algorithm is analogous to the random walk algorithm described in one of our previous papers [M. Alsolami and M. Mascagni, A random walk algorithm to estimate a lower bound of the star discrepancy, Monte Carlo Methods Appl.28 (2022), 4, 341–348.]. We add a statistical technique to the random walk algorithm by implementing the Metropolis algorithm in random walks on each chosen dimension to accept or reject this movement. We call this Metropolis random walk algorithm. In comparison to all previously known techniques, our new algorithm is superior, especially in high dimensions. Also, it can quickly determine the precise value of the star discrepancy in most of our data sets of various sizes and dimensions, or at least the lower bounds of the star discrepancy. [ABSTRACT FROM AUTHOR]

In many Monte Carlo applications, one can substitute the use of pseudorandom numbers with quasirandom numbers and achieve improved convergence. This is because quasirandom numbers are more uniform that pseudorandom numbers. The most common measure of that uniformity is the star discrepancy. Moreover, the main error bound in quasi-Monte Carlo methods, called the Koksma–Hlawka inequality, has the star discrepancy in the formulation. A difficulty with this bound is that computing the star discrepancy is very costly. The star discrepancy can be computed by evaluating a function called the local discrepancy at a number of points. The supremum of these local discrepancy values is the star discrepancy. If we have a point set in [ 0 , 1 ] s with N members, we need to compute the local discrepancy at N s points. In fact, computing star discrepancy is NP-hard. In this paper, we will consider an approximate algorithm for a lower bound on the star discrepancy based on using a random walk through some of the N s points. This approximation is much less expensive that computing the star discrepancy, but still accurate enough to provide information on convergence. Our numerical results show that the random walk algorithm has the same convergence rate as the Monte Carlo method, which is O (N - 1 2 ). [ABSTRACT FROM AUTHOR]

Randomized scalable vector algorithms for calculation of matrix iterations and solving extremely large linear algebraic equations are developed. Among applications presented in this paper are randomized iterative methods for large linear systems of algebraic equations governed by M-matrices. The crucial idea of the randomized method is that the iterations are performed by sampling random columns only, thus avoiding not only matrix-matrix but also matrix-vector multiplications. The suggested vector randomized methods are highly efficient for solving linear equations of high dimension, the computational cost depends only linearly on the dimension. [ABSTRACT FROM AUTHOR]

We suggest in this paper a global Random Walk on Spheres (gRWS) method for solving transient boundary value problems, which, in contrast to the classical RWS method, calculates the solution in any desired family of m prescribed points. The method uses only N trajectories in contrast to mN trajectories in the conventional RWS algorithm. The idea is based on the symmetry property of the Green function and a double randomization approach. We present the gRWS method for the heat equation with arbitrary initial and boundary conditions, and the Laplace equation. Detailed description is given for 3D problems; the 2D problems can be treated analogously. Further extensions to advection-diffusion-reaction equations will be presented in a forthcoming paper. [ABSTRACT FROM AUTHOR]

We further develop in this study the Random Walk on Spheres (RWS) stochastic algorithm for solving systems of coupled diffusion-recombination equations first suggested in our recent article [K. Sabelfeld, First passage Monte Carlo algorithms for solving coupled systems of diffusion–reaction equations, Appl. Math. Lett. 88 2019, 141–148]. The random walk on spheres process mimics the isotropic diffusion of two types of particles which may recombine to each other. Our motivation comes from the transport problems of free and bound exciton recombination. The algorithm is based on tracking the trajectories of the diffusing particles exactly in accordance with the probabilistic distributions derived from the explicit representation of the relevant Green functions for balls and spheres. Therefore, the method is mesh free both in space and time. In this paper we implement the RWS algorithm for solving the diffusion-recombination problems both in a steady-state and transient settings. Simulations are compared against the exact solutions. We show also how the RWS algorithm can be applied to calculate exciton flux to the boundary which provides the electron beam-induced current, the concentration of the survived excitons, and the cathodoluminescence intensity which are all integral characteristics of the solution to diffusion-recombination problem. [ABSTRACT FROM AUTHOR]

In this paper we develop stochastic simulation methods for solving large systems of linear equations, and focus on two issues: (1) construction of global random walk algorithms (GRW), in particular, for solving systems of elliptic equations on a grid, and (2) development of local stochastic algorithms based on transforms to balanced transition matrix. The GRW method calculates the solution in any desired family of prescribed points of the gird in contrast to the classical stochastic differential equation based Feynman–Kac formula. The use in local random walk methods of balanced transition matrices considerably decreases the variance of the random estimators and hence decreases the computational cost in comparison with the conventional random walk on grids algorithms. [ABSTRACT FROM AUTHOR]

We develop a last-passage Monte Carlo algorithm on a conducting surface at non-constant potentials. In the previous researches, last-passage Monte Carlo algorithms on conducting surfaces with a constant potential have been developed for charge density at a specific point or on a finite region and a hybrid BIE-WOS algorithm for charge density on a conducting surface at non-constant potentials. In the hybrid BIE-WOS algorithm, they used a deterministic method for the contribution from the lower non-constant potential surface. In this paper, we modify the hybrid BIE-WOS algorithm to a last-passage Monte Carlo algorithm on a conducting surface at non-constant potentials, where we can avoid the singularities on the non-constant potential surface very naturally. We demonstrate the last-passage Monte Carlo algorithm for charge densities on a circular disk and the four rectangle plates with a simple voltage distribution, and update the corner singularities on the unit square plate and cube. [ABSTRACT FROM AUTHOR]

In our paper [A. Nasroallah and K. Elkimakh, HMM with emission process resulting from a special combination of independent Markovian emissions, Monte Carlo Methods Appl. 23 2017, 4, 287–306] we have studied, in a first scenario, the three fundamental hidden Markov problems assuming that, given the hidden process, the observed one selects emissions from a combination of independent Markov chains evolving at the same time. Here, we propose to conduct the same study with a second scenario assuming that given the hidden process, the emission process selects emissions from a combination of independent Markov chain evolving according to their own clock. Three basic numerical examples are studied to show the proper functioning of the iterative algorithm adapted to the proposed model. [ABSTRACT FROM AUTHOR]

This study deals with a narrow escape problem, a well-know difficult problem of evaluating the probability for a diffusing particle to reach a small part of a boundary far away from the starting position of the particle. A direct simulation of the diffusion trajectories would take an enormous computer simulation time. Instead, we use a different approach which drastically improves the efficiency of the diffusion trajectory tracking algorithm by introducing an artificial drift velocity directed to the target position. The method can be efficiently applied to solve narrow escape problems for domains of long extension in one direction which is the case in many practical problems in biology and chemistry. The algorithm is meshless both in space and time, and is well applied to solve high-dimensional problems in complicated domains. We present in this paper a detailed numerical analysis of the method for the case of a rectangular parallelepiped. Both stationary and transient diffusion problems are handled. [ABSTRACT FROM AUTHOR]

In this paper a random walk on arbitrary rectangles (2D) and parallelepipeds (3D) algorithm is developed for solving transient anisotropic drift-diffusion-reaction equations. The method is meshless, both in space and time. The approach is based on a rigorous representation of the first passage time and exit point distributions for arbitrary rectangles and parallelepipeds. The probabilistic representation is then transformed to a form convenient for stochastic simulation. The method can be used to calculate fluxes to any desired part of the boundary, from arbitrary sources. A global version of the method we call here as a stochastic expansion from cell to cell (SECC) algorithm for calculating the whole solution field is suggested. Application of this method to solve a system of transport equations for electrons and holes in a semicoductor is discussed. This system consists of the continuity equations for particle densities and a Poisson equation for electrostatic potential. To validate the method we have derived a series of exact solutions of the drift-diffusion-reaction problem in a three-dimensional layer presented in the last section in details. [ABSTRACT FROM AUTHOR]

Sobol' sequences are widely used for quasi-Monte Carlo methods that arise in financial applications. Sobol' sequences have parameter values called direction numbers, which are freely chosen by the user, so there are several implementations of Sobol' sequence generators. The aim of this paper is to provide a comparative study of (non-commercial) high-dimensional Sobol' sequences by calculating financial models. Additionally, we implement the Niederreiter sequence (in base 2) with a slight modification, that is, we reorder the rows of the generating matrices, and analyze and compare it with the Sobol' sequences. [ABSTRACT FROM AUTHOR]

The generation of appropriate parallel and high-quality quasirandom sequences (low-discrepancy sequences) is crucial to the success of quasi-Monte Carlo methods. The Kronecker sequence is well known to be one of the special types of low-discrepancy sequences, and one of its important advantages is that the Kronecker sequence is easy to implement due to its definition via the fractional parts of multiples of irrationals. However, the original Kronecker sequence suffers from correlations for different dimensions. These correlations result in poorly distributed two-dimensional projections. An approach to this is to find a modified Kronecker sequence via generalizing golden ratio and generate parallel sequences. This paper presents a new algorithm for finding a modified Kronecker sequence within special choices of irrationals. This modified sequence is numerically tested and shown empirically to be superior to the other widely used quasirandom sequences. In addition, based on analysis and insight into the correlations between dimensions of the Kronecker sequence, we illustrate why our algorithm is efficient for breaking these correlations. [ABSTRACT FROM AUTHOR]

The ziggurat method is a fast random variable generation method introduced by Marsaglia and Tsang in a series of papers. We discuss how the ziggurat method can be implemented for low-discrepancy sequences, and present algorithms and numerical results when the method is used to generate samples from the normal and gamma distributions. [ABSTRACT FROM AUTHOR]

This paper presents a hybrid model (stochastic/deterministic) that describes the time evolution of chemical species in a homogenous gas-phase combustion reaction process at constant volume. First, the paper briefly introduces currently employed stochastic algorithms. Next, the development of the hybrid algorithm is detailed. The model is then validated and tested using a reduced reaction mechanism for methane combustion. The effect of user-input performance parameters on stochastic behavior and computational time is studied. The computational time of the algorithm compared to the stochastic simulation algorithm is then compared, and finally, the effect of multiple runs on auto-ignition time is investigated. [ABSTRACT FROM AUTHOR]

We consider statistical inference from incomplete sets of binary data. Our approach is based on the autologistic model, which is very flexible and well suited for medical applications. We propose a Bayesian approach, essentially using Monte Carlo techniques. The method developed in this paper is a special version of Gibbs sampler. We repeat intermittently the following two steps. First, missing values are generated from the predictive distribution. Second, unknown parametes are estimated from the completed data. The Monte Carlo method of computing maximum likelihood estimates due to Geyer and Thompson (J. R. Statist. Soc. B 54: 657-699, 1992) is modified to the Bayesian setting and missing data problems. We include results of some small scale simulation experiments. We artificially introduce missing values in a real data set and then use our algorithm to refill missings. The rate of correct imputations is quite satisfactory. [ABSTRACT FROM AUTHOR]

Monte Carlo methods are now widely used in solving various computational fluid dynamics systems. This paper presents an improved scrambled quasi-Monte Carlo method for solving fluid dynamics applications. In our parallel implementation we use an independent scrambled quasirandom sequence for each processor. We explore the use of both scrambled quasi-Monte Carlo and variance reduction methods to improve the accuracy for Monte Carlo schemes. We also present theoretical analyses and numerical experiments to validate our numerical algorithms. [ABSTRACT FROM AUTHOR]

The paper considers dynamic systems with a distributed change of structure, where the structure number process is Markov process or a conditional Markov process. A statistical algorithm was constructed for probabilistic analysis of such systems. It is based on numerical methods for solution of the Stochastic Differential Equations (SDEs) and on the "maximum cross-section method". Some results of numerical experiments are given. [ABSTRACT FROM AUTHOR]

Matsumoto, Saito and Matoba recently proposed the Walsh figure of merit (WAFOM), which is a computable criterion for quasi-Monte Carlo point sets using digital nets. Several algorithms have been proposed for finding low-WAFOM point sets. In the existing algorithms, the number of points is fixed in advance, but extensible point sets are preferred in some applications. In this paper, we propose a random search algorithm for extensible low-WAFOM point sets. For this, we introduce a method that uses lookup tables to compute WAFOM faster. Numerical results show that our extensible low-WAFOM point sets are comparable with Niederreiter-Xing sequences for some low-dimensional and smooth test functions. [ABSTRACT FROM AUTHOR]

In this paper we first investigate the use of Markov Chain Monte Carlo (MCMC) methods to attack classical ciphers. MCMC has previously been used to break simple substitution, transposition and substitution-transposition ciphers. Here, we improve the accuracy of obtained results by these algorithms and we show the performance of the algorithms using quasi random numbers such as Faure, Sobol and Niederreiter sequences. [ABSTRACT FROM AUTHOR]

We suggest a series of extremely fast stochastic algorithms based on exact representations we derive in this paper for the first passage time and exit point probability densities, splitting and survival probabilities. We apply the developed algorithms to the following three classes of problems: (1) simulation of epitaxial nanowire growth, (2) diffusion imaging of microstructures, in particular, cathodoluminescence imaging for threading dislocations, and (3) simulation of the annihilation of electrons and holes in vicinity of nonradiative centers and quantum efficiency evaluation. In the last example the Random Walk on Spheres method is used to solve nonlinear diffusion equations, and to more general systems of nonlinear Smoluchowski equations combined with the kinetic Monte Carlo method. [ABSTRACT FROM AUTHOR]

In this paper we generalize an explicit numerical scheme for the CIR process that we have proposed before. The advantage of the new proposed scheme is that preserves positivity and is well posed for a (little bit) broader set of parameters among the positivity preserving schemes. The order of convergence is at least logarithmic in general and for a smaller set of parameters is at least 1/4. [ABSTRACT FROM AUTHOR]

A generalization of a polynomial chaos-based algorithm for solving PDEs with random input data is suggested. The input random field is assumed to be defined by its mean and correlation function. The method uses the Karhunen-Loève expansion, in its analytical form, for the input random field. Potentially, however, if desired, the Karhunen-Loève expansion can be also constructed by a randomized singular value decomposition of the correlation function recently suggested in our paper [Math. Comput. Simulation 82 (2011), 295-317]. The polynomial chaos expansion is then constructed by resolving a probabilistic collocation-based system of linear equations. The method is compared against a direct Monte Carlo method which solves repeatedly many times the PDE for a set of samples of the input random field. Along with the commonly used statistical characteristics like the mean and variance of the solution, we were able to calculate more sophisticated functionals like the instant velocity samples and the mean for Eulerian and Lagrangian velocity fields. [ABSTRACT FROM AUTHOR]

In this paper, we present the application of our recently developed Green's function Monte Carlo algorithm to the solution of the one-dimensional Helmholtz equation subject to Neumann and mixed boundary conditions problems. The traditional Green's function Monte Carlo approach for the solution of partial differential equations subjected to Neumann and mixed boundary conditions involves 'reflecting boundaries' resulting in relatively large computational times. Our algorithm, motivated by the work of K. K. Sabelfeld is philosophically different in that there is no requirement for reflection at these boundaries. The underlying feature of this algorithm is the elimination of the use of reflecting boundaries through the use of novel Green's functions that mimic the boundary conditions of the problem of interest. In the past, we have applied it to the solution of the one-dimensional Laplace equation and the modified Helmholtz equation. In this work, we apply it to the solution of the Helmholtz equation. In the case of the Helmholtz equation, unlike the Laplace equation and modified Helmholtz equation, the algorithm is constrained to quarter-wavelength length scales, a constraint that is the result of resonance in the Green's function for the Helmholtz equation. This constraint is also present in the case of the Helmholtz equation subjected to Dirichlet conditions and is not specific to Neumann and mixed boundary conditions. However, within this constraint, excellent agreement has been obtained between an analytical solution and numerical results. [ABSTRACT FROM AUTHOR]

In this paper, we describe a stochastic algorithm to solve sudoku puzzles. Our method consists in computing probabilities for each symbol of each cell updated at each step of the algorithm using estimation of distributions algorithms (EDA). This update is done using the empirical estimators of these probabilities for a fraction of the best puzzles according to a cost function. We develop also some partial restart techniques in the RESEDA algorithm to obtain a convergence for the most difficult puzzles. Our algorithm is tested numerically on puzzles with various levels of difficulty starting from very easy ones to very hard ones including the famous puzzle AI Escargot. The CPU times vary from few hundreds of a second for the easy ones to about one minute for the most difficult one. [ABSTRACT FROM AUTHOR]

Many studies of randomly packed hyperspheres in multiple dimensions have been performed using Monte Carlo or Molecular Dynamics simulations to probe the behaviour of the systems. The calculations are usually initiated by randomly placing the hyperspheres in a D-dimensional box until some randomly loosely packed density is achieved. Then either a compression algorithm or a particle scaling technique is used to reach higher packing fractions. The interesting aspect in the initial random placing of the hyperspheres is that it is closely related to a test of random number generators that was proposed by Marsaglia, the 'parking lot' test. It is this relationship that is investigated in this paper. [ABSTRACT FROM AUTHOR]

Value-at-Risk (VaR) and Conditional-Value-at-Risk (CVaR) are two risk measures which are widely used in the practice of risk management. This paper deals with the problem of estimating both VaR and CVaR using stochastic approximation (with decreasing steps): we propose a first Robbins–Monro (RM) procedure based on Rockafellar–Uryasev's identity for the CVaR. Convergence rate of this algorithm to its target satisfies a Gaussian Central Limit Theorem. As a second step, in order to speed up the initial procedure, we propose a recursive and adaptive importance sampling (IS) procedure which induces a significant variance reduction of both VaR and CVaR procedures. This idea, which has been investigated by many authors, follows a new approach introduced in [Lemaire and Pagès, Unconstrained Recursive Importance Sampling, 2008]. Finally, to speed up the initialization phase of the IS algorithm, we replace the original confidence level of the VaR by a slowly moving risk level. We prove that the weak convergence rate of the resulting procedure is ruled by a Central Limit Theorem with minimal variance and its efficiency is illustrated on several typical energy portfolios. [ABSTRACT FROM AUTHOR]

The paper describes the deviational particle Monte Carlo method for the Boltzmann equation. The approach is an application of the general “control variates” variance reduction technique to the problem of solving a nonlinear equation. The deviation of the solution from a reference Maxwellian is approximated by a system of positive and negative particles. Previous results from the literature are modified and extended. New algorithms are proposed that cover the nonlinear Boltzmann equation (instead of a linearized version) with a general interaction model (instead of hard spheres). The algorithms are obtained as procedures for generating trajectories of Markov jump processes. This provides the framework for deriving the limiting equations, when the number of particles tends to infinity. These equations reflect the influence of various numerical approximation parameters. Detailed simulation schemes are provided for the variable hard sphere interaction model. [ABSTRACT FROM AUTHOR]

In this paper a modification of the standard algorithm for the order statistics modeling, tied with the usage of confidence intervals is proposed. A study of applications of the standard algorithm for the order statistics modeling leads us to a conclusion that one of these applications (namely, the modeling of beta-distribution with integer parameters) gives the most effective algorithm for the order statistics modeling. A possibility to use the constructed algorithms in numerical modeling of random variables with polynomial distribution, as well as the beta-distribution with non-integer parameters, is shown. [ABSTRACT FROM AUTHOR]

The standard Monte Carlo algorithm for estimating global sensitivity indices may be spoilt by loss of accuracy if the index is very small. Two approaches were proposed for eliminating the loss of accuracy: reduction of the mean value and correlated sampling. In the present paper both approaches are investigated and a third combined approach is suggested. [ABSTRACT FROM AUTHOR]

Conventional approaches to Monte Carlo experiments involve finding the performance measure of a system to a particular input. Inverse Monte Carlo experiment reverses this and attempts to find the control inputs required to achieve a particular performance measure. Extensive computer processing is needed to find a design parameter value given a desired target for the performance measure of a given system. The designer simulates the process numerically and obtains an approximation for that same output. The goal is to match the numerical and experimental results as closely as possible by varying the values of input parameters in the numerical Monte Carlo experiments. The most obvious difficulty in solving the design problem is that one cannot simply calculate a straightforward solution and be done. Since the output has to be matched by varying the input, an iterative method of solution is implied. This paper proposes a "stochastic approximation" algorithm to estimate the necessary controllable input parameters within a desired accuracy given a target value for the performance function. The proposed solution algorithm is based on Newton's methods using a single-run Monte Carlo experiments approach to estimate the needed derivative. The proposed approach may be viewed as an optimization scheme, where a loss function must be minimized. The solution algorithm properties and the validity of the estimates are examined by applying it to a reliability system with known analytical solutions. [ABSTRACT FROM AUTHOR]

Taking advantage of the recent literature on exact simulation algorithms (Beskos, Papaspiliopoulos and Roberts [A. Beskos, O. Papaspiliopoulos, and Gareth O. Roberts, Retrospective exact simulation of diffusion sample paths. Bernoulli 12 (December 2006).]) and unbiased estimation of the expectation of certain functional integrals (Wagner [W. Wagner, Unbiased Monte Carlo evaluation of certain functional integrals. J. Comput. Phys. 71 (1987), 21–33.], Beskos et al. [A. Beskos, O. Papaspiliopoulos,Gareth O. Roberts, and P. Fearnhead, Exact and computationally efficient likelihood-based estimation for discretely observed diffusion processes. To appear in the Journal of the Royal Statistical Society, Series B.] and Fearnhead et al. [P. Fearnhead, O. Papaspiliopoulos, and G. O. Roberts, Particle Filters for Partially observed diffusions. Working paper: Lancaster University. (2006).]), we apply an exact simulation based technique for pricing continuous arithmetic average Asian options in the Black & Scholes framework. Unlike existing Monte Carlo methods, we are no longer prone to the discretization bias resulting from the approximation of continuous time processes through discrete sampling. Numerical results of simulation studies are presented and variance reduction problems are considered. [ABSTRACT FROM AUTHOR]

In this paper we introduce reproducing kernel Hilbert spaces based on Taylor series. The unit ball of this space contains functions which are infinite at the boundary. We investigate multivariate integration in such spaces and show how functions in such spaces can be integrated with orderO(N–τ) for τ > 0 arbitrarily large, in spite of the unboundedness of the functions at the boundary. Further we prove that the Taylor space contains functions with infinite variance and hence the function space contains functions for which a simple Monte Carlo algorithm converges with probability one but convergence could be arbitrarily slow. [ABSTRACT FROM AUTHOR]

In this paper we propose an improved quasi-Monte Carlo method for solving Linear Algebra problems. We show that by using low-discrepancy sequences both the convergence and the CPU time of the algorithm are improved. Two parallelization schemes using the Message Passing Interface with static and dynamic load balancing are proposed. The dynamic scheme is useful for computing in the GRID environment. [ABSTRACT FROM AUTHOR]

This paper introduces a semilinear stochastic evolution equation which contains fractional powers of the infinitesimal generator of a strongly continuous semigroup and is driven by Hilbert space-valued fractional Brownian motion. Fractional powers of the generator induce long-range dependence in space, while fractional Brownian motion induces long-range dependence in time in the solution of the equation. An approximation of the evolution solution is then constructed by the splitting method. The existence and uniqueness of the solution and mean-square convergence of the approximation algorithm are established. [ABSTRACT FROM AUTHOR]

In this paper we present a numerical scheme for the Random Cloud Model (RCM) on a bounded domain which approximates the solution of the time-dependent Schrödinger equation. The RCM is formulated as a Markov jump process on a particle number state space. Based on this process a stochastic algorithm is developed. It is shown that the algorithm reproduces the dynamics of the time-dependent Schrödinger equation for exact initial conditions on a bounded domain. The algorithm is then tested for two different cases. First, it is shown that the RCM reproduces the analytic solution for a particle in a potential well with infinite potential. Second, the RCM is used to study three cases with finite potential walls. It is found that the potential triggers processes, which produces RCM particles at a high rate that annihilate each other. [ABSTRACT FROM AUTHOR]

In the paper 'Fast simulation of Gaussian random fields', a typo occurred. Instead of it should read in Algorithm 3.1, Remark d). For convenience of the reader we reproduce below the complete corrected algorithms. [ABSTRACT FROM AUTHOR]

Exact yet simple simulation algorithms are developed for a wide class of Ornstein-Uhlenbeck processes with tempered stable stationary distribution of finite variation with the help of their exact transition probability between consecutive time points. Random elements involved can be divided into independent tempered stable and compound Poisson distributions, each of which can be simulated in the exact sense through acceptance-rejection sampling, respectively, with stable and gamma proposal distributions. We discuss various alternative simulation methods within our algorithms on the basis of acceptance rate in acceptance-rejection sampling for both high- and low-frequency sampling. Numerical results illustrate their advantage relative to the existing approximative simulation method based on infinite shot noise series representation. [ABSTRACT FROM AUTHOR]

Combined control variates and importance sampling variance reduction and its two-fold optimality are investigated. Two-time-scale stochastic approximation algorithm is applied in parameter search for the combination and almost sure convergence of the algorithm to the unique optimum is proved. The parameter search procedure is further incorporated into adaptive Monte Carlo simulation, and its law of large numbers and central limit theorem are proved to hold. An numerical example is provided to illustrate the effectiveness of the method. [ABSTRACT FROM AUTHOR]

The Smoluchowski equation is a nonlinear integro-differential equation describing the evolution of the concentration μt(dx) of particles of mass in (x, x + dx) in an infinite particle system where coalescence occurs. We introduce a class of algorithms, which allow, under some conditions, to simulate exactly a stochastic process (Xt)t≥o, whose time marginals are given by (xμt(dx))t≥0. [ABSTRACT FROM AUTHOR]

Presents the jointly distributed mean and mixing coefficients for Bayesian source separation using the Markov chain Monte Carlo method and the iterated conditional modes algorithm. Details on the multivariate Bayesian statistical approach and the linear synthesis model; Information on the conjugate estimation; Gibbs sampling estimation of the posterior.

Presents a study which described a computer technique for calculating the spatial detector depth sensitivity of diffuse back-scattered light from a multi-layered complex inhomogeneous medium, imitating the human skin. Description of the principles of Monte Carlo algorithm; Difference of the Monte Carlo algorithm from other algorithms; Discussion of the optical parameters of the modeling medium and the results of the simulations; Summary of the results of the model and simulation.

Gibbs samplers are common Markov chain Monte Carlo (MCMC) algorithms that are used to sample from intractable probability distributions when sampling directly from full conditional distributions is possible. These types of MCMC algorithms come up frequently in many applications, and because of their popularity it is important to have a sense of how long it takes for the Gibbs sampler to become close to its stationary distribution. To this end, it is common to rely on the values of drift and minorization coefficients to bound the mixing time of the Gibbs sampler. This manuscript provides a computational method for estimating these coefficients. Herein, we detail the several advantages of the proposed methods, as well as the limitations of this approach. These limitations are primarily related to the "curse of dimensionality", which for these methods is caused by necessary increases in the numbers of initial states from which chains need be run and the need for an exponentially increasing number of grid points for estimation of minorization coefficients. [ABSTRACT FROM AUTHOR]

The pricing of Bermudan options amounts to solving a dynamic programming principle, in which the main difficulty, especially in high dimension, comes from the conditional expectation involved in the computation of the continuation value. These conditional expectations are classically computed by regression techniques on a finite-dimensional vector space. In this work, we study neural networks approximations of conditional expectations. We prove the convergence of the well-known Longstaff and Schwartz algorithm when the standard least-square regression is replaced by a neural network approximation, assuming an efficient algorithm to compute this approximation. We illustrate the numerical efficiency of neural networks as an alternative to standard regression methods for approximating conditional expectations on several numerical examples. [ABSTRACT FROM AUTHOR]

A Random Walk on Ellipsoids (RWE) algorithm is developed for solving a general class of elliptic equations involving second- and zero-order derivatives. Starting with elliptic equations with constant coefficients, we derive an integral equation which relates the solution in the center of an ellipsoid with the integral of the solution over an ellipsoid defined by the structure of the coefficients of the original differential equation. This integral relation is extended to parabolic equations where a first passage time distribution and survival probability are given in explicit forms. We suggest an efficient simulation method which implements the RWE algorithm by introducing a notion of a separation sphere. We prove that the logarithmic behavior of the mean number of steps for the RWS method remains true for the RWE algorithm. Finally we show how the developed RWE algorithm can be applied to solve elliptic and parabolic equations with variable coefficients. A series of supporting computer simulations are given. [ABSTRACT FROM AUTHOR]

In this article, we consider the general problem of checking the correctness of matrix multiplication. Given three n × n n\times n matrices 𝐴, 𝐵 and 𝐶, the goal is to verify that A × B = C A\times B=C without carrying out the computationally costly operations of matrix multiplication and comparing the product A × B A\times B with 𝐶, term by term. This is especially important when some or all of these matrices are very large, and when the computing environment is prone to soft errors. Here we extend Freivalds' algorithm to a Gaussian Variant of Freivalds' Algorithm (GVFA) by projecting the product A × B A\times B as well as 𝐶 onto a Gaussian random vector and then comparing the resulting vectors. The computational complexity of GVFA is consistent with that of Freivalds' algorithm, which is O ⁢ (n 2) O(n^{2}). However, unlike Freivalds' algorithm, whose probability of a false positive is 2 - k 2^{-k} , where 𝑘 is the number of iterations, our theoretical analysis shows that, when A × B ≠ C A\times B\neq C , GVFA produces a false positive on set of inputs of measure zero with exact arithmetic. When we introduce round-off error and floating-point arithmetic into our analysis, we can show that the larger this error, the higher the probability that GVFA avoids false positives. Moreover, by iterating GVFA 𝑘 times, the probability of a false positive decreases as p k p^{k} , where 𝑝 is a very small value depending on the nature of the fault on the result matrix and the arithmetic system's floating-point precision. Unlike deterministic algorithms, there do not exist any fault patterns that are completely undetectable with GVFA. Thus GVFA can be used to provide efficient fault tolerance in numerical linear algebra, and it can be efficiently implemented on modern computing architectures. In particular, GVFA can be very efficiently implemented on architectures with hardware support for fused multiply-add operations. [ABSTRACT FROM AUTHOR]

It has been shown that when using a Monte Carlo algorithm to estimate the electrostatic free energy of a biomolecule in a solution, individual random walks can become entrapped in the geometry. We examine a proposed solution, using a sharp restart during the Walk-on-Subdomains step, in more detail. We show that the point at which this solution introduces significant bias is related to properties intrinsic to the molecule being examined. We also examine two potential methods of generating a sharp restart point and show that they both cause no significant bias in the examined molecules and increase the stability of the run times of the individual walks. [ABSTRACT FROM AUTHOR]

The standard coupling from the past (CFTP) algorithm is an interesting tool to sample from exact Markov chain steady-state probability. The CFTP detects, with probability one, the end of the transient phase (called burn-in period) of the chain and consequently the beginning of its stationary phase. For large and/or stiff Markov chains, the burn-in period is expensive in time consumption. In this work, we propose a kind of dual form for CFTP called D-CFTP that, in many situations, reduces the Monte Carlo simulation time and does not need to store the history of the used random numbers from one iteration to another. A performance comparison of CFTP and D-CFTP will be discussed, and some numerical Monte Carlo simulations are carried out to show the smooth running of the proposed D-CFTP. [ABSTRACT FROM AUTHOR]

We explore different methods of solving systems of stochastic differential equations by first implementing the Euler–Maruyama and Milstein methods with a Monte Carlo simulation on a CPU. The performance of the methods is significantly improved through the recently developed antithetic multilevel Monte Carlo estimator, which yields a computation complexity of 𝒪 ⁢ (ϵ - 2) {\mathcal{O}(\epsilon^{-2})} root-mean-square error and does so without the approximation of Lévy areas. Further improvements in performance are gained by moving the algorithms to a GPU - first on a single device and then on a multi-GPU cluster. Our GPU implementation of the antithetic multilevel Monte Carlo displays a major speedup in computation when compared with many commonly used approaches in the literature. While our work is focused on the simulation of the stochastic volatility and interest rate model, it is easily extendable to other stochastic systems, and it is of particular interest to those with non-diagonal, non-commutative noise. [ABSTRACT FROM AUTHOR]

We review the derivation of the Kac master equation model for random collisions of particles, its relationship to the Poisson process, and existing algorithms for simulating values from the marginal distribution of velocity for a single particle at any given time. We describe and implement a new algorithm that efficiently and more fully leverages properties of the Poisson process, show that it performs at least as well as existing methods, and give empirical evidence that it may perform better at capturing the tails of the single particle velocity distribution. Finally, we derive and implement a novel "ε-perfect sampling" algorithm for the limiting marginal distribution as time goes to infinity. In this case the importance is a proof of concept that has the potential to be expanded to more interesting (DSMC) direct simulationMonte Carlo applications. [ABSTRACT FROM AUTHOR]