The validity of Algorithm 1 #
The joint distribution of the reference trajectory x_{1:T} ∼ π and of the variables generated by
steps (a) and (b) of Algorithm 1 of the paper is computed here. Integrals with respect to it are
integrals, with respect to the product of μ on the particle positions, of a sum, over the
ancestor indices and the final index b_T, of the density (6) times the integrand evaluated at the
trajectory traced back from b_T.
Lemma 3 of the paper follows. By its first part, (x, a, b_T) ∼ π̄, with x_{1:T} the trajectory
traced back from b_T, which is stated as an identity of joint distributions. By its second part,
under π̄, the conditional distribution of (a, b_T) given x is the product of W_T and of the
B_t(·|n). This proof is not ours and is provided for completeness and ease of reference. The
first part of Lemma 3 is due to Andrieu et al. (2010), in the form of Chopin and Singh (2015,
Section 2.3). The second part is the observation of Chopin and Singh (2015, proof of
Proposition 9).
With the variables of steps (c) and (d) of Algorithm 1, Lemma 4 follows: the particle positions
have their distribution under π̄ and, given them, the indices (b, l) of the reference and of
the output form the backward Markov chain pairChain K, both with the backward pass of
Algorithm 1 and, if K_{t,j,j'}(i, ·) = B_t(·|j') for j ≠ j', with its usual implementation.
The sums over the ancestor indices are those of Algorithm/Lineage. As for Lemma 3, the identity
of joint distributions includes the reference trajectory, which is (x_1^{b_1}, …, x_T^{b_T}).
Proposition 1 then follows: under the hypotheses of Algorithm 1, pairChain K does not change
when b and l are exchanged. The joint distribution of the reference trajectory and of the
output (x_1^{l_1}, …, x_T^{l_T}) therefore does not change when the two are exchanged, so that
the kernel of Algorithm 1 is reversible with respect to π and hence leaves π invariant.
The sum over the sequences of indices traced back from their final index is the sum over the final index.
The numerator of the target density is a measurable function of the trajectory.
The density of step (b) of Algorithm 1 is a measurable function of the particle positions.
The forward pass of Algorithm 1 is an s-finite kernel.
The target distribution is a probability measure.
The joint distribution of the variables of Algorithm 1 is an s-finite kernel.
The joint distribution of the variables of Algorithm 1 with the usual implementation of Algorithm 1.d is an s-finite kernel.
Integrals with respect to the joint distribution of x_{1:T} ∼ π and of the variables
(b, (y, a)) of steps (a) and (b) of Algorithm 1 are integrals over the particle positions of
sums, over the ancestor indices and the sequences b traced back from their final index, of the
density (6) times the integrand evaluated at the reference trajectory (x_1^{b_1}, …, x_T^{b_T}).
Integrals with respect to the extended distribution π̄ are integrals over the particle
positions of sums over the ancestor indices and the final index of the density (6) times the
integrand.
The trajectory traced back from the final index is a measurable function of the particle positions, the ancestor indices, and the final index.
The joint distribution of x_{1:T} ∼ π and of the variables of steps (a) and (b) of
Algorithm 1, arranged as (x, (y, a, b_T)), is that of the trajectory traced back from b_T and
of (y, a, b_T) ∼ π̄: the variables (y, a, b_T) have the distribution π̄, with x_{1:T} the
trajectory traced back from b_T (first part of Lemma 3).
The variables (y, a, b_T) of steps (a) and (b) of Algorithm 1 started from x_{1:T} ∼ π
have the extended distribution π̄ (first part of Lemma 3).
With at least one particle, the uniform distribution of the indices of the reference is a probability measure.
With at least one particle, the extended distribution is a probability measure.
The probabilities W_T^{b_T} ∏_{t,n} B_t(a_t^n|n) of the final index and the ancestor indices
given the particle positions, as extended nonnegative real numbers, sum to one.
Under π̄, conditionally on the particle positions, the indices b_T and a_t^n are
independent, with the distributions W_T and B_t(·|n) (second part of Lemma 3).
Integrals with respect to the joint distribution of x_{1:T} ∼ π, of the variables
(b, (y, a)) of steps (a) and (b) of Algorithm 1, and of a variable c drawn from a kernel η
given these, are integrals over the particle positions of sums, over the ancestor indices and the
final index b_T, of the density (6) times the integral with respect to η, at the indices b
traced back from b_T and at the reference trajectory (x_1^{b_1}, …, x_T^{b_T}).
The probability pathProb W_T B K b l of the indices b of the reference and l of the output
is a measurable function of the particle positions.
Integrals with respect to the backward Markov chain on pairs of indices are sums over the
pairs, weighted by pathProb W_T B K.
The backward Markov chain on pairs of indices is an s-finite kernel.
The trajectory (x_1^{l_1}, …, x_T^{l_T}) of the particles with the indices l is a
measurable function of the particle positions and of l.
The map (y, (b, l)) ↦ (x, (y, (b, l))) which adds the trajectory (x_1^{b_1}, …, x_T^{b_T})
of the particles with the indices b is measurable.
Under π̄, conditionally on the particle positions y, (a, b_T) has the probabilities
W_T^{b_T} ∏_{t,n} B_t(a_t^n|n) (second part of Lemma 3): if the expectation of T(a, b_T)
under these probabilities is S, the integral of T against the density (6) at y is that
of S.
The joint distribution of x_{1:T} ∼ π, of the particle positions, and of the indices of the
reference and of the output of Algorithm 1, arranged as (x, (y, b, l)), is that of the trajectory
(x_1^{b_1}, …, x_T^{b_T}) and of (y, b, l), where y has its distribution under π̄ and,
given y, (b, l) is the backward Markov chain pairChain K (Lemma 4).
The joint distribution of x_{1:T} ∼ π, of the particle positions, and of the indices of the
reference and of the output of Algorithm 1 with the usual implementation of Algorithm 1.d,
arranged as (x, (y, b, l)), is that of Algorithm 1 (map_target_compProd_algLaw_traced) if
K_{t,j,j'}(i, ·) = B_t(·|j') for j ≠ j' (Lemma 4).
The particle positions and the indices of the reference and of the output of Algorithm 1
started from x_{1:T} ∼ π have the distribution of the particle positions under π̄ followed by
the backward Markov chain pairChain K (Lemma 4).
The same holds with the usual implementation of Algorithm 1.d if K_{t,j,j'}(i, ·) = B_t(·|j')
for j ≠ j' (Lemma 4).
Under the hypotheses of Algorithm 1, the backward Markov chain on pairs of indices does not change when the indices of the reference and of the output are exchanged.
For measurable kernels which satisfy the hypotheses of Algorithm 1, the kernel of Algorithm 1 is a Markov kernel.
The joint distribution of x_{1:T} ∼ π and of the output of Algorithm 1 is that of the
trajectories (x_1^{b_1}, …, x_T^{b_T}) and (x_1^{l_1}, …, x_T^{l_T}), where the particle
positions have their distribution under π̄ and, given them, (b, l) is the backward Markov
chain pairChain K.
For kernels K_T and K_{t,j,j'} as in Algorithm 1, the Markov kernel defined by
Algorithm 1 is reversible with respect to π (Proposition 1).
For kernels K_T and K_{t,j,j'} as in Algorithm 1, the Markov kernel defined by
Algorithm 1 leaves π invariant (Proposition 1).