A Monte Carlo method for high dimensional integration

Summary A new method for the numerical integration of very high dimensional functions is introduced and implemented based on the Metropolis' Monte Carlo algorithm. The logarithm of the high dimensional integral is reduced to a 1-dimensional integration of a certain statistical function with respect to a scale parameter over the range of the unit interval. The improvement in accuracy is found to be substantial comparing to the conventional crude Monte Carlo integration. Several numerical demonstrations are made, and variability of the estimates are shown.     

Hybrid Monte Carlo on Hilbert spaces

The Hybrid Monte Carlo (HMC) algorithm provides a framework for sampling from complex, high-dimensional target distributions. In contrast with standard Markov chain Monte Carlo (MCMC) algorithms, it generates nonlocal, nonsymmetric moves in the state space, alleviating random walk type behaviour for the simulated trajectories. However, similarly to algorithms based on random walk or Langevin proposals, the number of steps required to explore the target distribution typically grows with the dimension of the state space. We define a generalized HMC algorithm which overcomes this problem for target measures arising as finite-dimensional approximations of measures π which have density with respect to a Gaussian measure on an infinite-dimensional Hilbert space. The key idea is to construct an MCMC method which is well defined on the Hilbert space itself.We successively address the following issues in the infinite-dimensional setting of a Hilbert space: (i) construction of a probability measure Π in an enlarged phase space having the target π as a marginal, together with a Hamiltonian flow that preserves Π; (ii) development of a suitable geometric numerical integrator for the Hamiltonian flow; and (iii) derivation of an accept/reject rule to ensure preservation of Π when using the above numerical integrator instead of the actual Hamiltonian flow. Experiments are reported that compare the new algorithm with standard HMC and with a version of the Langevin MCMC method defined on a Hilbert space.     

On a Monte Carlo method for neutron transport criticality computations

^** Email: maire{at}univ-tln.fr^*** Email: denis.talay{at}sophia.inria.fr We give a stochastic representation of the principal eigenvalueof some homogeneous neutron transport operators. Our constructionis based upon the Feynman–Kac formula for integral transportequations, and uses probabilistic techniques only. We developa Monte Carlo method for criticality computations. We numericallytest this method on various homogeneous and inhomogeneous problems,and compare our results with those obtained by standard methods.     

Efficiency of Monte Carlo EM and Simulated Maximum Likelihood in Two-Stage Hierarchical Models

Likelihood estimation in hierarchical models is often complicated by the fact that the likelihood function involves an analytically intractable integral. Numerical approximation to this integral is an option but it is generally not recommended when the integral dimension is high. An alternative approach is based on the ideas of Monte Carlo integration, which approximates the intractable integral by an empirical average based on simulations. This article investigates the efficiency of two Monte Carlo estimation methods, the Monte Carlo EM (MCEM) algorithm and simulated maximum likelihood (SML). We derive the asymptotic Monte Carlo errors of both methods and show that, even under the optimal SML importance sampling distribution, the efficiency of SML decreases rapidly (relative to that of MCEM) as the missing information about the unknown parameter increases. We illustrate our results in a simple mixed model example and perform a simulation study which shows that, compared to MCEM, SML can be extremely inefficient in practical applications.     

Graphs as navigational infrastructure for high dimensional data spaces

We propose using graph theoretic results to develop an infrastructure that tracks movement from a display of one set of variables to another. The illustrative example throughout is the real-time morphing of one scatterplot into another. Hurley and Oldford (J Comput Graph Stat 2010) made extensive use of the graph having variables as nodes and edges indicating a paired relationship between them. The present paper introduces several new graphs derivable from this one whose traversals can be described as particular movements through high dimensional spaces. These are connected to known results in graph theory and the graph theoretic results applied to the problem of visualizing high-dimensional data.     

Approachability in infinite dimensional spaces

The approachability theorem of Blackwell (1956b) is extended to infinite dimensional spaces. Two players play a sequential game whose payoffs are random variables. A set C of random variables is said to be approachable by player 1 if he has a strategy that ensures that the difference between the average payoff and its closest point in C, almost surely converges to zero. Necessary conditions for a set to be approachable are presented. Received February 2002/Final version July 2002  I acknowledge Eilon Solan for his helpful comments. The author acknowledges the support of the Israel Science Foundation, grant no. 178/99.     

Efficiency estimation and error decomposition in the stochastic frontier model: A Monte Carlo analysis

Critics of the deterministic approach to efficiency measurement argue that no allowance is made for measurement error and other statistical noise. Without controlling for measurement error, the resulting measure of efficiency will be distorted due to the contamination of noise. The stochastic frontier models purportedly allow both inefficiency and measurement error. Some proponents argue that the stochastic frontier models should be used despite the limitations because of the superior conceptual treatment of noise. However, the ultimate value of the stochastic frontier depends on its ability to properly decompose noise and inefficiency. This paper tests the validity of the stochastic frontier cross-sectional models using a Monte Carlo analysis. The results suggest that the technique does not accurately decompose the total error into inefficiency and noise components. Further, the results suggest that at best, the stochastic frontier is only as good as the deterministic model.     

