betaFeedback

WorksMathematics

Convergence of replicator-mutator particle systems via bounded Wasserstein distance

Abstract

Interacting particle systems with selection and mutation mechanisms arise in biological modeling, evolutionary optimization, and particle filtering methods. In this work we will consider the paradigmatic replicator-mutator PDE, which combines a diffusive component with a source term that depends on an external potential. We derive quantitative error estimates for the distance between the empirical measure of an unweighted particle system and the solution of the PDE. The proof uses a Wasserstein-1 distance with a bounded ground cost, which allows us to treat unbounded potentials on an unbounded state space. The key tools are the optimal coupling of newly resampled particles and, for the time-continuous limit, the use of a discrete-time killing resampling.

Introduction and main result

Complex systems where different interacting particles undergo birth and death dynamics appear in several contexts. In biology, they describe the evolution of a population of cells which reproduce and mutate [23]. In Bayesian statistics, they constitute a large class of particle filter algorithms, particularly effective for multi-modal targets, under the name Sequential Monte Carlo [12]. In optimization, such dynamics is at the basis of genetic algorithms [20], a popular heuristic involving particle exploration to find global minimizers of non-differentiable functions.

All such systems can be described at two different levels. One is the microscopic level of the finite NN particle systems. One is the statistical level of an evolving probability distribution ρ∈P(Rd)\rho\in\mathcal{P}(\mathbb{R}^{d}) typically obtained by taking the many particle limit N→∞N \to\infty. In this paper we are interested in rigorously studying the relation between these two descriptions with quantitative approximation errors. We focus on maybe the simplest of such models, that is, the Replicator-Mutator (RM) PDE which describes particles undergoing birth or death according to a fitness potential V:Rd→RV : \mathbb{R}^{d} \to\mathbb{R}, and diffusion with strength σ>0\sigma> 0:

∂tρt=σ22Δρt−(V−Eρt[V])ρt.(1)\partial_t \rho_t = \frac{\sigma^2}{2}\Delta\rho_t - \left(V - \mathbb{E}_{\rho_t}[V]\right)\rho_t . \tag*{(1)}
Algorithm 1: Replicator-mutator particle dynamics
Input: Potential function $V \ge 0$, population size $N$, initial distribution $\rho_0 \in \mathcal{P}(\mathbb{R}^d)$, diffusion coefficient $\sigma \ge 0$, time discretization $\tau \in (0,1]$, time horizon $T > 0$.
Particle initialization $X_0^i \sim \rho_0$ i.i.d., $i=1,\ldots,N$
$n=0$
while $n\tau \le T$ do
    Compute weights $w_n^i = e^{-\tau V(X_n^i)}/\sum_{j=1}^N e^{-\tau V(X_n^j)}$, $i=1,\ldots,N$
    for all $i=1,\ldots,N$ do
        Sample $\xi_n^i \sim \mathcal{N}(0,I_d)$
        with probability $1-e^{-\tau V(X_n^i)}$:
            sample $J_n^i \sim \operatorname{Categorical}(w_n^1,\ldots,w_n^N)$
            $X_{n+1}^i = X_n^{J_n^i}+\sigma\sqrt{\tau}\xi_n^i$
        else:
            $X_{n+1}^i = X_n^i+\sigma\sqrt{\tau}\xi_n^i$
    end for
    $n=n+1$
end while

The constant Eρt[V]=∫V(y)ρt(dy)\mathbb{E}_{\rho_t}[V]=\int V(y)\rho_t(\mathrm{d}y) ensures the total mass remains constant during the evolution. The RM appears in mathematical biology for the description of cell dynamics [23], in machine learning as the grazing collision limit of collective hyperparameter learning dynamics [Borghi et al., 2026]. It can also be regarded as the time-continuous limit of a bootstrap particle filter [6]. From a variational point of view, while (1) is not a gradient flow, it is comprised of two gradients: the Laplacian corresponds to the L2L^2-Wasserstein gradient of the log-entropy, while the source term corresponds to the Fisher–Rao gradient of the external energy ∫Vρ\int V\rho. Interestingly, the two energies together form the KL divergence to π∝e−V/σ\pi\propto e^{-V/\sigma}, up to a constant.

Contribution

We are interested in connecting (1) and the simple time-discrete particle discretization described by Algorithm 1. At every step nn, particles may undergo independent resampling according to their potential value VV following a discrete-time killing resampling mechanism [8], also known as ϵ\epsilon-bootstrap interaction [28]. Gaussian increments are added at every step to discretize the Laplacian operator. Let τ∈(0,1]\tau\in(0,1] be the time-step. We will show that, as the number of particles NN increases, the particle distribution converges to the splitting scheme made by alternating distribution reweighting and convolution with the heat kernel KsK_s

Rτ[ρ]:=e−τVρρ(e−τV)andMτ[ρ]:=Kστ∗ρR_\tau[\rho] := \frac{e^{-\tau V}\rho}{\rho(e^{-\tau V})} \qquad\text{and}\qquad M_\tau[\rho] := K_{\sigma\sqrt{\tau}} * \rho

leading to the time discrete update

ρn+1=Mτ[Rτ[ρn]].(2)\rho_{n+1}=M_\tau[R_\tau[\rho_n]]. \tag*{(2)}

To study the convergence of the particle system we consider a Wasserstein-1 distance with bounded ground cost:

W1d(μ,ν)=inf⁡X∼μ,Y∼νE[d(X,Y)],withd(x,y):=∣x−y∣∧1.\mathsf{W}_1^d(\mu,\nu)=\inf_{X\sim\mu,Y\sim\nu}\mathbb{E}[d(X,Y)], \qquad\text{with}\qquad d(x,y):=|x-y|\wedge1.

Note that, by the Kantorovich–Rubinstein duality [29], it corresponds to the Bounded Lipschitz norm between measures (see (3)). Since d(x,y)≤∣x−y∣d(x,y) \le|x-y|, one can use the usual Wasserstein concentration inequalities [17] for i.i.d. particles for the L1L^1-Wasserstein distance

E[W1d(ρ0N,ρ0)]≲CMq1/q(ρ0) ε(N,d)\mathbb{E}\left[\mathcal{W}_1^d(\rho_0^N,\rho_0)\right] \lesssim C M_q^{1/q}(\rho_0)\,\varepsilon(N,d)

with the rate ε(N,d)\varepsilon(N,d) given by

