Montreal University, Nov. 2002

A new class of genealogical and interacting Metropolis particle models

Pierre DEL MORAL LSP-C.N.R.S, Univ. Paul Sabatier, F-Toulouse.

↪ On a Class of Genealogical and Interacting Metropolis Models join work with Arnaud Doucet, Séminaire de Probabilités 37, Lecture Notes in Mathematics, Springer (2003)

Notations (S, S) measurable space

P(S) = {μ probability on S }
B_{b}(S) = {f : S → ℝ bounded + S-measurable }

• (μ, f) ∈ P(S) × B_{b}(S) ⟶ μ(f) = ∫ f(y)μ(dy)

• M(y, dy′) Markov kernel on S

μM(dy′) = ∫ μ(dy)M(y, dy′) and M(f)(y) = ∫ M(y, dy′)f(y′)

• Probability measures on E = S × S

(μ × M)_{1}(d(y, y′)) = μ(dy)M(y, dy′) or (μ × M) = (μ × M)_{1}
(μ × M)_{2}(d(y, y′)) = μ(dy′)M(y′, dy)

• a ∧ b = min {a, b}, a^{+} = max {a, 0}.

Monte-Carlo Markov chain Methods Target π ∈ P(S) → Ex.: Gibbs’ π(dy) = \frac{1}{ν(e^{−V})} e^{−V (y)} ν(dy) ∃? M_{π}(y, dy′) Markov ⊕ mixing s.t. π = πM_{π} MCMC algo.→ ℙ(Y_{n} ∈ dy | Y_{n−1}) = M_{π}(Y_{n−1}, dy)

⇓

Linear recursive eq.  Law (Y_{n}) = μ_{n}
= μ_{n−1}M_{π} ⟶ π

Metropolis-Hasting ⟶ K, L Markov on S s.t. (π × L)_{2} ≪ (π × K)_{1} and

G = \frac{d(π × L)_{2}}{d(π × K)_{1}} > 0 + bounded

Ex.: Gibbs’

G(y, y′) = e^{−(V (y′)−V (y))} × \frac{d(ν × L)_{2}}{d(ν × K)_{1}} (y, y′)
( = e^{−(V (y′)−V (y))} if K = L ν − reversible. )

Y_{n} ⟶^{K} Y′_{n} −⇀^{accept/reject} Y_{n+1} = \{ \begin{matrix}Y′_{n} & probab & (1 ∧ G)(Y_{n}, Y′_{n}) \\ Y_{n} & probab & 1 − (1 ∧ G)(Y_{n}, Y′_{n}) \end{matrix}

• K = L ⟹ π = πM_{π}

• Ex.: Gibbs’ ⟹ “simulated annealing” (1 ∧ G)(Y_{n}, Y′_{n}) = e^{−(V (Y′_{n})−V (Y_{n}))^{+}} Ex.Gibbs’: S =3 points ν = (1, 3, 1)/5, V = (0, h, 0) and K = L ν-reversible

β(M_{π}^{n}) = sup_{y,y′} ∥M_{π}^{n})(y,.) − M_{π}^{n})(y′,.)∥_{tv} = (1 − e^{−h})^{n}
≥ β(K^{n+1} ) = (2/3)^{n}

Non linear approach

μ_{n+1} = μ_{n}M_{π} ↪ ∃?(𝕂_{μ})_{μ∈P(S)} s.t. μ_{n+1} = μ_{n}𝕂_{μ_{n}} ⟶ π

• Better stability properties.

• Biological + physical intuitions ↪ Engineering, statistical problems • Branching and interacting particle models.

Idea ∼ Non linear Feynman-Kac type simulated annealing ↪ Annealed Feynman-Kac Models, join work with Laurent Miclo, Communications in Mathematical Physics (2003)

Feynman-Kac-Metropolis: transitions space E = (S × S) Metropolis-Hastings algo.

(Y_{n}, Y′_{n}) ⟶^{𝕊} (Ŷ_{n}, Ŷ′_{n}) ⟶^{𝕄^{K}} (Y_{n+1} , Y′_{n+1} )

with 𝕄^{K}((y, y′), d(z, z′)) = δ_{y′}(dz) K(z, dz′) and

𝕊((y, y′),.) = (1 ∧ G(y, y′)) δ_{(y,y′)} + (1 − (1 ∧ G(y, y′))) δ_{(y,y)}

Feynman-Kac-Metropolis algo. η_{n} = Law (Y_{n}, Y′_{n}), ∀ϵ ≥ 0 : ϵG ≤ 1

