28th Conference on Stochastic Processes and their Applications, Melbourne July 2002.

FEYNMAN-KAC FORMULAE GENEALOGICAL AND INTERACTING PARTICLE MODELS

Applications:

non linear filtering, smoothing/path estimation, directed polymers, rare event anal-

ysis and spectral analysis of Feynman-Kac-Schrödinger semigroups.

Pierre DEL MORAL Lab. Stat. & Probab.-C.N.R.S Université Paul Sabatier, F-Toulouse. e-mail : delmoral@cict.fr

Particle Methods

• Mathematical physics:

particle microscopic interpretation

• Biology:

population or gene elovutions, genealogies of species

• Pure mathematics:

stochastic linearization technique

• Probability and Statistics:

approximating simulation technique (recursive rejections)

• Evolutionary mathematics and engineering sciences: adaptative stochastic search method,

⇓

Physical and biological intuitions ∈ Engineering problems

Feynman-Kac/Particle Interpretations

• Signal-Processing/Nonlinear filtering – Branching and interacting particle systems.

– Monte-Carlo optimal filters.

– Genetic algorithms.

– Bootstrap or particle filters.

– Sampling-Importance-Resampling.

– Condensation filters.

• Rare event analysis: Multi-splitting/Restart method.

• Physics and biology:

– Moran particle systems.

– Weighted genetic algorithm.

– Evolutionary particle models.

– Particle polymerizations.

• Numerical function optimization: – Genetic algorithms.

– Evolutionary random search algorithms.

Common features

• Objectives – Solve measure valued (non linear) equations.

– Simulation of (conditional) distributions.

– Global optimization of a numerical fitness function.

– Sampling a rare event/flexible polymer chain.

– Evolving a particle in an aborbing medium.

– ../...

• Particle Methods

– Random explorations of the state space ⟶ Markov evolution X

– Random selections of the proposal ⟶potential/likelihood/fitness V

Feynman-Kac or Boltzmann-Gibbs’ formula

Physics ⟷ Biology ⟷ Engineering

Discrete time

ℚ_{n} = \frac{1}{Z_{n}} exp \{− n ; ∑ ; p=0 V_{p}(X_{p})\} ℙ_{n} = \frac{1}{Z_{n}} \{ n ; ∏ ; p=0 G_{p}(X_{p}) \} ℙ_{n}

Continuous time

dℚ_{t} = \frac{1}{Z_{t}} exp \{− ∫_{0}^{t} V_{s}(X_{s}) ds\} dℙ_{t}

Traditional Monte-Carlo

ℚ_{n}^{N} = N ; ∑ ; i=1 \frac{e^{− ∑_{p=0}^{n} V_{p}(X_{p}^{i})}}{∑_{j=1}^{N} e^{− ∑_{q=0}^{n} V_{q}(X_{q}^{j})}} δ_{(X_{0}^{i},,...,X_{n}^{i})} ⇒ Degenerate weighted-grids

⇓

Interacting particle systems

∈ {Adaptative stochastic grids, Simulation technique }

ℚ_{n}^{N} = \frac{1}{N} N ; ∑ ; i=1 δ_{(ξ_{0,n}^{i},,...,ξ_{n,n}^{i})} ⟶ genealogical particle tree

Feynman-Kac distribution flow models

Potential function Gn : En → [0, 1]

Markov chain X_{n} ∈ E_{n}, transitions M_{n}(x_{n−1}, dx_{n})

η_{n}(f) = γ_{n}(f)/γ_{n}(1) with γ_{n}(f) = 𝔼(f(X_{n}) n−1 ; ∏ ; p=0 G_{p}(X_{p}))

Ex.

