arXiv:1605.08534v1 [] 27 May 2016

On the two-filter approximations of marginal smoothing
distributions in general state space models
Thi Ngoc Minh Nguyen∗

Sylvain Le Corff†

Eric Moulines‡

Abstract
A prevalent problem in general state space models is the approximation of the
smoothing distribution of a state conditional on the observations from the past, the
present, and the future. The aim of this paper is to provide a rigorous analysis of
such approximations of smoothed distributions provided by the two-filter algorithms.
We extend the results available for the approximation of smoothing distributions to
these two-filter approaches which combine a forward filter approximating the filtering
distributions with a backward information filter approximating a quantity proportional
to the posterior distribution of the state given future observations.

1

Introduction

State-space models play a key role in a large variety of disciplines such as engineering,
econometrics, computational biology or signal processing, see [9, 8] and references therein.
This paper provides a nonasymptotic analysis of a Sequential Monte Carlo Method (SMC)
which aims at performing optimal smoothing in nonlinear and non Gaussian state space
models. Given two measurable spaces (X, X ) and (Y, Y), consider a bivariate stochastic
process {(Xt , Yt )}t≥0 taking values in the product space (X × Y, X ⊗ Y), where the hidden
state sequence {Xt }t≥0 is observed only through the observation process {Yt }t≥0 . Statistical inference in general state space models usually involves the computation of conditional
distributions of some unobserved states given a set of observations. These posterior distributions are crucial to compute smoothed expectations of additive functionals which appear
naturally for maximum likelihood parameter inference in hidden Markov models (computation of the Fisher score or of the intermediate quantity of the Expectation Maximization
algorithm), see [3, Chapter 10 and 11], [17, 25, 20, 21].
Nevertheless, exact computation of the filtering and smoothing distributions is possible
only for linear and Gaussian state spaces or when the state space X is finite. This paper
focuses on particular instances of Sequential Monte Carlo methods which approximate sequences of distributions in a general state space X with random samples, named particles,
associated with nonnegative importance weights. Those particle filters and smoothers rely
on the combination of sequential importance sampling steps to propagate particles in the
state space and importance resampling steps to duplicate or discard particles according to
their importance weights. The first implementation of these SMC methods, introduced in
∗ LTCI,

CNRS and Télécom ParisTech.
de Mathématiques d’Orsay, Univ. Paris-Sud, CNRS, Université Paris-Saclay.
‡ Centre de Mathématiques Appliquées, Ecole Polytechnique.

† Laboratoire

1

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

[14, 18], propagates the particles using the Markov kernel of the hidden process {Xt }t≥0
and uses a multinomial resampling step based on the importance weights to select particles
at each time step. An interesting feature of this Poor man’s smoother is that it provides
an approximation of the joint smoothing distribution by storing the ancestral line of each
particle with a complexity growing only linearly with the number N of particles, see for instance [4]. However, this smoothing algorithm has a major shortcoming since the successive
resampling steps induce an important depletion of the particle trajectories. This degeneracy
of the particle sequences leads to trajectories sharing a common ancestor path; see [25, 16]
for a discussion.
Approximations of the smoothing distributions may also be obtained using the forward
filtering backward smoothing decomposition in general state space models. The Forward
Filtering Backward Smoothing algorithm (FFBS) and the Forward Filtering Backward Simulation algorithm (FFBSi) developed respectively in [18, 15, 10] and [13] avoid the path
degeneracy issue of the Poor man’s smoother at the cost of a computational complexity
growing with N 2 . Both algorithms rely on a forward pass which produces a set of particles
and weights approximating the sequence of filtering distributions up to time T . Then, the
backward pass of the FFBS algorithm modifies all the weights computed in the forward pass
according to the so-called backward decomposition of the smoothing distribution keeping
all the particles fixed. On the other hand, the FFBSi algorithm samples independently
particle trajectories among all the possible paths produced by the forward pass. It is shown
in [22, 2, 5] that the FFBS algorithm can be implemented using only a forward pass when
approximating smoothed expectations of additive functionals but with a complexity still
growing quadratically with N . Under the mild assumption that the transition density of the
hidden chain {Xt }t≥0 is uniformly bounded above, [6] proposed an accept-reject mechanism
to implement the FFBSi algorithm with a complexity growing only linearly with N . Concentration inequalities, controls of the Lq -norm of the deviation between smoothed functionals
and their approximations and Central Limit Theorems (CLT) for the FFBS and the FFBSi
algorithms have been established in [5, 6, 11].
Recently, [23] proposed a new SMC algorithm, the particle-based rapid incremental
smoother (PaRIS), to approximate online, using only a forward pass, smoothed expectations of additive functionals. The crucial feature of this algorithm is that its complexity
grows only linearly with N as it samples on-the-fly particles distributed according to the
backward dynamics of the hidden chain conditionally on the observations Y0 , . . . , YT . The
authors show concentration inequalities and CLT for the estimators provided by the PaRIS
algorithm.
In this paper, we extend the theoretical results available for the SMC approximations of
smoothing distributions to the estimators given by the two-filter algorithms. These methods were first introduced in the particle filter literature by [18] and developed further by
[1] and [12]. The two-filter approach combines the output of two independent filters, one
that evolves forward in time and approximates the filtering distributions and another that
evolves backward in time approximating a quantity proportional to the posterior distribution
of a state given future observations. In [12], the authors introduced a proposal mechanism
leading to algorithms whose complexity grows linearly with the number of particles. An algorithm similar to the algorithm of [1] may also be implemented with an O(N ) computational
complexity following the same idea. We analyze all these algorithms which approximate
the marginal smoothing distributions (smoothing distributions of one state given all the
observations) and provide concentration inequalities as well as CLT.
This paper is organized as follows. Section 2 introduces the different particle approxima2

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

tions of the marginal smoothing distributions given by the two-filter algorithms. Sections 3
and 4 provide exponential deviation inequalities and CLT for the particle approximations
under mild assumptions on the hidden Markov chain. Under additional strong mixing assumptions, it is shown that the results of Section 3 are uniform in time and that the asymptotic variance in Section 4 may be uniformly bounded in time. All proofs are postponed to
Section 5.

Notations and conventions
Let X and Y be two general state-spaces endowed with countably generated σ-fields X and Y.
Fb (X, X ) is the set of all real valued bounded measurable functions on (X, X ). Q is a Markov
transition kernel defined on X×X and {gt }t≥0 a family of positive functions defined on X. For
any x ∈ X, Q(x, ·) has a density q(x, ·) with respect to a measure λ on (X, X ). The oscillation
of a real valued function defined on a space Z is given by: osc (h) := supz,z′ ∈Z |h(z) − h(z ′ )|.

2

The two-filter algorithms

For any measurable function h on Xt−s+1 , probability distribution χ on (X, X ), T ≥ 0 and
0 ≤ s ≤ t ≤ T , define the joint smoothing distribution by:
R
QT
χ(dx0 )g0 (x0 ) u=1 Q(xu−1 , dxu )gu (xu )h(xs:t )
φχ,s:t|T [h] :=
,
(1)
R
QT
χ(dx0 )g0 (x0 ) u=1 Q(xu−1 , dxu )gu (xu )

where au:v is a short-hand notation for {as }vs=u . In the following we use the notations
φχ,s|T := φχ,s:s|T and φχ,t := φχ,t:t|t . The aim of this paper is to provide a rigorous analysis
of the performance of SMC algorithms approximating the sequence φχ,s|T for 0 ≤ s ≤ T .
The algorithms analyzed in this paper are based on the two-filter formula introduced in
[1, 12], which we now detail.

2.1

Forward filter

Let {ξ0ℓ }N
ℓ=1 be i.i.d. and distributed according to the instrumental distribution ρ0 and define
the importance weights
dχ ℓ
(ξ ) g0 (ξ0ℓ ) .
ω0ℓ :=
dρ0 0
For any h ∈ Fb (X, X ),
−1
φN
χ,0 [h] := Ω0

N
X

ω0ℓ h(ξ0ℓ ) ,

where Ω0 :=

ℓ=1

N
X

ω0ℓ ,

ℓ=1

ℓ
ℓ
is a consistent estimator of φχ,0 [h], see for instance [4]. Then, based on {(ξs−1
, ωs−1
)}N
ℓ=1 a
new set of particles and importance weights is obtained using the auxiliary sampler introduced in [24]. Pairs {(Isℓ , ξsℓ )}N
ℓ=1 of indices and particles are simulated independently from
the instrumental distribution with density on {1, . . . , N } × X:
ℓ
ℓ
ℓ
πs|s (ℓ, x) ∝ ωs−1
ϑs (ξs−1
)ps (ξs−1
, x) ,

3

(2)

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

where ϑs is the adjustment multiplier weight function and ps is a Markovian transition
density. For any ℓ ∈ {1, . . . , N }, ξsℓ is associated with the importance weight defined by:
Iℓ

ωsℓ :=

s
q(ξs−1
, ξsℓ )gs (ξsℓ )

Iℓ

(3)

Iℓ

s
s
ϑs (ξs−1
)ps (ξs−1
, ξsℓ )

to produce the following approximation of φχ,s [h]:
−1
φN
χ,s [h] := Ωs

N
X

ωsℓ h(ξsℓ ) ,

where Ωs :=

ℓ=1

2.2

N
X

ωsℓ .

ℓ=1

Backward filter

Let {γt }t≥0 be a family of positive measurable functions such that, for all t ∈ {0, . . . , T },
" T
#
Z
Y
γt (xt ) dxt
gu−1 (xu−1 ) Q(xu−1 , dxu ) gT (xT ) < ∞ .
(4)
u=t+1

