page_title: Walk-on-spheres method
section_title: Formulation of the method
hierarchical_section_title: Walk-on-spheres method / Formulation of the method
caption_attribution_description: English: Illustration of a run of the Walk of Spheres algorithm on an arbitrary domain \Omega with an \epsilon-shell
context_page_description: In mathematics, the walk-on-spheres method 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. 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,
  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.
context_section_description: Choose . Using the same notations as above, the Walk-on-spheres algorithm is described as follows:
  Initialize : 
  While :
  Set .
  Sample  a vector uniformly distributed over the unit sphere, independently from the preceding ones.
  Set 
  When :
  , the orthogonal projection of  on 
  Return 
  The result  is an estimator of the first exit point from  of a Wiener process starting from , in the sense that they have close probability distributions (see below for comments on the error).
caption: Illustration of a run of the Walk-on-spheres algorithm on an arbitrary domain 
    
      
        
          Ω
        
      
      {\displaystyle \Omega }
    
   with an 
    
      
        
          ε
        
      
      {\displaystyle \varepsilon }
    
  -shell
exif: {}