G_{n}(x_{n}) = 1_{A_{n}}(x_{n}) → \{ \begin{matrix}γ_{n+1} (1) & = & ℙ(X_{0} ∈ A_{0}, …, X_{n} ∈ A_{n}) \\ η_{n+1} (f) & = & 𝔼(f(X_{n+1} ) | X_{0} ∈ A_{0}, …, X_{n} ∈ A_{n}) \end{matrix}

Important Formula γ_{n}(f) = η_{n}(f) n−1 ; ∏ ; p=0 η_{p}(G_{p})

Non linear measure valued process

η_{n+1} = Φ_{n+1} (η_{n})

One step transf.

Φ_{n+1} : η ∈ P(E_{n}) ⟶ \begin{aligned}Φ_{n+1} (η) & = & Ψ_{n}(η)M_{n+1} \\ & = & ∫_{E_{n}} Ψ_{n}(η)(dx_{n})M_{n+1} (x_{n},.) ∈ P(E_{n}) \end{aligned}

Boltzmann-Gibbs’ transf.

Ψ_{n}(η)(dx) = \frac{1}{η(G_{n})} G_{n}(x) η(dx)

Markov interpretation

Ψ_{n}(η_{n}) = η_{n}S_{n,η_{n}} = ∫_{E_{n}} η_{n}(dx_{n})S_{n,η_{n}}(x_{n},.)

with Markov kernel

S_{n,η_{n}}(x_{n}, dy_{n}) = G_{n}(x_{n}) δ_{x_{n}}(dy_{n}) + (1 − G_{n}(x_{n})) Ψ_{n}(η_{n})(dy_{n})

⇓

η_{n+1} = η_{n}K_{n+1,η_{n}} with K_{n+1,η} = S_{n,η}M_{n+1}

ηn = 𝕂 − Law (Xn) ⟶ 𝕂 McKean measure(canonical space)

𝕂_{n}(d(x_{0}, …, x_{n})) = η_{0}(dx_{0}) K_{1,η_{0}} (x_{0}, dx_{1}) … K_{n,η_{n−1}}(x_{n−1}, dx_{n})

Particle interpretation

η_{n+1} = Φ_{n+1} (η_{n}) = η_{n}K_{n+1,η_{n}}

↓

Objective ξn = (ξ1 n, …, ξN n) ∈ EN n Markov s.t. limN→∞ \frac{1}{N} ∑{N \atop i=1} δξin = ηn

Idea/Rationale

m(ξ_{n}) = \frac{1}{N} N ; ∑ ; i=1 δ_{ξ_{n}^{i}} ≃ η_{n} ⟹ Φ_{n+1} (m(ξ_{n})) ≃ Φ_{n+1} (η_{n}) = η_{n+1}

-Φn⇒ conditional iid particles

ξ_{n} = (ξ_{n}^{1}, …, ξ_{n}^{N}) iid ∼ Φ_{n}(m(ξ_{n−1}))

-Kn,η⇒ conditional indp particles

ξ_{n}^{j} ∼ K_{n,m(ξ_{n−1})}(ξ_{n−1}^{j}, dy)

Genetic particle models

1) (ξ_{n+1}^{1} , …, ξ_{n+1}^{N} ) iid ∼ \begin{aligned}Φ_{n+1} (m(ξ_{n})) & = & Ψ_{n}(m(ξ_{n}))M_{n+1} \\ & = & N ; ∑ ; i=1 \frac{G_{n}(ξ_{n}^{i})}{∑_{j=1}^{N} G_{n}(ξ_{n}^{j})} M_{n+1} (ξ_{n}^{i},.) \end{aligned}

⇓

ξ_{n} ∈ E_{n}^{N} ⟶^{selection} ξ̂_{n} ∈ E_{n}^{N} ⟶^{mutation} ξ_{n+1} ∈ E_{n+1}^{N}

-selection

ξ̂_{n} = (ξ̂_{n}^{1}, …, ξ̂_{n}^{N}) iid Ψ_{n}(m(ξ_{n}))

-mutation

ξ̂_{n}^{i} ⟶ ξ_{n+1}^{i} ∼ M_{n+1} (ξ̂_{n}^{i},.)

2) ξ_{n+1}^{i} ∼ K_{n+1,m(ξ_{n})} (ξ_{n}^{i},.) = S_{n,m(ξ_{n})}M_{n+1} (ξ_{n}^{i},.)

⇓

ξ_{n} ∈ E_{n}^{N} ⟶^{selection} ξ̂_{n} ∈ E_{n}^{N} ⟶^{mutation} ξ_{n+1} ∈ E_{n+1}^{N}