Following [1], for any 0 ≤ t ≤ T we introduce the backward filtering distribution ψγ,t|T on X
(referred to as the backward information filter in [18] and [1]) defined, for any h ∈ Fb (X, X ),
by:
i
hQ
R
T
g
(x
)
Q(x
,
dx
)
gT (xT )h(xt )
γt (xt ) dxt
u−1
u
u=t+1 u−1 u−1
hQ
i
.
ψγ,t|T [h] :=
R
T
γt (xt ) dxt
u=t+1 gu−1 (xu−1 ) Q(xu−1 , dxu ) gT (xT )

If the distribution of Xt has probability density function
γt , then ψγ,t|T is the conditional
R
distribution of Xt given Yt:T . Contrary to [1] or [12], γt (xt )dxt may be infinite. The only
requirement about the nonnegative functions {γt }t≥0 is the condition (4) and the fact that
γt should be available in closed form. Here γt is a possibly improper prior introduced to
make ψγ,t|T a proper posterior distribution, which is of key importance when producing
particle approximations of such quantities. For 0 ≤ t ≤ T − 1, the backward information
filter is computed by the recursion


Z
q(xt , xt+1 )
h(xt ) dxt ,
(5)
ψγ,t|T [h] ∝ ψγ,t+1|T (dxt+1 ) γt (xt )gt (xt )
γt+1 (xt+1 )
in the backward time direction. (5) is analogous to the forward filter recursion and particle
approximations of the backward information filter can be obtained similarly. Using the
definition of the forward filtering distribution at time s − 1 and the backward information
filter at time s + 1, the marginal smoothing distribution may be expressed as
Z
q(xs , xs+1 )
h(xs )dxs . (6)
φχ,s|T [h] ∝ φχ,s−1 (dxs−1 )ψγ,s+1|T (dxs+1 )q(xs−1 , xs )gs (xs )
γs+1 (xs+1 )
We now describe the Sequential Monte Carlo methods used to approximate the recursion
(5) in [1], [12]. Let ρ̌T be an instrumental probability density on X and {ξˇTi |T }N
i=1 be i.i.d.
i
random variables such that ξ̌T |T ∼ ρ̌T and define
ω̌Ti |T

gT (ξˇTi |T )γT (ξˇTi |T )
.
:=
ρ̌T (ξˇi )
T |T

4

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

i
i
Let now {(ξˇt+1|T
, ω̌t+1|T
)}N
i=1 be a weighted sample targeting the backward information
filter distribution ψγ,t+1|T [h] at time t + 1:

N
[h] := Ω̌−1
ψγ,t+1|T
t+1|T

N
X

