The Random Batch Method (RBM) proposed in [Jin et al. J Comput Phys, 2020] 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 $N$. In the RBM-r algorithm, one randomly picks a small batch of size $p \ll N$, 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 $\frac{1}{N-1}$) in the original system is replaced by a strong interaction (of strength $\frac{1}{p-1}$). Then one repeats this pick-interact process. This KMC algorithm dramatically reduces the computational cost from $O(N^2)$ to $O(pN)$ 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 $O(\kappa^{1/4})$ upper bound, where $\kappa$ is the time step for choosing the random batch and the bound is independent of $N$. An improved $O(\kappa^{1/2})$ 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.

翻译：随机批处理方法（RBM）由[Jin et al. J Comput Phys, 2020]提出，是一种用于模拟相互作用粒子系统（IPS）的高效算法。本文研究了带替换的随机批处理方法（RBM-r），该方法对于规模为$N$的成对相互作用粒子系统与动力学蒙特卡洛（KMC）方法等价。在RBM-r算法中，每次随机选取一个规模为$p \\ll N$的小批次，仅批次内的粒子在短时间内发生相互作用，其中原始系统中的弱相互作用（强度为$\\frac{1}{N-1}$）被替换为强相互作用（强度为$\\frac{1}{p-1}$）。随后重复此选取-相互作用过程。该KMC算法将每时间步的计算成本从$O(N^2)$显著降低至$O(pN)$，并为相互作用粒子系统的原始力/速度场提供了无偏近似。我们通过显式收敛速率严格证明了该近似性质。具体而言，我们证明IPS与RBM-r的第一边际分布之间的Wasserstein-2距离具有$O(\\kappa^{1/4})$上界，其中$\\kappa$为选取随机批次的时间步长，且该上界与$N$无关。当系统中不存在扩散时，进一步获得了改进的$O(\\kappa^{1/2})$收敛速率。值得注意的是，我们分析中的技术可推广至研究其他系统的KMC方法，包括随机伊辛自旋系统。