The complexity of simulating Brownian Motion

ABSTRACT

We analyze the complexity of the Walk on Spheres algorithm for simulating Brownian Motion in a domain Ω ⊂R^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 X₀ = x in a given bounded domain Ω until it gets ε-close to the boundary ∂Ω. At every step, the algorithm measures the distance d_k from its current position X_k to ∂Ω and jumps a distance of d_k/2 in a uniformly random direction from X_k to obtain X_k+1. The algorithm terminates when it reaches X_n 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(log² 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 R³ with connected exterior, the WoS converges in O(log² 1/ε) steps;

• for d > 2, if Ω is a domain in R^d, the WoS converges in O((1/ε)^2-4/d) steps;

• for d > 3, if Ω is a domain in R^d with connected exterior, the WoS converges in O((1/ε)^2--4/(d--1)) steps;

• for any d, if Ω is a domain in R^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.

REFERENCES

• 1: Ilia Binder , Mark Braverman, Derandomization of Euclidean Random Walks, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_26]
• 2: Vasco Brattka , Klaus Weihrauch, Computability on subsets of Euclidean space I: closed and compact subsets, Theoretical Computer Science, v.219 n.1-2, p.65-93, May 28, 1999 [doi>10.1016/S0304-3975(98)00284-9]
• 3: M. Braverman and S. Cook. Computing over the reals: Foundations for scientific computing. Notices of the AMS, 53(3):318--329, 2006.
• 4: B. S. Elepov, A. A. Kronberg, G. A. Mihailov, and K. K. Sabel'fel'd. Reshenie kraevykh zadach metodom Monte-Karlo. "Nauka" Sibirsk. Otdel., Novosibirsk, 1980.
• 5: Paul Embrechts , Thomas Mikosch , Claudia Klüppelberg, Modelling extremal events: for insurance and finance, Springer-Verlag, London, 1997
• 6: J. B. Garnett and D. E. Marshall. Harmonic Measure. Cambridge Univ Press, 2004.
• 7: Shizuo Kakutani. Two-dimensional Brownian motion and harmonic functions. Proc. Imp. Acad. Tokyo, 20:706--714, 1944.
• 8: I. Karatzas and S. E. Shreve. Methods of Mathematical Finance. Springer, 1998.
• 9: N. S. Landkof. Foundations of modern potential theory. Translated from the Russian by AP Doohovskoy, volume 180. 1972.
• 10: R. M. Mazo. Brownian Motion: Fluctuations, Dynamics, and Applications. Oxford University Press, 2002.
• 11: G. A. Mihailov. Estimation of the difficulty of simulating the process of "random walk on spheres" for some types of regions. Zh. Vychisl. Mat. i Mat. Fiz., 19(2):510--515, 558--559, 1979.
• 12: G. N. Milstein. Numerical Integration of Stochastic Differential Equations. Kluwer Academic Publishers, Dodrecht, 1995.
• 13: Minoru Motoo. Some evaluations for continuous Monte Carlo method by using Brownian hitting process. Ann. Inst. Statist. Math. Tokyo, 11:49--54, 1959.
• 14: M. E. Muller. Some continuous Monte Carlo methods for the Dirichlet problem. Ann. Math. Statist., 27:569--589, 1956.
• 15: E. Nelson. Dynamical Theories of Brownian Motion. Princeton University Press Princeton, NJ, 1967.
• 16: A. S. Sznitman. Brownian Motion, Obstacles and Random Media. Springer, 1998.
• 17: Klaus Weihrauch, Computable analysis: an introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 2000

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms