Sign-switched antithetic coupling in gradient random-walk methods for convection-diffusion equations

Abstract

We propose an antithetic coupling that reduces the computational cost of gradient random-walk methods for one-dimensional convection-diffusion equations. The methods represent the solution's spatial derivative by particles with positive or negative masses, whose cumulative sums reconstruct the solution, and model diffusion by Gaussian displacements. The particles reorder and, for a nonlinear flux, interact. Antithetic sampling negates the displacements of a second simulation, which positively correlates the contributions of particles matched by position when their masses have opposite signs. Our coupling instead gives matched particles of opposite sign identical displacements and retains opposite displacements for equal-sign pairs. We prove that each simulation keeps the distribution of an uncoupled run as the matching changes, so the averaged solution keeps the bias of one simulation. For fixed particle configurations and matching, the coupling minimizes each matched pair's conditional variance contribution after diffusion among all couplings with the same Gaussian marginal distributions. From the same configurations, its variance reduction over antithetic sampling at the final diffusion stage has a closed form for any flux. For the heat equation, a martingale decomposition extends both results to each step's contribution to the terminal variance. In a Burgers' equation test, the coupling meets a tolerance for the spatially integrated mean squared error with 4 simulations, against 34 for antithetic sampling and 65 for independent sampling. In a second test, it meets a common error tolerance in about 40% less time than pairing particles only within each sign.

arXiv comment23 pages, 6 figures, 4 tables. Code and data: https://doi.org/10.5281/zenodo.23055907; https://github.com/stephen122204/sac-grw