A random walk on rectangles algorithm. (English) Zbl 1104.60046
The authors introduce a new algorithm that is designed to simulate the first exit time and first exit position from a rectangle (or a parallelepiped or polygonal domain) for a Brownian motion that starts at any point inside. This method provides an approximative solution to some nonrandom Dirichlet problems for linear second order PDEs in any dimension. It represents an analogous method to the method of the random walk on spheres (WOS) and can be adapted to treat Neumann boundary conditions or Brownian motion with a constant drift. Some numerical tests and discussions are presented as well.
Reviewer: Henri Schurz (Carbondale)
MSC:
| 60J65 | Brownian motion |
| 65C05 | Monte Carlo methods |
| 60G35 | Signal detection and filtering (aspects of stochastic processes) |
| 60H10 | Stochastic ordinary differential equations (aspects of stochastic analysis) |
| 60H30 | Applications of stochastic analysis (to PDEs, etc.) |
| 65N99 | Numerical methods for partial differential equations, boundary value problems |
Keywords:
Monte Carlo method; Laplace operator; random walk on spheres/squares/rectangles; Green functions; Dirichlet-Neumann problem; numerical algorithmReferences:
| [1] | J. V. Beck, K. D. Cole, A. Haji-Sheikh, and B. Litkouhi, Heat conduction using Green’s functions, Series in Computational and Physical Processes in Mechanics and Thermal Sciences, Hemisphere Publishing Corp.:London, 1992. · Zbl 1272.80001 |
| [2] | L. Breiman, Probability, Addison-Wesley, 1981. |
| [3] | F. Campillo and A. Lejay, ”A Monte Carlo method without grid for a fractured porous domain model,” Monte Carlo Methods and Applications vol. 8(2) pp. 129–148, 2002. · Zbl 1116.76445 · doi:10.1515/mcma.2002.8.2.129 |
| [4] | J. M. DeLaurentis and L. A. Romero, ”A Monte Carlo method for Poisson’s equation,” Journal of Computational Physics vol. 90(1) pp. 123–140, 1990. · Zbl 0716.65105 · doi:10.1016/0021-9991(90)90199-B |
| [5] | L. Devroye, Non-Uniform Random Variate Generation, Springer-Verlag, 1986. · Zbl 0593.65005 |
| [6] | M. S. P. Eastham, Theory of ordinary differential equations, Van Nostrand Reinhold Company, 1970. · Zbl 0195.37001 |
| [7] | N. Golyanda, ”Convergence rate for spherical processes with shifted centres,” Monte Carlo Methods and Applications vol. 10(3–4), pp. 287–296, 2004. Conference proceeding of IV IMACS Seminar on Monte Carlo Methods. · Zbl 1068.65004 · doi:10.1515/mcma.2004.10.3-4.287 |
| [8] | C.-O. Hwang, M. Mascagni, and J. A. Given, ”A Feynman-Kac path-integral implementation for Poisson’s equation using an \(h\) -conditioned Green’s function,” Mathematics and Computers in Simulation vol. 62(3–6) pp. 347–355, 2003. 3rd IMACS Seminar on Monte Carlo Methods-MCM 2001 (Salzburg). · Zbl 1025.65006 · doi:10.1016/S0378-4754(02)00224-0 |
| [9] | V. Linetsky, ”On the transition densities for reflected diffusions,” Advances in Applied Probability vol. 37(2) pp. 435–460, 2005. · Zbl 1073.60074 · doi:10.1239/aap/1118858633 |
| [10] | S. Maire, Réduction de variance pour l’intégration numérique et pour le calcul critique en transport neutronique, PhD thesis, Université de Toulon et de Var (France), 2001. |
| [11] | G. N. Mil’shtejn and N. F. Rybkina, ”An algorithm for random walks over small ellipsoids for solving the general Dirichlet problem,” Computational Mathematics and Mathematical Physics vol. 33(5) pp. 631–647, 1993. · Zbl 0795.60073 |
| [12] | G. N. Milstein and M. V. Tretyakov, ”Simulation of a space-time bounded diffusion,” Annals of Applied Probability vol. 9(3) pp. 732–779, 1999. · Zbl 0964.60065 · doi:10.1214/aoap/1029962812 |
| [13] | M. E. Muller, ”Some continuous Monte Carlo methods for the Dirichlet problem,” Annals of Mathematical Statistics vol. 27 pp. 569–589, 1956. · Zbl 0075.28902 · doi:10.1214/aoms/1177728169 |
| [14] | B. Noetinger and T. Estébenet, ”Up scaling of fractured media using continuous-time random walks methods,” Transport in Porous Media vol. 39(3) pp. 315–337, 2000. · doi:10.1023/A:1006639025910 |
| [15] | W. H. Press, S. A Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C (2nd ed.), Cambridge University Press, 1992. · Zbl 0778.65003 |
| [16] | K. Sabelfeld, I. Shalimova, and A. I. Levykin, ”Discrete random walk on large spherical grids generated by spherical means for PDEs,” Monte Carlo Methods and Applications vol. 10(3–4) pp. 559–574, 2004. Conference proceeding of IV IMACS Seminar on Monte Carlo Methods. · Zbl 1068.65006 · doi:10.1515/mcma.2004.10.3-4.559 |
| [17] | K. K. Sabelfeld and D. Talay, ”Integral formulation of the boundary value problems and the method of random walk on spheres,” Monte Carlo Methods and Applications vol. 1(1) pp. 1–34, 1995. · Zbl 0824.65127 · doi:10.1515/mcma.1995.1.1.1 |
| [18] | N. A. Simonov and M. Mascagni, ”Random walk algorithm for estimating effective properties of digitized porous media,” Monte Carlo Methods and Applications vol. 10(3–4) pp. 599–608, 2004. Conference proceeding of IV IMACS Seminar on Monte Carlo Methods. · Zbl 1152.76480 · doi:10.1515/mcma.2004.10.3-4.599 |
| [19] | S. Torquato and C. Kim, ”Effective conductivity, dielectric constant, and diffusion coefficient of digitized composite media via first-passage-time equations,” Journal of Applied Physics vol. 85(3) pp. 1560–1571, 1999. · doi:10.1063/1.369287 |
| [20] | D. Veestraeten, ”The conditional probability density function for a reflected Brownian motion,” Computational Economics vol. 24(2) pp. 185–207, 2005. · Zbl 1067.60082 · doi:10.1023/B:CSEM.0000049491.13935.af |
| [21] | E. Zauderer, Partial differential equations of applied mathematics. Pure and Applied Mathematics, John Wiley & Sons Inc.: New York, 1983. · Zbl 0551.35002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