-selection = cond. indpt. ξin ⟶ ξ̂_{n}^{i}

∼ S_{n,m(ξ_{n})}(ξ_{n}^{i}, dy) = G_{n}(ξ_{n}^{i}) δ_{ξ_{n}^{i}}(dy) + (1 − G_{n}(ξ_{n}^{i})) Ψ_{n}(m(ξ_{n}))(dy)

-mutation [idem]

ξ̂_{n}^{i} ⟶ ξ_{n+1}^{i} ∼ M_{n+1} (ξ̂_{n}^{i},.)

Ex.: Gn = 1A_{n}⟶ particle rejection technique

S_{n,m(x)}(x^{i},.) = 1_{A_{n}}(x^{i}) δ_{x^{i}} + (1 − 1_{A_{n}}(x^{i})) Ψ_{n}(m(x))

A_{n}(x) = {i ; x^{i} ∈ A_{n}}

Ψ_{n}(m(x)) = \frac{1}{|A_{n}(x)|} _{i∈A_{n}(x)}^{∑} δ_{x^{i}}

Stopping time

τ^{N} = inf {n ≥ 0 ; η_{n}^{N}(G_{n}) = 0}

ℙ(τ^{N} ≤ n) ≤ c(n) exp (−N (γ_{n}^{2}(1)/(8n))^{2})

Genealogical trees and historical models

Selection = birth-death ⟶ ancestral lines

Feynman-Kac flow (G_{n}, M_{n}) ⟷ Genetic (selection/mutation) (G_{n}, M_{n})

Historical model

X_{n} = (X′_{0}, …, X_{n}) ∈ E_{n} = E′_{0} × … × E′_{n}
X′_{n} ∈ E′_{n} , ∼ M′_{n}(X_{n−1},.)
⇓

Path particles

