Simulation of diffusion using quasi-random walk methods
We present a method for computer simulation of diffusion. The method uses quasi-random walk of particles. We consider a pure initial value problem for a simple diffusion equation in s space dimensions. We introduce s spatial steps Delta x(i). A semidiscrete approximation to the equation is obtained by replacing the spatial derivatives with finite differences. N particles are sampled from the initial distribution. The time interval is partitioned into subintervals of length Delta t. The discretization in time is obtained by resorting to the forward Euler method. In every time step the particle movement is regarded as an approximate integration is s+1 dimensions. A quasi-Monte Carlo estimate for the integral is obtained by using a (0, s+1)-sequence. A key element in successfully applying the low discrepancy sequence is a technique involving renumbering the particles at each time step. We prove that the computed solution converges to the solution of the semi-discrete equation as N-->infinity and Delta t-->0. We present numerical tests which show that random walk results are improved with quasi random sequences and renumbering. (C) 1998 IMACS/Elsevier Science B.V.
diffusion random walk discrepancy monte carlo methods error bounds