The comparison of the selection rules for Algorithm S1 #
By Proposition S2 of the supplementary material, Theorem 1, Corollary 1, and Propositions 2 and 3
of the main text hold for Algorithm S1, with the probabilities (S3) and with the density (S4) in
place of ฯฬ. By the analogue of Lemma 4 for Algorithm S1 (map_target_compProd_algLaw), the
reference and the output of Algorithm S1 have the joint distribution of the trajectories
(x_1^{b_1}, โฆ, x_T^{b_T}) and (x_1^{l_1}, โฆ, x_T^{l_T}), where (๐ฑ, a) has its distribution
under the density (S4) and, given (๐ฑ, a), the indices (b, l) have the probabilities pathProb
of the backward Markov chain pairChain K. The proofs of Algorithm/Comparison then apply with
(๐ฑ, a) in place of ๐ฑ, and with P_{๐ฑ,a} and E_{๐ฑ,a} in place of P_๐ฑ and E_๐ฑ.
For kernels which satisfy the hypotheses of Algorithm S1, integrals with respect to the backward
Markov chain pairChain K are the sums over the pairs (b, l) weighted by pathProb.
The map which sends the particle positions, the ancestor indices, and the pair (b, l) to the
trajectories (x_1^{b_1}, โฆ, x_T^{b_T}) and (x_1^{l_1}, โฆ, x_T^{l_T}) is measurable.
For measurable kernels which satisfy the hypotheses of Algorithm S1, the expectation of an
integrable function g of the reference x_{1:T} โผ ฯ and of the output xฬ_{1:T} of Algorithm S1
is the expectation, under the distribution of the particle positions and the ancestor indices
(๐ฑ, a) under the density (S4), of
E_{๐ฑ,a}{g(x, xฬ)} = โ_{b, l} pathProb(b, l) g((x_t^{b_t})_t, (x_t^{l_t})_t), which is integrable.
For measurable kernels which satisfy the hypotheses of Algorithm S1, if ฯ(x)ยฒ is integrable
under ฯ, then ฯ(x) ฯ(xฬ) is integrable under the joint distribution of the reference and the
output, because both have the distribution ฯ.
For measurable kernels which satisfy the hypotheses of Algorithm S1, if f(x_t)ยฒ is integrable
under ฯ, then the expected product Q_t(ฯ), with ฯ(i) = f(x_t^i), is integrable under the
distribution of the particle positions and the ancestor indices under the density (S4), with
expectation E{f(x_t) f(xฬ_t)}.
For measurable kernels which satisfy the hypotheses of Algorithm S1, if f(x_t, x_{t+1})ยฒ is
integrable under ฯ, then expprodPair at ฯ(i, j) = f(x_t^i, x_{t+1}^j) is integrable under the
distribution of the particle positions and the ancestor indices under the density (S4), with
expectation E{f(x_t, x_{t+1}) f(xฬ_t, xฬ_{t+1})}.
For measurable kernels which satisfy the hypotheses of Algorithm S1 and a measurable set S of
pairs (x, xฬ), P_{๐ฑ,a}((x, xฬ) โ S) is integrable under the distribution of the particle
positions and the ancestor indices under the density (S4), with expectation P((x, xฬ) โ S).
For measurable kernels which satisfy the hypotheses of Algorithm S1, the function
1 - โ_S Q_t(1_S) of the particle positions and the ancestor indices, where S ranges over the
classes of indices whose particles at time t are equal, is integrable under their distribution
under the density (S4), with expectation the update rate P(xฬ_t โ x_t).
Theorem 1 for Algorithm S1 (Proposition S2), first part: for x_{1:T} โผ ฯ and a function
f with f(x_t)ยฒ integrable, E{f(x_t) f(xฬ_t)} is nonincreasing from AT to BS, FM-BS, and
M-BS, and is at most as large under CM-BS as under FM-BS.
Theorem 1 for Algorithm S1 (Proposition S2), second part: the update rates P(xฬ_t โ x_t)
are nonincreasing from M-BS to FM-BS, BS, and AT, and are at least as large under CM-BS as under
FM-BS.
Corollary 1 for Algorithm S1 (Proposition S2), first part: for x_{1:T} โผ ฯ and a function
f with f(x_t, x_{t+1})ยฒ integrable, E{f(x_t, x_{t+1}) f(xฬ_t, xฬ_{t+1})} is nonincreasing from
AT to BS, FM-BS, and M-BS.
For measurable kernels which satisfy the hypotheses of Algorithm S1, if the particles at time
t = s.castSucc and those at time t + 1 = s.succ are almost surely pairwise distinct under the
density (S4), the function 1 - โ_j P_{๐ฑ,a}(b_{t+1} = l_{t+1} = j) โ_i B_t(i|j) K_{t,j,j}(i, i) of
the particle positions and the ancestor indices is integrable under their distribution under the
density (S4), with expectation P{(xฬ_t, xฬ_{t+1}) โ (x_t, x_{t+1})}.
Corollary 1 for Algorithm S1 (Proposition S2), second part: if the particles at time t and
those at time t + 1 are almost surely pairwise distinct under the density (S4), the probabilities
of {(xฬ_t, xฬ_{t+1}) โ (x_t, x_{t+1})} are nonincreasing from M-BS to FM-BS, BS, and AT, and are
at least as large under CM-BS as under FM-BS.
The Dobrushin coefficient of B_t, with the probabilities (S3), is a measurable function of the
particle positions and the ancestor indices.
If m_{s+1}(x, ยท) g_{s+1}(x, ยท) โฅ ฮต m_{s+1}(x', ยท) g_{s+1}(x', ยท) for all x, x' โ X and s,
with ฮต โค 1, then B_s(i|j) โฅ ฮต W_s^i for the probabilities (S3).
Proposition 2 for Algorithm S1 (Proposition S2): the update rate P(xฬ_t โ x_t) is at least
as large under FM-BS as under BS, by at most E(โ_{s=t}^{T-1} ฮฒ_s) under the density (S4). This
expectation is at most (1 - ฮต)^{T-t} if, for some ฮต โ (0, 1],
m_{s+1}(x, ยท) g_{s+1}(x, ยท) โฅ ฮต m_{s+1}(x', ยท) g_{s+1}(x', ยท) for all x, x' โ X and
s โ [T - 1].
For measurable kernels which satisfy the hypotheses of Algorithm S1 and a bounded measurable
function G of the particle positions, the ancestor indices, the indices of the reference, and the
indices of the output, E_{๐ฑ,a}{G((๐ฑ, a), b, l)} = โ_{b, l} pathProb(b, l) G((๐ฑ, a), b, l) is
integrable under the distribution of the particle positions and the ancestor indices under the
density (S4), with expectation that of G under x_{1:T} โผ ฯ and Algorithm S1.
Proposition 3 for Algorithm S1 (Proposition S2): if the particles at time t are almost
surely pairwise distinct under the density (S4), then, for M-BS and CM-BS, the gains ฮณ_t(j, j')
with the probabilities (S3) are nonnegative and the update rate at time t exceeds that of FM-BS
by at least E{ฮณ_t(b_{t+1}, l_{t+1})}.