ε(N,d):={N−1/2if d=1(1+log⁡N)N−1/2if d=2N−1/dif d≥3,\varepsilon(N,d) := \begin{cases} N^{-1/2} & \text{if } d=1 \\ (1+\log N)N^{-1/2} & \text{if } d=2 \\ N^{-1/d} & \text{if } d\ge3, \end{cases}

when q>2q>2. Our objective is to show that the rate is preserved at later times, and that the time-discretization introduces an error of order τ\tau.

Assumption 1.1. Let V∈C2(Rd)V \in C^2(\mathbb{R}^d), V≥0V \ge0, such that there exist CV,CV′>0C_V,C'_V>0

V(x)≤CV(1+∣x∣2)∣∇V(x)∣≤CV′+V(x)for all x∈Rd.∣ΔV(x)∣≤CV′′(1+∣x∣2)\begin{aligned} V(x) &\le C_V(1+|x|^2) \\ |\nabla V(x)| &\le C'_V+V(x) && \text{for all } x\in\mathbb{R}^d. \\ |\Delta V(x)| &\le C''_V(1+|x|^2) \end{aligned}

Theorem 1.2. Given a time horizon T>0T>0, let ρ∈C([0,T],P(Rd))\rho\in C([0,T],\mathcal{P}(\mathbb{R}^d)) be a measure solution to (1) (see Definition 4.1) with finite qq-th moments, q≥4q\ge4. Let ρnN=1/N∑iδXin\rho_n^N=1/N\sum_i\delta_{X_i^n} be the empirical measure of the particle system constructed according to Algorithm 1 with time step τ∈(0,1]\tau\in(0,1].

If the potential VV satisfies 1.1, it holds

sup⁡tn=nτ≤TE[W1d(ρnN,ρ(tn))]≤C(1+T2)eC(1+T2)(ε(N,d)+τ)\sup_{t_n=n\tau\le T}\mathbb{E}\left[\mathcal{W}_1^d(\rho_n^N,\rho(t_n))\right] \le C(1+T^2)e^{C(1+T^2)}\left(\varepsilon(N,d)+\tau\right)

with the positive constant CC depending on V,q,dV,q,d and on the qq-th moment of ρ0\rho_0.

The propagation of chaos result is obtained via the coupling method [7], by considering an auxiliary system of NN i.i.d. particles {X‾ni}i=1N\{\overline{X}_n^i\}_{i=1}^N, with X‾ni∼ρn\overline{X}_n^i\sim\rho_n. Interestingly, the dependence on the dimension dd already appears in the coupling estimate:

EW1(ρnN,ρ‾nN)≲Tε(N,d),\mathbb{E}\mathcal{W}_1(\rho_n^N,\overline{\rho}_n^N)\lesssim_T\varepsilon(N,d),

(see Proposition 3.2) where mean-field type models, instead, typically exhibit an interaction error of order 1/N1/\sqrt{N}. This is due to the fact that in Algorithm 1 the interaction requires, at each step, a resampling procedure. This may explain the empirically observed struggle of discretizing particle filters in high dimension due to the weight collapse phenomenon [1, 24]. Convergence of the time-discretization is more standard and is obtained via the Feynman–Kac representation of solutions to (1), as in [14].

Related literature

Evolution of probabilities involving selection and mutation, either in the time-continuous form (1) or the time-discrete one (2), has been subject to extensive studies [11], with the prominent application being Sequential Monte Carlo methods [12]. The time-continuous particle system is sometimes called a Moran particle process or a branching-diffusion process, and the corresponding nonlinear evolution is called a Fleming Viot process [15]. What we call the external potential VV is sometimes referred to as a fitness function. The evolution can be studied via its Feynman–Kac formulation (see (4)) and, typically, particle approximation errors of the type

sup⁡nτE∣⟨ϕ,ρnN⟩−⟨ϕ,ρn⟩∣≲1N\sup_{n\tau}\mathbb{E}\left|\langle\phi,\rho_n^N\rangle-\langle\phi,\rho_n\rangle\right|\lesssim\frac{1}{\sqrt{N}}

are obtained for a class of observables ϕ∈Φ\phi\in\Phi; see, for instance, [10]. Note that, differently from Theorem 1.2, the expectation is taken with respect to one single observable. Intuitively, this corresponds to averaging the error among different runs and considering EρnN\mathbb{E}\rho_n^N instead of a single instance ρnN\rho_n^N.

In the more recent work [21], instead, convergence is shown with respect to the expected Wasserstein distance by considering evolution on the torus Td\mathbb{T}^d with rate ε(N,d)\varepsilon(N,d), as here. The use of Wasserstein distance with bounded ground cost, as W1dW_1^d, has been used in [26] to study particle systems also evolving in a bounded domain, and undergoing resampling when hitting the boundary. In the work [Bo and Liao, 2022] the authors also consider a Bounded-Lipschitz (BL) distance, with general RM dynamics which also includes (1). The particle system for which propagation of chaos is established, though, is obtained via the Feynman–Kac representation of the evolution, and, practically, corresponds to a weighted particle discretization. In Algorithm 1, instead, we consider unweighted particles, which is computationally more desirable to avoid loss of diversity. In [27] the author also considers the BL distance to study the bootstrap particle filter, similar to Algorithm 1, and obtains non-quantitative convergence of the particle approximation for non-compact domains and possibly unbounded fitness. Recent work [19] also considers particle filters and establishes almost sure, quantitative, convergence for one-dimensional systems with quadratic potential. Long-time high probability bounds for particle filters are also studied in [13] for non-compact state spaces via total variation and Kolmogorov distance under confinement assumptions on the potential. The authors of [16] consider a jump-diffusion process, as in (1), for an unbounded state space, and use the L1L^1-Wasserstein distance W1W_1. The analysis assumes directly the resampling mechanism to be Lipschitz with respect to W1W_1, which does not cover, for instance, quadratic VV.

Our contribution follows a different line of work on propagation of chaos results for collisional models in kinetic theory, [18, 9], where each particle interacts with a randomly sampled partner from the ensemble. While in Algorithm 1 there is no binary interaction, the technique of optimally coupling the newly sampled particle is central in our proof. More precisely, we follow the strategy developed in [Borghi and Pareschi, 2026] for studying Nambu-type Monte Carlo methods and in [3] for Genetic Algorithms, where first the limit N→∞N\to\infty is considered, and only afterward do we go to the time-continuous settings with τ→0\tau\to0.

Preliminary lemmas

Let us set the notation first. Given a Borel probability measure μ∈P(Rd)\mu\in\mathcal{P}(\mathbb{R}^d), we denote by Mq(μ)=∫∣x∣qμ(dx)M_q(\mu)=\int|x|^q\mu(\mathrm{d}x) its qq-th moment. We equip the space with the Wasserstein-1 distance W1dW_1^d associated with the cost d(x,y)=∣x−y∣∧1=min⁡(∣x−y∣,1)d(x,y)=|x-y|\wedge1=\min(|x-y|,1). By Kantorovich–Rubinstein duality [29], W1dW_1^d corresponds to the Bounded Lipschitz norm between measures

W1d(μ,ν)=∥μ−ν∥BL=sup⁡{∣∫ϕ(μ−ν)∣∣∥ϕ∥Lip≤1, osc⁡(ϕ)≤1}.(3)W_1^d(\mu,\nu)=\|\mu-\nu\|_{\mathrm{BL}}=\sup\left\{\left|\int\phi(\mu-\nu)\right|\mid\|\phi\|_{\mathrm{Lip}}\leq1,\ \operatorname{osc}(\phi)\leq1\right\}. \tag*{(3)}

where ∥ϕ∥Lip=sup⁡x,y∣ϕ(x)−ϕ(y)∣/∣x−y∣\|\phi\|_{\mathrm{Lip}} = \sup_{x,y} |\phi(x)-\phi(y)|/|x-y| and osc⁡(ϕ)=sup⁡ϕ−inf⁡ϕ\operatorname{osc}(\phi) = \sup\phi- \inf\phi. Also, note that we can restrict the class to the Lipschitz functions with ∥ϕ∥∞≤1/2\|\phi\|_{\infty} \le1/2 since translations ϕ−c\phi-c do not change the value of the integrals appearing in the dual formulation.

Random variables are assumed to be defined over an underlying probability space (P,F,Ω)(\mathbb{P},\mathcal{F},\Omega) and we write X∼μX \sim\mu if Law⁡(X)=μ\operatorname{Law}(X)=\mu. For a measurable test function ϕ\phi and a measure μ\mu we write the duality pairing as μ(ϕ)=∫ϕ(x)μ(dx)\mu(\phi)=\int\phi(x)\mu(dx).

Useful bounds

The nonlinear update ρn\rho_n defined in (2) admits a useful representation via a time discrete Feynman–Kac formula [11 Chapter 2]. Let X0∼ρ0X_0 \sim\rho_0 and (Bt)t≥0(B_t)_{t\geq0} be an independent standard Brownian process and define

Yt=X0+σBt.Y_t = X_0 + \sigma B_t .

The law ρn\rho_n can be equivalently defined as

ρn(ϕ)=E[ϕ(Ynτ)exp⁡(−τ∑k=0n−1V(Ykτ))]E[exp⁡(−τ∑k=0n−1V(Ykτ))](4)\rho_n(\phi) = \frac{\mathbb{E}\left[\phi(Y_{n\tau})\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right]}{\mathbb{E}\left[\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right]} \tag*{(4)}

for any bounded test function ϕ\phi.

Lemma 2.1. Let ρ0∈Pq(Rd)\rho_0 \in\mathcal{P}_q(\mathbb{R}^d) with q>2q>2. If VV satisfies Assumption 1.1, then for every τ>0\tau>0 there exists a constant C=C(d,q,σ,V,ρ0)>0C=C(d,q,\sigma,V,\rho_0)>0 such that

sup⁡nτ≤TMq(ρn)≤C(1+T)eC(1+T2)=:M‾T\sup_{n\tau\leq T} M_q(\rho_n) \leq C(1+\sqrt{T})e^{C(1+T^2)} =: \overline{M}_T

and

inf⁡nτ≤T∏k=0n−1Zτ(ρk)≥Ce−C(1+T2)=:e−V‾T.\inf_{n\tau\leq T}\prod_{k=0}^{n-1} Z_\tau(\rho_k) \geq C e^{-C(1+T^2)} =: e^{-\overline{V}_T}.

Proof. We use (4) with ϕ(x)=∣x∣q\phi(x)=|x|^q to obtain

Mq(ρn)=E[∣Ynτ∣qexp⁡(−τ∑k=0n−1V(Ykτ))]E[exp⁡(−τ∑k=0n−1V(Ykτ))](5)M_q(\rho_n) = \frac{\mathbb{E}\left[|Y_{n\tau}|^q\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right]}{\mathbb{E}\left[\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right]} \tag*{(5)}

Recall that for a Brownian process, it holds that E∣Bt∣q=tq/2E∣B1∣q\mathbb{E}|B_t|^q=t^{q/2}\mathbb{E}|B_1|^q. Therefore, we have for all t∈[0,T]t\in[0,T]

E∣Yt∣q≤Cq,d(E∣X0∣q+σqE∣Bt∣q)≤Cd,q(Mq(ρ0)+Tq/2σq).\mathbb{E}|Y_t|^q \leq C_{q,d}\left(\mathbb{E}|X_0|^q+\sigma^q\mathbb{E}|B_t|^q\right) \leq C_{d,q}\left(M_q(\rho_0)+T^{q/2}\sigma^q\right).

Since the exponential weights exp⁡(−τ∑k=0n−1V(Ykτ))\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right) take values in (0,1](0,1], the numerator in (5) can be bounded as

