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
A wide class of such applications can be characterized as those based on
generation of random walks via a Markov process. In these cases the Monte
Carlo method is based on the probabilistic application of a linear
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.
Exploring the Use of Quasirandom Numbers in Monte Carlo
Quasirandom numbers do improve the convergence of applications like
integration, and it is by no means trivial to enhance the convergence of
In fact, even with numerical integration, enhanced convergence is by no
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
was that a considerable fraction of the enhanced convergence
is lost in quasi-Monte Carlo integration when the integrand is
In fact, even in two dimensions one can loose the approximately
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
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
solving a system of linear algebraic equations, approximately inverting a
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