𝕊 ⇝ 𝕊_{η_{n}}((y, y′),.) = ϵG(y, y′) δ_{(y,y′)} + (1 − ϵG(y, y′)) \frac{1}{η_{n}(G)} G dη_{n}

F-K-M semi-group

η_{n+1} = η_{n}(𝕊_{η_{n}}𝕄^{K}) = Φ^{n+1} (η_{0}) ∈ P(E)

Th.1

• (X_{n} Markov 𝕄^{K})

η_{n}(f) = γ_{n}(f)/γ_{n}(1) with γ_{n}(f) = 𝔼_{η_{0}}^{K}(f(X_{n}) ∏_{p=0}^{n−1} G(X_{p}))

• If L^{m}(y,.) ≤ l_{m} L^{m}(y′,.), for some m ≥ 1 then (π × K) = Φ(π × K) unique

and

sup_{μ_{1},μ_{2}} ∥ϕ^{m+n+1} (μ_{1}) − ϕ^{m+n+1} (μ_{2})∥_{tv} ≤ sup_{v} ∫ π(du) |\frac{dL^{m+n} (u,.)}{dπL^{m+n}} (v) − 1|
≤ 2l_{m} β(L^{n})
↑  independent of π !!

Non linear m.v.p. ⟶ Interacting particle syst. (IPS) Non linear equation η_{n+1} = η_{n}𝕂_{η_{n}}

⇓ N-(IPS)=Markov ξ_{n} = (ξ_{n}^{1}, …, ξ_{n}^{N}) ∈ E^{N} s.t.

η_{n}^{N} = m(ξ_{n}) = \frac{1}{N} ∑_{i=1}^{N}δ_{ξ_{n}^{i}} ⟶ η_{n} (as N → ∞)

Elementary transitions, for all 1 ≤ i ≤ N

ξ_{n}^{i} ⟶ ξ_{n+1}^{i} ∼ 𝕂_{m(ξ_{n})}(ξ_{n}^{i},.)

Note:

𝕂_{m(ξ_{n})} = 𝕊_{m(ξ_{n})}𝕄^{K} (not unique ) ⟹ 2 steps transitions

Genetic IPS (𝕂_{η} = 𝕊_{η}𝕄^{K}, η_{0} = (μ_{0} × K))

ξ_{n}^{i} = (Y_{n}^{i}, Y_{n}^{′i}) \underrightarrow{selection} ξ̂_{n}^{i} = (Ŷ_{n}^{i}, Ŷ_{n}^{′i}) \underrightarrow{mutation} ξ_{n+1}^{i} = (Y_{n+1}^{i} , Y_{n+1}^{′i} )

• Selection ξ_{n}^{i} ⟶^{𝕊_{m(ξn)}} ξ̂_{n}^{i}

𝕊_{m(ξ_{n})}(ξ_{n}^{i},.) = ϵG(ξ_{n}^{i}) δ_{ξ_{n}^{i}} + (1 − ϵG(ξ_{n}^{i})) ∑_{j=1}^{N} \frac{G(ξ_{n}^{j})}{∑_{k=1}^{N} G(ξ_{n}^{k})} δ_{ξ_{n}^{j}}

• Mutation ξ̂_{n}^{i} ⟶^{𝕄^{K}} ξ_{n+1}^{i}

(Y_{n+1}^{i} , Y_{n+1}^{′i} ) = (Ŷ_{n}^{′i}, Y_{n+1}^{′i} ) with Y_{n+1}^{′i} ∼ K(Ŷ_{n}^{′i},.)

Note: (branching selection variants: Bernoulli, Baker, Poisson, …)

11

Th.2 (hyp.th1 ⇒ ∃!ν_{L} = ν_{L}L) If for any x, x′ ∈ E = (S × S), y, y′ ∈ S

G(x) ≤ gG(x′) and \frac{dν_{L}}{dπ}(y) ≤ k_{π} \frac{dν_{L}}{dπ}(y′)

Then

𝔼 (|η_{n+m+1}^{N} (f) − (π × K)(f)|^{p}) ^{1/p} ≤ c_{p} \frac{a_{π,L}}{√N} + b_{L} β(L^{n})

with a_{π,L} ≤ a.(g ∨ k_{π})^{2(m∨1)} Crude comparison [Metropolis iid and ips] Ex.Gibbs’: → K = L ν − reversible, m = 1, ϵ = 1/l_{m}, h = osc (V)

Th2’s 𝕃_{p}-estimates:

