Walk-on-spheres method

In mathematics, the walk-on-spheres method (WoS) is a numerical probabilistic algorithm, or Monte-Carlo method, used mainly in order to approximate the solutions of some specific boundary value problem for partial differential equations (PDEs). The WoS method was first introduced by Mervin E. Muller in 1956 to solve Laplace's equation, and was since then generalized to other problems. It relies on probabilistic interpretations of PDEs, and simulates paths of Brownian motion (or for some more general variants, diffusion processes), by sampling only the exit-points out of successive spheres, rather than simulating in detail the path of the process. This often makes it less costly than "grid-based" algorithms, and it is today one of the most widely used "grid-free" algorithms for generating Brownian paths. Let be a bounded domain in with a sufficiently regular boundary , let h be a function on , and let be a point inside . Consider the Dirichlet problem: It can be easily shown that when the solution exists, for : where W is a d-dimensional Wiener process, the expected value is taken conditionally on , and τ is the first-exit time out of Ω. To compute a solution using this formula, we only have to simulate the first exit point of independent Brownian paths since with the law of large numbers: The WoS method provides an efficient way of sampling the first exit point of a Brownian motion from the domain, by remarking that for any (d − 1)-sphere centred on x, the first point of exit of W out of the sphere has a uniform distribution over its surface. Thus, it starts with x(0) equal to x, and draws the largest sphere centered on x(0) and contained inside the domain. The first point of exit x(1) from is uniformly distributed on its surface. By repeating this step inductively, the WoS provides a sequence (x(n)) of positions of the Brownian motion. According to intuition, the process will converge to the first exit point of the domain. However, this algorithm takes almost surely an infinite number of steps to end.