A random walk on rectangles algorithm

DOI10.1007/S11009-006-7292-3MaRDI QIDQ2433258zbMATH OpenOpenAlexFDO

Authors Madalina Deaconu, Antoine Lejay

Publication date 27 October 2006

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11009-006-7292-3

zbMATH Keywords

Dirichlet-Neumann problemGreen functionsLaplace operatorMonte Carlo methodnumerical algorithmrandom walk on spheres/squares/rectangles

Mathematics Subject Classification ID

Signal detection and filtering (aspects of stochastic processes) (60G35) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Applications of stochastic analysis (to PDEs, etc.) (60H30) Brownian motion (60J65) Monte Carlo methods (65C05) Numerical methods for partial differential equations, boundary value problems (65N99)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 50876
• scientific article; zbMATH DE number 1472174
• scientific article; zbMATH DE number 704317
• Random walk on a polygon
• Random walk over spheres algorithms
• scientific article; zbMATH DE number 718655
• A randomized variant of the Gröbner Walk
• Self-avoiding walks in a rectangle

Cites work

• A Feynman-Kac path-integral implementation for Poisson's equation using an h-conditioned Green's function
• A Monte Carlo method for Poisson's equation
• A Monte Carlo method without grid for a fractured porous domain model
• An algorithm for random walks over small ellipsoids for solving the general Dirichlet problem
• Convergence rate for spherical processes with shifted centres *
• Discrete random walk on large spherical grids generated by spherical means for PDEs *
• Heat conduction using Green's functions
• scientific article; zbMATH DE number 3877593 (Why is no real title available?)
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 274379 (Why is no real title available?)
• scientific article; zbMATH DE number 3311089 (Why is no real title available?)
• Integral Formulation of the Boundary Value Problems and the Method of Random Walk on Spheres
• On the transition densities for reflected diffusions
• Random Walk Algorithms for Estimating Effective Properties of Digitized Porous Media *
• Simulation of a space-time bounded diffusion
• Some Continuous Monte Carlo Methods for the Dirichlet Problem
• The conditional probability density function for a reflected Brownian motion

Cited in

(28)

• The rate of convergence of the walk on spheres algorithm
• Stochastic simulation algorithms for solving a nonlinear system of drift-diffusion-Poisson equations of semiconductors
• Stochastic finite differences for elliptic diffusion equations in stratified domains
• The walk on moving spheres: a new tool for simulating Brownian motion's exit time from a domain
• Stopped diffusion processes: boundary corrections and overshoot
• Stochastic algorithm for solving transient diffusion equations with a precise accounting of reflection boundary conditions on a substrate surface
• An implementation of Milstein's method for general bounded diffusions
• Random walk on rectangles and parallelepipeds algorithm for solving transient anisotropic drift-diffusion-reaction problems
• Random walk on spheres algorithm for solving transient drift-diffusion-reaction problems
• A global random walk on spheres algorithm for transient heat equation and some extensions
• Simulating diffusion processes in discontinuous media: a numerical scheme with constant time steps
• Simulation of reflected Brownian motion on two dimensional wedges
• Stochastic simulation algorithms for solving transient anisotropic diffusion-recombination equations and application to cathodoluminescence imaging
• scientific article; zbMATH DE number 3856156 (Why is no real title available?)
• A first-passage kinetic Monte Carlo method for reaction-drift-diffusion processes
• The complexity of simulating Brownian motion
• An efficient algorithm to simulate a Brownian motion over irregular domains
• Multidimensional Exponential Timestepping with Boundary Test
• An algorithm for probabilistic solution of parabolic PDEs
• A global random walk on grid algorithm for second order elliptic equations
• A global random walk on grid algorithm for second order elliptic equations
• Simulating diffusions with piecewise constant coefficients using a kinetic approximation
• Exact simulation of the first-passage time of diffusions to time-dependent thresholds
• Escape-from-a-layer approach for simulating the boundary local time in Euclidean domains
• Extended Walk-on-Spheres Algorithm for Linear and Nonlinear Elliptic Problems of Divergence-type
• Computing the principal eigenvalue of the Laplace operator by a stochastic method
• Computing the principal eigenelements of some linear operators using a branching Monte Carlo method
• Simulation of diffusions by means of importance sampling paradigm

This page was built for publication: A random walk on rectangles algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2433258)