\{ \begin{matrix}ξ_{n}^{i} & = & (ξ_{0,n}^{′i}, …, ξ_{n,n}^{′i}) ∈ E_{n} = E′_{0} × ⋯ × E′_{n} \\ ξ̂_{n}^{i} & = & (ξ̂_{0,n}^{′i}, …, ξ̂_{n,n}^{′i}) ∈ E_{n} = E′_{0} × ⋯ × E′_{n} \end{matrix}

Genetic-path model

path-selection

N ; ∑ ; i=1 \frac{G_{n}(ξ_{0,n}^{′i}, …, ξ_{n,n}^{′i})}{∑_{j=1}^{N} G_{n}(ξ_{0,n}^{′i}, …, ξ_{n,n}^{′i})} δ_{(ξ_{0,n}^{′i},...,ξ_{n,n}^{′i})}

path-mutation

ξ_{n+1}^{i} = (\underbrace{[ξ̂_{0,n}^{′i}, . . . . . . , ξ̂_{n,n}^{′i}]}_{selected−path}, \underbrace{ξ_{n+1,n+1}^{′i}}_{\begin{matrix}path − extension \\ ∼ M′_{n+1} (ξ̂_{n}^{i},.) \end{matrix}} )

Genealogies

-Historical model, X ′n Markov

X_{n} = (X′_{0}, …, X_{n}) ∈ E_{n} = E′_{0} × … × E′_{n}
X′_{n} ∈ E′_{n} , ∼ M′_{n}(X′_{n−1},.)

-”marginal potentials” Gn(x′0, …, x′n) = G′n(x′n)

Genealogical particle tree model

path-selection

N ; ∑ ; i=1 \frac{G′_{n}(ξ_{n,n}^{′i})}{∑_{j=1}^{N} G′_{n}(ξ_{n,n}^{′i})} δ_{(ξ_{0,n}^{′i},...,ξ_{n,n}^{′i})}

path-mutation

ξ_{n+1}^{i} = (\underbrace{[ξ̂_{0,n}^{′i}, . . . . . . , ξ̂_{n,n}^{′i}]}_{selected−path}, \underbrace{ξ_{n+1,n+1}^{′i}}_{\begin{matrix}path − extension \\ ∼ M′_{n+1} (ξ̂_{n,n}^{i},.) \end{matrix}} )

Marginal genetic model

ξ′_{n} ⟶^{G′_{n}} ξ̂′_{n} ⟶^{M′_{n+1}} ξ′_{n+1}

Historical process and genealogical Markov model

ξ_{n} ⟶^{G_{n}} ξ̂_{n} ⟶^{M_{n+1}} ξ_{n+1}

Particle approximating measures

Limiting Feynman-Kac path measures

-path-measures

η_{n}(f_{n}) = γ_{n}(f_{n})/γ_{n}(1)
γ_{n}(f_{n}) = 𝔼(f_{n}(X′_{0}, …, X′_{n}) n−1 ; ∏ ; p=0 G′_{p}(X′_{p}))

-n-time marginals

η′_{n}(f′_{n}) = γ′_{n}(f′_{n})/γ′_{n}(1)
γ′_{n}(f′_{n}) = 𝔼(f′_{n}(X′_{n}) n−1 ; ∏ ; p=0 G′_{p}(X′_{p}))

Particle measures -path-measures

η_{n}^{N} = \frac{1}{N} N ; ∑ ; i=1 δ_{ξ_{n}^{i}} = \frac{1}{N} N ; ∑ ; i=1 δ_{(ξ_{0,n}^{′i},...,ξ_{n,n}^{′i})}
γ_{n}^{N}(f_{n}) = [n−1 ; ∏ ; p=0 η_{p}^{N}(G_{p})] × η_{n}^{N}(f_{n})

-n-time marginals ξ_{n}^{′i} = ξ_{n,n}^{′i}

η_{n}^{′N} = \frac{1}{N} N ; ∑ ; i=1 δ_{ξ_{n}^{′i}}
γ_{n}^{′N}(f′_{n}) = [n−1 ; ∏ ; p=0 η_{p}^{N}(G_{p})] × η_{n}^{′N}(f′_{n})

Particle approx. measures (continued)

McKean measures

𝕂_{n}(d(x_{0}, …, x_{n})) = η_{0}(dx_{0}) K_{1,η_{0}} (x_{0}, dx_{1}) … K_{n,η_{n−1}}(x_{n−1}, dx_{n})

Particle McKean measures

𝕂_{n}^{N} = \frac{1}{N} N ; ∑ ; i=1 δ_{(ξ_{0}^{i},...,ξ_{n}^{i})}

Ex.: Φ_{n}⇒ conditional iid particles

(ξ_{n}^{1}, …, ξ_{n}^{N}) iid Φ_{n}(m(ξ_{n−1})) ⇒ lim_{N→∞} 𝕂_{n}^{N} = 𝕂_{n} = η_{0} ⊗ … ⊗ η_{n}

K_{n,η}⇒ conditional indp particles

ξ_{n+1}^{i} ∼ S_{n,m(ξ_{n})}M_{n+1} (ξ_{n}^{i},.) ⇒ lim_{N→∞} 𝕂_{n}^{N} = 𝕂_{n} ≠ η_{0} ⊗ … ⊗ η_{n}

Some asympt. results (mild assumpt.)

𝕃p-unif. estimates (↪(CLT))

𝔼(sup_{f∈F} |η_{n}^{N}(f) − η_{n}(f)|^{p} )^{1/p} ≤ I(F)/√N

Φn-exp. asympt. stable

∃α ∈ (0, 1] : sup_{n≥0} 𝔼(sup_{f∈F} |η_{n}^{N}(f) − η_{n}(f)|^{p} )^{1/p} ≤ I(F)/N^{α/2}

M_{n} mixing ⟹ α = 1

Exp. estimates (↪(LDP))

ℙ(sup_{f∈F} |η_{n}^{N}(f) − η_{n}(f)| ≥ ϵ) ≤ c(n) N (ϵ, F) e^{−Nϵ^{2}/c(n)}

↑ prop. chaos

ℙ_{n}^{(q,N)} = Law ((ξ_{0}^{i}, …, ξ_{n}^{i})_{1≤i≤q}) and ℙ_{[n]}^{(q,N)} = Law ((ξ_{n}^{i})_{1≤i≤q})

⇓

∥ℙ_{[n]}^{(N,q)} − η_{n}^{⊗q}∥_{tv} ≤ \frac{exp (q c(n))}{N} and Ent (ℙ_{n}^{(N,q)} | 𝕂_{n}^{⊗q}) ≤ c \frac{q n}{N}

Applications

• Statistics – Sampling Boltzmann-Gibbs conditional distributions – Particle rejection technique

• Signal processing – Non linear filtering

– Smoothing and path estimation

– Interacting Kalman-Bucy filters

• Rare event analysis – Multilevel Feynman-Kac models

– Genealogical tree based algorithms • Directed polymers simulation

– Directed polymers models

– Particle polymerizations

– Self-avoiding and reinforced Markov motions

• Spectral analysis of FKS semigroups – Lyapunov exponents and spectral radii

– Particle exponents

Applications

-Conditional distributions

X_{n} = (X_{0}, …, X_{n}) and G_{n}(x_{0}, …, x_{n}) = 1_{A_{n}}(x_{n})

⇒ η_{n} = Law (X_{0}, …, X_{n}|X_{0} ∈ A_{0}, …, X_{n} ∈ A_{n})

⟹Particle rejection technique -Markov motion in absorbing medium Gn(x) = e−V (x) ∈ [0, 1], E ∪ {c}

X_{n} ⟶^{killing} X̂_{n} ⟶^{exploration} X_{n+1}

killing transition

G_{n}^{c}(x, dy) = G_{n}(x) δ_{x}(dy) + (1 − G_{n}(x)) δ_{c}(dy)

Note:

A_{n} = {x : G_{n}(x) = 0} ⟶ hard obstacles

T = inf {n ≥ 0 ; X̂_{n} = c} ⇒ η_{n} = Law (X_{0}, …, X_{n}|T ≥ n)

⟹Genealogical particle strategies -Filtering (X, Y) Markov, sensor/obs. Yn = Hn((X0, …, Xn), Vn)

↓

ℙ(H_{n}((x_{0}, …, x_{n}), V_{n}) ∈ dy_{n}) = \underbrace{g_{n}(y_{n}, (x_{0}, …, x_{n}))}_{=G_{n}(x_{0},...,x_{n})} q_{n}(dy_{n})

filtering/path estimation/smoothing

η_{n} = Law (X_{0}, …, X_{n}|Y_{0}, …, Y_{n−1})

⟹Adaptative stochastic grid -Polymers/Non intersecting Markov chains

X_{n} = (X_{0}, …, X_{n}) and G_{n}(x_{0}, …, x_{n}) = 1_{E−{x_{0},...,x_{n−1}}}(x_{n})

⇓
ℚ_{n} = Law (X_{0}, …, X_{n}|∀p < q < n X_{p} ≠ X_{q})

-Rare events

rare target level B = B_{m+1} ⊂ B_{m} ⊂ … ⊂ B_{1} ⊂ B_{0} (initial level )

n-th excursion or ”return to B_{0}” X_{n} = (X_{t} , T_{n−1} ≤ t ≤ T_{n})
G_{n}(X_{n}) = 1_{B_{n}}(X_{T_{n}})

η_{n} = Law ([X_{0}, (X_{t} , T_{0} ≤ t ≤ T_{1}), …, (X_{t} , T_{n−1} ≤ t ≤ T_{n})] | T_{n} < Return time )

-Spectral analysis FK-Schrödinger semigroups

Λ(V) = log Lyap (e^{V} × M) = log Spr (e^{V} × M)
= lim_{n→∞} \frac{1}{n} log 𝔼(exp n−1 ; ∑ ; p=0 V (X_{p}))

= lim_{n→∞} \frac{1}{n} n−1 ; ∑ ; p=0 log η_{p}[exp (V)] = η_{∞}[exp (V)]
⇓
Λ(V) ∼ Λ_{n}^{N}(V) = \frac{1}{n} n−1 ; ∑ ; p=0 log η_{p}^{N}[exp (V)]

continuous time: Schrödinger op. Lv = L + V ⟶ top Lyap. expo

Λ(V) ∼ Λ_{t}^{N}(V) = \frac{1}{t} ∫_{0}^{t} η_{s}^{N}(V) ds