Combinatorics of reliability Monte Carlo

We study one class of unbiased Monte Carlo estimators for system reliability, avoiding the rare event difficulty. This class is closely related to the system combinatorics and contains unique “extreme” members, having the minimum and maximum relative error. Some known Monte Carlo heuristics for network reliability, including fully polynomial cases, are of this type. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14: 329–343, 1999     

Sampling efficiency in Monte Carlo analyses

Stochastic processes that are sampled in Monte Carlo analyses can be so complex that sampling efficiency is difficult to attain. To handle these difficulties we introduce a model of the elements of a stochastic process which are relevant to the problem of sampling efficiency. From this model we derive a multistage estimating procedure which automatically adjusts the parameters of an efficient sampling design.     

Conditioning in Markov Chain Monte Carlo

Abstract

The so-called “Rao-Blackwellized” estimators proposed by Gelfand and Smith do not always reduce variance in Markov chain Monte Carlo when the dependence in the Markov chain is taken into account. An illustrative example is given, and a theorem characterizing the necessary and sufficient condition for such an estimator to always reduce variance is proved.     

Hamilton-Jacobi semi-groups in infinite dimensional spaces

Let (X,ρ) be a Polish space endowed with a probability measure μ. Assume that we can do Malliavin Calculus on (X,μ). Let be a pseudo-distance. Consider QtF(x)=infy∈X{F(y)+d²(x,y)/2t}. We shall prove that QtF satisfies the Hamilton-Jacobi inequality under suitable conditions. This result will be applied to establish transportation cost inequalities on path groups and loop groups in the spirit of Bobkov, Gentil and Ledoux.     

Monte Carlo EM加速算法

EM算法是近年来常用的求后验众数的估计的一种数据增广算法, 但由于求出其E步中积分的显示表达式有时很困难, 甚至不可能, 限制了其应用的广泛性. 而Monte Carlo EM算法很好地解决了这个问题, 将EM算法中E步的积分用Monte Carlo模拟来有效实现, 使其适用性大大增强. 但无论是EM算法, 还是Monte Carlo EM算法, 其收敛速度都是线性的, 被缺损信息的倒数所控制, 当缺损数据的比例很高时, 收敛速度就非常缓慢. 而Newton-Raphson算法在后验众数的附近具有二次收敛速率. 本文提出Monte Carlo EM加速算法, 将Monte Carlo EM算法与Newton-Raphson算法结合, 既使得EM算法中的E步用Monte Carlo模拟得以实现, 又证明了该算法在后验众数附近具有二次收敛速度. 从而使其保留了Monte Carlo EM算法的优点, 并改进了Monte Carlo EM算法的收敛速度. 本文通过数值例子, 将Monte Carlo EM加速算法的结果与EM算法、Monte Carlo EM算法的结果进行比较, 进一步说明了Monte Carlo EM加速算法的优良性.     

Population Monte Carlo Algorithm in High Dimensions

The population Monte Carlo algorithm is an iterative importance sampling scheme for solving static problems. We examine the population Monte Carlo algorithm in a simplified setting, a single step of the general algorithm, and study a fundamental problem that occurs in applying importance sampling to high-dimensional problem. The precision of the computed estimate from the simplified setting is measured by the asymptotic variance of estimate under conditions on the importance function. We demonstrate the exponential growth of the asymptotic variance with the dimension and show that the optimal covariance matrix for the importance function can be estimated in special cases.     

Monte Carlo Maximum Likelihood in Model-Based Geostatistics

When using a model-based approach to geostatistical problems, often, due to the complexity of the models, inference relies on Markov chain Monte Carlo methods. This article focuses on the generalized linear spatial models, and demonstrates that parameter estimation and model selection using Markov chain Monte Carlo maximum likelihood is a feasible and very useful technique. A dataset of radionuclide concentrations on Rongelap Island is used to illustrate the techniques. For this dataset we demonstrate that the log-link function is not a good choice, and that there exists additional nonspatial variation which cannot be attributed to the Poisson error distribution. We also show that the interpretation of this additional variation as either micro-scale variation or measurement error has a significant impact on predictions. The techniques presented in this article would also be useful for other types of geostatistical models.     

Allometry constants of finite-dimensional spaces: theory and computations

We describe the computations of some intrinsic constants associated to an n-dimensional normed space , namely the N-th “allometry” constants

Multilevel Monte Carlo in approximate Bayesian computation

In the following article, we consider approximate Bayesian computation (ABC) inference. We introduce a method for numerically approximating ABC posteriors using the multilevel Monte Carlo (MLMC). A sequential Monte Carlo version of the approach is developed and it is shown under some assumptions that for a given level of mean square error, this method for ABC has a lower cost than i.i.d. sampling from the most accurate ABC approximation. Several numerical examples are given.