Study of weighted Monte Carlo algorithms with branching

Various weighted algorithms for numerical statistical simulation are formulated and studied. The trajectory of an algorithm branches when the current weighting factor exceeds unity. As a result, the weight of an individual branch does not exceed unity and the variance of the estimate for the computed functional is finite. The unbiasedness and finiteness of the variance of estimates are analyzed using the recurrence “partial“ averaging method formulated in this study. The estimation of the particle reproduction factor and solutions to the Helmholtz equation are considered as applications. The comparative complexity of the algorithms is examined using a test problem. The variances of weighted algorithms with branching as applied to integral equations with power nonlinearity are analyzed.     

Modifications of weighted Monte Carlo algorithms for nonlinear kinetic equations

Test problems for the nonlinear Boltzmann and Smoluchowski kinetic equations are used to analyze the efficiency of various versions of weighted importance modeling as applied to the evolution of multiparticle ensembles. For coagulation problems, a considerable gain in computational costs is achieved via the approximate importance modeling of the “free path” of the ensemble combined with the importance modeling of the index of a pair of interacting particles. A weighted modification of the modeling of the initial velocity distribution was found to be the most efficient for model solutions to the Boltzmann equation. The technique developed can be useful as applied to real-life coagulation and relaxation problems for which the model problems considered give approximate solutions.     

Hypothesis Tests of Convergence in Markov Chain Monte Carlo

Abstract

Deciding when a Markov chain has reached its stationary distribution is a major problem in applications of Markov Chain Monte Carlo methods. Many methods have been proposed ranging from simple graphical methods to complicated numerical methods. Most such methods require a lot of user interaction with the chain which can be very tedious and time-consuming for a slowly mixing chain. This article describes a system to reduce the burden on the user in assessing convergence. The method uses simple nonparametric hypothesis testing techniques to examine the output of several independent chains and so determines whether there is any evidence against the hypothesis of convergence. We illustrate the proposed method on some examples from the literature.     

A Markov Chain Monte Carlo Convergence Diagnostic Using Subsampling

Abstract

A new diagnostic procedure for assessing convergence of a Markov chain Monte Carlo (MCMC) simulation is proposed. The method is based on the use of subsampling for the construction of confidence regions from asymptotically stationary time series as developed in Politis, Romano, and Wolf. The MCMC subsampling diagnostic is capable of gauging at what point the chain has “forgotten” its starting points, as well as to indicate how many points are needed to estimate the parameters of interest according to the desired accuracy. Simulation examples are also presented showing that the diagnostic performs favorably in interesting cases.     

Robustness and applicability of Markov chain Monte Carlo algorithms for eigenvalue problems

In this paper we analyse applicability and robustness of Markov chain Monte Carlo algorithms for eigenvalue problems. We restrict our consideration to real symmetric matrices.

Almost Optimal Monte Carlo (MAO) algorithms for solving eigenvalue problems are formulated. Results for the structure of both – systematic and probability error are presented. It is shown that the values of both errors can be controlled independently by different algorithmic parameters. The results present how the systematic error depends on the matrix spectrum. The analysis of the probability error is presented. It shows that the close (in some sense) the matrix under consideration is to the stochastic matrix the smaller is this error. Sufficient conditions for constructing robust and interpolation Monte Carlo algorithms are obtained. For stochastic matrices an interpolation Monte Carlo algorithm is constructed.

A number of numerical tests for large symmetric dense matrices are performed in order to study experimentally the dependence of the systematic error from the structure of matrix spectrum. We also study how the probability error depends on the balancing of the matrix.     

Markov Chain Monte Carlo Convergence Assessment via Two-Way Analysis of Variance

Abstract

In this article we discuss the problem of assessing the performance of Markov chain Monte Carlo (MCMC) algorithms on the basis of simulation output. In essence, we extend the original ideas of Gelman and Rubin and, more recently, Brooks and Gelman, to problems where we are able to split the variation inherent within the MCMC simulation output into two distinct groups. We show how such a diagnostic may be useful in assessing the performance of MCMC samplers addressing model choice problems, such as the reversible jump MCMC algorithm. In the model choice context, we show how the reversible jump MCMC simulation output for parameters that retain a coherent interpretation throughout the simulation, can be used to assess convergence. By considering various decompositions of the sampling variance of this parameter, we can assess the performance of our MCMC sampler in terms of its mixing properties both within and between models and we illustrate our approach in both the graphical Gaussian models and normal mixtures context. Finally, we provide an example of the application of our diagnostic to the assessment of the influence of different starting values on MCMC simulation output, thereby illustrating the wider utility of our method beyond the Bayesian model choice and reversible jump MCMC context.     

