The rate of convergence of the Walk on Spheres Algorithm

Ilia Binder; Mark Braverman

doi:10.1007/s00039-012-0161-z

The rate of convergence of the Walk on Spheres Algorithm

Ilia Binder
, Mark Braverman

Research output: Contribution to journal › Article › peer-review

24 Scopus citations

Abstract

In this paper we examine the rate of convergence of one of the standard algorithms for emulating exit probabilities of Brownian motion, the Walk on Spheres (WoS) algorithm. We obtain a complete characterization of the rate of convergence of WoS in terms of the local geometry of a domain.

Original language	English (US)
Pages (from-to)	558-587
Number of pages	30
Journal	Geometric and Functional Analysis
Volume	22
Issue number	3
DOIs	https://doi.org/10.1007/s00039-012-0161-z
State	Published - Sep 2012
Externally published	Yes

All Science Journal Classification (ASJC) codes

Analysis
Geometry and Topology

Keywords

Walk on spheres algorithm
harmonic measure
potential theory

Access to Document

10.1007/s00039-012-0161-z

Cite this

@article{d69e9175dce84c84bc82209eb1593791,

title = "The rate of convergence of the Walk on Spheres Algorithm",

abstract = "In this paper we examine the rate of convergence of one of the standard algorithms for emulating exit probabilities of Brownian motion, the Walk on Spheres (WoS) algorithm. We obtain a complete characterization of the rate of convergence of WoS in terms of the local geometry of a domain.",

keywords = "Walk on spheres algorithm, harmonic measure, potential theory",

author = "Ilia Binder and Mark Braverman",

note = "Funding Information: Keywords and phrases: Walk on spheres algorithm, harmonic measure, potential theory Mathematics Subject Classification (2000): 60G42, 65C05, 31B25, 31B05 I. Binder and M. Braverman were partially supported by their respective NSERC Discovery grant. This research was partially conducted during the period the second author was employed by the Clay Mathematics Institute as a Liftoff Fellow, as a postdoctoral researcher with Microsoft Research New England, and as a faculty member at the University of Toronto. A preliminary version of this work appeared in the proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA09).",

year = "2012",

month = sep,

doi = "10.1007/s00039-012-0161-z",

language = "English (US)",

volume = "22",

pages = "558--587",

journal = "Geometric and Functional Analysis",

issn = "1016-443X",

publisher = "Springer International Publishing",

number = "3",

}

TY - JOUR

T1 - The rate of convergence of the Walk on Spheres Algorithm

AU - Binder, Ilia

AU - Braverman, Mark

N1 - Funding Information: Keywords and phrases: Walk on spheres algorithm, harmonic measure, potential theory Mathematics Subject Classification (2000): 60G42, 65C05, 31B25, 31B05 I. Binder and M. Braverman were partially supported by their respective NSERC Discovery grant. This research was partially conducted during the period the second author was employed by the Clay Mathematics Institute as a Liftoff Fellow, as a postdoctoral researcher with Microsoft Research New England, and as a faculty member at the University of Toronto. A preliminary version of this work appeared in the proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA09).

PY - 2012/9

Y1 - 2012/9

N2 - In this paper we examine the rate of convergence of one of the standard algorithms for emulating exit probabilities of Brownian motion, the Walk on Spheres (WoS) algorithm. We obtain a complete characterization of the rate of convergence of WoS in terms of the local geometry of a domain.

AB - In this paper we examine the rate of convergence of one of the standard algorithms for emulating exit probabilities of Brownian motion, the Walk on Spheres (WoS) algorithm. We obtain a complete characterization of the rate of convergence of WoS in terms of the local geometry of a domain.

KW - Walk on spheres algorithm

KW - harmonic measure

KW - potential theory

UR - https://www.scopus.com/pages/publications/84866890859

UR - https://www.scopus.com/pages/publications/84866890859#tab=citedBy

U2 - 10.1007/s00039-012-0161-z

DO - 10.1007/s00039-012-0161-z

M3 - Article

AN - SCOPUS:84866890859

SN - 1016-443X

VL - 22

SP - 558

EP - 587

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

IS - 3

ER -

The rate of convergence of the Walk on Spheres Algorithm

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this