E[∣Ynτ∣qexp⁡(−τ∑k=0n−1V(Ykτ))]≤C(1+Tq/2),\mathbb{E}\left[|Y_{n\tau}|^q\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right] \leq C(1+T^{q/2}),

with C=C(d,q,σ,Mq(ρ0))>0C=C(d,q,\sigma,M_q(\rho_0))>0. By the quadratic upper bound on VV in Assumption 1.1, therefore we also have

EV(Yt)≤C(1+t).\mathbb{E}V(Y_t) \leq C(1+t).

For the denominator in (5), instead, we apply Jensen’s inequality to obtain

E[exp⁡(−τ∑k=0n−1V(Ykτ))]≥exp⁡(−τ∑k=0n−1EV(Ykτ))≥e−CT(1+T),(6)\mathbb{E}\left[\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right]\ge\exp\left(-\tau\sum_{k=0}^{n-1}\mathbb{E}V(Y_{k\tau})\right)\ge e^{-CT(1+T)}, \tag*{(6)}

where CC is independent of TT and τ\tau. Putting the two estimates together in (5) gives the first desired bound.

For the second bound we note that, by using the Feynman–Kac formula with ϕ=e−τV\phi=e^{-\tau V},

Zτ(ρk)=E[e−τV(Ynτ)exp⁡(−τ∑m=0k−1V(Ymτ))]E[exp⁡(−τ∑m=0k−1V(Ymτ))]=E[exp⁡(−τ∑m=0kV(Ymτ))]E[exp⁡(−τ∑m=0n−1V(Ymτ))]=:zkzk−1.Z_\tau(\rho_k)=\frac{\mathbb{E}\left[e^{-\tau V(Y_{n\tau})}\exp\left(-\tau\sum_{m=0}^{k-1}V(Y_{m\tau})\right)\right]}{\mathbb{E}\left[\exp\left(-\tau\sum_{m=0}^{k-1}V(Y_{m\tau})\right)\right]}=\frac{\mathbb{E}\left[\exp\left(-\tau\sum_{m=0}^{k}V(Y_{m\tau})\right)\right]}{\mathbb{E}\left[\exp\left(-\tau\sum_{m=0}^{n-1}V(Y_{m\tau})\right)\right]}=:\frac{z_k}{z_{k-1}}.

Note that z0=1z_0=1 since e0=1e^0=1. By multiplying this ratio for k=1,…,nk=1,\ldots,n, the product simplifies to

∏k=0n−1Zτ(ρk)=∏k=0n−1zkzk−1=zn−1z0=E[exp⁡(−τ∑k=0n−1V(Ykτ))].\prod_{k=0}^{n-1}Z_\tau(\rho_k)=\prod_{k=0}^{n-1}\frac{z_k}{z_{k-1}}=\frac{z_{n-1}}{z_0}=\mathbb{E}\left[\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right].

for which we already derived a lower bound in (6).

Thanks to the bound on the moments, we can also estimate the error in approximating the partition function from i.i.d. samples. For a bound of order τ/N\tau/\sqrt{N} at a single step, it suffices to assume q≥4q\ge4, since VV grows at most quadratically.

Lemma 2.2. Let ρ∈Pq(Rd)\rho\in\mathcal{P}_q(\mathbb{R}^d) with q≥4q\ge4 and Xi∼ρX^i\sim\rho, i.i.d. with empirical measure ρˉN=1N∑i=1NδXi\bar{\rho}^N=\frac{1}{N}\sum_{i=1}^N\delta_{X^i}. If VV satisfies Assumption 1.1, it holds that

E∣Zτ(ρˉN)−Zτ(ρ)∣≤CVτN(1+Mq(ρ)2/q).\mathbb{E}\left|Z_\tau(\bar{\rho}^N)-Z_\tau(\rho)\right|\le C_V\frac{\tau}{\sqrt{N}}\left(1+M_q(\rho)^{2/q}\right).

Proof. Since E[e−τV(Xi)]=Zτ(ρ)\mathbb{E}[e^{-\tau V(X^i)}]=Z_\tau(\rho) and the samples are independent, we have

E∣Zτ(ρˉN)−Zτ(ρ)∣2=1NVar⁡ρ(e−τV).\mathbb{E}\left|Z_\tau(\bar{\rho}^N)-Z_\tau(\rho)\right|^2=\frac{1}{N}\operatorname{Var}_{\rho}(e^{-\tau V}).

By Cauchy–Schwarz, then we have

E∣Zτ(ρˉN)−Zτ(ρ)∣≤Var⁡ρ(e−τV)1/2N≤(∫(1−e−τV(x))2ρ(dx))1/2N≤τN(∫V2(x)ρ(dx))1/2\mathbb{E}\left|Z_\tau(\bar{\rho}^N)-Z_\tau(\rho)\right|\le\frac{\operatorname{Var}_{\rho}(e^{-\tau V})^{1/2}}{\sqrt{N}}\le\frac{\left(\int(1-e^{-\tau V(x)})^2\rho(dx)\right)^{1/2}}{\sqrt{N}}\le\frac{\tau}{\sqrt{N}}\left(\int V^2(x)\rho(dx)\right)^{1/2}

where we also used 1−e−u≤u1-e^{-u}\le u with u=τV(x)≥0u=\tau V(x)\ge0. Finally, since VV satisfies the quadratic upper bound of Assumption 1.1, we have

(∫V2(x)ρ(dx))1/2≤CV(1+M4(ρ)1/2)≤CV(1+Mq(ρ)2/q).\left(\int V^2(x)\rho(dx)\right)^{1/2}\le C_V(1+M_4(\rho)^{1/2})\le C_V(1+M_q(\rho)^{2/q}).

Stability of replicator operator

We collect another important result concerning the Lipschitz continuity of Rτ\mathbf{R}_{\tau} with respect to the bounded Wasserstein distance W1dW_{1}^{d}. A key aspect of the estimate is its asymmetry with respect to the two input measures, similarly to [25 Theorem 15], as only one of them appears in the Lipschitz constant through its partition function Zτ(ν)Z_{\tau}(\nu).

Lemma 2.3. Let VV satisfy Assumption 1.1 and let μ,ν∈P(Rd)\mu,\nu\in\mathcal{P}(\mathbb{R}^{d}). It holds that

W1d(Rτ[μ],Rτ[ν])≤1+τCV′Zτ(ν)W1d(μ,ν).W_{1}^{d}\left(\mathbf{R}_{\tau}[\mu],\mathbf{R}_{\tau}[\nu]\right) \leq\frac{1+\tau C_{V}^{\prime}}{Z_{\tau}(\nu)}W_{1}^{d}(\mu,\nu).

Proof. We will make use of the dual formulation of W1dW_{1}^{d} as the bounded Lipschitz norm (3). Let ϕ\phi be such that ∥ϕ∥Lip≤1\lVert\phi\rVert_{\mathrm{Lip}} \leq1 and osc⁡(ϕ)≤1\operatorname{osc}(\phi) \leq1 and consider

ϕ^=e−τV(ϕ−Rτ[μ](ϕ)).\widehat{\phi}=e^{-\tau V}\left(\phi-\mathbf{R}_{\tau}[\mu](\phi)\right).

Recall Rτ[μ]=e−τVμ/Zτ(μ)\mathbf{R}_{\tau}[\mu]=e^{-\tau V}\mu/Z_{\tau}(\mu). By performing some algebraic computations we can show

Rτ[μ](ϕ)−Rτ[ν](ϕ)=Rτ[μ](ϕ)⋅Zτ(ν)Zτ(ν)−ν(e−τVϕ)Zτ(ν)±μ(e−τVϕ)Zτ(ν)=ν(e−τVRτ[μ](ϕ)−e−τVϕ)±μ(e−τVϕ)Zτ(ν)=ν(e−τVRτ[μ](ϕ)−e−τVϕ+μ(e−τVϕ)−μ(e−τVRτ[μ](ϕ)))Zτ(ν)=μ(ϕ^)−ν(ϕ^)Zτ(ν).\begin{aligned} \mathbf{R}_{\tau}[\mu](\phi)-\mathbf{R}_{\tau}[\nu](\phi) &=\mathbf{R}_{\tau}[\mu](\phi)\cdot\frac{Z_{\tau}(\nu)}{Z_{\tau}(\nu)} -\frac{\nu(e^{-\tau V}\phi)}{Z_{\tau}(\nu)} \pm\frac{\mu(e^{-\tau V}\phi)}{Z_{\tau}(\nu)}\\ &=\frac{\nu\left(e^{-\tau V}\mathbf{R}_{\tau}[\mu](\phi)-e^{-\tau V}\phi\right)\pm\mu(e^{-\tau V}\phi)}{Z_{\tau}(\nu)}\\ &=\frac{\nu\left(e^{-\tau V}\mathbf{R}_{\tau}[\mu](\phi)-e^{-\tau V}\phi+\mu(e^{-\tau V}\phi)-\mu(e^{-\tau V}\mathbf{R}_{\tau}[\mu](\phi))\right)}{Z_{\tau}(\nu)}\\ &=\frac{\mu(\widehat{\phi})-\nu(\widehat{\phi})}{Z_{\tau}(\nu)}. \end{aligned}