Semidefinite diagonal directions Monte Carlo algorithms for detecting necessary linear matrix inequality constraints

Hit-and-run algorithms are Monte Carlo methods for detecting necessary constraints in convex programming including semidefinite programming. The well known of these in semidefinite programming are semidefinite coordinate directions (SCD), semidefinite hypersphere directions (SHD) and semidefinite stand-and-hit (SSH) algorithms. SCD is considered to be the best on average and hence we use it for comparison.We develop two new hit-and-run algorithms in semidefinite programming that use diagonal directions. They are the uniform semidefinite diagonal directions (uniform SDD) and the original semidefinite diagonal directions (original SDD) algorithms. We analyze the costs and benefits of this change in comparison with SCD. We also show that both uniform SDD and original SDD generate points that are asymptotically uniform in the interior of the feasible region defined by the constraints.     

Modification of two-step Monte Carlo algorithms based on the symmetry of the first step

Two-step Monte Carlo algorithms are modified taking into account the symmetry (i.e., invariance) of the first step about some initial vector parameter of the modeled trajectory. In the modification, the modeling of this parameter is formally transferred to the second step of the algorithm. In the “splitting method,” this means the randomization of the initial points of auxiliary trajectories. It is shown that the randomization can be improved by applying the Bellman principle.     

Weight Monte Carlo algorithms for estimation and parametric analysis of the solution to the kinetic coagulation equation

The Smoluchowski equation with linear coagulation coefficients depending on two parameters is considered. We construct weight algorithms for estimating various linear functionals in an ensemble that is governed by the equation under study. The algorithms constructed allow us to estimate the functionals for various parameters, as well as parametric derivatives by using the same set of trajectories. Moreover, we construct the value algorithms and analyze their efficiency for estimating the total monomer concentration, as well as the total monomer and dimer concentration in the ensemble. The computational cost is considerably reduced via the approximate value simulation of the time between interactions combined with the value simulation of the interacting pair number.     

User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient

In this paper, we study the problem of sampling from a given probability density function that is known to be smooth and strongly log-concave. We analyze several methods of approximate sampling based on discretizations of the (highly overdamped) Langevin diffusion and establish guarantees on its error measured in the Wasserstein-2 distance. Our guarantees improve or extend the state-of-the-art results in three directions. First, we provide an upper bound on the error of the first-order Langevin Monte Carlo (LMC) algorithm with optimized varying step-size. This result has the advantage of being horizon free (we do not need to know in advance the target precision) and to improve by a logarithmic factor the corresponding result for the constant step-size. Second, we study the case where accurate evaluations of the gradient of the log-density are unavailable, but one can have access to approximations of the aforementioned gradient. In such a situation, we consider both deterministic and stochastic approximations of the gradient and provide an upper bound on the sampling error of the first-order LMC that quantifies the impact of the gradient evaluation inaccuracies. Third, we establish upper bounds for two versions of the second-order LMC, which leverage the Hessian of the log-density. We provide non asymptotic guarantees on the sampling error of these second-order LMCs. These guarantees reveal that the second-order LMC algorithms improve on the first-order LMC in ill-conditioned settings.     

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)     

Convergence rates for Kaczmarz-type algorithms

By making use of the normal and skew-Hermitian splitting (NSS) method as the inner solver for the modified Newton method, we establish a class of modified Newton-NSS method for solving large sparse systems of nonlinear equations with positive definite Jacobian matrices at the solution points. Under proper conditions, the local convergence theorem is proved. Furthermore, the successive-overrelaxation (SOR) technique has been proved quite successfully in accelerating the convergence rate of the NSS or the Hermitian and skew-Hermitian splitting (HSS) iteration method, so we employ the SOR method in the NSS iteration, and we get a new method, which is called modified Newton SNSS method. Numerical results are given to examine its feasibility and effectiveness.