e_{iid}(n, N) = \frac{1}{√N} + (1 − ϵ e^{−h})^{n} and e_{ips}(n, N) = \frac{e^{2h}}{√N} + (1 − ϵ)^{n}

If \frac{1}{√N} = (1 − ϵ)^{n} then

√N e_{iid}(n, N) = 1 + (1 + \frac{ϵ}{1 − ϵ} (1 − e^{−h})) ^{n} ≥ 1 + e^{2h} = √N e_{ips}(n, N)

Genealogical tree model (ex.:ϵ = 0)

• mutations ξ̂_{n}^{i} ⟶^{𝕄^{K}} ξ_{n+1}^{i}

• ξ̂_{n} = (ξ̂_{n}^{1}, …, ξ̂_{n}^{N}) iid Ψ(m(ξ_{n}))  =  ∑_{j=1}^{N} \frac{G(ξ_{n}^{j})}{∑_{k=1}^{N} G(ξ_{n}^{k})} δ_{ξ_{n}^{j}} =^{Gibbs′⊕rev.} ∑_{j=1}^{N} \begin{matrix}exp & (V (Y_{n}^{j})−V (Y_{n}^{′j})) \\ ∑ & {N \atop k=1} & exp & (V (Y_{n}^{k})−V (Y_{n}^{′k})) \end{matrix} δ_{(Y_{n}^{i},Y_{n}^{′i})}
⇓

birth/death process ⟹ ancestral lines ⟹ Genealogical tree algo.

ξ_{0,n}^{i} ⟵ ξ_{1,n}^{i} ⟵ … ⟵ ξ_{n−1,n}^{i} ⟵ ξ_{n,n}^{i} = ξ_{n}^{i}

15

Genealogical tree model=(path-space ips)

X_{n} → X_{n} = (X_{0}, …, X_{n})

Th [Miclo & DM,Annals Applied Proba 2001]

ℚ_{n}^{N}(F_{n}) = \frac{1}{N} ∑_{i=1}^{N}F_{n}(ξ_{0,n}^{i}, …, ξ_{n,n}^{i}) ⟶ ℚ_{n}(F_{n}) = \frac{𝔼_{η_{0}}^{K}(F_{n}(X_{0}, …, X_{n}) ∏_{p=0}^{n−1} G(X_{p}))}{𝔼_{η_{0}}^{K}(∏_{p=0}^{n−1} G(X_{p}))}

• 𝕃_{p}, increasing propagations of chaos, fluctuations,...

• Applications: physics trapping analysis, directed polymer simulations, smoothing/filtering, rare event estimation,...

Time inversion formula ↪ Metropolis ratio G = d(π × L)_{2}/d(π × K)_{1}

𝔼_{π}^{L}(φ_{n}(Y_{n}, Y_{n−1}, …, Y_{0})) = 𝔼_{π}^{K}(φ_{n}(Y_{0}, Y_{1}, …, Y_{n}) ∏_{p=0}^{n−1} G(Y_{p}, Y_{p+1} )).

Th.3 [Feynman-Kac representation]

𝔼_{π}^{L}(φ_{n}(Y_{n}, Y_{n−1} …, Y_{0}) | Y_{n} = y) = \frac{𝔼_{y}^{K}(φ_{n}(Y_{0}, …, Y_{n}) ∏_{p=0}^{n−1} G(Y_{p}, Y_{p+1} ))}{𝔼_{y}^{K}(∏_{p=0}^{n−1} G(Y_{p}, Y_{p+1} ))}

Notes :

• Y_{n} ∈ S Markov ∼ K(y, dy′) ⟹ X_{n} = (Y_{n}, Y_{n+1} ) ∈ E Markov ∼ 𝕄^{K}(x, dx′)

• “Time inversion ⇒ π at infinity”

ℚ_{n}(Y_{n} ∈.) = ℙ_{π}^{L}(Y_{0} ∈. | Y_{n} = y) ⟶ π Th.3 [Feynman-Kac N-path particle approx.]

√N 𝔼_{y}(|\frac{1}{N} ∑_{i=1}^{N}φ_{n}(Y_{0,n}^{i}, …, Y_{n,n}^{i}) − 𝔼_{π}^{L}(φ_{n}(Y_{n}, Y_{n−1} …, Y_{0}) | Y_{n} = y)|^{p})^{1/p} = O(n)

Open questions • Branching variants + precise comparisons + applications.

• Continuous time inversion formulae (?).

• Fluctuations, LDP,... when (n, N) ⟶ ∞.

• Annealed models ∼ simulated annealing (gobal optimization).

• ∃? other classes of non linear “Metropolis” models