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).
[1][2] The WoS method was first introduced by Mervin E. Muller in 1956 to solve Laplace's equation,[1] 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.
: where W is a d-dimensional Wiener process, the expected value is taken conditionally on {W0 = x}, 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.
By repeating this step inductively, the WoS provides a sequence (x(n)) of positions of the Brownian motion.
One must then ensure that the radius of the spheres stays large enough so that the process reaches the border.
The statistical error is reduced by increasing the number of paths sampled, or by using variance reduction methods.
The WoS theoretically provides exact (or unbiased) simulations of the paths of the Brownian motion.
[4] This error has been studied, and can be avoided in some geometries by using Green's Functions First Passage method:[5] one can change the geometry of the "spheres" when close enough to the border, so that the probability of reaching the border in one step becomes positive.
(see also Harmonic measure) When it is possible to use it, the Green's function first-passage (GFFP) method is usually preferred, as it is both faster and more accurate than the classical WoS.
[2] Therefore, one can increase the precision to a certain extent without making the number of steps grow notably.
As it is commonly the case for Monte-Carlo methods, this algorithm performs particularly well when the dimension is higher than
For example, it is now extensively used for the computation of physical properties of materials (such as capacitance, electrostatic internal energy of molecules, etc.).
Some notable extensions include: The WoS method can be modified to solve more general problems.
In particular, the method has been generalized to solve Dirichlet problems for equations of the form
[7] More efficient ways of solving the linearized Poisson–Boltzmann equation have also been developed, relying on Feynman−Kac representations of the solutions.
[8] Again, within a regular enough border, it possible to use the WoS method to solve the following problem : of which the solution can be represented as:[9] where the expectation is taken conditionally on
To use the WoS through this formula, one needs to sample the exit-time from each sphere drawn, which is an independent variable
The WoS method has been generalized to estimate the solution to elliptic partial differential equations everywhere in a domain, rather than at a single point.
[11] The WoS method has also been generalized in order to compute hitting times for processes other than Brownian motions.
For example, hitting times of Bessel processes can be computed via an algorithm called "Walk on moving spheres".
The WoS can be adapted to solve the Poisson and Poisson–Boltzmann equation with flux conditions on the boundary.
[13] Finally, WoS can be used to solve problems where coefficients vary continuously in space, via connections with the volume rendering equation.
