Convergence of Random Batch Method with replacement for interacting particle systems

The Random Batch Method (RBM) proposed by [J. Comput. Phys. 400 (2020), p. 30] is an efficient algorithm for simulating interacting particle systems (IPS). In this paper, we investigate the Random Batch Method with replacement (RBM-r), which is the same as the kinetic Monte Carlo (KMC) method for the pairwise interacting particle system of size <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In the RBM-r algorithm, one randomly picks a small batch of size <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p much-less-than upper N"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo> ≪ </mml:mo> <mml:mi>N</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p \ll N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and only the particles in the picked batch interact among each other within the batch for a short time, where the weak interaction (of strength <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartFraction 1 Over upper N minus 1 EndFraction"> <mml:semantics> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> <mml:annotation encoding="application/x-tex">\frac {1}{N-1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ) in the original system is replaced by a strong and sparce interaction (of strength <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartFraction 1 Over p minus 1 EndFraction"> <mml:semantics> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> <mml:annotation encoding="application/x-tex">\frac {1}{p-1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> ). Then one repeats this pick-interact process. This KMC algorithm dramatically reduces the computational cost from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis upper N squared right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>N</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(N^2)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis p upper N right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(pN)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> per time step, and provides an unbiased approximation of the original force/velocity field of the interacting particle system. We give a rigorous proof of this approximation with an explicit convergence rate. In detail, we show that the Wasserstein-2 distance between first marginal distributions of IPS and RBM-r has an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis kappa Superscript 1 slash 4 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi> κ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>4</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(\kappa ^{1/4})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> upper bound, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="kappa"> <mml:semantics> <mml:mi> κ </mml:mi> <mml:annotation encoding="application/x-tex">\kappa</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the time step for choosing the random batch and the bound is independent of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . An improved <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis kappa Superscript 1 slash 2 Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi> κ </mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(\kappa ^{1/2})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> rate is also obtained when there is no diffusion in the system. Notably, the techniques in our analysis can potentially be applied to study KMC for other systems, including the stochastic Ising spin system.