Group: QMC

Quasi-Monte Carlo Methods

Department of Computer Science
Florida State University

Monte Carlo methods (MCMs) are based on the simulation of stochastic processes whose expected values are equal to computationally interesting quantities. MCMs offer simplicity of construction, and are often designed to mirror some process whose behavior is only understood in a statistical sense. Despite the universality of MCMs, a serious drawback is their slow convergence. The error of MCMs is stochastic, and the uncertainty in an average taken from N samples is O(N-1/2) by virtue of the central limit theorem. One generic approach to improving the convergence of MCMs has been the use of highly uniform, quasirandom, numbers (QRNs) in place of the usual pseudo random numbers (PRNs). While PRNs are constructed to mimic the behavior of truly random numbers QRNs are constructed to be distributed as evenly as mathematically possible. With QRNs, for example, the convergence of numerical integration can sometimes be improved to O(N-1).
There are many Monte Carlo application areas besides numerical integration. A wide class of such applications can be characterized as those based on the generation of random walks via a Markov process. In these cases the Monte Carlo method is based on the probabilistic application of a linear operator. However, the investigation of the applicability of QRNs for convergence acceleration for a wide class of problems based on Markov chain MCMs have never been carefully undertaken.
Therefore, we are currently working to determine best practices and performance of quasi-Monte Carlo methods for Markov chain problems. Such a study includes a theoretical investigation into the convergence and computational complexity of these methods as well as empirical comparisons of these methods to standard MCMs.

Time: Mondays 8:00 AM
Place: 486 Dirac Science Library
Dr. Aneta Karaivanova
Yaohang Li
Peter Bismuti
  Peter's home page
PRNG Group
Testing Group
QRNG Group
Discrete Group
QMC Group
Finance Group
Prof. Michael Mascagni
Ethan Kromhout
Project 11
Exploring the Use of Quasirandom Numbers in Monte Carlo

Quasirandom numbers do improve the convergence of applications like numerical integration, and it is by no means trivial to enhance the convergence of all MCMs. In fact, even with numerical integration, enhanced convergence is by no means assured in all situations with the naive use of quasirandom numbers. In high dimensions, s > 40 quasi-Monte Carlo integration ceases an improvement over regular Monte Carlo integration. Perhaps more startling was that a considerable fraction of the enhanced convergence is lost in quasi-Monte Carlo integration when the integrand is discontinuous. In fact, even in two dimensions one can loose the approximately O(N-1) quasi-Monte Carlo convergence for an integrand that is discontinuous on a curve such as a circle. In the best cases the convergence drops to O(N-2/3), which is only slightly better than regular Monte Carlo integration.
In the framework of this project we are studying quasi-Monte Carlo methods for Markov chain based problems. The specific computational problems we investigate include: Discrete Markov Chain problems: Quasi-MCMs for matrix computations, including solving a system of linear algebraic equations, approximately inverting a given matrix,
and computing the extremal eigenvalues of a given matrix. Continuous Markov Chain problems: Quasi-MCMs for solving Fredholm integral equations of the second kind, and elliptic boundary value problems based on a local integral Green's function representation, and, path integral calculations.