ϵ-Shell error analysis for “Walk On Spheres” algorithms

The “Walk On Spheres” (WOS) algorithm and its relatives have long been used to solve a wide variety of boundary value problems [Ann. Math. Stat. 27 (1956) 569; J. Heat Transfer 89 (1967) 121; J. Chem. Phys. 100 (1994) 3821; J. Appl. Phys. 71 (1992) 2727]. All WOS algorithms that require the construction of random walks that terminate, employ an ϵ-shell to ensure their termination in a finite number of steps. To remove the error related to this ϵ-shell, Green’s function first-passage (GFFP) algorithms have been proposed [J. Chem. Phys. 106 (1997) 3721] and used in several applications [Phys. Fluids A 12 (2000) 1699; Monte Carlo Meth. Appl. 7 (2001) 213; The simulation–tabulation method for classical diffusion Monte Carlo, J. Comput. Phys. submitted]. One way to think of the GFFP algorithm is as an ϵ=0 extension of WOS. Thus, an important open question in the use of GFFP is to understand the tradeoff made in the efficiency of GFFP versus the ϵ-dependent error in WOS. In this paper, we present empirical evidence and analytic analysis of the ϵ-shell error in some simple boundary value problems for the Laplace and Poisson equations and show that the error associated with the ϵ-shell is O(ϵ), for small ϵ. This fact supports the conclusion that GFFP is preferable to WOS in cases where both are applicable.