Robust variance reduction for random walk methods

Gang Zou

doi:10.1137/S1064827503424025

Robust variance reduction for random walk methods

2004-01-01

6

PRE

AI

DOI：10.1137/S1064827503424025

Original

Original request for help

Save

Abstract

En 中文

Random walk methods are effective for solving linear partial differential equations in many dimensions, especially those involving complex geometries. They are based on an equivalence given by a Feynman - Kac formula between an expectation of a functional of a stochastic process and the solution at a point of a partial differential equation. The drawback is that the error is proportional only to the square root of the reciprocal of the number of trials. Efficiency depends critically on variance reduction. A general strategy for doing this in the case of stochastic differential equations is proposed by Milstein. The idea is to introduce a bias in the drift term and to exactly compensate for this by unequal weighting of the trials. There is an optimal bias defined in terms of the solution of the partial differential equation which reduces the variance to zero. In practice, an approximation is used. This idea has been tested under the name biased Brownian dynamics on the problem of calculating rate constants for diffusion-limited reactions. The approach is successful in some cases but is less successful in more difficult cases due to the occasional occurrence of a well-above-average weight. Proposed and tested here is a weight control algorithm, which greatly enhances the effectiveness of biased Brownian dynamics.

Keywords:

variance reduction

importance sampling

random walk methods

path integrals

stochastic differential equations

Robust variance reduction for random walk methods

Abstract

Journal

Organization