Computational Mathematics and Statistics Seminar by Valerie N. P. Ho: Randomized Quasi-Monte Carlo for Walk on Spheres

Walk on Spheres (WOS) is a grid-free Monte Carlo method for estimating solutions to boundary value problems via probabilistic representations [1]. Rather than simulating full Brownian paths, WOS iteratively samples exit points from the largest sphere contained in the domain and centered at the current location. The walk stops when it enters a small boundary neighborhood, and the boundary data are evaluated at the projected terminal point. Averaging over many independent walks produces an estimator of the solution.

 

This talk will discuss two related projects on improving WOS using randomized quasi-Monte Carlo methods. In the first project [2], we replaced standard Monte Carlo sampling within WOS by randomized quasi-Monte Carlo (RQMC) point sets and study the resulting error and variance behavior. Across a range of test problems and geometries, including examples drawn from computer graphics and from prior research on WOS [3], RQMC yields modest but consistent improvements in root mean squared error and in variance decay. Empirically, we observe variance rates close to n^(-1.2) in several settings, compared with the n^(-1) baseline of Monte Carlo, corresponding to a gain of approximately 5–10 times for the same sample size. We provide a theoretical analysis of the convergence rate, making use of results available in the literature regarding RQMC rates of convergence for discontinuous integrands [4].

 

In the second project [5], we combine WOS with Array-RQMC [6], a sequential RQMC method for Markov chains. On the same set of examples, the resulting estimator attains empirical variance rates between O(n^(-1.4)) and O(n^(-1.8)), with variance reduction factors ranging from 57 to 2290 relative to standard Monte Carlo at n = 2^17.