Note that since V≥0V \geq0 and translation by Rτ[μ](ϕ)\mathbf{R}_{\tau}[\mu](\phi) does not change the oscillations of the test function, we have osc⁡(ϕ^)≤1\operatorname{osc}(\widehat{\phi}) \leq1. For the Lipschitz constant, we have ∣∇ϕ∣≤1\lvert\nabla\phi\rvert\leq1 and by Assumption 1.1 it holds that ∣∇V∣≤V+CV′\lvert\nabla V\rvert\leq V+C_{V}^{\prime}, which leads to

∣∇ϕ^∣=e−τV∣∇ϕ−τ(ϕ−Rτ[μ](ϕ))∇V∣≤e−τV(1+τV)+τCV′e−τV≤(1+τCV′),\begin{aligned} \lvert\nabla\widehat{\phi}\rvert &=e^{-\tau V}\left\lvert\nabla\phi-\tau\left(\phi-\mathbf{R}_{\tau}[\mu](\phi)\right)\nabla V\right\rvert\\ &\leq e^{-\tau V}(1+\tau V)+\tau C_{V}^{\prime}e^{-\tau V}\leq(1+\tau C_{V}^{\prime}), \end{aligned}

where we also used e−u(1+u)≤1e^{-u}(1+u)\leq1 with u=τVu=\tau V. Therefore, we have that ϕ^/(1+τCV′)\widehat{\phi}/(1+\tau C_{V}^{\prime}) is a suitable test function and we have μ(ϕ^)−ν(ϕ^)≤(1+τCV′)W1d(μ,ν)\mu(\widehat{\phi})-\nu(\widehat{\phi})\leq(1+\tau C_{V}^{\prime})W_{1}^{d}(\mu,\nu), from which the desired bound follows. □\square

We note that, if ν(V)<∞\nu(V)<\infty, Jensen’s inequality gives Zτ(ν)≥e−τν(V)Z_{\tau}(\nu)\geq e^{-\tau\nu(V)} and the constant is of order 1+O(τ)1+O(\tau). Keeping Zτ(ρk)Z_{\tau}(\rho_{k}) in the estimate allows us to apply Lemma 2.1 directly when iterating over kk.

Stability of resampling probabilities

The last result we collect concerns the probability of a particle undergoing resampling. Specifically, given two particles x,y∈Rdx,y\in\mathbb{R}^{d}, we ask ourselves what the probability is that they are simultaneously resampled, or not. From Algorithm 1, we have that an x∈Rdx\in\mathbb{R}^{d} particle is resampled with probability

β(z):=1−e−τV(z).\beta(z):=1-e^{-\tau V(z)}.

If we try to maximize the correspondence between particles xx and yy, we have:

  • with probability min⁡{β(x),β(y)}\min\{\beta(x),\beta(y)\}: both resampled

  • with probability ∣β(x)−β(y)∣|\beta(x)-\beta(y)|: only one resampled

  • with probability 1−max⁡{β(x),β(y)}1-\max\{\beta(x),\beta(y)\}: neither resampled

Lemma 2.4. Let the potential VV satisfy Assumption 1.1. For any x,y∈Rdx,y\in\mathbb{R}^d, it holds that

∣β(x)−β(y)∣−max⁡{β(x),β(y)}d(x,y)≤τCV′d(x,y).|\beta(x)-\beta(y)|-\max\{\beta(x),\beta(y)\}d(x,y)\leq\tau C'_Vd(x,y).

Proof. Consider first the case d(x,y)=1d(x,y)=1. Since β(x),β(y)∈[0,1]\beta(x),\beta(y)\in[0,1], it holds that

∣β(x)−β(y)∣−max⁡{β(x),β(y)}≤0|\beta(x)-\beta(y)|-\max\{\beta(x),\beta(y)\}\leq0

and the bound is satisfied. For d(x,y)=∣x−y∣<1d(x,y)=|x-y|<1, recall from Assumption 1.1 that ∣∇V∣≤CV′+V|\nabla V|\leq C'_V+V almost everywhere. We have

