The complexity of simulating Brownian Motion

Ilia Binder, Mark Braverman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

We analyze the complexity of the Walk on Spheres algorithm for simulating Brownian Motion in a domain Ω ⊂ ℝd. 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. The WoS algorithm simulates a BM starting at a point X0 = x in a given bounded domain Ω until it gets ε-close to the boundary ∂Ω. At every step, the algorithm measures the distance dk from its current position Xk to ∂Ω and jumps a distance of d k/2 in a uniformly random direction from Xk to obtain Xk+1. The algorithm terminates when it reaches Xn that is ε-close to ∂Ω. It is not hard to see that the algorithm requires at least Ω(log 1/ε) steps to converge. Only partial results with respect to the upper bound existed. In 1959 M. Motoo established an O(log 1/ε) bound on the running time for convex domains. The results were later generalized for a wider, but still very restricted, class of planar and 3-dimensional domains by G.A. Mikhailov (1979). In our earlier work (2007), we established an upper bound of O(log2 1/ε) on the rate of convergence of WoS for arbitrary planar domains. In this paper we introduce energy functions using Newton potentials to obtain very general upper bounds on the convergence of the algorithm. Special instances of the upper bounds yield the following results for bounded domains Ω: • if Ω is a planar domain with connected exterior, the WoS converges in O(log 1/ε) steps; • if Ω is a domain in ℝ3 with connected exterior, the WoS converges in O(log2 1/ε) steps; • for d > 2, if Ω is a domain in ℝd, the WoS converges in O((1/ε)2-4/d) steps; • for d > 3, if Ω is a domain in ℝd with connected exterior, the WoS converges in O((1/ε)2-4/(d-1)) steps; • for any d, if Ω is a domain in ℝd bounded by a smooth surface ∂Ω, the WoS converges in O(log 1/ε) steps. We also demonstrate that the bounds are tight, i.e. we construct a domain from each class for which the upper bound is exact. Our results give the optimal upper bound of O(log 1/ε) in many cases for which only a bound polynomial in 1/ε was previously known.

Original languageEnglish (US)
Title of host publicationProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
PublisherAssociation for Computing Machinery
Pages58-67
Number of pages10
ISBN (Print)9780898716801
DOIs
StatePublished - Jan 1 2009
Externally publishedYes
Event20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, United States
Duration: Jan 4 2009Jan 6 2009

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other20th Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew York, NY
Period1/4/091/6/09

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The complexity of simulating Brownian Motion'. Together they form a unique fingerprint.

  • Cite this

    Binder, I., & Braverman, M. (2009). The complexity of simulating Brownian Motion. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 58-67). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973068.7