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…
≈ 5 min read
Walk-on-spheres method. encyclopegia.org, snapshot enwiki-001368623327. /a/walk-on-spheres-method
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
Informal description
Let \Omega be a bounded domain in \mathbb{R}^d with a sufficiently regular boundary \Gamma , let h be a function on \Gamma , and let x be a point inside \Omega . Consider the Dirichlet problem: \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 that when the solution u exists, for x \in \Omega : u(x) = \mathbb{E}_x[ h(W_{\tau}) ] where is a -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: \mathbb{E}_x[ h(W_\tau) ] \sim \frac{1}{n} \sum_{i=1}^n h(W^i_\tau) 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 -sphere centred on , the first point of exit of out of the sphere has a uniform distribution over its surface. Thus, it starts with equal to , and draws the largest sphere \mathcal{S}_0 centered on and contained inside the domain.
The first point of exit from \mathcal{S}_0 is uniformly distributed on its surface. By repeating this step inductively, the WoS provides a sequence 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 \varepsilon -shell, or \varepsilon -layer.
Initialize : x^{(0)} = x While d(x^{(n)}, \Gamma) > \varepsilon : Set r_n = d(x^{(n)}, \Gamma) . Sample \gamma_n a vector uniformly distributed over the unit sphere, independently from the preceding ones.
Set x^{(n+1)} := x^{(n)} + r_n \gamma_n When d(x^{(n)}, \Gamma) \le \varepsilon : x_f := p_{\Gamma}(x^{(n)}) , the orthogonal projection of x^{(n)} on \Gamma Return x_f The result x_f is an estimator of the first exit point from \Omega of a Wiener process starting from x , in the sense that they have close probability distributions (see below for comments on the error). 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 \Delta u = cu + f (which include the Poisson and linearized Poisson−Boltzmann equations) or for any elliptic partial differential equation with constant coefficients. More efficient ways of solving the linearized Poisson–Boltzmann equation have also been developed, relying on Feynman−Kac representations of the solutions. \begin{cases} \partial_t u(x,t) + \frac{1}{2}\Delta_x u (x, t) =0 & \mbox{if }x \in \Omega \mbox{ and } t of which the solution can be represented as: u(x,t) = \mathbb{E}_{t,x} (h(X_{T \wedge \tau}, T \wedge \tau)) , where the expectation is taken conditionally on 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 \tau_0 with Laplace transform (for a sphere of radius R ): \mathbb{E}(\exp(- s \tau_0)) = \frac{R \sqrt{2s}}{\sinh(R \sqrt{2s})} The total time of exit from the domain \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 T .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368623327 under CC BY-SA 4.0; modifications have been made.