∣∇β∣≤τ(CV′+V)e−τV≤τCV′+β,|\nabla\beta|\leq\tau(C'_V+V)e^{-\tau V}\leq\tau C'_V+\beta,

where in the last step we used ue−u≤1−e−uue^{-u}\leq1-e^{-u} with u=τVu=\tau V. Let m=max⁡{β(x),β(y)}m=\max\{\beta(x),\beta(y)\}. The function min⁡{β,m}\min\{\beta,m\} agrees with β\beta at xx and yy and has gradient bounded by τCV′+m\tau C'_V+m almost everywhere. Its Lipschitz bound therefore gives

∣β(x)−β(y)∣≤∣x−y∣τCV′+∣x−y∣max⁡{β(x),β(y)}|\beta(x)-\beta(y)|\leq|x-y|\tau C'_V+|x-y|\max\{\beta(x),\beta(y)\}

Given we are considering the case d(x,y)=∣x−y∣<1d(x,y)=|x-y|<1, this inequality corresponds to the desired estimate.

Coupling and limit N→∞N\to\infty

Two particle systems

We show propagation of chaos by coupling the particle system (Xn)n(X_n)_n generated via Algorithm 1 with a nonlinear system (X‾n)N(\overline{X}_n)_N sharing the same random variables. The key coupling is the one of the newly sampled particles, which will depend on i.i.d. continuous random variables αni∼Unif⁡[0,N)\alpha_n^i\sim\operatorname{Unif}[0,N).

To this end, given a set of positive weights w∈int⁡(ΔN)\mathbf{w}\in\operatorname{int}(\Delta_N) we introduce the index map j:[0,N)→{1,…,N}\mathbf{j}:[0,N)\to\{1,\ldots,N\}

j(w,α):=min⁡{j∈{1,…,N}:α<N∑ℓ=1jwℓ}.(7)\mathbf{j}(\mathbf{w},\alpha):=\min\left\{j\in\{1,\ldots,N\}:\alpha<N\sum_{\ell=1}^{j}w^\ell\right\}. \tag*{(7)}

If α∼Unif⁡[0,N)\alpha\sim\operatorname{Unif}[0,N), note that P(j(w,α)=j)=wj\mathbb{P}(\mathbf{j}(\mathbf{w},\alpha)=j)=w^j and so j(α)∼Categorical⁡(w1,…,wN)\mathbf{j}(\alpha)\sim\operatorname{Categorical}(w^1,\ldots,w^N) as in Algorithm 1.

Recall a particle XniX_n^i gets resampled with probability 1−e−τV(Xni)1-e^{-\tau V(X_n^i)}. We make the activation also explicitly dependent on i.i.d. continuous random variables βni∼Unif⁡[0,1)\beta_n^i\sim\operatorname{Unif}[0,1) so that XniX_n^i is resampled if βni<1−e−τV(Xni)\beta_n^i<1-e^{-\tau V(X_n^i)}.

Starting from X0i∼ρ0X_0^i\sim\rho_0 i.i.d., the update procedure of Algorithm 1 can then be rewritten as

Xn+1i={Xnj(wn,αni)+στ ξniif βni<1−e−τV(Xni),Xni+στ ξnielse(8)X_{n+1}^i= \begin{cases} X_n^{\mathbf{j}(\mathbf{w}_n,\alpha_n^i)}+\sigma\sqrt{\tau}\,\xi_n^i & \text{if }\beta_n^i<1-e^{-\tau V(X_n^i)},\\ X_n^i+\sigma\sqrt{\tau}\,\xi_n^i & \text{else} \end{cases} \tag*{(8)}

with the weights given by wn=(wn1,…,wnN)\mathbf{w}_n=(w_n^1,\ldots,w_n^N), wni=e−τV(Xni)/∑j=1Ne−τV(Xnn)w_n^i=e^{-\tau V(X_n^i)}/\sum_{j=1}^N e^{-\tau V(X_n^n)}.

To construct the nonlinear particle system we will re-use the random variables X0iX_0^i, αni\alpha_n^i, βni\beta_n^i, ξni\xi_n^i and, most importantly, optimally couple the newly sampled random variables thanks to the following result, which we recall for completeness.

Lemma 3.1. [3 Lemma 3.1] For p≥1p\ge1, let WpcW_p^c be the Wasserstein distance with a lower semi-continuous cost function c(x,y)c(x,y), and let f∈P(Rd)f\in\mathcal{P}(\mathbb{R}^d) such that Wpc(f,δ0)<+∞W_p^c(f,\delta_0)<+\infty. Consider x=(x1,…,xN)∈(Rd)N\mathbf{x}=(x^1,\ldots,x^N)\in(\mathbb{R}^d)^N and weights w=(w1,…,wN)∈int⁡(ΔN)\mathbf{w}=(w^1,\ldots,w^N)\in\operatorname{int}(\Delta_N) such that wi>0w^i>0 and ∑i=1Nwi=1\sum_{i=1}^N w^i=1. Define the weighted empirical measure as μx,w:=∑i=1Nwiδxi\mu_{\mathbf{x},\mathbf{w}}:=\sum_{i=1}^N w^i\delta_{x_i}, and recall from (7) the index-map j(w,⋅)\mathbf{j}(\mathbf{w},\cdot).

There exists a measurable mapping

Xf∗:(Rd)N×int⁡(ΔN)×[0,N)→RdX_f^*:(\mathbb{R}^d)^N\times\operatorname{int}(\Delta_N)\times[0,N)\to\mathbb{R}^d
(x,w,α)↦Xf∗(x,w,α)(\mathbf{x},\mathbf{w},\alpha)\mapsto X_f^*(\mathbf{x},\mathbf{w},\alpha)

with the following property: if α∼Unif⁡[0,N)\alpha\sim\operatorname{Unif}[0,N), then the pair (Xf∗(x,w,α),xj(w,α))(X_f^*(\mathbf{x},\mathbf{w},\alpha),x^{\mathbf{j}(\mathbf{w},\alpha)}) is an optimal coupling between ff and μx,w\mu_{\mathbf{x},\mathbf{w}}, namely

E[c(Xf∗(x,w,α),xj(w,α))p]=(Wpc(f,μx,w))p.\mathbb{E}\left[c\left(X_f^*(\mathbf{x},\mathbf{w},\alpha),x^{\mathbf{j}(\mathbf{w},\alpha)}\right)^p\right]=\left(W_p^c(f,\mu_{\mathbf{x},\mathbf{w}})\right)^p.

For any n∈Nn\in\mathbb{N}, let Xρn∗X_{\rho_n}^* be the map defined above with f=Rτ[ρn]f=R_\tau[\rho_n] for the cost dd and p=1p=1. The nonlinear particle system is iteratively defined as X‾0=X0\overline{X}_0=X_0 and

X‾n+1i={Xρn∗(Xn,wn,αni)+στξniif βni<1−e−τV(X‾ni),X‾ni+στξnielse.(9)\overline{X}_{n+1}^i= \begin{cases} X_{\rho_n}^*(X_n,\mathbf{w}_n,\alpha_n^i)+\sigma\sqrt{\tau}\xi_n^i & \text{if }\beta_n^i<1-e^{-\tau V(\overline{X}_n^i)},\\ \overline{X}_n^i+\sigma\sqrt{\tau}\xi_n^i & \text{else}. \end{cases} \tag*{(9)}

Note that, by Lemma 3.1, conditionally on the particles at time nn, we have Xρn∗(Xn,wn,αni)∼Rτ[ρn]X_{\rho_n}^*(X_n,\mathbf{w}_n,\alpha_n^i)\sim R_\tau[\rho_n] and these draws are conditionally independent since the αni\alpha_n^i are independent. The conditional law of each update then depends only on X‾ni\overline{X}_n^i. If the X‾ni\overline{X}_n^i are i.i.d. with law ρn\rho_n, the law after resampling is e−τVρn+(1−Zτ(ρn))Rτ[ρn]=Rτ[ρn]e^{-\tau V}\rho_n+(1-Z_\tau(\rho_n))R_\tau[\rho_n]=R_\tau[\rho_n]. Adding the independent Gaussian increments gives ρn+1\rho_{n+1}. Therefore, by induction, we have that

X‾ni∼ρnfor all i=1,…,N, i.i.d.,\overline{X}_n^i\sim\rho_n\qquad\text{for all }i=1,\ldots,N,\ \text{i.i.d.},

with ρn\rho_n being the time-discrete update ρn+1=Mτ[Rτ[ρn]]\rho_{n+1}=M_\tau[R_\tau[\rho_n]], see (2).

Propagation of chaos

To show convergence as N→∞N\to\infty, we track the distance Ed(Xni,X‾ni)\mathbb{E}d(X_n^i,\overline{X}_n^i) for nτ≤Tn\tau\le T and iterate the estimate via a time-discrete Grönwall argument.

Proposition 3.2. Let VV satisfy Assumption 1.1, and ρ0∈Pq(Rd)\rho_0\in\mathcal{P}_q(\mathbb{R}^d), q≥4q\ge4. Let ρnN\rho_n^N be the empirical measure associated with the algorithm’s particle system and ρ‾nN\overline{\rho}_n^N the one associated with the i.i.d. system (9). For every fixed T>0T>0 and all nn such that nτ≤Tn\tau\le T it holds

EW1d(ρnN,ρ‾nN)≤C(1+T2)eC(1+T2)ε(N,d)\mathbb{E}W_1^d(\rho_n^N,\overline{\rho}_n^N)\le C(1+T^2)e^{C(1+T^2)}\varepsilon(N,d)

with C>0C>0 depending only on V,σ,d,qV,\sigma,d,q, and the qq-th moment of ρ0\rho_0.

Proof. Let the particles’ resampling probability be given by β(z)=1−e−τV(z)\beta(z)=1-e^{-\tau V(z)}. Since the resampling probabilities of the particles are coupled through the same random variables βni∼Unif⁡[0,1)\beta_n^i\sim\operatorname{Unif}[0,1), we have that, conditionally on the particles at time nn, the probabilities of both, only one, and neither being resampled are respectively

P(βni<min⁡{β(Xni),β(X‾ni)})=min⁡{β(Xni),β(X‾ni)}.\mathbb{P}\left(\beta_n^i<\min\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\right)=\min\{\beta(X_n^i),\beta(\overline{X}_n^i)\}.
P(min⁡{β(Xni),β(X‾ni)}≤βni≤max⁡{β(Xni),β(X‾ni)})=∣β(Xni)−β(X‾ni)∣.\mathbb{P}\left(\min\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\leq\beta_n^i\leq\max\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\right)=\left|\beta(X_n^i)-\beta(\overline{X}_n^i)\right|.
P(βni>max⁡{β(Xni),β(X‾ni)})=1−max⁡{β(Xni),β(X‾ni)}.\mathbb{P}\left(\beta_n^i>\max\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\right)=1-\max\{\beta(X_n^i),\beta(\overline{X}_n^i)\}.

The common Gaussian increment does not change dd. When only one is resampled, we will use that the maximum transport cost to be paid is max⁡x,x‾d(x,x‾)=1\max_{x,\overline{x}}d(x,\overline{x})=1.

By applying Lemma 2.4 and optimality of the α\alpha-coupling we have

1N∑i=1NE[d(Xn+1i,X‾n+1i)]≤1N∑i=1NE[min⁡{β(Xni),β(X‾ni)}d(Xnj(wn,αni),Xρn∗(Xn,wn,αni))]\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[d(X_{n+1}^i,\overline{X}_{n+1}^i)\right]\leq\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[\min\{\beta(X_n^i),\beta(\overline{X}_n^i)\}d\left(X_n^{j(w_n,\alpha_n^i)},X_{\rho_n}^{*}(X_n,w_n,\alpha_n^i)\right)\right]
+1N∑i=1NE[∣β(Xni)−β(X‾ni)∣+(1−max⁡{β(Xni),β(X‾ni)})d(Xni,X‾ni)]≤1N∑i=1NE[min⁡{β(Xni),β(X‾ni)}W1d(Rτ[ρnN],Rτ[ρn])]\begin{aligned} \qquad+\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[\left|\beta(X_n^i)-\beta(\overline{X}_n^i)\right|+\left(1-\max\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\right)d(X_n^i,\overline{X}_n^i)\right] \\ &\leq\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[\min\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\mathcal{W}_1^d\left(\mathcal{R}_{\tau}[\rho_n^N],\mathcal{R}_{\tau}[\rho_n]\right)\right] \end{aligned}
+1N∑i=1N(τCV′Ed(Xni,X‾ni)+Ed(Xni,X‾ni)).(10)\qquad+\frac{1}{N}\sum_{i=1}^{N}\left(\tau C'_V\mathbb{E}d(X_n^i,\overline{X}_n^i)+\mathbb{E}d(X_n^i,\overline{X}_n^i)\right). \tag*{(10)}

Let us focus on the first term. Since min⁡{β(Xni),β(X‾ni)}≤β(X‾ni)\min\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\leq\beta(\overline{X}_n^i) and 1N∑i=1Nβ(X‾ni)=1−Zτ(ρ‾n)\frac{1}{N}\sum_{i=1}^{N}\beta(\overline{X}_n^i)=1-Z_{\tau}(\overline{\rho}_n), we have

1N∑i=1NE[min⁡{β(Xni),β(X‾ni)}W1d(Rτ[ρnN],Rτ[ρn])]≤1N∑i=1NE[β(X‾ni)W1d(Rτ[ρnN],Rτ[ρn])]=E[(1−Zτ(ρ‾n))W1d(Rτ[ρnN],Rτ[ρn])]≤(1−Zτ(ρn))EW1d(Rτ[ρnN],Rτ[ρn])+E∣Zτ(ρn)−Zτ(ρ‾n)∣≤(1−Zτ(ρn))EW1d(Rτ[ρnN],Rτ[ρn])+CVτN(1+Mq(ρn)2)1/q≤(1−Zτ(ρn))1+τCV′Zτ(ρn)EW1d(ρnN,ρn)+CVτN(1+Mq(ρn)2)1/q,\begin{aligned} \frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[\min\{\beta(X_n^i),\beta(\overline{X}_n^i)\}\mathcal{W}_1^d\left(\mathcal{R}_{\tau}[\rho_n^N],\mathcal{R}_{\tau}[\rho_n]\right)\right]\leq\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\left[\beta(\overline{X}_n^i)\mathcal{W}_1^d\left(\mathcal{R}_{\tau}[\rho_n^N],\mathcal{R}_{\tau}[\rho_n]\right)\right] \\ &=\mathbb{E}\left[(1-Z_{\tau}(\overline{\rho}_n))\mathcal{W}_1^d\left(\mathcal{R}_{\tau}[\rho_n^N],\mathcal{R}_{\tau}[\rho_n]\right)\right] \\ &\leq(1-Z_{\tau}(\rho_n))\mathbb{E}\mathcal{W}_1^d\left(\mathcal{R}_{\tau}[\rho_n^N],\mathcal{R}_{\tau}[\rho_n]\right)+\mathbb{E}\left|Z_{\tau}(\rho_n)-Z_{\tau}(\overline{\rho}_n)\right| \\ &\leq(1-Z_{\tau}(\rho_n))\mathbb{E}\mathcal{W}_1^d\left(\mathcal{R}_{\tau}[\rho_n^N],\mathcal{R}_{\tau}[\rho_n]\right)+\frac{C_V\tau}{\sqrt{N}}\left(1+M_q(\rho_n)^2\right)^{1/q} \\ &\leq(1-Z_{\tau}(\rho_n))\frac{1+\tau C'_V}{Z_{\tau}(\rho_n)}\mathbb{E}\mathcal{W}_1^d(\rho_n^N,\rho_n)+\frac{C_V\tau}{\sqrt{N}}\left(1+M_q(\rho_n)^2\right)^{1/q}, \end{aligned}

where in the last steps we have used W1d≤1\mathcal{W}_1^d\leq1, Lemma 2.2 for the difference between the partition functions and Lemma 2.3 for the stability of the replicator operator Rτ\mathcal{R}_{\tau}.

The Wasserstein distance term EW1d(ρnN,ρn)\mathbb{E}\mathcal{W}_1^d(\rho_n^N,\rho_n) itself, instead, can be bounded by the triangular inequality as

EW1d(ρnN,ρn)≤EW1d(ρnN,ρ‾nN)+EW1d(ρ‾nN,ρn)≤1N∑i=1NEd(Xni,X‾ni)+CMq(ρn)1/qε(N,d),(11)\begin{aligned} \mathbb{E}\mathcal{W}_1^d(\rho_n^N,\rho_n)\leq\mathbb{E}\mathcal{W}_1^d(\rho_n^N,\overline{\rho}_n^N)+\mathbb{E}\mathcal{W}_1^d(\overline{\rho}_n^N,\rho_n) \\ &\leq\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}d(X_n^i,\overline{X}_n^i)+CM_q(\rho_n)^{1/q}\varepsilon(N,d), \tag*{(11)} \end{aligned}

by the concentration inequalities of i.i.d. particles with respect to the Wasserstein-1 distance W1W_1 [17]. Note that the Monte Carlo rate 1/N1/\sqrt{N} is faster than the concentration rate ε(N,d)\varepsilon(N,d) (or equal if d=1d=1) and therefore can be absorbed in an O(ε(N,d))O(\varepsilon(N,d)) term.

Continuing the estimate from (10) and collecting the two terms in the distance between the coupled particles, we obtain

1N∑i=1NEd(Xn+1i,X‾n+1i)≤1+τCV′Zτ(ρn)1N∑i=1NEd(Xni,X‾ni)+C(1+τCV′)(1−Zτ(ρn))Zτ(ρn)M‾T1/qε(N,d)+CVτN(1+M‾T2/q).(12)\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n+1}^{i},\overline{X}_{n+1}^{i}) \leq\frac{1+\tau C_{V}^{\prime}}{Z_{\tau}(\rho_{n})}\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n}^{i},\overline{X}_{n}^{i}) + C\frac{(1+\tau C_{V}^{\prime})(1-Z_{\tau}(\rho_{n}))}{Z_{\tau}(\rho_{n})}\overline{M}_{T}^{1/q}\varepsilon(N,d) + \frac{C_{V}\tau}{\sqrt{N}}(1+\overline{M}_{T}^{2/q}). \tag*{(12)}