i
i
),
h(ξˇt+1|T
ω̌t+1|T

where

Ω̌t+1|T :=

N
X

i
.
ω̌t+1|T

i=1

i=1

Plugging this approximation into (5) yields the target probability density
"
#
i
N
X
q(xt , ξ̌t+1|T
)
i
tar
ω̌t+1|T γt (xt )gt (xt )
ψ̂γ,t|T (xt ) ∝
,
i
)
γt+1 (ξˇt+1|T
i=1
which is the marginal probability density function of xt of the joint density
aux
(i, xt ) ∝
ψ̂γ,t|T

i
ω̌t+1|T
γt+1 (ξˇi

t+1|T )

i
).
γt (xt )gt (xt )q(xt , ξˇt+1|T

A particle approximation of the backward information filter at time t can be derived by
choosing an adjustment weight function ϑt|T and an instrumental density kernel rt|T , and
i
simulating {(Iˇti , ξˇt|T
)}N
i=1 from the instrumental probability density on {1, . . . , N } × X given
by
i
i
ω̌t+1|T
ϑt|T (ξˇt+1|T
)
i
πt|T (i, xt ) ∝
, xt ) .
(7)
rt|T (ξˇt+1|T
)
γt+1 (ξˇi
t+1|T

Subsequently, the particles are associated with the importance weights
Iˇi

i
:=
ω̌t|T

i
i
i
t
)
γt (ξˇt|T
)gt (ξˇt|T
)q(ξˇt|T
, ξˇt+1|T
Iˇi

Iˇi

i )
t
t
, ξˇt|T
)rt|T (ξˇt+1|T
ϑt|T (ξˇt+1|T

.

(8)

Ideally, a fully adapted version of the auxiliary
backward information filter is obtained by
R
using the adjustment weights ϑ⋆t|T (x) = γt (xt )gt (xt )q(xt , x) dxt and the proposal kernel
density
q(xt , x)
⋆
rt|T
(x, xt ) = γt (xt )gt (xt ) ⋆
,
ϑt|T (x)
yielding uniform importance weights. Such a solution is most likely to be cumbersome from
a computational perspective.

2.3

Two-filter approximations of the marginal smoothing distributions

Plugging the particle approximations of the forward and backward filter distributions into
(6) provides the following mixture approximation of the smoothing distribution:
φ̂tar
χ,s|T (xs )

j
N X
N ωi
X
s−1 ω̌s+1|T
j
i
q(ξs−1
, xs )gs (xs )q(xs , ξˇs+1|T
).
∝
γs+1 (ξˇj
)
i=1 j=1

s+1|T

5

(9)

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

Following the TwoFiltf wt algorithm of Fearnhead, Wyncoll and Tawn [12], the probability
density (9) might be seen as the marginal density of xs obtained from the joint density on
the product space {1, . . . , N }2 × X given by
φ̂aux
χ,s|T (i, j, xs ) ∝

j
i
ωs−1
ω̌s+1|T
j
i
q(ξs−1
, xs )gs (xs )q(xs , ξ̌s+1|T
).
γs+1 (ξˇj
)

(10)

s+1|T

ℓ
The TwoFiltf wt algorithm draws a set {(Isℓ , Iˇsℓ , ξ˜s|T
)}N
ℓ=1 of indices and particle positions
from the instrumental density
j
j
i
i
ωs−1
ϑ̃s|T (ξs−1
, ξˇs+1|T
)ω̌s+1|T
j
i
r̃s|T (ξs−1
, ξˇs+1|T
; xs ) ,
πs|T (i, j, xs ) ∝
j
ˇ
γs+1 (ξ
)

(11)

s+1|T

where, as above, ϑ̃s|T (x, x′ ) is an adjustment multiplier weight function (which now depends
on the forward and backward particles) and r̃s|T is an instrumental kernel. We then associate
ℓ
with each draw (Isℓ , Iˇsℓ , ξ˜s|T
) the importance weight
Iˇℓ

Iℓ

ℓ
ω̃s|T

:=

ℓ
ℓ
ℓ
s
s
)
q(ξs−1
, ξ̃s|T
)gs (ξ˜s|T
)q(ξ˜s|T
, ξˇs+1|T
Iℓ

Iˇℓ

Iˇℓ

Iℓ

s
s
s
ℓ )
s
ϑ̃s|T (ξs−1
, ξ̌s+1|T
)r̃s|T (ξs−1
, ξˇs+1|T
; ξ̃s|T

,

Ω̃s|T :=

N
X

ℓ
.
ω̃s|T

(12)

ℓ=1

ℓ
ℓ
N
Then, the auxiliary indices {(Isℓ , Iˇsℓ )}N
ℓ=1 are discarded and {(ω̃s|T , ξ̃s|T )}ℓ=1 approximate the

target smoothing density φ̂tar
χ,s|T . Mimicking the arguments in [15] and further developed
in [19], the auxiliary
particle
filter is fully adapted if the adjustment weight function is
R
ϑ⋆s|T (x, x′ ) = q(x, xs )gs (xs )q(xs , x′ ) dxs and the instrumental kernel is
⋆
(x, x′ ; xs ) = q(x, xs )gs (xs )q(xs , x′ )/ϑ⋆s|T (x, x′ ) .
rs|T

Except in simple scenarios, simulating from the fully adapted auxiliary filter is computationally intractable.
Instead of considering the target distribution (9) as the marginal of the auxiliary distribution (10) over pairs of indices, the TwoFiltbdm algorithm of [1] uses the following partial
auxiliary distributions having densities,
φ̂aux,f
s|T (i, xs )

∝

φ̂aux,b
s|T (j, xs ) ∝

i
i
ωs−1
q(ξs−1
, xs )gs (xs )

N
X
j=1

j
ω̌s+1|T
γs+1 (ξˇj

s+1|T )

j
q(xs , ξˇs+1|T
),

j
N
X
ω̌s+1|T
j
i
i
ωs−1
q(ξs−1
, xs )
q(x
,
ξ̌
)g
(x
)
s
s
s
s+1|T
j
γs+1 (ξˇs+1|T
)
i=1

.

aux,f
Since φ̂tar
χ,s|T is the marginal probability density of the partial auxiliary distributions φ̂s|T

and φ̂aux,b
with respect to the forward and the backward particle indices, respectively,
s|T
ℓ ℓ N
N
ˇℓ ˇℓ
we may sample from φ̂tar
χ,s|T by simulating instead {(Is , ξs )}ℓ=1 or {(Is , ξs|T )}ℓ=1 from the
instrumental probability density functions
f
i
i
i
πs|T
(i, xs ) ∝ ωs−1
ϑs (ξs−1
)ps (ξs−1
, xs ) ,

j
j
j
j
b
πs|T
(j, xs ) ∝ ϑs|T (ξˇs+1|T
)ω̌s+1|T
rs|T (ξˇs+1|T
, xs )/γs+1 (ξˇs+1|T
),

6

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

where (ϑs , ps ) and (ϑs+1|T , rs|T ) are the adjustment multiplier weight functions and the
instrumental kernels used in the forward and backward passes. In this case the algorithm
uses the particles obtained when approximating the forward filter and backward information
i,f
i,b
i
N
filter to provide two different weighted samples {(ω̃s|T
, ξsi )}N
i=1 and {(ω̃s|T , ξ̌s|T )}i=1 targeting

i,b N
i,f N
}i=1
the marginal smoothing distribution, where the forward {ω̃s|T
}i=1 and backward {ω̃s|T
importance weights are given by
i,f
ω̃s|T
:= ωsi

N
X

j
j
j
ω̌s+1|T
q(ξsi , ξ̌s+1|T
)/γs+1 (ξˇs+1|T
),

N
X

Ω̃fs|T :=

(13)

j=1

j=1

j,b
j
ω̃s|T
:= ω̌s|T

j,f
ω̃s|T
,

N
X

j
j
i
i
ωs−1
q(ξs−1
, ξ̌s|T
)/γs (ξˇs|T
),

Ω̃bs|T :=

N
X

j,b
ω̃s|T
.

(14)

j=1

i=1

An important drawback of these algorithms is that the computation of the forward and
backward importance weights grows quadratically with the number N of particles.

2.4

O(N) approximations of the marginal smoothing distributions

In [12], the authors introduced a proposal mechanism in (11) such that the indices (Is , Iˇs )
of the forward and backward particles chosen at time s − 1 and s + 1 are sampled independently. Such choices lead to algorithms whose complexity grows linearly with the number
of particles. The O(N ) algorithm displayed in [12] suggests to use an adjustment multiplier
weight function in (11) such that Is and Iˇs are chosen according to the same distributions as
the indices sampled in the forward filter and in the backward information filter. It is done
in [12] by choosing ϑ̃s|T (x, x′ ) = ϑs (x)ϑs|T (x′ ) so that (11) becomes
πs|T (i, j, xs ) ∝

i
i
ωs−1
ϑs (ξs−1
)

j
j
ϑs|T (ξˇs+1|T
)ω̌s+1|T
j
i
r̃s|T (ξs−1
, ξˇs+1|T
; xs ) .
j
ˇ
γs+1 (ξ
)

(15)

s+1|T

ℓ
In this case, the importance weight (12) associated with each draw (Isℓ , Iˇsℓ , ξ˜s|T
) is given by
Is
Iˇs
ℓ
ℓ
ℓ
)
q(ξs−1
, ξ˜s|T
)gs (ξ˜s|T
)q(ξ˜s|T
, ξ̌s+1|T
ℓ

ℓ
ω̃s|T

:=

ℓ

Isℓ
Iˇsℓ
Isℓ
Iˇsℓ
ℓ )
ϑs (ξs−1
)ϑs|T (ξˇs+1|T
)r̃s|T (ξs−1
, ξ̌s+1|T
; ξ̃s|T

.

(16)

Instead of sampling new particles at time s, an algorithm similar to the TwoFiltbdm algorithm
ˇℓ N
of [1] which uses the forward particles {ξsℓ }N
ℓ=1 or backward particles {ξs|T }ℓ=1 may also be
implemented with an O(N ) computational complexity.
Iℓ

Iˇℓ

Iˇℓ

s
s
s
, xs ) in (15), the smoothing distribution
; xs ) = rs|T (ξˇs+1|T
, ξ̌s+1|T
(a) Choosing r̃s|T (ξs−1
approximation is obtained by reweighting the particles obtained in the backward pass.
ℓ
The backward particles {ξˇs|T
}N
ℓ=1 are associated with the importance weights:

Iˇs
ℓ
ℓ
ℓ
)
γs (ξˇs|T
)gs (ξˇs|T
)q(ξˇs|T
, ξˇs+1|T
ℓ

ℓ
:=
ω̃s|T

ˇℓ

ˇℓ

Iℓ

ℓ
s
, ξ̌s|T
)
q(ξs−1
Iℓ

Is
Is
ℓ ) γ (ξˇℓ )ϑ (ξ s )
ϑs|T (ξˇs+1|T
)rs|T (ξˇs+1|T
, ξˇs|T
s s−1
s s|T

,

Iℓ

=

ℓ
ω̌s|T

ℓ
s
, ξ̌s|T
)
q(ξs−1
Iℓ

ℓ )ϑ (ξ s )
γs (ξˇs|T
s s−1

7

.

(17)

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

Iˇℓ

Iℓ

Iℓ

s
s
s
; xs ) = ps (ξs−1
, xs ) in (15), the smoothing distribution ap(b) Choosing r̃s|T (ξs−1
, ξ̌s+1|T
proximation is obtained by reweighting the particles obtained in the forward filtering
pass. The forward particles {ξsℓ }N
ℓ=1 are associated with the importance weights:

Iˇℓ

Iℓ

ℓ
ω̃s|T

3

:=

s
)
q(ξsℓ , ξˇs+1|T

s
q(ξs−1
, ξsℓ )gs (ξsℓ )

Is
Is
Iˇsℓ
ϑs (ξs−1
)ps (ξs−1
, ξsℓ ) ϑs|T (ξˇs+1|T
)
ℓ

ℓ

Iˇℓ

=

ωsℓ

s
)
q(ξsℓ , ξ̌s+1|T

Iˇsℓ
ϑs|T (ξˇs+1|T
)

.

(18)

Exponential deviation inequality for the two-filter algorithms

In this section, we establish exponential deviation inequalities for the two-filter algorithms
introduced in Section 2. Before stating the results, some additional notations are required.
Define, for all (x, x′ , x′′ ) ∈ X3 ,
q [2] (x, x′ ; x′′ ) = q(x, x′′ )q(x′′ , x′ )

and for any functions f : X2 → R and g : X → R,

f ⊙ g(x, x′ ) := f (x, x′ )g(x′ ) .

Consider the following assumptions:
A1. |q|∞ < ∞ and for all 0 ≤ t ≤ T , gt is positive and |gt |∞ < ∞.

A2. For all 0 ≤ t ≤ T , |ϑt |∞ < ∞, |pt |∞ < ∞ and |ωt |∞ < ∞ where
ω0 (x) :=

dχ
(x)g0 (x)
dρ0

and for all t ≥ 1

A3. - For all 0 ≤ t ≤ T − 1, ϑt|T /γt+1
ω̌t|T ∞ < ∞, where
ω̌T |T (x) :=

∞

q(x, x′ )gt (x′ )
.
ϑt (x)pt (x, x′ )

< ∞ and |rt|T |∞ < ∞. For all 0 ≤ t ≤ T

gT (x)γT (x)
γt (x)gt (x)q(x, x′ )
and for all 0 ≤ t < T, ω̌t|T (x, x′ ) :=
.
ρ̌T (x)
ϑt|T (x′ )rt|T (x′ , x)

−1
- For all 1 ≤ t ≤ T − 1, ϑ̃t|T ⊙ γt+1

r̃t|T

∞

ωt (x, x′ ) :=

∞

< ∞ where

ω̃t|T (x, x′ ; x′′ ) :=

−1
< ∞, q ⊙ γt+1

∞

< ∞, ω̃t|T

q [2] (x, x′ ; x′′ )gs (x′′ )
ϑ̃t|T (x, x′′ )r̃t|T (x, x′ ; x′′ )

∞

< ∞ and

.

j
j
We first show that the weighted sample {(ωsi ω̌t|T
), (ξsi , ξˇt|T
)}N
i,j=1 targets the product
distribution φχ,s ⊗ ψγ,t|T .

Theorem 1. Assume that A1, A2 and A3 hold for some T < ∞. Then, for all 0 ≤
s < t ≤ T , there exist 0 < Bs,t|T , Cs,t|T < ∞ such that for all N ≥ 1, ǫ > 0 and all
h ∈ Fb (X × X, X ⊗ X ),


N
i ω̌ j
X
2
2
ω
t|T
j
s
P
h(ξsi , ξˇt|T
) − φχ,s ⊗ ψγ,t|T [h] > ǫ ≤ Bs,t|T e−Cs,t|T N ǫ / osc (h) .
Ω
Ω̌
i,j=1 s t|T
8

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

Proof. The proof is postponed to Section 5.1.
i
ℓ
We now study the weighted sample {(ω̃s|T
, ξ˜s|T
)}N
ℓ=1 produced by the TwoFiltf wt algorithm of Fearnhead, Wyncoll and Tawn [12] defined in (11) and (12) and targeting the
marginal smoothing distribution φχ,s|T .

Theorem 2 (deviation inequality for TwoFiltf wt of [12]). Assume that A1, A2 and A3 hold
for some T < ∞. Then, for all s < T , there exist 0 < Bs|T , Cs|T < ∞ such that for all
N ≥ 1, ε > 0 and all h ∈ Fb (X, X ),
P

N
i
X
ω̃s|T
i=1

Ω̃s|T

i
)
h(ξ˜s|T

− φχ,s|T [h] > ǫ

!

≤ Bs|T e−Cs|T N ǫ

2

/ osc2(h)

.

Proof. The proof is postponed to Section 5.2.
Using Theorem 1 and Lemma 7, we may derive an exponential inequality for the weighted
i,f
i,b
N
ˇi
samples {(ξsi , ω̃s|T
)}N
i=1 and {(ξs|T , ω̃s|T )}i=1 produced by the TwoFiltbdm algorithm of [1],

i,f
i,b
where ω̃s|T
and ω̃s|T
are defined in (13) and (14). Therefore, both the forward and the
backward particle approximations of the smoothing distribution converge to the marginal
smoothing distribution, and these two approximations satisfy an exponential inequality.

Theorem 3 (deviation inequality for the TwoFiltbdm algorithm of [1]). Assume that A1, A2
and A3 hold for some T < ∞. Then, for all 1 ≤ s ≤ T − 1, there exist 0 < Bs|T , Cs|T < ∞
such that for all N ≥ 1, ε > 0 and all h ∈ Fb (X, X ),
P

P

N ω̃ i,f
X
s|T

Ω̃fs|T
i=1
N ω̃ i,b
X
s|T
b
Ω̃
s|T
i=1

h(ξsi )

− φχ,s|T [h] > ǫ

!

i
) − φχ,s|T [h] > ǫ
h(ξˇs|T

≤ Bs|T e−Cs|T N ǫ
!

2

/ osc2(h)

≤ Bs|T e−Cs|T N ǫ

2

,

/ osc2(h)

(19)

.

(20)

Proof. The proof is postponed to Section 5.3.
Remark 1. Following [23, 6, 11], time uniform exponential inequalities for the two-filter
approximations of the marginal smoothing distributions may be obtained using strong mixing
assumptions which are standard in the SMC literature:
H1. There exist 0 < σ− < σ+ < ∞ and c− > 0 such that for all x, x′ ∈ X, σ− ≤ q(x, x′ ) ≤
σ+ and for all t ≥ 0,
Z
Z
χ(dx0 )g0 (x0 ) ≥ c− and inf
Q(x, dx′ )gt (x′ ) ≥ c− .
x∈X

H 2. There exist 0 < γ− < γ+ < ∞ and č− > 0 such that for all x ∈ X and all t ≥ 0,
γ− ≤ γt (x) ≤ γ+ and for all t ≥ 0,
Z
Z
−1
γT (xT )gT (xT )dxT ≥ č− and inf
γt (xt )gt (xt )q(xt , x)γt+1
(x)dxt ≥ č− .
x∈X

9

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

(i) If A1 and A2 hold uniformly in T and if H1 holds, then, it is proved in [6] that
Proposition 8 holds with constants that are uniform in time : there exist 0 < B, C < ∞
such that for all s ≥ 0, N > 0, ǫ > 0 and all h ∈ Fb (X, X ),
!
N
X
2
2
ωsi h(ξsi ) − φχ,s [h] ≥ ǫ ≤ Be−CN ǫ / osc(h) .
P Ω−1
s
i=1

(ii) It can be shown following the exact same steps that if A1 and A3 hold uniformly in
T and if H1 and H2 hold then Proposition 9 holds with constants that are uniform
in time: there exist 0 < B, C < ∞ such that for all t ≥ 0, N ≥ 1, ǫ > 0, and all
h ∈ Fb (X, X ),
"
#
N
X
2
2
−1
i
i
ˇ
P Ω̌t|T
ω̌t|T h(ξt|T ) − ψγ,t|T [h] ≥ ǫ ≤ Be−CN ǫ / osc(h) .
i=1

(iii) Therefore, if A1, A2 and A3 hold uniformly in T and if H1 and H2 hold, then Theorem 1
holds with constants that are uniform in time. As a direct consequence, Theorems 2
and 3 hold also with constants that are uniform in time.

4

Asymptotic normality of the two-filter algorithms

We now establish CLT for the two-filter algorithms. Note first that under assumptions
A1, A2 and A3, for all 0 ≤ s, t ≤ T a CLT may be derived for the weighted samples
N
i
ˇi
{(ξsℓ , ωsℓ )}N
ℓ=1 and {(ξt|T , ω̌t|T )}i=1 which target respectively the filtering distribution φχ,s
and the backward information filter ψγ,t|T . By Propositions 10 and 11, there exist Γχ,s and
Γ̌γ,t|T such that for any h ∈ Fb (X, X ),
N 1/2
N 1/2

N
X
 D
ωsi
h(ξsi ) − φχ,s [h] −→N →∞ N (0, Γχ,s [h − φχ,s [h]]) ,
Ωs
i=1

N ω̌ j

X
t|T
j=1

Ω̌t|T




D
j
h(ξˇt|T
) − ψγ,t|T [h] −→N →∞ N 0, Γ̌γ,t|T h − ψγ,t|T [h] .

(21)

(22)

j
j
Theorem 4 establishes a CLT for the weighted sample {ωsi ω̌t|T
, (ξsi , ξ̌t|T
)}N
i,j=1 which targets
the product distribution φχ,s ⊗ψγ,t|T . As an important consequence, the asymptotic variance
of the weighted sample {ω i ω̌ j , (ξ i , ξˇj )}N
is the sum of two contributions, the first one
s t|T

s

t|T

i,j=1

involves Γχ,s and the second one Γ̌γ,t|T . Intuitively, this may be explained by the fact that
N
the estimator φN
χ,s ⊗ψγ,t|T [h] is obtained by mixing two independent weighted samples which
suggests the following decomposition:
j
N
N ω̌ j
√ X
√ X
ωsi ω̌t|T
t|T
j
j
N
φχ,s [h̃s,t (·, ξˇt|T
)]
h̃s,t (ξsi , ξ̌t|T
)= N
Ωs Ω̌t|T
Ω̌t|T
i,j=1

j=1

+

10

N
√ X
ωsi
N
N
ψγ,t|T [h̃s,t (ξsi , ·)] + Es,T
|t (h̃s,t ) ,
Ω
s
i=1

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

where h̃s,t = h − φχ,s ⊗ ψγ,t|T [h] and
N
Es,T
|t (h)

j
N
o
√ X
ωsi ω̌t|T n i j
j
h(ξs , ξ̌t|T ) − φχ,s [h(·, ξˇt|T
)] − ψγ,t|T [h(ξsi , ·)] .
:= N
Ω Ω̌
i,j=1 s t|T

A CLT for the two independent first terms is obtained by (21) and (22). It remains then to
N
prove that Es,T
|t (h) converges in probability to 0. However, this cannot be obtained directly
from the exponential deviation inequality derived in Theorem 1 and requires sharper controls
of the smoothing error (for instance nonasymptotic Lp -mean error bounds). Theorem 4
provides a direct proof following the asymptotic theory of weighted system of particles
developed in [7].
Theorem 4. Assume that A1, A2 and A3 hold for some T < ∞. Then, for all 0 ≤ s < t ≤
T and all h ∈ Fb (X × X, X × X ),


N
i ω̌ j
X
√
ω
t|T
j
s
h(ξsi , ξˇt|T
) − φχ,s ⊗ ψγ,t|T [h]
N
Ω
Ω̌
s
t|T
i,j=1




D
−→N →∞ N 0, Γ̃s,t|T h − φχ,s ⊗ ψγ,t|T [h] ,

where Γ̃s,t|T [h] is defined by:
Z

Z

Γ̃s,t|T [h] := Γχ,s
ψγ,t|T (dxt )h(·, xt ) + Γ̌γ,t|T
φχ,s (dxs )h(xs , ·) ,

(23)

with Γχ,s and Γ̌γ,t|T are given in Proposition 10 and Proposition 11.
Proof. The proof is postponed to Section 5.4.
Define
Z

[2]

−1
γs+1



σs := φχ,s−1 ⊗ ψγ,s+1|T
,
q (·, x)gs (x)dx ⊙
Z

−1
Σs [h] := Γ̃s−1,s+1|T
.
q [2] (·; x)gs (x)h(x)dx ⊙ γs+1
Theorem 5 provides a CLT for the TwoFiltf wt algorithm of [12]
Theorem 5 (CLT for the TwoFiltf wt algorithm of [12]). Assume that A1, A2 and A3 hold
for some T < ∞. Then, for all 1 ≤ s ≤ T − 1 and all h ∈ Fb (X, X ),
!
N
i
X
√
ω̃s|T


D
i
N
h(ξ˜s|T ) − φχ,s|T [h] −→N →∞ N 0, Υχ,s|T h − φχ,s|T [h] .
Ω̃s|T
i=1
where

i
h
−1
Υχ,s|T [h] = σs−2 Σs [h] + φχ,s−1 ⊗ ψγ,s+1|T ϑ̃s|T ⊙ γs+1
Z

−1
× φχ,s−1 ⊗ ψγ,s+1|T
. (24)
ω̃s|T (·; x)q [2] (·, x)gs (x)h2 (x)dx ⊙ γs+1
11

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

Proof. The proof is postponed to Section 5.5.
The decompositions (27) and (28) together with Theorem 4 allow to prove a CLT form
the forward and the backward approximations of the marginal smoothing distribution. Theorem 6 is a direct consequence of Proposition 11, Theorem 4 and Slutsky Lemma.
Theorem 6 (CLT for the TwoFiltbdm algorithm of [1]). Assume that A1, A2 and A3 hold
for some T < ∞. Then, for all 1 ≤ s ≤ T − 1 and all h ∈ Fb (X, X ),
√
N

N ω̃ i,f
X
s|T
i=1

Ω̃fs|T

h(ξsi )

− φχ,s|T [h]

!




D
−→N →∞ N 0, ∆fχ,s|T h − φχ,s|T [h] ,

where
 
−1
]}2 ,
∆fχ,s|T [h] := Γ̃s,s+1|T Hsf /{φχ,s ⊗ ψγ,s+1|T [q ⊙ γs+1
−1
Hsf (x, x′ ) := h(x)q(x, x′ )γs+1
(x′ ) .

Similarly,
√
N

N ω̃ i,b
X
s|T
i=1

Ω̃bs|T

h(ξsi )

− φχ,s|T [h]

!




D
−→N →∞ N 0, ∆bχ,s|T h − φχ,s|T [h] ,

where
 
∆bχ,s|T [h] := Γ̃s−1,s|T Hsb /{φχ,s−1 ⊗ ψγ,s|T [q ⊙ γs−1 ]}2 ,
Hsb (x, x′ ) := q(x, x′ )γs−1 (x′ )h(x′ ) .

Note that σs and Σs [h] may be written as:


−1
σs = φχ,s ⊗ ψγ,s+1|T q ⊙ γs+1
× φχ,s−1

Z


q(·, x)gs (x)dx

and by Theorem 4,
Σs [h] = Γχ,s−1

Z



q(·, x)gs (x)h1s+1 (x)dx

+

φ2χ,s−1

Z




q(·, x)gs (x)dx Γ̌γ,s+1|T h2s+1 ,

−1
−1
with h1s+1 (x) := h(x)ψγ,s+1|T [q(x, ·)γs+1
] and h2s+1 (x) := γs+1
(x)φχ,s [h(·)q(·, x)]. In the
case where r̃s|T (xs , xs+1 ; xs ) = ps (xs−1 , xs ) in (15) and ϑ̃s|T (x, x′ ) = ϑs (x)ϑs|T (x′ ), the
smoothing distribution approximation given by the TwoFiltf wt algorithm is obtained by
reweighting the particles obtained in the forward filtering pass and Υχ,s|T [h] may be compared to ∆fχ,s|T [h] as both approximations of φχ,s|T [h] are based on the same particles
(associated with different importance weights). In this case, the two last terms in (24) are
easily interpreted in the case ϑs|T = γs+1 :
i
h
−1
−1
= φχ,s−1 [ϑs ]ψγ,s+1|T [ϑs|T γs+1
] = φχ,s−1 [ϑs ]
φχ,s−1 ⊗ ψγ,s+1|T ϑ̃s|T ⊙ γs+1

12

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

and by Jensen’s inequality,
Z

−1
[2]
2
φχ,s−1 ⊗ ψγ,s+1|T
ω̃s|T (·; x)q (·, x)gs (x)h (x)dx ⊙ γs+1
Z
−2
= φχ,s−1 (dxs−1 )ωs (xs−1 , x)gs (x)q(xs−1 , x)ψγ,s+1|T [q 2 (x, ·)γs+1
]h2 (x)dx ,
Z
≥ φχ,s−1 (dxs−1 )ωs (xs−1 , x)gs (x)q(xs−1 , x)(h1s+1 (x))2 dx .
Therefore, by Proposition 11 and Theorem 6




Γχ,s h1s+1 + Γ̌γ,s+1|T h2s+1
f
Υχ,s|T [h] ≥
2 = ∆χ,s|T [h] ,

−1
φχ,s ⊗ ψγ,s+1|T q ⊙ γs+1

where the last inequality comes from Theorem 4. The same inequality holds for ∆bχ,s|T [h]
when r̃s|T (xs−1 , xs+1 ; xs ) = rs|T (xs+1 , xs ) in (15).

Remark 2. Under the strong mixing assumptions H1 and H2, time uniform bounds for the
asymptotic variances of the two-filter approximations of the marginal smoothing distributions may be obtained.
(i) If A1 and A2 hold uniformly in T and if H1 holds, then it is proved in [6] that there
exists C > 0 such that for all s ≥ 0 and all h ∈ Fb (X, X ), the asymptotic variance
Γχ,s [h] defined in Proposition 10 satisfies:
2

Γχ,s [h] ≤ C |h|∞ .
(ii) Following the same steps, if A1 and A3 hold uniformly in T and if H1 and H2 hold,
there exists C > 0 such that for all 0 ≤ t ≤ T and all h ∈ Fb (X, X ), the asymptotic
variance Γ̌t|T [h] defined in Proposition 11 satisfies:
2

Γ̌γ,t|T [h] ≤ C |h|∞ .
(iii) As a consequence, if A1, A2 and A3 hold uniformly in T and if H1 and H2 hold, the
asymptotic variances Γ̃s,t|T [h], ∆fχ,s|T [h], ∆bχ,s|T [h] and Υχ,s|T [h] defined in Theorem 4, Theorem 5 and Theorem 6 are all uniformly bounded.

5
5.1

Proofs
Proof of Theorem 1

j
j
N
, 1 ≤ j ≤ N ) and
Define Gt|T
:= σ(ξˇt|T
, ω̌t|T

ft|T (x) := Ω̌−1
t|T

N
X
j=1

13

j
j
ω̌t|T
h(x, ξˇt|T
)

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

whose oscillation is bounded by osc (h). By the exponential inequality for the auxiliary
particle filter (Proposition 8), there exist constants Bs and Cs such that

Z
N ω̌ j
N
i ω̌ j
X
X
ω
t|T
t|T
j
j
s
h(ξsi , ξ̌t|T
)−
φχ,s (dxs )h(xs , ξˇt|T
) > ǫ
P
Ω
Ω̌
Ω̌
s
t|T
t|T
j=1
i,j=1
!#
"
N
X ωi
2
2
s
i
N
≤ Bs e−Cs N ǫ / osc (h) . (25)
=E P
ft|T (ξs ) − φχ,s (ft|T ) > ǫ Gt|T
Ωs
i=1


R
Since the oscillation of the function x 7→ φχ,s (dxs )h(xs , x) is bounded by osc (h), by
Proposition 9 there exist constants Bt|T and Ct|T such that


P

Z
N ω̌ j
X
t|T
j=1

Ω̌t|T



j
φχ,s (dxs )h(xs , ξ̌t|T
) − φχ,s ⊗ ψγ,t|T [h] > ǫ

≤ Bt|T e−Ct|T N ǫ

2

/ osc2(h)

, (26)

which concludes the proof.

5.2

Proof of Theorem 2

Define h̃s|T := h − φχ,s|T [h]. Lemma 7 is used with
aN := N −1

N
X

i
i
h̃s|T (ξ˜s|T
),
ω̃s|T

bN := N −1 Ω̃s|T ,

i=1

b :=


−1
q [2] (·; xs )gs (xs )dxs ⊙ γs+1
i
h
.
−1
φχ,s ⊗ ψγ,s+1|T ϑ̃s|T ⊙ γs+1

φχ,s ⊗ ψγ,s+1|T

R

Lemma 7-(i) is satisfied using β := b and |aN |/|bN | ≤ osc (h). To prove Lemma 7-(ii) for
aN , note that Hoeffding inequality implies that, for any ǫ > 0,
(
)

h
i

2
N
ǫ
1
N
1
N
≥ ǫ Gs,T
h̃s|T (ξ˜s|T
) Gs,T
≤ 2 exp −
P aN − E ω̃s|T
,
2
8 ω̃s|T ∞ osc2 (h)
N,+
N,−
N
where Gs,T
:= Gs−1
∨ Gs+1,T
and

GsN,+ := σ {(ωui , ξui )}N
i=1 , u = 1, . . . , s − 1 ,
o
n
N,−
i
i
Gs,T := σ {(ω̌u|T , ξˇu|T )}N
.
i=1 , u = s + 1, . . . , T

On the other hand, for all ℓ ∈ {1, . . . , N },

i
h
N
ℓ
ℓ
) Gs,T
h̃s|T (ξ˜s|T
E ω̃s|T
R [2] i
PN
j
−1 ˇj
i
ˇj
i,j=1 ωs−1 ω̌s+1|T γs+1 (ξs+1|T ) q (ξs−1 , ξs+1|T ; xs )gs (xs )h̃s|T (xs )dxs
=
.
PN
j
j
−1 ˇj
i
i
i,j=1 ωs−1 ω̌s+1|T γs+1 (ξs+1|T )ϑ̃s|T (ξs−1 , ξ̌s+1|T )
14

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

The proof of Lemma 7-(ii) is then completed by applying Lemma 7 to a′N , b′N and b′ defined
by:
a′N

:=

j
i
N
X
ωs−1
ω̌s+1|T

i,j=1

b′N

:=

Ωs−1 Ω̌s+1|T

j
i
N
X
ωs−1
ω̌s+1|T

i,j=1

Ωs−1 Ω̌s+1|T

−1 ˇj
γs+1
(ξs+1|T )

Z

j
i
q [2] (ξs−1
, ξˇs+1|T
; xs )gs (xs )h̃s|T (xs )dxs ,

j
−1 ˇj
i
),
γs+1
(ξs+1|T )ϑ̃s|T (ξs−1
, ξˇs+1|T

−1
b := φχ,s ⊗ ψγ,s+1|T [ϑ̃s|T ⊙ γs+1
].
′

Note first that Lemma 7-(i) is satisfied using β ′ := b′ and |a′N /b′N | ≤ ω̃s|T
addition, by (6),
φχ,s ⊗ ψγ,s+1|T [h̄s|T ] ∝ φχ,s|T [h̃s|T ] = 0 ,
where
h̄s|T (x, x′ ) :=

Z

∞

osc (h). In

−1
q [2] (·; xs )gs (xs )h̃s|T (xs )dxs ⊙ γs+1
(x, x′ ) .

Theorem 1 ensures that Lemma 7-(ii) is satisfied for a′N as

−1
osc h̄s|T ≤ 2 ϑ̃s|T ⊙ γs+1

∞

ω̃s|T

∞

osc (h) .

Similarly, Theorem 1 yields:

P (|b′N − b′ | ≥ ǫ) ≤ Bs e−Cs N ǫ

2

−1
/ osc2(ϑ̃s|T ⊙γs+1
)

,

which proves Lemma 7-(iii) for b′N and concludes the proof of Lemma 7-(ii) for aN . The
proof of Lemma 7-(iii) for bN is along the same lines.

5.3

Proof of Theorem 3

Define
−1
hs (x, x′ ) := γs+1
(x′ )h(x)q(x, x′ ) and hs (x, x′ ) := γs−1 (x′ )q(x, x′ )h(x′ ) .

It follows from the definition of the forward and backward smoothing weights (13) and (14)
that,
PN
i j
−1 −1
i j
N ω̃ i,f
X
Ω̌
Ω
s
i,j=1 ωs ω̌s+1|T hs (ξs , ξ̌s+1|T )
s|T
s+1|T
i
h(ξs ) = −1 −1 PN
,
(27)
j
j
Ω̃fs|T
Ωs Ω̌s+1|T i,j=1 ωsi ω̌s+1|T
1s (ξsi , ξ̌s+1|T
)
i=1
j
j
−1 PN
i
i
N ω̃ i,b
X
Ω−1
s−1 Ω̌s|T
i,j=1 ωs−1 ω̌s|T hs (ξs−1 , ξ̌s|T )
s|T
i
ˇ
h(ξs|T ) = −1 −1 PN
.
(28)
j
j
i
i
Ω̃bs|T
Ωs−1 Ω̌s|T i,j=1 ωs−1
ω̌s|T
1s (ξs−1
, ξ̌s|T
)
i=1

On the other hand, from the definition of the filtering distribution and of the backward
information filter
 
 
φχ,s|T [h] = φχ,s ⊗ ψs+1|T hs /φχ,s ⊗ ψs+1|T 1s ,
φχ,s|T [h] = φχ,s−1 ⊗ ψs|T [hs ] /φχ,s−1 ⊗ ψs|T [1s ] .
15

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

Then, (19) is established by writing:
N ω̃ i,f
X
s|T
i=1

Ω̃fs|T

i,f
h(ξsi ) − φχ,s|T [h] = ai,f
N /bN ,

where
ai,f
N

:=

j
N
X
ωsi ω̌s+1|T

i,j=1

bi,f
N :=

Ωs Ω̌s+1|T

j
N
X
ωsi ω̌s+1|T

i,j=1

Ωs Ω̌s+1|T

j
1s (ξsi , ξˇs+1|T
)

(

j
1s (ξsi , ξˇs+1|T
),

j
hs (ξsi , ξˇs+1|T
) φχ,s ⊗ ψs+1|T
−
j
i
ˇ
1s (ξs , ξs+1|T ) φχ,s ⊗ ψs+1|T

 
b := φχ,s ⊗ ψs+1|T 1s .

 )
hs
  ,
1s

Lemma 7 may then be applied with β := b. Note that
j
hs (ξsi , ξ̌s+1|T
)

 
φχ,s ⊗ ψs+1|T hs
  = h(ξsi ) − φχ,s|T [h] ,
−
j
1s (ξsi , ξ̌s+1|T
) φχ,s ⊗ ψs+1|T 1s

i,f
which ensures that ai,f
N /bN ≤ osc (h) and that Lemma 7-(i) is satisfied. By



−1
,
osc 1s = osc q ⊙ γs+1
 i

−1
osc 1s ⊙ h(ξs ) − φχ,s|T [h] ≤ 2 q ⊙ γs+1

∞

osc (h) ,

Theorem 1 shows that Lemma 7-(ii) and (iii) are satisfied. The proof of (20) follows the
exact same lines.

5.4

Proof of Theorem 4

For all 1 ≤ t ≤ T , the result is shown by induction on s where s ∈ {0, . . . , t − 1}. Write
h̃0,t := h − φχ,0 ⊗ ψγ,t|T [h] and set, for i ∈ {1, . . . , N },
UN,i := N

−1/2

ω0i

N ω̌ j
X
t|T
j=1

Ω̌t|T

j
h̃0,t (ξ0i , ξ̌t|T
).

Then,


N
N
i ω̌ j
X
X
√
ω0 t|T
−1
j
UN,i .
h(ξ0i , ξˇt|T
) − φχ,0 ⊗ ψγ,t|T [h] = (Ω0 /N )
N
Ω Ω̌
i,j=1 0 t|T
i=1



j
Define GN,i := σ {ξ0ℓ }ℓ≤i , {ξˇu|T
}t≤u≤T , j = 1, . . . , N . Then,
N
X
i=1

E [ UN,i | GN,i−1 ] = N

1/2

N ω̌ j
X
t|T
j=1

16

Ω̌t|T

h
i
j
ρ0 ω0 h̃0,t (·, ξˇt|T
) .

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

R
As ψγ,t|T (dxt )ρ0 (dx0 )ω0 (x0 )h̃0,t (x0 , xt ) = 0, by the CLT for the backward information
filter (Proposition 11),
N
X
i=1


D
E [ UN,i | GN,i−1 ] −→N →∞ N 0, Γ̌t|T [H0,t ] ,

R

where H0,t (xt ) := ρ0 (dx0 )ω0 (x0 )h̃0,t (x0 , xt ). We now prove that
!
"
!
#
N
2
X
u2 σ0,t|T
[h]
P
{UN,i − E [ UN,i | GN,i−1 ]} GN,0 −→N →∞ exp −
E exp iu
,
2
i=1
where
2
[h] :=
σ0,t|T

Z

2
[h̃0,t (x, ·)] .
ρ0 (dx)ω02 (x)ψγ,t|T

This is done by applying [7, Theorem A.3] which requires to show that
N 

X
 2

P
2
2
E UN,i
[h] ,
GN,i−1 − E [ UN,i | GN,i−1 ] −→N →∞ σ0,t|T

(29)

i=1

N
X
 P
 2
E UN,i
1{|UN,i | > ε} GN,i−1 −→N →∞ 0 .

(30)

i=1

By Proposition 9,


2
N ω̌ j
X
t|T
P
2
j
2
E [ UN,i | GN,i−1 ] = 
H0,t (ξˇt|T
) −→N →∞ ψγ,t|T
[H0,t ] = 0 .
Ω̌
t|T
i=1
j=1

N
X

On the other hand,
#
" N
X 

2
2
E UN,i GN,i−1 − σ0,t|T [h]
E
i=1



2
N ω̌ j
X
t|T


j
2
= ρ0 (dx)ω02 (x)E  
h̃0,t (x, ξˇt|T
) − ψγ,t|T
[h̃0,t (x, ·)]  ,
Ω̌
j=1 t|T
Z
≤ 2 osc (h) ρ0 (dx)ω02 (x)E [AN (x)] ,
Z

where
AN (x) :=

N ω̌ j
X
t|T
j=1

Ω̌t|T

j
h̃0,t (x, ξˇt|T
) − ψγ,t|T [h̃0,t (x, ·)] .

By Proposition 9, there exist Bt|T and Ct|T such that for all x ∈ X,
E [AN (x)] =

Z

0

∞

P (AN (x) ≥ ε) dε
≤ Bt|T

Z

∞

e−Ct|T N ǫ

0

17

2

/ osc(h)2

dε ≤ Dt|T osc (h) N −1/2 , (31)

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

which shows that

N
X
i=1

 2
 P
2
E UN,i
[h]
GN,i−1 −→N →∞ σ0,t|T

and concludes the proof of (29). For all N ≥ 1,
n
o
−1
{|UN,i | ≥ ε} ⊆ ω0i ≥ εN 1/2 osc (h)
,

which implies that
N
X
i=1

Z


 2
2
E UN,i
1{|UN,i| ≥ ε} GN,i−1 ≤ osc (h)

o
n
−1
ρ0 (dx)ω02 (x)1 ω0 (x) ≥ N 1/2 osc (h)

and (30) follows by letting N → ∞. Note that
Z
P
−1
N Ω0 −→N →∞ χ(dx0 )g0 (x0 ) ,
which shows (23) since
−2
i Z
h
χ(dx0 )g0 (x0 )
Γ̃0,t|T h̃0,t =


Z
2
× Γ̌γ,t|T [H0,t ] + ρ0 (dx)ω02 (x)ψγ,t|T
[h̃0,t (x, ·)] ,
Z
Z


= Γ̌γ,t|T
φχ,0 (dx0 )h̃0,t (x0 , ·) + Γχ,0
ψγ,t|T (dxt )h̃0,t (·, xt ) .
Assume now that the result holds for some s − 1. Write h̃s,t := h − φχ,s ⊗ ψγ,t|T [h] and set,
for i ∈ {1, . . . , N },
N ω̌ j
X
t|T
j
−1/2 i
h̃s,t (ξsi , ξˇt|T
).
UN,i := N
ωs
Ω̌
j=1 t|T

Then,



N
N
i ω̌ j
X
X
√
ωs t|T
−1
j
N
UN,i .
h(ξsi , ξˇt|T
) − φχ,0 ⊗ ψγ,t|T [h] = (Ωs /N )
Ω Ω̌
i,j=1 s t|T
i=1

Define, for 1 ≤ i ≤ N ,
GN,i
Then,
N
X
i=1


 j
ξs
:= σ

i
j=1


, ξuℓ


n
oN
j
ˇ
, ξv|T
, 1 ≤ u < s, t ≤ v ≤ T .
ℓ=1
N

j=1

E [ UN,i | GN,i−1 ] = φN
χ,s−1 [ϑs ]

where
Hs,t (xs−1 , xt ) :=

Z

−1

N 1/2

j
N
i
X
ω̌t|T
ωs−1
j
i
Hs (ξs−1
, ξ̌t|T
),
Ω
Ω̌
i,j=1 s−1 t|T

q(xs−1 , x)gs (x)h̃s,t (x, xt )dx .
18

(32)

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

Since φχ,s−1 ⊗ ψγ,t|T [Hs,t ] = 0, by the induction assumption,
N
X
i=1



D
E [ UN,i | GN,i−1 ] −→N →∞ N 0, Γ̃s−1,t|T [Hs,t ] /φ2χ,s−1 [ϑs ] .

We will now prove that
#
!
"
!
2
N
X
u2 σs,t|T
[h]
P
{UN,i − E [ UN,i | GN,i−1 ]} GN,0 −→N →∞ exp −
E exp iu
,
2
i=1
where

2
σs,t|T
[h] := φχ,s−1 [ϑs ]−1 φχ,s−1 [fs−1,t ] ,
Z
2
[h̃s,t (xs , ·)]gs (xs )dxs .
fs−1,t (xs−1 ) := q(xs−1 , xs )ωs (xs−1 , xs )ψγ,t|T

2
This is done using again [7, Theorem A.3] and proving that (29) and (30) hold with σ0,t|T
[h]
2
replaced by σs,t|T [h]. Note that

2
j
N
i
X
ω̌
ω
2
j
s−1 t|T
i
2
E [ UN,i | GN,i−1 ] = 
Hs,t (ξs−1
, ξˇt|T
) /(φN
χ,s−1 [ϑs ]) ,
Ω
Ω̌
s−1
t|T
i=1
i,j=1


N
X

which converges in probability to 0 by Theorem 1 and the fact that φχ,s−1 ⊗ ψγ,t|T [Hs,t ] = 0.
In addition,
Z
N
N
i
i
X
 2

−1 X
q 2 (ξs−1
, xs )gs (xs )
ωs−1
N
E UN,i GN,i−1 = φχ,s−1 [ϑs ]
i
i
Ωs−1
ϑs (ξs−1 )ps (ξs−1
, xs )
i=1
i=1
2

N
[h̃s,t (xs , ·)] gs (xs )dxs ,
× ψγ,t|T
Z
N
i
X
ωs−1
i
i
=
ωs (ξs−1
, xs )q(ξs−1
, xs )
Ω
s−1
i=1
2

N
[h̃s,t (xs , ·)] gs (xs )dxs ,
× ψγ,t|T
 N 
−1 N
,
= φN
φχ,s−1 fs−1,t
χ,s−1 [ϑs ]
−1
φN
χ,s−1 [ϑs ]

where
N
fs−1,t
(xs−1 ) :=

Z

2

N
[h̃s,t (xs , ·)] gs (xs )dxs .
q(xs−1 , xs )ωs (xs−1 , xs ) ψγ,t|T
P

First note that φN
χ,s−1 [ϑs ] −→N →∞ φχ,s−1 [ϑs ] and write
 N 
N
N
φN
χ,s−1 fs−1,t − φχ,s−1 [fs−1,t ] ≤ As,t + Bs,t ,

N
N
N
N
N
where AN
s,t := |φχ,s−1 [fs−1,t ] − φχ,s−1 [fs−1,t ]| and Bs,t := |φχ,s−1 [fs−1,t ] − φχ,s−1 [fs−1,t ]|.
j
j
i
i
N
As (ωs−1
, ξs−1
)N
i=1 and (ω̌t|T , ξ̌t|T )j=1 are independent,
"N
#
Z
h
i
i
X ωs−1
 N
N
i
E As,t ≤ |ωs |∞ |gs |∞ E
[h̃s,t ](xs ) dxs ,
q(ξs−1
, xs )E ∆ψγ,t|T
Ω
s−1
i=1

19

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

N
N
2
where ∆ψγ,t|T
[h̃s,t ](xs ) := (ψγ,t|T
[h̃s,t (xs , ·)])2 − ψγ,t|T
[h̃s,t (xs , ·)]. Following the same steps
as in (31), there exists Dt|T such that

h
i
√
2
N
E ∆ψγ,t|T
[h̃s,t ](xs ) ≤ 2Dt|T osc (h) / N ,

which yields
E AN
s,t




#
Z
N
i
X
√
ωs−1
i
≤ 2 osc (h) |ωs |∞ |gs |∞ DT |t E
q(ξs−1
, xs )dxs / N ,
Ωs−1
i=1
√
≤ 2 osc (h)2 |ωs |∞ |gs |∞ DT |t / N
"

2



P
2
N
and E AN
s,t −→N →∞ 0. On the other hand, as osc (fs−1,t ) ≤ osc (h) |ωs |∞ |gs |∞ , Bs,t −→N →∞
0 by Proposition 8. Finally, the tightness condition (30) holds since |UN,i | ≤ N −1/2 |ωs |∞ osc (h).
Note that,
Z

P

N −1 Ωs −→N →∞ φχ,s−1

q(·, xs )gs (xs )dxs /φχ,s−1 [ϑs ] .

Therefore (23) holds with
Γ̃s,t|T

i
h
h̃s,t =
=

φ2χ,s−1 [ϑs ]

R
φ2χ,s−1 q(·, xs )gs (xs )dxs
φ2χ,s−1

(

Γ̃s−1,t|T [Hs,t ] φχ,s−1 [fs−1,t ]
+
φ2χ,s−1 [ϑs ]
φχ,s−1 [ϑs ]

)

,

Γ̃s−1,t|T [Hs,t ]
φ
[f
]φ
[ϑ ]
 + 2 χ,s−1R s−1,t χ,s−1 s  ,
R
q(·, xs )gs (xs )dxs
φχ,s−1 q(·, xs )gs (xs )dxs

where, by induction assumption,
Γ̃s−1,t|T [Hs,t ] = Γχ,s−1

Z


ψγ,t|T (dxt )Hs,t (·, xt )
+ Γ̌γ,t|T

Z


φχ,s−1 (dxs−1 )Hs,t (xs−1 , ·) .

The proof is completed upon noting that
R
R
φχ,s−1 (dxs−1 )q(xs−1 , xs )gs (xs )h̃s,t (xs , ·)dxs
φχ,s−1 (dxs−1 )Hs (xs−1 , ·)
 =

R
R
,
φχ,s−1 q(·, xs )gs (xs )dxs
φχ,s−1 q(·, xs )gs (xs )dxs
Z
= φχ,s (dxs )h̃s,t (xs , ·)
and, by Proposition 10,
Γχ,s−1

"

#
ψγ,t|T (dxt )Hs,t (·, xt )
φ
[f
]φ
[ϑ ]
 + 2 χ,s−1R s−1,t χ,s−1 s 
R
φχ,s−1 q(·, xs )gs (xs )dxs
φχ,s−1 q(·, xs )gs (xs )dxs
Z

= Γχ,s
ψγ,t|T (dxt )h̃s,t (·, xt ) .
R

20

Nguyen et al.

5.5

Two-filter approximations of marginal smoothing distributions

Proof of Theorem 5

Write h̃s,T = h − φχ,s|T (h). Note that
√

N

N
i
X
ω̃s|T
i=1

where UN,ℓ := N

−1/2

Ω̃s|T

N

−1 X
i
) = Ω̃s|T /N
UN,i ,
h̃s,T (ξ˜s|T

ℓ
ℓ
h̃s,T (ξ˜s|T
).
ω̃s|T

i=1

Set, for i ∈ {1, . . . , N },

n
ℓ
ℓ
)}iℓ=1 , {(ωuℓ , ξuℓ )}N
, ξ̃s|T
GN,i := σ {(ω̃s|T
ℓ=1 , u = 0, . . . , s − 1,

ℓ
ℓ
{(ω̌v|T
, ξˇv|T
)}N
ℓ=1 , v = s + 1, . . . , T

By the proof of Theorem 2,
N

−1

P

Ω̃s|T −→N →∞

o

.


−1
q [2] (·, x)gs (x)dx ⊙ γs+1
i
h
.
−1
φχ,s−1 ⊗ ψs+1|T ϑ̃s|T ⊙ γs+1

φχ,s−1 ⊗ ψs+1|T

R

PN
The proof therefore amounts to establish a CLT for
ℓ=1 UN,ℓ and then to use Slutsky
PN
Lemma. The limit distribution of ℓ=1 UN,ℓ is again obtained using the invariance principle
for triangular array of dependent random variables derived in [7]. As
N
X
i=1

E [ UN,i | GN,i−1 ]
√
= N

PN

i,j=1

R [2]
j
j
−1
i
i
ωs−1
ω̌s+1|T
q (·; xs )gs (xs )h̃s,T (xs )dxs ⊙ γs+1
(ξs−1
, ξˇs+1|T
)
,
PN
j
j
−1 ˇj
i
i
ˇ
i,j=1 ωs−1 ω̌s+1|T γs+1 (ξs+1|T )ϑ̃s|T (ξs−1 , ξs+1|T )

it follows from Theorems 1 and 4 that
N
X
i=1

Using that



P

E [ UN,i | GN,i−1 ] −→N →∞ N 0, 

φχ,s|T [h̃s,T ] =

i=1

−1
φχ,s−1 ⊗ ψs+1|T [ϑ̃s|T ⊙ γs+1
]


2  .

i
−1
q [2] (·; x)gs (x)h̃s,T (x)dx ⊙ γs+1
R

=0,
−1
φχ,s−1 ⊗ ψs+1|T
q [2] (·; x)gs (x)dx ⊙ γs+1

φχ,s−1 ⊗ ψs+1|T

Theorem 1 yields
N
X

Σs [h̃s,T ]



hR

2

E [ UN,i | GN,i−1 ] =
R
!2
j
j
−1 ˇj
i
i
ωs−1
ω̌s+1|T
γs+1
(ξs+1|T ) q [2] (ξs−1
, ξˇs+1|T
; x)gs (x)h̃s,T (x)
PN
j
j
−1 ˇj
i
i
i,j=1 ωs−1 ω̌s+1|T γs+1 (ξs+1|T )ϑ̃s|T (ξs−1 , ξ̌s+1|T )
i 2
hR

−1
[2]
φ
⊗
ψ
q
(·;
x)g
(x)
h̃
(x)dx
⊙
γ
χ,s−1
s
s,T
s+1|T
s+1
P
 =0.
−→N →∞ 
−1
φχ,s−1 ⊗ ψs+1|T [ϑ̃s|T ⊙ γs+1 ]
PN

i,j=1

21

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

Similarly, using again Theorem 1,
N
X
i=1

 2
 P
E UN,i
GN,i−1 −→N →∞

φχ,s−1 ⊗ ψs+1|T

hR

−1
ω̃s|T (·; x)q [2] (·; x)gs (x)h̃2s,T (x)dx ⊙ γs+1

−1
φχ,s−1 ⊗ ψs+1|T [ϑ̃s|T ⊙ γs+1
]

Since under A2, |UN,i | ≤ N −1/2 ω̃s|T
N
X
i=1

∞

osc (h), for any ǫ > 0,

 P
 2
E UN,i
1{|UN,i | ≥ ǫ} GN,i−1 −→N →∞ 0 ,

which concludes the proof.

22

i

.

Nguyen et al.

A

Two-filter approximations of marginal smoothing distributions

Exponential deviation inequalities for the forward filter and the backward information filter

The following result is proved in [6].
Lemma 7. Assume that aN , bN , and b are random variables defined on the same probability
space such that there exist positive constants β, B, C, and M satisfying
(i) |aN /bN | ≤ M , P-a.s. and b ≥ β, P-a.s.,
2

(ii) For all ǫ > 0 and all N ≥ 1, P [|aN | > ǫ] ≤ Be−CN (ǫ/M) ,
2

(iii) For all ǫ > 0 and all N ≥ 1, P [|bN − b| > ǫ] ≤ Be−CN ǫ .
Then, for all ε > 0,
P



(
2 )


aN
ǫβ
.
> ǫ ≤ B exp −CN
bN
2M

Proposition 8 provides an exponential deviation inequality for the forward filter and is
proved in [6].
Proposition 8. Assume that A1 and A2 hold for some T > 0. Then, for all s ≥ 1, there
exist 0 < Bs , Cs < ∞ such that for all N ≥ 1, ǫ > 0, and all h ∈ Fb (X, X ),
!
N
X
2
2
ωsi h(ξsi ) − φχ,s [h] ≥ ǫ ≤ Bs e−Cs N ǫ / osc(h) .
P Ω−1
s
i=1

Proposition 9 provides an exponential inequality for the backward information filter
ψγ,t|T and its unnormalized approximation. Its proof is similar to the proof [6, Theorem 5]
and is omitted.
Proposition 9. Assume that A1 and A3 hold for some T > 0. Then, for all 0 ≤ t ≤ T ,
there exist 0 < Bt|T , Ct|T < ∞ such that for all N ≥ 1, ǫ > 0, and all h ∈ Fb (X, X ),
P

B

"

−1
Ω̌t|T

N
X
i=1

i
i
)
h(ξˇt|T
ω̌t|T

#

− ψγ,t|T [h] ≥ ǫ ≤ Bt|T e−Ct|T N ǫ

2

/ osc(h)2

.

Asymptotic normality of the forward filter and the
backward information filter

Proposition 10 provides a CLT for the weighted particles {(ωsi , ξsi )}N
i=1 approximating the
filtering distribution φχ,s and is proved for instance in [4].
Proposition 10. Assume that A1 and A2 hold for some T > 0. Then, for all 0 ≤ s ≤ T
and all h ∈ Fb (X, X ),
N

1/2

N
X
ωsi
h(ξsi ) − φχ,s [h]
Ω
s
i=1

!

D

−→N →∞ N (0, Γχ,s [h − φχ,s [h]]) ,

23

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

where
ρ0 (dx0 )ω02 (x0 )h2 (x0 )
and for all s ≥ 1 ,
2
R
ρ0 (dx0 )ω0 (x0 )

R
Γχ,s−1 q(·, xs )gs (xs )h(xs )dxs

R
Γχ,s [h] :=
φ2χ,s−1 q(·, xs )gs (xs )dxs

R
φχ,s−1 ωs (·, xs )q(·, xs )gs (xs )h2 (xs )dxs φχ,s−1 [ϑs ]

R
+
.
φ2χ,s−1 q(·, xs )gs (xs )dxs

Γχ,0 [h] :=

R

j
j
Proposition 11 provides a CLT for the weighted particles {(ω̌t|T
, ξ̌t|T
)}N
j=1 approximating
the backward information filter. Its proof follows the same lines as the proof of Proposition 10
and is omitted for brevity.

Proposition 11. Assume that A1 and A3 hold. Then, for all 0 ≤ t ≤ T and all h ∈
Fb (X, X ),


N ω̌ j
X


t|T
D
j
N 1/2 
h(ξˇt|T
) − ψγ,t|T [h] −→N →∞ N 0, Γ̌γ,t|T h − ψγ,t|T [h] ,
Ω̌t|T
j=1
where

ρ̌T (dxT )ω̌T2 |T (xT )h2 (xT )
and for all t ≤ T − 1 ,
R
2
ρ̌T (dxT )ω̌T |T (xT )

R
−1
Γ̌γ,t+1|T
γt (xt )gt (xt )q(xt , ·)γt+1
(·)h(xt )dxt

R
[h] :=
−1
2
ψγ,t+1|T
γt (xt )gt (xt )q(xt , ·)γt+1
(·)dxt



R
−1
−1
ψγ,t+1|T
ω̌t (xt , ·)q(xt , ·)gt (xt )γt (xt )γt+1
(·)h2 (xt )dxt ψγ,t+1|T ϑt|T γt+1
R

.
+
−1
2
γt (xt )gt (xt )q(xt , ·)γt+1
ψγ,t+1|T
(·)dxt

Γ̌γ,T |T [h] :=

Γ̌γ,t|T

R

References

[1] M. Briers, A. Doucet, and S. Maskell. Smoothing algorithms for state-space models.
Annals Institute Statistical Mathematics, 62(1):61–89, 2010.
[2] O. Cappe. Online EM algorithm for hidden Markov models. Journal of Computational
and Graphical Statistics, 20(73):728–749, 2011.
[3] O. Cappé, E. Moulines, and T. Rydén. Inference in Hidden Markov Models. Springer,
2005.
[4] P. Del Moral. Feynman-Kac Formulae. Genealogical and Interacting Particle Systems
with Applications. Springer, 2004.
[5] P. Del Moral, A. Doucet, and S. Singh. A Backward Particle Interpretation of FeynmanKac Formulae. ESAIM M2AN, 44(5):947–975, 2010.

24

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

[6] R. Douc, A. Garivier, E. Moulines, and J. Olsson. Sequential Monte Carlo smoothing
for general state space hidden Markov models. Ann. Appl. Probab., 21(6):2109–2145,
2011.
[7] R. Douc and E. Moulines. Limit theorems for weighted samples with applications to
sequential Monte Carlo methods. Ann. Statist., 36(5):2344–2376, 2008.
[8] R. Douc, E. Moulines, and D.S. Stoffer. Nonlinear time series: theory, methods and
applications with R examples. CRC Press, 2014.
[9] A. Doucet, N. de Freitas, and N. Gordon, editors. Sequential Monte Carlo methods in
practice. Springer, 2001.
[10] A. Doucet, S. Godsill, and C. Andrieu. On sequential Monte-Carlo sampling methods
for Bayesian filtering. Stat. Comput., 10:197–208, 2000.
[11] C. Dubarry and S. Le Corff. Non-asymptotic deviation inequalities for smoothed additive functionals in nonlinear state-space models. Bernoulli, 19(5B):2222–2249, 2013.
[12] P. Fearnhead, D. Wyncoll, and J. Tawn. A sequential smoothing algorithm with linear
computational cost. Biometrika, 97(2):447–464, 2010.
[13] S. J. Godsill, A. Doucet, and M. West. Monte Carlo smoothing for non-linear time
series. J. Am. Statist. Assoc., 50:438–449, 2004.
[14] N. Gordon, D. Salmond, and A.F. Smith. Novel approach to nonlinear/non-Gaussian
bayesian state estimation. IEE Proc. F, Radar Signal Process, 140:107–113, 1993.
[15] M. Hürzeler and H. R. Künsch. Monte Carlo approximations for general state-space
models. J. Comput. Graph. Statist., 7:175–193, 1998.
[16] P.E. Jacob, L.M. Murray, and S. Rubenthaler. Path storage in the particle filter.
Statistics and Computing, pages 1–10, 2013.
[17] N. Kantas, A. Doucet, S.S. Singh, J. Maciejowski, and N. Chopin. On particle methods
for parameter estimation in state-space models. Statist. Sci., 30(3):328–351, 2015.
[18] G. Kitagawa. Monte-Carlo filter and smoother for non-Gaussian nonlinear state space
models. J. Comput. Graph. Statist., 1:1–25, 1996.
[19] H. R. Künsch. Recursive Monte Carlo filters: Algorithms and theoretical analysis. Ann.
Statist., 33(5):1983–2021, 2005.
[20] S. Le Corff and G. Fort. Convergence of a particle-based approximation of the block
online Expectation Maximization algorithm. ACM Transactions on Modeling and Computer Simulation, 23(1):2, 2013.
[21] S. Le Corff and G. Fort. Online Expectation Maximization based algorithms for inference in hidden Markov models. Electronic Journal of Statistics, 7:763–792, 2013.
[22] G. Mongillo and S. Deneve. Online learning with hidden Markov models. Neural
Computation, 20(7):1706–1716, 2008.

25

Nguyen et al.

Two-filter approximations of marginal smoothing distributions

[23] J. Olsson and J. Westerborn. Efficient particle-based online smoothing in general hidden
Markov models: the PaRIS algorithm. ArXiv:1412.7550, 2015.
[24] M. K. Pitt and N. Shephard. Filtering via simulation: Auxiliary particle filters. J. Am.
Statist. Assoc., 94(446):590–599, 1999.
[25] G. Poyiadjis, A. Doucet, and S.S Singh. Particle approximations of the score and
observed information matrix in state space models with application to parameter estimation. Biometrika, 98:65–80, 2011.

26

