1444:
797:
2022:
1752:
747:
According to intuition, the process will converge to the first exit point of the domain. However, this algorithm takes almost surely an infinite number of steps to end. For computational implementation, the process is usually stopped when it gets sufficiently close to the border, and returns the
62:), by sampling only the exit-points out of successive spheres, rather than simulating in detail the path of the process. This often makes it less costly than "grid-based" algorithms, and it is today one of the most widely used "grid-free" algorithms for generating Brownian paths.
1434:
In some cases the distance to the border might be difficult to compute, and it is then preferable to replace the radius of the sphere by a lower bound of this distance. One must then ensure that the radius of the spheres stays large enough so that the process reaches the border.
338:
1543:
First
Passage method: one can change the geometry of the "spheres" when close enough to the border, so that the probability of reaching the border in one step becomes positive. This requires the knowledge of Green's functions for the specific domains. (see also
2017:{\displaystyle {\begin{cases}\partial _{t}u(x,t)+{\frac {1}{2}}\Delta _{x}u(x,t)=0&{\mbox{if }}x\in \Omega {\mbox{ and }}t<T\\u(x,T)=h(x,T)&{\mbox{if }}x\in {\bar {\Omega }}\\u(x,t)=h(x,t)&{\mbox{if }}x\in \Gamma .\end{cases}}}
2321:
625:
2127:
1661:, and one only needs a small set of values. Indeed, the computational cost increases linearly with the dimension, whereas the cost of grid dependant methods increase exponentially with the dimension.
1636:
220:
1203:
1145:
967:
1537:
1267:
1031:
459:
734:
691:
868:
121:
1717:
1581:
1504:
838:
786:
766:
387:
1061:
1669:
This method has been largely studied, generalized and improved. For example, it is now extensively used for the computation of physical properties of materials (such as
2193:
911:
2795:
2401:
2164:
1465:
1399:
1320:
1300:
818:
205:
165:
141:
88:
2344:
1681:
The WoS method can be modified to solve more general problems. In particular, the method has been generalized to solve
Dirichlet problems for equations of the form
1379:
1349:
2221:
2364:
2213:
1659:
1419:
361:
185:
2374:
The WoS method has been generalized to estimate the solution to elliptic partial differential equations everywhere in a domain, rather than at a single point.
518:
3040:
2377:
The WoS method has also been generalized in order to compute hitting times for processes other than
Brownian motions. For example, hitting times of
2033:
3050:
2426:
The link was first established by
Kakutani for the 2-dimensional Brownian motion, it can now be seen as a trivial case of the FeynmanâKac formula.
2939:
Sawhney, Rohan; Seyb, Dario; Jarosz, Wojciech; Crane, Keenan (July 2022). "Grid-Free Monte Carlo for PDEs with
Spatially Varying Coefficients".
1728:
2387:
Finally, WoS can be used to solve problems where coefficients vary continuously in space, via connections with the volume rendering equation.
2923:
2779:
2754:
2704:
Hwang, Chi-Ok; Mascagni, Michael; Given, James A. (March 2003). "A FeynmanâKac path-integral implementation for
Poisson's equation using an
2346:
can be computed as the sum of the exit-times from the spheres. The process also has to be stopped when it has not exited the domain at time
1486:
The WoS theoretically provides exact (or unbiased) simulations of the paths of the
Brownian motion. However, as it is formulated here, the
630:
The WoS method provides an efficient way of sampling the first exit point of a
Brownian motion from the domain, by remarking that for any
2510:
1476:
508:
To compute a solution using this formula, we only have to simulate the first exit point of independent
Brownian paths since with the
3035:
2997:
2851:
Deaconu, Madalina; Herrmann, Samuel (December 2013). "Hitting time for Bessel processesâwalk on moving spheres algorithm (WoMS)".
3045:
2168:
To use the WoS through this formula, one needs to sample the exit-time from each sphere drawn, which is an independent variable
1641:
As it is commonly the case for Monte-Carlo methods, this algorithm performs particularly well when the dimension is higher than
1724:
333:{\displaystyle {\begin{cases}\Delta u(x)=0&{\mbox{if }}x\in \Omega \\u(x)=h(x)&{\mbox{if }}x\in \Gamma .\end{cases}}}
91:
40:
1586:
2381:
can be computed via an algorithm called "Walk on moving spheres". This problem has applications in mathematical finance.
1154:
1069:
918:
2810:
2406:
1509:
3013:
2384:
The WoS can be adapted to solve the
Poisson and PoissonâBoltzmann equation with flux conditions on the boundary.
1638:. Therefore, one can increase the precision to a certain extent without making the number of steps grow notably.
1555:
first-passage (GFFP) method is usually preferred, as it is both faster and more accurate than the classical WoS.
1210:
2593:"A first-passage algorithm for the hydrodynamic friction and diffusion-limited reaction rate of macromolecules"
1746:
Again, within a regular enough border, it possible to use the WoS method to solve the following problem :
2396:
1734:
More efficient ways of solving the linearized PoissonâBoltzmann equation have also been developed, relying on
975:
395:
2901:
2717:
2669:
Booth, Thomas E (February 1981). "Exact Monte Carlo solution of elliptic partial differential equations".
36:
3022:
by Peter Mörters and Yuval Peres. See Chapter 3.3 on harmonic measure, Green's functions and exit-points.
2564:
Mascagni, Michael; Hwang, Chi-Ok (June 2003). "Ï”-Shell error analysis for "Walk On Spheres" algorithms".
736:
is uniformly distributed on its surface. By repeating this step inductively, the WoS provides a sequence
1467:-close to the border. Then the sphere is replaced by its "intersection" with the boundary of the domain.
708:
665:
847:
48:
97:
2896:
Simonov, Nikolai A. (2007). "Random Walks for Solving Boundary-Value Problems with Flux Conditions".
2825:
2678:
2604:
1472:
1421:, in the sense that they have close probability distributions (see below for comments on the error).
509:
2722:
1761:
1443:
229:
2906:
2630:
Elepov, B.S.; Mikhailov, G.A. (January 1969). "Solution of the dirichlet problem for the equation Î
1684:
1552:
1540:
59:
1566:
1489:
823:
771:
751:
366:
2966:
2948:
2878:
2860:
2789:
2478:
1480:
1039:
32:
2171:
1506:-shell introduced to ensure that the algorithm terminates also adds an error, usually of order
877:
796:
2993:
2919:
2775:
2750:
2506:
1471:
As it is a Monte-Carlo method, the error of the estimator can be decomposed into the sum of a
211:
2316:{\displaystyle \mathbb {E} (\exp(-s\tau _{0}))={\frac {R{\sqrt {2s}}}{\sinh(R{\sqrt {2s}})}}}
2136:
1450:
1384:
1305:
1272:
803:
190:
150:
126:
73:
2958:
2911:
2870:
2833:
2727:
2686:
2651:
2612:
2573:
2539:
2468:
2452:
2378:
1720:
1545:
870:. Using the same notations as above, the Walk-on-spheres algorithm is described as follows:
44:
2329:
1735:
1357:
1327:
1063:
a vector uniformly distributed over the unit sphere, independently from the preceding ones.
748:
projection of the process on the border. This procedure is sometimes called introducing an
1479:. The statistical error is reduced by increasing the number of paths sampled, or by using
55:
2829:
2682:
2608:
2349:
2198:
1644:
1404:
477:
346:
170:
2731:
2577:
1673:, electrostatic internal energy of molecules, etc.). Some notable extensions include:
3029:
2970:
2837:
2690:
2655:
2882:
650:
out of the sphere has a uniform distribution over its surface. Thus, it starts with
620:{\displaystyle \mathbb {E} _{x}\sim {\frac {1}{n}}\sum _{i=1}^{n}h(W_{\tau }^{i})}
2915:
1670:
1563:
It can be shown that the number of steps taken for the WoS process to reach the
20:
2747:
Méthodes de Monte-Carlo et processus stochastiques du linéaire au non-linéaire
2473:
2456:
1539:. This error has been studied, and can be avoided in some geometries by using
800:
Illustration of a run of the Walk-on-spheres algorithm on an arbitrary domain
2544:
2527:
2122:{\displaystyle u(x,t)=\mathbb {E} _{t,x}(h(X_{T\wedge \tau },T\wedge \tau ))}
2962:
28:
54:
It relies on probabilistic interpretations of PDEs, and simulates paths of
3019:
2811:"Regional Monte Carlo solution of elliptic partial differential equations"
2900:. Lecture Notes in Computer Science. Vol. 4310. pp. 181â188.
2482:
2874:
2616:
35:, used mainly in order to approximate the solutions of some specific
2592:
2953:
2865:
1442:
795:
2457:"Some continuous Monte-Carlo Methods for the Dirichlet Problem"
2591:
Given, James A.; Hubbard, Joseph B.; Douglas, Jack F. (1997).
3016:
The paper in which Marvin Edgar Muller introduced the method.
3014:
Some continuous Monte-Carlo methods for the Dirichlet problem
1592:
1515:
715:
672:
2010:
326:
1447:
The Walk-on-spheres method is used until the process gets
699:
and contained inside the domain. The first point of exit
2528:"Two-dimensional Brownian motion and harmonic functions"
2644:
USSR Computational Mathematics and Mathematical Physics
2559:
2557:
2555:
1989:
1919:
1858:
1842:
305:
256:
2772:
Handbook of Brownian motion : facts and formulae
2352:
2332:
2224:
2201:
2174:
2139:
2036:
1755:
1687:
1647:
1589:
1569:
1512:
1492:
1453:
1407:
1387:
1360:
1330:
1308:
1275:
1213:
1157:
1072:
1042:
978:
921:
880:
850:
826:
806:
774:
754:
711:
668:
521:
398:
369:
349:
223:
193:
173:
153:
129:
100:
76:
1631:{\displaystyle {\mathcal {O}}(|\log(\varepsilon )|)}
51:, and was since then generalized to other problems.
1198:{\displaystyle d(x^{(n)},\Gamma )\leq \varepsilon }
1140:{\displaystyle x^{(n+1)}:=x^{(n)}+r_{n}\gamma _{n}}
2409:to sample the paths of general diffusion processes
2358:
2338:
2315:
2207:
2187:
2158:
2121:
2016:
1711:
1653:
1630:
1575:
1531:
1498:
1459:
1413:
1393:
1373:
1343:
1314:
1294:
1261:
1197:
1139:
1055:
1025:
962:{\displaystyle d(x^{(n)},\Gamma )>\varepsilon }
961:
905:
862:
832:
812:
780:
760:
728:
685:
619:
453:
381:
355:
332:
199:
179:
159:
135:
115:
82:
2749:. Palaiseau: Editions de l'Ecole polytechnique.
2402:Stochastic processes and boundary value problems
2133:where the expectation is taken conditionally on
2195:with Laplace transform (for a sphere of radius
480:, the expected value is taken conditionally on
43:(PDEs). The WoS method was first introduced by
2990:Monte Carlo methods in boundary value problems
2503:Monte Carlo methods in boundary value problems
343:It can be easily shown that when the solution
2027:of which the solution can be represented as:
1381:is an estimator of the first exit point from
8:
2794:: CS1 maint: multiple names: authors list (
1532:{\displaystyle {\mathcal {O}}(\varepsilon )}
2770:Salminen, Andrei N. Borodin; Paavo (2002).
2496:
2494:
2492:
1262:{\displaystyle x_{f}:=p_{\Gamma }(x^{(n)})}
2952:
2905:
2864:
2721:
2543:
2472:
2351:
2331:
2297:
2273:
2267:
2252:
2226:
2225:
2223:
2200:
2179:
2173:
2144:
2138:
2089:
2064:
2060:
2059:
2035:
1988:
1932:
1931:
1918:
1857:
1841:
1809:
1795:
1768:
1756:
1754:
1686:
1646:
1620:
1600:
1591:
1590:
1588:
1568:
1514:
1513:
1511:
1491:
1452:
1406:
1386:
1365:
1359:
1335:
1329:
1307:
1280:
1274:
1244:
1231:
1218:
1212:
1168:
1156:
1131:
1121:
1102:
1077:
1071:
1047:
1041:
1002:
983:
977:
932:
920:
885:
879:
849:
825:
805:
773:
753:
720:
714:
713:
710:
677:
671:
670:
667:
608:
603:
587:
576:
562:
547:
528:
524:
523:
520:
439:
420:
416:
415:
397:
368:
348:
304:
255:
224:
222:
192:
172:
152:
128:
107:
103:
102:
99:
75:
2447:
2445:
2443:
1026:{\displaystyle r_{n}=d(x^{(n)},\Gamma )}
2710:Mathematics and Computers in Simulation
2566:Mathematics and Computers in Simulation
2439:
2419:
2326:The total time of exit from the domain
2787:
1729:elliptic partial differential equation
2461:The Annals of Mathematical Statistics
1425:Comments and practical considerations
744:of positions of the Brownian motion.
454:{\displaystyle u(x)=\mathbb {E} _{x}}
123:with a sufficiently regular boundary
7:
58:(or for some more general variants,
2774:(2. ed.). Basel : BirkhÀuser.
2642:by a model of "walks on spheres"".
2532:Proceedings of the Imperial Academy
1551:When it is possible to use it, the
2898:Numerical Methods and Applications
2001:
1934:
1854:
1806:
1765:
1738:representations of the solutions.
1688:
1401:of a Wiener process starting from
1388:
1309:
1232:
1183:
1017:
947:
807:
729:{\displaystyle {\mathcal {S}}_{0}}
686:{\displaystyle {\mathcal {S}}_{0}}
376:
317:
268:
232:
194:
154:
130:
77:
14:
2853:The Annals of Applied Probability
863:{\displaystyle \varepsilon >0}
3041:Numerical differential equations
2818:Journal of Computational Physics
2708:-conditioned Green's function".
2671:Journal of Computational Physics
116:{\displaystyle \mathbb {R} ^{d}}
2597:The Journal of Chemical Physics
1269:, the orthogonal projection of
662:, and draws the largest sphere
3051:Partial differential equations
2307:
2291:
2261:
2258:
2239:
2230:
2116:
2113:
2082:
2076:
2052:
2040:
1983:
1971:
1962:
1950:
1937:
1913:
1901:
1892:
1880:
1830:
1818:
1789:
1777:
1625:
1621:
1617:
1611:
1601:
1597:
1526:
1520:
1287:
1281:
1256:
1251:
1245:
1237:
1186:
1175:
1169:
1161:
1109:
1103:
1090:
1078:
1020:
1009:
1003:
995:
950:
939:
933:
925:
892:
886:
614:
596:
556:
553:
540:
534:
501:is the first-exit time out of
448:
445:
432:
426:
408:
402:
299:
293:
284:
278:
244:
238:
41:partial differential equations
1:
2809:Booth, Thomas (August 1982).
2732:10.1016/S0378-4754(02)00224-0
2578:10.1016/S0378-4754(03)00038-7
1712:{\displaystyle \Delta u=cu+f}
644:, the first point of exit of
27:is a numerical probabilistic
2992:. Berlin : Springer-Verlag.
2941:ACM Transactions on Graphics
2916:10.1007/978-3-540-70942-8_21
2838:10.1016/0021-9991(82)90079-1
2691:10.1016/0021-9991(81)90159-5
2656:10.1016/0041-5553(69)90070-6
2505:. Berlin : Springer-Verlag.
1731:with constant coefficients.
1576:{\displaystyle \varepsilon }
1499:{\displaystyle \varepsilon }
833:{\displaystyle \varepsilon }
781:{\displaystyle \varepsilon }
761:{\displaystyle \varepsilon }
382:{\displaystyle x\in \Omega }
25:walk-on-spheres method (WoS)
2988:Sabelfeld, Karl K. (1991).
2501:Sabelfeld, Karl K. (1991).
1439:Bias in the method and GFFP
1056:{\displaystyle \gamma _{n}}
3067:
2526:Kakutani, Shizuo (1944).
2188:{\displaystyle \tau _{0}}
906:{\displaystyle x^{(0)}=x}
792:Formulation of the method
3036:Variants of random walks
2745:Gobet, Emmanuel (2013).
3046:Boundary value problems
2963:10.1145/3528223.3530134
2474:10.1214/aoms/1177728169
2159:{\displaystyle X_{t}=x}
1460:{\displaystyle \delta }
1394:{\displaystyle \Omega }
1315:{\displaystyle \Gamma }
1295:{\displaystyle x^{(n)}}
813:{\displaystyle \Omega }
200:{\displaystyle \Omega }
160:{\displaystyle \Gamma }
136:{\displaystyle \Gamma }
83:{\displaystyle \Omega }
2545:10.3792/pia/1195572706
2360:
2340:
2317:
2209:
2189:
2160:
2123:
2018:
1727:equations) or for any
1713:
1655:
1632:
1577:
1533:
1500:
1468:
1461:
1415:
1395:
1375:
1345:
1316:
1296:
1263:
1199:
1141:
1057:
1027:
963:
907:
864:
841:
834:
814:
782:
762:
730:
687:
621:
592:
455:
383:
357:
334:
201:
181:
161:
137:
117:
84:
37:boundary value problem
16:Mathematical algorithm
2407:EulerâMaruyama method
2361:
2341:
2339:{\displaystyle \tau }
2318:
2210:
2190:
2161:
2124:
2019:
1714:
1656:
1633:
1578:
1534:
1501:
1462:
1446:
1430:Radius of the spheres
1416:
1396:
1376:
1374:{\displaystyle x_{f}}
1346:
1344:{\displaystyle x_{f}}
1317:
1297:
1264:
1200:
1142:
1058:
1028:
964:
908:
865:
835:
815:
799:
783:
763:
731:
688:
622:
572:
456:
384:
358:
335:
202:
182:
162:
138:
118:
85:
2350:
2330:
2222:
2199:
2172:
2137:
2034:
1753:
1685:
1665:Variants, extensions
1645:
1587:
1567:
1510:
1490:
1451:
1405:
1385:
1358:
1328:
1306:
1273:
1211:
1155:
1070:
1040:
976:
919:
878:
848:
824:
804:
772:
752:
709:
666:
519:
510:law of large numbers
396:
367:
347:
221:
191:
171:
151:
127:
98:
74:
66:Informal description
2830:1982JCoPh..47..281B
2683:1981JCoPh..39..396B
2609:1997JChPh.106.3761G
2397:FeynmanâKac formula
1719:(which include the
1583:-shell is of order
638:-sphere centred on
613:
60:diffusion processes
2356:
2336:
2313:
2205:
2185:
2156:
2119:
2014:
2009:
1993:
1923:
1862:
1846:
1709:
1677:Elliptic equations
1651:
1628:
1573:
1529:
1496:
1481:variance reduction
1469:
1457:
1411:
1391:
1371:
1341:
1312:
1292:
1259:
1195:
1137:
1053:
1023:
959:
903:
874:Initialize :
860:
842:
830:
810:
778:
758:
726:
683:
617:
599:
451:
379:
353:
330:
325:
309:
260:
197:
187:be a point inside
177:
157:
133:
113:
80:
49:Laplace's equation
33:Monte-Carlo method
2925:978-3-540-70940-4
2875:10.1214/12-AAP900
2781:978-3-7643-6705-3
2756:978-2-7302-1616-6
2453:Muller, Mervin E.
2359:{\displaystyle T}
2311:
2305:
2281:
2208:{\displaystyle R}
1992:
1940:
1922:
1861:
1845:
1803:
1725:PoissonâBoltzmann
1654:{\displaystyle 3}
1541:Green's Functions
1477:statistical error
1414:{\displaystyle x}
570:
356:{\displaystyle u}
308:
259:
212:Dirichlet problem
180:{\displaystyle x}
147:be a function on
47:in 1956 to solve
3058:
3003:
2975:
2974:
2956:
2936:
2930:
2929:
2909:
2893:
2887:
2886:
2868:
2859:(6): 2259â2289.
2848:
2842:
2841:
2815:
2806:
2800:
2799:
2793:
2785:
2767:
2761:
2760:
2742:
2736:
2735:
2725:
2716:(3â6): 347â355.
2701:
2695:
2694:
2666:
2660:
2659:
2627:
2621:
2620:
2617:10.1063/1.473428
2588:
2582:
2581:
2561:
2550:
2549:
2547:
2523:
2517:
2516:
2498:
2487:
2486:
2476:
2449:
2427:
2424:
2379:Bessel processes
2370:Other extensions
2365:
2363:
2362:
2357:
2345:
2343:
2342:
2337:
2322:
2320:
2319:
2314:
2312:
2310:
2306:
2298:
2283:
2282:
2274:
2268:
2257:
2256:
2229:
2214:
2212:
2211:
2206:
2194:
2192:
2191:
2186:
2184:
2183:
2165:
2163:
2162:
2157:
2149:
2148:
2128:
2126:
2125:
2120:
2100:
2099:
2075:
2074:
2063:
2023:
2021:
2020:
2015:
2013:
2012:
1994:
1990:
1942:
1941:
1933:
1924:
1920:
1863:
1859:
1847:
1843:
1814:
1813:
1804:
1796:
1773:
1772:
1718:
1716:
1715:
1710:
1660:
1658:
1657:
1652:
1637:
1635:
1634:
1629:
1624:
1604:
1596:
1595:
1582:
1580:
1579:
1574:
1553:Green's function
1546:Harmonic measure
1538:
1536:
1535:
1530:
1519:
1518:
1505:
1503:
1502:
1497:
1466:
1464:
1463:
1458:
1420:
1418:
1417:
1412:
1400:
1398:
1397:
1392:
1380:
1378:
1377:
1372:
1370:
1369:
1350:
1348:
1347:
1342:
1340:
1339:
1321:
1319:
1318:
1313:
1301:
1299:
1298:
1293:
1291:
1290:
1268:
1266:
1265:
1260:
1255:
1254:
1236:
1235:
1223:
1222:
1204:
1202:
1201:
1196:
1179:
1178:
1146:
1144:
1143:
1138:
1136:
1135:
1126:
1125:
1113:
1112:
1094:
1093:
1062:
1060:
1059:
1054:
1052:
1051:
1032:
1030:
1029:
1024:
1013:
1012:
988:
987:
968:
966:
965:
960:
943:
942:
912:
910:
909:
904:
896:
895:
869:
867:
866:
861:
839:
837:
836:
831:
819:
817:
816:
811:
787:
785:
784:
779:
767:
765:
764:
759:
743:
735:
733:
732:
727:
725:
724:
719:
718:
704:
698:
692:
690:
689:
684:
682:
681:
676:
675:
661:
655:
649:
643:
637:
626:
624:
623:
618:
612:
607:
591:
586:
571:
563:
552:
551:
533:
532:
527:
504:
500:
494:
475:
469:
460:
458:
457:
452:
444:
443:
425:
424:
419:
388:
386:
385:
380:
362:
360:
359:
354:
339:
337:
336:
331:
329:
328:
310:
306:
261:
257:
206:
204:
203:
198:
186:
184:
183:
178:
166:
164:
163:
158:
142:
140:
139:
134:
122:
120:
119:
114:
112:
111:
106:
89:
87:
86:
81:
45:Mervin E. Muller
3066:
3065:
3061:
3060:
3059:
3057:
3056:
3055:
3026:
3025:
3020:Brownian Motion
3010:
3000:
2987:
2984:
2982:Further reading
2979:
2978:
2938:
2937:
2933:
2926:
2895:
2894:
2890:
2850:
2849:
2845:
2813:
2808:
2807:
2803:
2786:
2782:
2769:
2768:
2764:
2757:
2744:
2743:
2739:
2723:10.1.1.123.3156
2703:
2702:
2698:
2668:
2667:
2663:
2629:
2628:
2624:
2590:
2589:
2585:
2563:
2562:
2553:
2538:(10): 706â714.
2525:
2524:
2520:
2513:
2500:
2499:
2490:
2451:
2450:
2441:
2436:
2431:
2430:
2425:
2421:
2416:
2393:
2372:
2348:
2347:
2328:
2327:
2284:
2269:
2248:
2220:
2219:
2197:
2196:
2175:
2170:
2169:
2140:
2135:
2134:
2085:
2058:
2032:
2031:
2008:
2007:
1986:
1944:
1943:
1916:
1874:
1873:
1860: and
1839:
1805:
1764:
1757:
1751:
1750:
1744:
1742:Time dependency
1723:and linearized
1683:
1682:
1679:
1667:
1643:
1642:
1585:
1584:
1565:
1564:
1561:
1508:
1507:
1488:
1487:
1449:
1448:
1441:
1432:
1427:
1403:
1402:
1383:
1382:
1361:
1356:
1355:
1331:
1326:
1325:
1304:
1303:
1276:
1271:
1270:
1240:
1227:
1214:
1209:
1208:
1164:
1153:
1152:
1127:
1117:
1098:
1073:
1068:
1067:
1043:
1038:
1037:
998:
979:
974:
973:
928:
917:
916:
881:
876:
875:
846:
845:
822:
821:
802:
801:
794:
770:
769:
750:
749:
737:
712:
707:
706:
700:
694:
669:
664:
663:
657:
651:
645:
639:
636: â 1)
631:
543:
522:
517:
516:
502:
499:
496:
488:
481:
471:
465:
435:
414:
394:
393:
365:
364:
345:
344:
324:
323:
302:
272:
271:
253:
225:
219:
218:
189:
188:
169:
168:
149:
148:
125:
124:
101:
96:
95:
72:
71:
68:
56:Brownian motion
17:
12:
11:
5:
3064:
3062:
3054:
3053:
3048:
3043:
3038:
3028:
3027:
3024:
3023:
3017:
3009:
3008:External links
3006:
3005:
3004:
2998:
2983:
2980:
2977:
2976:
2931:
2924:
2907:10.1.1.63.3780
2888:
2843:
2824:(2): 281â290.
2801:
2780:
2762:
2755:
2737:
2696:
2677:(2): 396â404.
2661:
2650:(3): 194â204.
2638: = â
2622:
2583:
2551:
2518:
2512:978-3540530015
2511:
2488:
2467:(3): 569â589.
2438:
2437:
2435:
2432:
2429:
2428:
2418:
2417:
2415:
2412:
2411:
2410:
2404:
2399:
2392:
2389:
2371:
2368:
2355:
2335:
2324:
2323:
2309:
2304:
2301:
2296:
2293:
2290:
2287:
2280:
2277:
2272:
2266:
2263:
2260:
2255:
2251:
2247:
2244:
2241:
2238:
2235:
2232:
2228:
2204:
2182:
2178:
2155:
2152:
2147:
2143:
2131:
2130:
2118:
2115:
2112:
2109:
2106:
2103:
2098:
2095:
2092:
2088:
2084:
2081:
2078:
2073:
2070:
2067:
2062:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2025:
2024:
2011:
2006:
2003:
2000:
1997:
1987:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1952:
1949:
1946:
1945:
1939:
1936:
1930:
1927:
1917:
1915:
1912:
1909:
1906:
1903:
1900:
1897:
1894:
1891:
1888:
1885:
1882:
1879:
1876:
1875:
1872:
1869:
1866:
1856:
1853:
1850:
1840:
1838:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1812:
1808:
1802:
1799:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1771:
1767:
1763:
1762:
1760:
1743:
1740:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1678:
1675:
1666:
1663:
1650:
1627:
1623:
1619:
1616:
1613:
1610:
1607:
1603:
1599:
1594:
1572:
1560:
1557:
1528:
1525:
1522:
1517:
1495:
1456:
1440:
1437:
1431:
1428:
1426:
1423:
1410:
1390:
1368:
1364:
1352:
1351:
1338:
1334:
1322:
1311:
1289:
1286:
1283:
1279:
1258:
1253:
1250:
1247:
1243:
1239:
1234:
1230:
1226:
1221:
1217:
1206:
1194:
1191:
1188:
1185:
1182:
1177:
1174:
1171:
1167:
1163:
1160:
1149:
1148:
1147:
1134:
1130:
1124:
1120:
1116:
1111:
1108:
1105:
1101:
1097:
1092:
1089:
1086:
1083:
1080:
1076:
1064:
1050:
1046:
1034:
1022:
1019:
1016:
1011:
1008:
1005:
1001:
997:
994:
991:
986:
982:
958:
955:
952:
949:
946:
941:
938:
935:
931:
927:
924:
913:
902:
899:
894:
891:
888:
884:
859:
856:
853:
829:
809:
793:
790:
777:
757:
723:
717:
680:
674:
628:
627:
616:
611:
606:
602:
598:
595:
590:
585:
582:
579:
575:
569:
566:
561:
558:
555:
550:
546:
542:
539:
536:
531:
526:
497:
486:
478:Wiener process
462:
461:
450:
447:
442:
438:
434:
431:
428:
423:
418:
413:
410:
407:
404:
401:
378:
375:
372:
352:
341:
340:
327:
322:
319:
316:
313:
303:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
273:
270:
267:
264:
254:
252:
249:
246:
243:
240:
237:
234:
231:
230:
228:
196:
176:
156:
132:
110:
105:
79:
67:
64:
15:
13:
10:
9:
6:
4:
3:
2:
3063:
3052:
3049:
3047:
3044:
3042:
3039:
3037:
3034:
3033:
3031:
3021:
3018:
3015:
3012:
3011:
3007:
3001:
2999:9783540530015
2995:
2991:
2986:
2985:
2981:
2972:
2968:
2964:
2960:
2955:
2950:
2946:
2942:
2935:
2932:
2927:
2921:
2917:
2913:
2908:
2903:
2899:
2892:
2889:
2884:
2880:
2876:
2872:
2867:
2862:
2858:
2854:
2847:
2844:
2839:
2835:
2831:
2827:
2823:
2819:
2812:
2805:
2802:
2797:
2791:
2783:
2777:
2773:
2766:
2763:
2758:
2752:
2748:
2741:
2738:
2733:
2729:
2724:
2719:
2715:
2711:
2707:
2700:
2697:
2692:
2688:
2684:
2680:
2676:
2672:
2665:
2662:
2657:
2653:
2649:
2645:
2641:
2637:
2634: â
2633:
2626:
2623:
2618:
2614:
2610:
2606:
2602:
2598:
2594:
2587:
2584:
2579:
2575:
2572:(2): 93â104.
2571:
2567:
2560:
2558:
2556:
2552:
2546:
2541:
2537:
2533:
2529:
2522:
2519:
2514:
2508:
2504:
2497:
2495:
2493:
2489:
2484:
2480:
2475:
2470:
2466:
2462:
2458:
2454:
2448:
2446:
2444:
2440:
2433:
2423:
2420:
2413:
2408:
2405:
2403:
2400:
2398:
2395:
2394:
2390:
2388:
2385:
2382:
2380:
2375:
2369:
2367:
2353:
2333:
2302:
2299:
2294:
2288:
2285:
2278:
2275:
2270:
2264:
2253:
2249:
2245:
2242:
2236:
2233:
2218:
2217:
2216:
2202:
2180:
2176:
2166:
2153:
2150:
2145:
2141:
2110:
2107:
2104:
2101:
2096:
2093:
2090:
2086:
2079:
2071:
2068:
2065:
2055:
2049:
2046:
2043:
2037:
2030:
2029:
2028:
2004:
1998:
1995:
1980:
1977:
1974:
1968:
1965:
1959:
1956:
1953:
1947:
1928:
1925:
1910:
1907:
1904:
1898:
1895:
1889:
1886:
1883:
1877:
1870:
1867:
1864:
1851:
1848:
1836:
1833:
1827:
1824:
1821:
1815:
1810:
1800:
1797:
1792:
1786:
1783:
1780:
1774:
1769:
1758:
1749:
1748:
1747:
1741:
1739:
1737:
1732:
1730:
1726:
1722:
1706:
1703:
1700:
1697:
1694:
1691:
1676:
1674:
1672:
1664:
1662:
1648:
1639:
1614:
1608:
1605:
1570:
1558:
1556:
1554:
1549:
1547:
1542:
1523:
1493:
1484:
1482:
1478:
1474:
1454:
1445:
1438:
1436:
1429:
1424:
1422:
1408:
1366:
1362:
1336:
1332:
1323:
1284:
1277:
1248:
1241:
1228:
1224:
1219:
1215:
1207:
1192:
1189:
1180:
1172:
1165:
1158:
1150:
1132:
1128:
1122:
1118:
1114:
1106:
1099:
1095:
1087:
1084:
1081:
1074:
1065:
1048:
1044:
1035:
1014:
1006:
999:
992:
989:
984:
980:
971:
970:
956:
953:
944:
936:
929:
922:
914:
900:
897:
889:
882:
873:
872:
871:
857:
854:
851:
827:
798:
791:
789:
775:
755:
745:
741:
721:
703:
697:
678:
660:
654:
648:
642:
635:
609:
604:
600:
593:
588:
583:
580:
577:
573:
567:
564:
559:
548:
544:
537:
529:
515:
514:
513:
511:
506:
492:
485:
479:
476:-dimensional
474:
468:
440:
436:
429:
421:
411:
405:
399:
392:
391:
390:
373:
370:
350:
320:
314:
311:
296:
290:
287:
281:
275:
265:
262:
250:
247:
241:
235:
226:
217:
216:
215:
213:
210:Consider the
208:
174:
146:
108:
93:
90:be a bounded
65:
63:
61:
57:
52:
50:
46:
42:
38:
34:
30:
26:
22:
2989:
2944:
2940:
2934:
2897:
2891:
2856:
2852:
2846:
2821:
2817:
2804:
2771:
2765:
2746:
2740:
2713:
2709:
2705:
2699:
2674:
2670:
2664:
2647:
2643:
2639:
2635:
2631:
2625:
2600:
2596:
2586:
2569:
2565:
2535:
2531:
2521:
2502:
2464:
2460:
2455:(Sep 1956).
2422:
2386:
2383:
2376:
2373:
2325:
2167:
2132:
2026:
1745:
1733:
1680:
1668:
1640:
1562:
1550:
1485:
1470:
1433:
1353:
843:
746:
739:
701:
695:
693:centered on
658:
652:
646:
640:
633:
629:
507:
490:
483:
472:
466:
463:
363:exists, for
342:
209:
144:
69:
53:
24:
18:
2947:(4): 1â17.
2603:(9): 3761.
1736:FeynmanâKac
1671:capacitance
1354:The result
768:-shell, or
21:mathematics
3030:Categories
2954:2201.13240
2434:References
1559:Complexity
167:, and let
2971:246430740
2902:CiteSeerX
2866:1111.3736
2790:cite book
2718:CiteSeerX
2334:τ
2289:
2250:τ
2243:−
2237:
2177:τ
2111:τ
2108:∧
2097:τ
2094:∧
2002:Γ
1999:∈
1938:¯
1935:Ω
1929:∈
1855:Ω
1852:∈
1807:Δ
1766:∂
1689:Δ
1615:ε
1609:
1571:ε
1524:ε
1494:ε
1483:methods.
1455:δ
1389:Ω
1310:Γ
1233:Γ
1193:ε
1190:≤
1184:Γ
1129:γ
1045:γ
1018:Γ
957:ε
948:Γ
852:ε
828:ε
808:Ω
776:ε
756:ε
656:equal to
605:τ
574:∑
560:∼
549:τ
441:τ
377:Ω
374:∈
318:Γ
315:∈
269:Ω
266:∈
233:Δ
195:Ω
155:Γ
131:Γ
78:Ω
29:algorithm
2883:25036031
2391:See also
1991:if
1921:if
1844:if
1475:, and a
820:with an
788:-layer.
307:if
258:if
2826:Bibcode
2679:Bibcode
2605:Bibcode
2483:2237369
1721:Poisson
1324:Return
1036:Sample
844:Choose
2996:
2969:
2922:
2904:
2881:
2778:
2753:
2720:
2509:
2481:
915:While
840:-shell
503:Ω
498:τ
495:, and
464:where
143:, let
92:domain
23:, the
2967:S2CID
2949:arXiv
2879:S2CID
2861:arXiv
2814:(PDF)
2479:JSTOR
2414:Notes
1151:When
705:from
470:is a
31:, or
2994:ISBN
2920:ISBN
2796:link
2776:ISBN
2751:ISBN
2507:ISBN
2286:sinh
1868:<
1473:bias
1066:Set
972:Set
954:>
855:>
70:Let
39:for
2959:doi
2912:doi
2871:doi
2834:doi
2728:doi
2687:doi
2652:doi
2613:doi
2601:106
2574:doi
2540:doi
2469:doi
2234:exp
2215:):
1606:log
1302:on
94:in
19:In
3032::
2965:.
2957:.
2945:41
2943:.
2918:.
2910:.
2877:.
2869:.
2857:23
2855:.
2832:.
2822:47
2820:.
2816:.
2792:}}
2788:{{
2726:.
2714:62
2712:.
2685:.
2675:39
2673:.
2646:.
2636:cu
2611:.
2599:.
2595:.
2570:63
2568:.
2554:^
2536:20
2534:.
2530:.
2491:^
2477:.
2465:27
2463:.
2459:.
2442:^
2366:.
1548:)
1225::=
1096::=
969::
512::
505:.
489:=
389::
214::
207:.
3002:.
2973:.
2961::
2951::
2928:.
2914::
2885:.
2873::
2863::
2840:.
2836::
2828::
2798:)
2784:.
2759:.
2734:.
2730::
2706:h
2693:.
2689::
2681::
2658:.
2654::
2648:9
2640:q
2632:u
2619:.
2615::
2607::
2580:.
2576::
2548:.
2542::
2515:.
2485:.
2471::
2354:T
2308:)
2303:s
2300:2
2295:R
2292:(
2279:s
2276:2
2271:R
2265:=
2262:)
2259:)
2254:0
2246:s
2240:(
2231:(
2227:E
2203:R
2181:0
2154:x
2151:=
2146:t
2142:X
2129:,
2117:)
2114:)
2105:T
2102:,
2091:T
2087:X
2083:(
2080:h
2077:(
2072:x
2069:,
2066:t
2061:E
2056:=
2053:)
2050:t
2047:,
2044:x
2041:(
2038:u
2005:.
1996:x
1984:)
1981:t
1978:,
1975:x
1972:(
1969:h
1966:=
1963:)
1960:t
1957:,
1954:x
1951:(
1948:u
1926:x
1914:)
1911:T
1908:,
1905:x
1902:(
1899:h
1896:=
1893:)
1890:T
1887:,
1884:x
1881:(
1878:u
1871:T
1865:t
1849:x
1837:0
1834:=
1831:)
1828:t
1825:,
1822:x
1819:(
1816:u
1811:x
1801:2
1798:1
1793:+
1790:)
1787:t
1784:,
1781:x
1778:(
1775:u
1770:t
1759:{
1707:f
1704:+
1701:u
1698:c
1695:=
1692:u
1649:3
1626:)
1622:|
1618:)
1612:(
1602:|
1598:(
1593:O
1527:)
1521:(
1516:O
1409:x
1367:f
1363:x
1337:f
1333:x
1288:)
1285:n
1282:(
1278:x
1257:)
1252:)
1249:n
1246:(
1242:x
1238:(
1229:p
1220:f
1216:x
1205::
1187:)
1181:,
1176:)
1173:n
1170:(
1166:x
1162:(
1159:d
1133:n
1123:n
1119:r
1115:+
1110:)
1107:n
1104:(
1100:x
1091:)
1088:1
1085:+
1082:n
1079:(
1075:x
1049:n
1033:.
1021:)
1015:,
1010:)
1007:n
1004:(
1000:x
996:(
993:d
990:=
985:n
981:r
951:)
945:,
940:)
937:n
934:(
930:x
926:(
923:d
901:x
898:=
893:)
890:0
887:(
883:x
858:0
742:)
740:x
738:(
722:0
716:S
702:x
696:x
679:0
673:S
659:x
653:x
647:W
641:x
634:d
632:(
615:)
610:i
601:W
597:(
594:h
589:n
584:1
581:=
578:i
568:n
565:1
557:]
554:)
545:W
541:(
538:h
535:[
530:x
525:E
493:}
491:x
487:0
484:W
482:{
473:d
467:W
449:]
446:)
437:W
433:(
430:h
427:[
422:x
417:E
412:=
409:)
406:x
403:(
400:u
371:x
351:u
321:.
312:x
300:)
297:x
294:(
291:h
288:=
285:)
282:x
279:(
276:u
263:x
251:0
248:=
245:)
242:x
239:(
236:u
227:{
175:x
145:h
109:d
104:R
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