where we used the bound Mq(ρn)≤M‾TM_{q}(\rho_{n})\leq\overline{M}_{T} from Lemma 2.1. To iterate the estimate, we add CM‾T1/qε(N,d)C\overline{M}_{T}^{1/q}\varepsilon(N,d) to both sides of (3.5). Since

1+(1+τCV′)(1−Zτ(ρn))Zτ(ρn)=1+τCV′Zτ(ρn)−τCV′≤1+τCV′Zτ(ρn),1+\frac{(1+\tau C_{V}^{\prime})(1-Z_{\tau}(\rho_{n}))}{Z_{\tau}(\rho_{n})}=\frac{1+\tau C_{V}^{\prime}}{Z_{\tau}(\rho_{n})}-\tau C_{V}^{\prime}\leq\frac{1+\tau C_{V}^{\prime}}{Z_{\tau}(\rho_{n})},

we obtain

1N∑i=1NEd(Xn+1i,X‾n+1i)+CM‾T1/qε(N,d)≤1+τCV′Zτ(ρn)[1N∑i=1NEd(Xni,X‾ni)+CM‾T1/qε(N,d)]+CVτN(1+M‾T2/q).\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n+1}^{i},\overline{X}_{n+1}^{i})+C\overline{M}_{T}^{1/q}\varepsilon(N,d) \leq\frac{1+\tau C_{V}^{\prime}}{Z_{\tau}(\rho_{n})}\left[\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n}^{i},\overline{X}_{n}^{i})+C\overline{M}_{T}^{1/q}\varepsilon(N,d)\right]+\frac{C_{V}\tau}{\sqrt{N}}(1+\overline{M}_{T}^{2/q}).

Since Zτ(ρk)≤1Z_{\tau}(\rho_{k})\leq1, each multiplier is at least one and every partial product appearing in the iteration is bounded by the full product. By Lemma 2.1, we have

∏k=0n−11+τCV′Zτ(ρk)=(1+τCV′)n∏k=0n−1Zτ(ρk)≤eCV′T+V‾T.\prod_{k=0}^{n-1}\frac{1+\tau C_{V}^{\prime}}{Z_{\tau}(\rho_{k})}=\frac{(1+\tau C_{V}^{\prime})^{n}}{\prod_{k=0}^{n-1}Z_{\tau}(\rho_{k})}\leq e^{C_{V}^{\prime}T+\overline{V}_{T}}.

Recall that X0i=X‾0iX_{0}^{i}=\overline{X}_{0}^{i}, so the initial particle distance is zero. Iterating the estimate above and using nτ≤Tn\tau\leq T therefore gives

1N∑i=1NEd(Xni,X‾ni)+CM‾T1/qε(N,d)≤eCV′T+V‾T[CM‾T1/qε(N,d)+CVTN(1+M‾T2/q)].\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n}^{i},\overline{X}_{n}^{i})+C\overline{M}_{T}^{1/q}\varepsilon(N,d)\leq e^{C_{V}^{\prime}T+\overline{V}_{T}}\left[C\overline{M}_{T}^{1/q}\varepsilon(N,d)+\frac{C_{V}T}{\sqrt{N}}(1+\overline{M}_{T}^{2/q})\right].

Subtracting the sampling term from both sides, we obtain

1N∑i=1NEd(Xni,X‾ni)≤CM‾T1/q(eCV′T+V‾T−1)ε(N,d)+CVTNeCV′T+V‾T(1+M‾T2/q).\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n}^{i},\overline{X}_{n}^{i})\leq C\overline{M}_{T}^{1/q}\left(e^{C_{V}^{\prime}T+\overline{V}_{T}}-1\right)\varepsilon(N,d)+\frac{C_{V}T}{\sqrt{N}}e^{C_{V}^{\prime}T+\overline{V}_{T}}(1+\overline{M}_{T}^{2/q}).

We note that N−1/2≤ε(N,d)N^{-1/2}\leq\varepsilon(N,d), and so this Monte Carlo rate can be absorbed in the Wasserstein concentration rate ε(N,d)\varepsilon(N,d). By recalling the definition of M‾T\overline{M}_{T} and V‾T\overline{V}_{T} from Lemma 2.1, we obtain

