Randomized quasi-Monte Carlo for Markov Chains
Seminar Room 1, Newton Institute
Quasi-Monte Carlo (QMC) methods are numerical techniques for estimating large-dimensional integrals, usually over the unit hypercube. They can be applied, at least in principle, to any stochastic simulation whose aim is to estimate a mathematical expectation. This covers a wide range of applications. Practical error bounds are hard to obtain with QMC but randomized quasi-Monte Carlo (RQMC) permits one to compute an unbiased estimator of the integral, together with a confidence interval. RQMC can in fact be viewed as a variance-reduction technique.
In this talk, we review some key ideas of RQMC methods and provide concrete examples of their application to simulate systems modeled as Markov chains. We also present a new RQMC method, called array-RQMC, recently introduced to simulate Markov chains over a large number of steps. Our numerical illustrations indicate that RQMC can dramatically reduce the variance compared with standard Monte Carlo.