The comparison of the selection rules #
By Lemma 4 of the paper, the joint distribution of the reference x_{1:T} ∼ π and of the output
x̃_{1:T} 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 𝐱, the indices (b, l) have the probabilities pathProb of the backward Markov chain
pairChain. Expectations under this joint distribution are therefore expectations, under the
distribution of 𝐱, of the expectations E_𝐱 given 𝐱, which are finite sums. This identity is
proved here for integrable functions. For the quantities of Section 4, the expectations E_𝐱 are
the following.
E_𝐱{f(x_t) f(x̃_t)}is the expected productQ_t(φ)ofφ(i) = f(x_t^i).E_𝐱{f(x_t, x_{t+1}) f(x̃_t, x̃_{t+1})}isexpprodPairofφ(i, j) = f(x_t^i, x_{t+1}^j).P_𝐱(x̃_t = x_t)is the sum ofQ_t(1_S)over the classesSof indices with equal particles.
Theorem 1, Corollary 1, and Propositions 2 and 3 then follow from the orderings of
Finite/Ordering at each value of 𝐱. Proposition 4 follows from the form of pathProb when the
transition densities do not depend on the previous state.
If the positions v i of the particles are pairwise distinct, the sum of Q_t(1_S) over the
classes S of indices whose particles are equal is ∑_i Q_t(1_{i}).
For kernels which satisfy the hypotheses of Algorithm 1, the probability that the indices of the
output and of the reference differ at the time s.castSucc or at the time s.succ is
1 - ∑_j P_𝐱(b_{t+1} = l_{t+1} = j) ∑_i B_t(i|j) K_{t,j,j}(i, i).
Under CM-BS with two particles, if B_s(i|j) = w_s(i) for all s, i, and j, where the
w_t are probability vectors and w_T is the vector of final weights, the probability of the
indices b of the reference and l of the output is w_T(b_T) ∏_s w_s(b_s) times
∏_t F_{w_t}(b_t, l_t).
For kernels which satisfy the hypotheses of Algorithm 1, the probabilities pathProb of the
backward Markov chain on pairs of indices are nonnegative.
With at least one particle, for kernels which satisfy the hypotheses of Algorithm 1, the
probabilities pathProb of the backward Markov chain on pairs of indices sum to one.
With at least one particle, for measurable kernels which satisfy the hypotheses of Algorithm 1,
the backward Markov chain pairChain K on pairs of indices is a Markov kernel.
For kernels which satisfy the hypotheses of Algorithm 1, 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 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 1, the expectation of an
integrable function g of the reference x_{1:T} ∼ π and of the output x̃_{1:T} of Algorithm 1
is the expectation, under the distribution of the particle positions 𝐱 under π̄, of
E_𝐱{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 1, if φ(x)² is integrable
under π, then φ(x) φ(x̃) is integrable under the joint distribution of the reference and the
output: both have the distribution π.
With at least one particle, the kernels of each selection rule satisfy the hypotheses of Algorithm 1 at all particle positions.
For measurable kernels which satisfy the hypotheses of Algorithm 1, if f(x_t)² is integrable
under π, then E{f(x_t) f(x̃_t)} is the expectation, under the distribution of the particle
positions under π̄, of the expected product Q_t(φ) with φ(i) = f(x_t^i), which is
integrable.
For measurable kernels which satisfy the hypotheses of Algorithm 1, if f(x_t, x_{t+1})² is
integrable under π, then E{f(x_t, x_{t+1}) f(x̃_t, x̃_{t+1})} is the expectation, under the
distribution of the particle positions under π̄, of expprodPair of
φ(i, j) = f(x_t^i, x_{t+1}^j), which is integrable.
For measurable kernels which satisfy the hypotheses of Algorithm 1, the probability of a
measurable set S of pairs (x, x̃) is the expectation, under the distribution of the particle
positions under π̄, of P_𝐱((x, x̃) ∈ S), which is integrable.
For measurable kernels which satisfy the hypotheses of Algorithm 1, the update rate
P(x̃_t ≠ x_t) is the expectation, under the distribution of the particle positions under π̄, of
1 - ∑_S Q_t(1_S), where S ranges over the classes of indices whose particles at time t are
equal. This function of the particle positions is integrable.
Theorem 1, 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, 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, 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.
The set of particle positions at which the particles at the time s.castSucc are pairwise
distinct and the particles at the time s.succ are pairwise distinct is measurable.
For measurable kernels which satisfy the hypotheses of Algorithm 1, if the particles at the
time s.castSucc and those at the time s.succ are almost surely pairwise distinct under π̄, the
probability P{(x̃_t, x̃_{t+1}) ≠ (x_t, x_{t+1})} is the expectation, under the distribution of the
particle positions under π̄, of 1 - ∑_j P_𝐱(b_{t+1} = l_{t+1} = j) ∑_i B_t(i|j) K_{t,j,j}(i, i),
which is integrable.
Corollary 1, second part: if the particles at the time t and those at the time t + 1
are almost surely pairwise distinct under π̄, 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 is a measurable function of the particle positions.
If m_{s+1}(x, ·) ≥ ε m_{s+1}(x', ·) for all x, x' ∈ X and s, with ε ≤ 1, then
B_s(i|j) ≥ ε W_s^i.
Proposition 2: 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 π̄. This expectation is at most (1 - ε)^{T-t} if
m_{s+1}(x, ·) ≥ ε m_{s+1}(x', ·) for all x, x' ∈ X and s ∈ [T - 1].
For measurable kernels which satisfy the hypotheses of Algorithm 1, the expectation of a
bounded measurable function G of the particle positions, the indices of the reference, and the
indices of the output, under x_{1:T} ∼ π and Algorithm 1, is the expectation, under the
distribution of the particle positions under π̄, of
E_𝐱{G(𝐱, b, l)} = ∑_{b, l} pathProb(b, l) G(𝐱, b, l), which is integrable.
Proposition 3: if the particles at the time t are almost surely pairwise distinct under
π̄, then, for M-BS and CM-BS, the gains γ_t(j, j') are nonnegative and the update rate at the
time t exceeds that of FM-BS by at least E{γ_t(b_{t+1}, l_{t+1})}.
If the transition densities m_{s+1}(x, x') do not depend on x, then B_s(i|j) = W_s^i.
Proposition 4: with two particles, if the transition densities m_{s+1}(x, x') do not
depend on x, then, under CM-BS and conditionally on the particle positions and the indices of the
reference, the indices of the output are independent, with l_t ∼ F_{W_t}(b_t, ·).