1N∑i=1NEd(Xni,X‾ni)≤C[(1+T)1/q+T+T(1+T)2/q]eC(1+T2)ε(N,d)≤C(1+T2)eC(1+T2)ε(N,d),\begin{aligned} \frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n}^{i},\overline{X}_{n}^{i})\leq C\left[(1+\sqrt{T})^{1/q}+T+T(1+\sqrt{T})^{2/q}\right]e^{C(1+T^{2})}\varepsilon(N,d) \\ &\leq C(1+T^{2})e^{C(1+T^{2})}\varepsilon(N,d), \end{aligned}

where the last inequality follows from q≥4q\geq4. Since EW1d(ρnN,ρ‾nN)≤1N∑i=1NEd(Xni,X‾ni)\mathbb{E}W_{1}^{d}(\rho_{n}^{N},\overline{\rho}_{n}^{N})\leq\frac{1}{N}\sum_{i=1}^{N}\mathbb{E}\mathrm{d}(X_{n}^{i},\overline{X}_{n}^{i}), we have obtained the desired estimate.

Limit τ→0\tau\to0 and proof of the main Theorem

We start by stating what we mean by a measure solution to the RM model (1).

Definition 4.1. Let T>0T > 0 and ρ0∈P(Rd)\rho_0 \in\mathcal{P}(\mathbb{R}^d). We say ρ∈C([0,T],P(Rd))\rho\in C([0,T],\mathcal{P}(\mathbb{R}^d)) is a weak solution to (1) with initial datum ρ0\rho_0 over [0,T][0,T] if for all ϕ∈Cc∞(Rd)\phi\in C^\infty_c(\mathbb{R}^d) and t∈[0,T]t \in[0,T]

ρt(ϕ)=ρ0(ϕ)+∫0T(σ22ρs(Δϕ)−ρs(Vϕ)+ρs(V)ρs(ϕ)) ds.\rho_t(\phi) = \rho_0(\phi) + \int_0^T \left( \frac{\sigma^2}{2}\rho_s(\Delta\phi) - \rho_s(V\phi) + \rho_s(V)\rho_s(\phi) \right) \, \mathrm{d}s .

Time-discretization error

To show the RM splitting scheme ρn+1=Mτ[Rτ[ρn]]\rho_{n+1} = M_\tau[R_\tau[\rho_n]] introduces a first order error with respect to the time discretization step τ\tau, we briefly adapt the proof of [14] to account for unbounded potentials.

Proposition 4.2. Let ρ∈C([0,T],P(Rd))\rho\in C([0,T],\mathcal{P}(\mathbb{R}^d)) be a measure solution to (1) with ρ0∈Pq(Rd)\rho_0 \in\mathcal{P}_q(\mathbb{R}^d), q>2q > 2, and (ρn)n∈N(\rho_n)_{n\in\mathbb{N}} be iteratively defined by (2) with τ∈(0,1]\tau\in(0,1]. If VV satisfies Assumption 1.1, it holds

sup⁡tn=nτW1d(ρn,ρ(tn))≤C(1+T2)eC(1+T2)τ,\sup_{t_n=n\tau} \mathcal{W}_1^d(\rho_n,\rho(t_n)) \le C(1+T^2)e^{C(1+T^2)\tau},

with the positive constant CC depending on VV, qq, dd and the qq-th moment of ρ0\rho_0.

Proof. We rely on the Feynman–Kac representation of both the time-continuous solution and its time-discrete approximation; see (4) and [11]. Recall Yt=X0+σBtY_t = X_0 + \sigma B_t with X0∼ρX_0 \sim\rho and BB an independent Brownian motion. We have for any bounded test function ϕ\phi

ρt(ϕ)=E[ϕ(Yt)exp⁡(−∫0tV(Ys) ds)]E[exp⁡(−∫0tV(Ys) ds)],ρn(ϕ)=E[ϕ(Ynτ)exp⁡(−τ∑k=0n−1V(Ykτ))]E[exp⁡(−τ∑k=0n−1V(Ykτ))].\rho_t(\phi) = \frac{\mathbb{E}\left[\phi(Y_t)\exp\left(-\int_0^t V(Y_s)\,\mathrm{d}s\right)\right]}{\mathbb{E}\left[\exp\left(-\int_0^t V(Y_s)\,\mathrm{d}s\right)\right]}, \qquad\rho_n(\phi) = \frac{\mathbb{E}\left[\phi(Y_{n\tau})\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right]}{\mathbb{E}\left[\exp\left(-\tau\sum_{k=0}^{n-1}V(Y_{k\tau})\right)\right]}.

By integrating by parts on each time interval and applying Itô’s formula, we obtain

∫0tnV(Ys) ds−τ∑k=0n−1V(Ytk)=∑k=0n−1∫tktk+1(V(Ys)−V(Ytk)) ds=∑k=0n−1∫tktk+1(tk+1−s) d[V(Ys)]=σ∑k=0n−1∫tktk+1(tk+1−s)∇V(Ys)⋅dBs+σ22∑k=0n−1∫tktk+1(tk+1−s)ΔV(Ys) ds.\begin{aligned} \int_0^{t_n} V(Y_s)\,\mathrm{d}s-\tau\sum_{k=0}^{n-1}V(Y_{t_k}) &=\sum_{k=0}^{n-1}\int_{t_k}^{t_{k+1}}\left(V(Y_s)-V(Y_{t_k})\right)\,\mathrm{d}s\\ &=\sum_{k=0}^{n-1}\int_{t_k}^{t_{k+1}}(t_{k+1}-s)\,\mathrm{d}[V(Y_s)]\\ &=\sigma\sum_{k=0}^{n-1}\int_{t_k}^{t_{k+1}}(t_{k+1}-s)\nabla V(Y_s)\cdot\mathrm{d}B_s+\frac{\sigma^2}{2}\sum_{k=0}^{n-1}\int_{t_k}^{t_{k+1}}(t_{k+1}-s)\Delta V(Y_s)\,\mathrm{d}s. \end{aligned}

To estimate each term, we use the fact that both ∣∇V∣|\nabla V| and ∣ΔV∣|\Delta V| grow at most quadratically by Assumption 1.1. Since tk+1−s≤τt_{k+1}-s \le\tau for s∈[tk,tk+1]s \in[t_k,t_{k+1}], by using the Burkholder–Davis–Gundy inequality [22], we have

E∣σ∑k=0n−1∫tktk+1(tk+1−s)∇V(Ys)⋅dBs∣≤τσE∣∫0tn∇V(Ys)⋅dBs∣≤CτE(∫0t∣∇V(Ys)∣2)1/2≤CτtnE[1+sup⁡s≤tn∣Ys∣2]1/2≤Cτtn(1+M2(ρ0)+tn)\begin{aligned} \mathbb{E}\left|\sigma\sum_{k=0}^{n-1}\int_{t_k}^{t_{k+1}}(t_{k+1}-s)\nabla V(Y_s)\cdot\mathrm{d}B_s\right| &\le\tau\sigma\mathbb{E}\left|\int_0^{t_n}\nabla V(Y_s)\cdot\mathrm{d}B_s\right|\\ &\le C\tau\mathbb{E}\left(\int_0^t|\nabla V(Y_s)|^2\right)^{1/2}\\ &\le C\tau\sqrt{t_n}\mathbb{E}\left[1+\sup_{s\le t_n}|Y_s|^2\right]^{1/2}\\ &\le C\tau\sqrt{t_n}\left(1+M_2(\rho_0)+t_n\right) \end{aligned}

with constants CC that depend on σ\sigma and the growth assumptions on VV. Note that we had already derived bounds for the moments of YtY_t in the proof of Lemma Lemma 2.1. Similarly, we also have the bound

E∣σ22∑k=0n−1∫tktk+1(tk+1−s)ΔV(Ys) ds∣≤Cτ∫0tnE[1+∣Ys∣s] ds≤Cτ(tn(1+M2(ρ0))+tn2).\mathbb{E}\left|\frac{\sigma^2}{2}\sum_{k=0}^{n-1}\int_{t_k}^{t_{k+1}}(t_{k+1}-s)\Delta V(Y_s)\,\mathrm{d}s\right| \le C\tau\int_0^{t_n}\mathbb{E}\left[1+|Y_s|^s\right]\,\mathrm{d}s \le C\tau\left(t_n(1+M_2(\rho_0))+t_n^2\right).

Let us take now a test function from the dual formulation (3) of W1d\mathbb{W}_1^d, that is, ϕ\phi with ∥ϕ∥Lip≤1\|\phi\|_{\mathrm{Lip}}\le1 and osc⁡(ϕ)≤1\operatorname{osc}(\phi)\le1. We use a similar trick to that in Lemma Lemma 2.3 and assume, without loss of generality, that ∥ϕ−ρtn(ϕ)∥∞≤1\|\phi-\rho_{t_n}(\phi)\|_\infty\le1. By also applying the inequality ∣e−a−e−b∣≤∣a−b∣|e^{-a}-e^{-b}|\le|a-b| for positive a,ba,b we have

