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. 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.

Informal description

Let ${\displaystyle \Omega }$ be a bounded domain in ${\displaystyle \mathbb {R} ^{d}}$ with a sufficiently regular boundary ${\displaystyle \Gamma }$, let h be a function on ${\displaystyle \Gamma }$, and let ${\displaystyle x}$ be a point inside ${\displaystyle \Omega }$.

Consider the Dirichlet problem:

${\displaystyle {\begin{cases}\Delta u(x)=0&{\mbox{if }}x\in \Omega \\u(x)=h(x)&{\mbox{if }}x\in \Gamma .\end{cases}}}$

It can be easily shown ^{[lower-alpha 1]} that when the solution ${\displaystyle u}$ exists, for ${\displaystyle x\in \Omega }$:

${\displaystyle u(x)=\mathbb {E} _{x}[h(W_{\tau })]}$

where W is a d-dimensional Wiener process, the expected value is taken conditionally on {W₀ = 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:

${\displaystyle \mathbb {E} _{x}[h(W_{\tau })]\sim {\frac {1}{n}}\sum _{i=1}^{n}h(W_{\tau }^{i})}$

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⁽⁰⁾ equal to x, and draws the largest sphere ${\displaystyle {\mathcal {S}}_{0}}$ centered on x⁽⁰⁾ and contained inside the domain. The first point of exit x⁽¹⁾ from ${\displaystyle {\mathcal {S}}_{0}}$ is uniformly distributed on its surface. By repeating this step inductively, the WoS provides a sequence (x⁽ⁿ⁾) 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. For computational implementation, the process is usually stopped when it gets sufficiently close to the border, and returns the projection of the process on the border. This procedure is sometimes called introducing an ${\displaystyle \varepsilon }$-shell, or ${\displaystyle \varepsilon }$-layer. ^[4]

Formulation of the method

Illustration of a run of the Walk-on-spheres algorithm on an arbitrary domain ${\displaystyle \Omega }$ with an ${\displaystyle \varepsilon }$-shell

Choose ${\displaystyle \varepsilon >0}$. Using the same notations as above, the Walk-on-spheres algorithm is described as follows:

1. Initialize : ${\displaystyle x^{(0)}=x}$
2. While ${\displaystyle d(x^{(n)},\Gamma )>\varepsilon }$:
   1. Set ${\displaystyle r_{n}=d(x^{(n)},\Gamma )}$.
   2. Sample ${\displaystyle \gamma _{n}}$ a vector uniformly distributed over the unit sphere, independently from the preceding ones.
   3. Set ${\displaystyle x^{(n+1)}:=x^{(n)}+r_{n}\gamma _{n}}$
3. When ${\displaystyle d(x^{(n)},\Gamma )\leq \varepsilon }$:
4. ${\displaystyle x_{f}:=p_{\Gamma }(x^{(n)})}$, the orthogonal projection of ${\displaystyle x^{(n)}}$ on ${\displaystyle \Gamma }$
5. Return ${\displaystyle x_{f}}$

The result ${\displaystyle x_{f}}$ is an estimator of the first exit point from ${\displaystyle \Omega }$ of a Wiener process starting from ${\displaystyle x}$, in the sense that they have close probability distributions (see below for comments on the error).

Comments and practical considerations

Radius of the spheres

In some cases the distance to the border might be difficult to compute, and it is then preferable to replace the radius of the sphere by a lower bound of this distance. One must then ensure that the radius of the spheres stays large enough so that the process reaches the border. ^[1]

Bias in the method and GFFP

The Walk-on-spheres method is used until the process gets ${\displaystyle \delta }$-close to the border. Then the sphere is replaced by its "intersection" with the boundary of the domain.

As it is a Monte-Carlo method, the error of the estimator can be decomposed into the sum of a bias, and a statistical error. 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. However, as it is formulated here, the ${\displaystyle \varepsilon }$-shell introduced to ensure that the algorithm terminates also adds an error, usually of order ${\displaystyle {\mathcal {O}}(\varepsilon )}$. ^[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. This requires the knowledge of Green's functions for the specific domains. (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. ^[4]

Complexity

It can be shown that the number of steps taken for the WoS process to reach the ${\displaystyle \varepsilon }$-shell is of order ${\displaystyle {\mathcal {O}}(|\log(\varepsilon )|)}$. ^[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 ${\displaystyle 3}$, and one only needs a small set of values. Indeed, the computational cost increases linearly with the dimension, whereas the cost of grid dependant methods increase exponentially with the dimension. ^[2]

Variants, extensions

This method has been largely studied, generalized and improved. 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:

Elliptic equations

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 ${\displaystyle \Delta u=cu+f}$ ^[6] (which include the Poisson and linearized Poisson−Boltzmann equations) or for any elliptic partial differential equation with constant coefficients. ^[7]

More efficient ways of solving the linearized Poisson–Boltzmann equation have also been developed, relying on Feynman−Kac representations of the solutions. ^[8]

Time dependency

Again, within a regular enough border, it possible to use the WoS method to solve the following problem :

${\displaystyle {\begin{cases}\partial _{t}u(x,t)+{\frac {1}{2}}\Delta _{x}u(x,t)=0&{\mbox{if }}x\in \Omega {\mbox{ and }}t<T\\u(x,T)=h(x,T)&{\mbox{if }}x\in {\bar {\Omega }}\\u(x,t)=h(x,t)&{\mbox{if }}x\in \Gamma .\end{cases}}}$

of which the solution can be represented as: ^[9]

${\displaystyle u(x,t)=\mathbb {E} _{t,x}(h(X_{T\wedge \tau },T\wedge \tau ))}$,

where the expectation is taken conditionally on ${\displaystyle X_{t}=x}$

To use the WoS through this formula, one needs to sample the exit-time from each sphere drawn, which is an independent variable ${\displaystyle \tau _{0}}$ with Laplace transform (for a sphere of radius ${\displaystyle R}$): ^[10]

${\displaystyle \mathbb {E} (\exp(-s\tau _{0}))={\frac {R{\sqrt {2s}}}{\sinh(R{\sqrt {2s}})}}}$

The total time of exit from the domain ${\displaystyle \tau }$ can be computed as the sum of the exit-times from the spheres. The process also has to be stopped when it has not exited the domain at time ${\displaystyle T}$.

Other extensions

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". ^[12] This problem has applications in mathematical finance.

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. ^[14]

See also

• Feynman–Kac formula
• Stochastic processes and boundary value problems
• Euler–Maruyama method to sample the paths of general diffusion processes

Notes

1. The link was first established by Kakutani for the 2-dimensional Brownian motion, ^[3] it can now be seen as a trivial case of the Feynman−Kac formula.

References

1. Muller, Mervin E. (Sep 1956). "Some continuous Monte-Carlo Methods for the Dirichlet Problem". The Annals of Mathematical Statistics. 27 (3): 569–589. doi: 10.1214/aoms/1177728169 . JSTOR   2237369.
2. Sabelfeld, Karl K. (1991). Monte Carlo methods in boundary value problems. Berlin [etc.]: Springer-Verlag. ISBN   978-3540530015.
3. Kakutani, Shizuo (1944). "Two-dimensional Brownian motion and harmonic functions". Proceedings of the Imperial Academy. 20 (10): 706–714. doi: 10.3792/pia/1195572706 .
4. Mascagni, Michael; Hwang, Chi-Ok (June 2003). "ϵ-Shell error analysis for "Walk On Spheres" algorithms". Mathematics and Computers in Simulation. 63 (2): 93–104. doi:10.1016/S0378-4754(03)00038-7.
5. Given, James A.; Hubbard, Joseph B.; Douglas, Jack F. (1997). "A first-passage algorithm for the hydrodynamic friction and diffusion-limited reaction rate of macromolecules". The Journal of Chemical Physics. 106 (9): 3761. Bibcode:1997JChPh.106.3761G. doi:10.1063/1.473428.
6. Elepov, B.S.; Mikhailov, G.A. (January 1969). "Solution of the dirichlet problem for the equation Δu − cu = −q by a model of "walks on spheres"". USSR Computational Mathematics and Mathematical Physics. 9 (3): 194–204. doi:10.1016/0041-5553(69)90070-6.
7. Booth, Thomas E (February 1981). "Exact Monte Carlo solution of elliptic partial differential equations". Journal of Computational Physics. 39 (2): 396–404. Bibcode:1981JCoPh..39..396B. doi:10.1016/0021-9991(81)90159-5.
8. Hwang, Chi-Ok; Mascagni, Michael; Given, James A. (March 2003). "A Feynman–Kac path-integral implementation for Poisson's equation using an h-conditioned Green's function". Mathematics and Computers in Simulation. 62 (3–6): 347–355. CiteSeerX   10.1.1.123.3156 . doi:10.1016/S0378-4754(02)00224-0.
9. Gobet, Emmanuel (2013). Méthodes de Monte-Carlo et processus stochastiques du linéaire au non-linéaire. Palaiseau: Editions de l'Ecole polytechnique. ISBN   978-2-7302-1616-6.
10. Salminen, Andrei N. Borodin; Paavo (2002). Handbook of Brownian motion : facts and formulae (2. ed.). Basel [u.a.]: Birkhäuser. ISBN   978-3-7643-6705-3.
11. Booth, Thomas (August 1982). "Regional Monte Carlo solution of elliptic partial differential equations" (PDF). Journal of Computational Physics. 47 (2): 281–290. Bibcode:1982JCoPh..47..281B. doi:10.1016/0021-9991(82)90079-1.
12. Deaconu, Madalina; Herrmann, Samuel (December 2013). "Hitting time for Bessel processes—walk on moving spheres algorithm (WoMS)". The Annals of Applied Probability. 23 (6): 2259–2289. arXiv: 1111.3736 . doi:10.1214/12-AAP900. S2CID   25036031.
13. Simonov, Nikolai A. (2007). "Random Walks for Solving Boundary-Value Problems with Flux Conditions". Numerical Methods and Applications. Lecture Notes in Computer Science. Vol. 4310. pp. 181–188. CiteSeerX   10.1.1.63.3780 . doi:10.1007/978-3-540-70942-8_21. ISBN   978-3-540-70940-4.{{cite book}}: Missing or empty |title= (help)
14. Sawhney, Rohan; Seyb, Dario; Jarosz, Wojciech; Crane, Keenan (July 2022). "Grid-Free Monte Carlo for PDEs with Spatially Varying Coefficients". ACM Transactions on Graphics. 41 (4): 1–17. arXiv: 2201.13240 . doi:10.1145/3528223.3530134. S2CID   246430740.

Further reading

• Sabelfeld, Karl K. (1991). Monte Carlo methods in boundary value problems. Berlin [etc.]: Springer-Verlag. ISBN   9783540530015.

External links

• Some continuous Monte-Carlo methods for the Dirichlet problem The paper in which Marvin Edgar Muller introduced the method.
• Brownian Motion by Peter Mörters and Yuval Peres. See Chapter 3.3 on harmonic measure, Green's functions and exit-points.