The complexity of simulating Brownian Motion

摘要

We analyze the complexity of the Walk on Spheres algorithm for simulating Brownian Motion in a domain Ω ⊂Rd. The algorithm, which was first proposed in the 1950s, produces samples from the hitting probability distribution of the Brownian Motion process on ∂Ω within an error of ε. The algorithm is used as a building block for solving a variety of differential equations, including the Dirichlet Problem.