ρtn(ϕ)−ρn(ϕ)=E[(ϕ(Yt)−ρtn(ϕ))(e−τ∑k=0n−1V(Ytk)−e−∫0tnV(Ys) ds)]E[e−τ∑k=0n−1V(Ytk)]≤E∣∫0tnV(Ys) ds−τ∑k=0n−1V(Ytk)∣∏k=0N−1Zτ(ρn).\rho_{t_n}(\phi)-\rho_n(\phi)=\frac{\mathbb{E}\left[(\phi(Y_t)-\rho_{t_n}(\phi))\left(e^{-\tau\sum_{k=0}^{n-1}V(Y_{t_k})}-e^{-\int_0^{t_n}V(Y_s)\,\mathrm{d}s}\right)\right]}{\mathbb{E}\left[e^{-\tau\sum_{k=0}^{n-1}V(Y_{t_k})}\right]} \le\frac{\mathbb{E}\left|\int_0^{t_n}V(Y_s)\,\mathrm{d}s-\tau\sum_{k=0}^{n-1}V(Y_{t_k})\right|}{\prod_{k=0}^{N-1}Z_\tau(\rho_n)}.

Now, to bound the numerator, we use the computation we just performed, while to bound the denominator we use Lemma Lemma 2.1. Altogether, since tn≤Tt_n\le T, this leads to

ρtn(ϕ)−ρn(ϕ)≤C(1+T2)eC(1+T2)τ.\rho_{t_n}(\phi)-\rho_n(\phi)\le C(1+T^2)e^{C(1+T^2)}\tau.

The desired estimate is obtained by taking the supremum over ϕ\phi and using the dual formulation (3). □\square

Proof of Theorem 1.2

Proof of Theorem 1.2. Let us recall the different probability measures we have considered: ρnN\rho_n^N is the empirical probability measure generated with Algorithm 1, ρn\rho_n is the time-discrete update (1.2), while $\bar{\rho}_n^N$ is the empirical measure of the particles (3.3) which are i.i.d. with law ρn\rho_n. Finally, ρ(tn)\rho(t_n) is the solution to (1.1) at time tn=nτt_n=n\tau.

By the triangular inequality, we have

EW1d(ρnN,ρ(tn))≤EW1d(ρnN,ρˉnN)+W1d(ρˉnN,ρn)+W1d(ρn,ρ(tn)).\mathbb{E}\mathbb{W}_1^d(\rho_n^N,\rho(t_n))\le\mathbb{E}\mathbb{W}_1^d(\rho_n^N,\bar{\rho}_n^N)+\mathbb{W}_1^d(\bar{\rho}_n^N,\rho_n)+\mathbb{W}_1^d(\rho_n,\rho(t_n)).

By Proposition Proposition 3.2, the first term is of order (1+T2)e(1+T2)ε(N,d)(1+T^2)e^{(1+T^2)}\varepsilon(N,d). Since ρˉnN\bar{\rho}_n^N is made of i.i.d. particles, Fournier and Guillin, [17] holds, and so the second error is also of order (1+T2)e(1+T2)ε(N,d)(1+T^2)e^{(1+T^2)}\varepsilon(N,d) given Mq(ρn)1/q≲(1+T2)e(1+T2)M_q(\rho_n)^{1/q}\lesssim(1+T^2)e^{(1+T^2)} by Lemma Lemma 2.1. Finally, the last term is of order (1+T2)e(1+T2)τ(1+T^2)e^{(1+T^2)}\tau by Proposition Proposition 4.2. Altogether, the rate with respect to the number of particles and time discretization is O(ε(N,d)+τ)O(\varepsilon(N,d)+\tau). □\square

Aknowledgments

The author was supported by the Advanced Grant NEITALG of the European Research Council Executive Agency (ERC) (grant agreement No. 101198055), and by the Munich Center for Machine Learning (MCML)

Funded by the European Union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon Europe research and innovation programme (grant agreement No. 101198055, project acronym NEITALG).

References

  1. [1]Bickel, P., Li, B., and Bengtsson, T. (2008). Sharp failure rates for the bootstrap particle filter in high dimensions. In Publishing the limits of contemporary statistics: Contributions in honor of Jayanta K. Ghosh, volume 3, pages 318–330. Institute of Mathematical Statistics.DOI
  2. [3]Borghi, G. (2026). Chaos propagation in genetic algorithms: An optimal transport approach. Bulletin of the London Mathematical Society, 58(3):e70333.arxiv.org/abs/2601.14169
  3. [6]Candy, J. V. (2007). Bootstrap particle filtering. IEEE Signal Processing Magazine, 24(4):73–85.DOI
  4. [7]Chaintron, L.-P. and Diez, A. (2022). Propagation of chaos: A review of models, methods and applications. I. Models and methods. Kinetic and Related Models, 15(6):895–1015.DOI
  5. [8]Chopin, N., Singh, S. S., Soto, T., and Vihola, M. (2022). On resampling schemes for particle filters with weakly informative observations. The Annals of Statistics, 50(6):3197–3222.arxiv.org/abs/2203.10037
  6. [9]Cortez, R. and Fontbona, J. (2016). Quantitative propagation of chaos for generalized Kac particle systems. The Annals of Applied Probability, 26(2):892 – 916.DOI
  7. [10]Crisan, D. and Doucet, A. (2002). A survey of convergence results on particle filtering methods for practitioners. IEEE Transactions on Signal Processing, 50(3):736–746.
  8. [11]Del Moral, P. (2004). Feynman–Kac Formulae: Genealogical and Interacting Particle Systems with Applications. Probability and Its Applications. Springer, New York.DOI
  9. [12]Del Moral, P., Doucet, A., and Jasra, A. (2006). Sequential Monte Carlo samplers. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(3):411–436.
  10. [13]Del Moral, P. and Gerber, M. (2026). A perturbation theory for Feynman-Kac models and their particle interpretations. arXiv preprint arXiv:2610.21587.arxiv.org/abs/2610.21587
  11. [14]Del Moral, P., Jacob, P. E., Lee, A., Murray, L., and Peters, G. W. (2013). Feynman-Kac particle integration with geometric interacting jumps. Stochastic Analysis and Applications, 31(5):830–871.arxiv.org/abs/1211.7191
  12. [15]Del Moral, P. and Miclo, L. (2000). A Moran particle system approximation of Feynman–Kac formulae. Stochastic processes and their applications, 86(2):193–216.
  13. [16]Erny, X. (2022). Well-posedness and propagation of chaos for McKean–Vlasov equations with jumps and locally Lipschitz coefficients. Stochastic Processes and their Applications, 150:192–214.arxiv.org/abs/2102.06472
  14. [17]Fournier, N. and Guillin, A. (2015). On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3-4):707–738.arxiv.org/abs/1312.2128
  15. [18]Fournier, N. and Mischler, S. (2016). Rate of convergence of the Nanbu particle system for hard potentials and Maxwell molecules. The Annals of Probability, 44(1):589 – 627.DOI
  16. [19]Gerber, M. (2026). Safety of particle filters: Some results on the time evolution of particle filter estimates. Electronic Journal of Probability, 31:1–24.arxiv.org/abs/2503.21334
  17. [20]Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press.
  18. [21]Journel, L. and Monmarché, P. (2022). Convergence of a particle approximation for the quasi-stationary distribution of a diffusion process: Uniform estimates in a compact soft case. ESAIM: Probability and Statistics, 26:1–25.arxiv.org/abs/1910.05060
  19. [22]Kallenberg, O. (2021). Foundations of Modern Probability. Probability Theory and Stochastic Modelling. Springer International Publishing.
  20. [23]Perthame, B. (2007). Transport equations in biology. Springer.
  21. [24]Snyder, C., Bengtsson, T., Bickel, P., and Anderson, J. (2008). Obstacles to high-dimensional particle filtering. Monthly Weather Review, 136(12):4629–4640.DOI
  22. [25]Sprungk, B. (2020). On the local Lipschitz stability of Bayesian inverse problems. Inverse Problems, 36(5):055015.DOI
  23. [26]Tough, O. and Nolen, J. (2022). The Fleming-Viot process with McKean-Vlasov dynamics. Electronic Journal of Probability, 27:1–72.arxiv.org/abs/2011.11689
  24. [27]Van Handel, R. (2009). Uniform time average consistency of Monte Carlo particle filters. Stochastic Processes and their Applications, 119(11):3835–3861.DOI
  25. [28]Vergé, C., Dubarry, C., Del Moral, P., and Moulines, E. (2015). On parallel implementation of sequential Monte Carlo methods: the island particle model. Statistics and Computing, 25(2):243–260.
  26. [29]Villani, C. (2009). Optimal transport, volume 338 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin. Old and new.

Paper details

vlnc:W_tx37whsy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents