CSMC with ancestor sampling of the reference #
Given the reference trajectory x_{1:T}, resampling schemes r_t, and kernels K_T and
K_{t,j,j'} which are functions of the particle positions and of the ancestor indices, Algorithm S1
of the supplementary material consists of the following steps.
(a) Draw b_1 uniformly on [N], set x_1^{b_1} = x_1, and draw x_1^i ∼ m_1 for i ≠ b_1.
(b) For t = 1, …, T - 1, draw c ∼ B_t(·|x_{t+1}), and then (b_{t+1}, a_t) with probabilities
proportional to r_t(a_t) on the set where a_t^{b_{t+1}} = c. Set
x_{t+1}^{b_{t+1}} = x_{t+1} and draw x_{t+1}^i ∼ m_{t+1}(x_t^{a_t^i}, ·) for i ≠ b_{t+1}.
(c) Run steps (c) to (e) of Algorithm 1.
In Lemma S1, c may also be drawn in Algorithm S1.b from the kernel K_{t,j,j} of one of the six
selection rules, with B_t(·|x_{t+1}) in place of B_t(·|j), started from b_t. In the forward
pass forwardPass r C, c is drawn from C(B_t(·|x_{t+1}))(b_t, ·), for a function C from
probability vectors to kernels. With the Gibbs kernel, this is Algorithm S1.b itself.
The density (S4) of the particle positions, the ancestor indices, and the indices of the reference is also defined here, together with the distribution with this density.
Three results are proved here. The first is the pointwise identity of the proof of Lemma S1
(target_mul_fwdDensity_eq_extDensity): if each C(p) is reversible with respect to p, as are
the kernels K_{t,j,j} of the six selection rules, the density of x_{1:T} ∼ π followed by
steps (a) and (b) of Algorithm S1 is the density (S4). The second is that the forward pass is a
Markov kernel (isMarkovKernel_forwardPass), which is proved by integrating out the particles and
summing over the indices backwards in time. The third is the measurability of the kernels of the
selection rules in the particle positions and the ancestor indices.
Summing over the functions b which agree with g at the indices t with Q t amounts to
summing over those which agree with g at the indices t with P t, and over the value at i,
when the indices t with Q t are those other than i with P t.
If the functions g j, j ∈ I, sum to one at the points which agree with x outside s,
the sum over j ∈ I of the marginal integrals over s of the products f * g j at x is the
marginal integral of f at x.
Under the condition of Definition S1, with positive weights w and a row-stochastic matrix
K, the probabilities K(β, a^j) r(a) / ∑_{(b', a') : a'^{b'} = a^j} r(a') of the pairs (j, a)
sum to one.
The density of steps (a) and (b) of Algorithm S1 at the particle positions y and the ancestor
indices a, given the indices b of the reference, when c is drawn from
C(B_t(·|x_{t+1}))(b_t, ·):
the product of 1/N, of m_1(x_1^i) for i ≠ b_1, and, for t ∈ [T - 1] and
c_t = a_t^{b_{t+1}}, of C(B_t(·|b_{t+1}))(b_t, c_t), of r_t(a_t) divided by the sum of
r_t(a') over the pairs (b', a') with a'^{b'} = c_t, and of m_{t+1}(x_t^{a_t^i}, x_{t+1}^i)
for i ≠ b_{t+1}.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Steps (a) and (b) of Algorithm S1, with c drawn from C(B_t(·|x_{t+1}))(b_t, ·), as a kernel
from the reference trajectory to the particle positions, the ancestor indices, and the indices of
the reference.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The density (S4) of the particle positions y, the ancestor indices a, and the indices b of
the reference, where K_{t,j,j} = C(B_t(·|j)).
Equations
- One or more equations did not get rendered due to their size.
Instances For
The distribution with density (S4) with respect to the product of μ on each particle
position and of the counting measures on the indices.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The joint distribution, given the reference trajectory, of the particle positions, the
ancestor indices, and the indices of the reference, (y, a, b), and of the indices l of the
output, generated by Algorithm S1 with the resampling scheme resdist and the kernels K.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The Markov kernel defined by Algorithm S1 with the resampling scheme resdist and the kernels
K.
Equations
Instances For
The numerator of the target density is a measurable function of the trajectory.
For resampling schemes which are measurable functions of the particles and the weights, and
kernels C(p) whose entries are measurable functions of p, the density of steps (a) and (b) of
Algorithm S1 is, for fixed ancestor indices and indices of the reference, a measurable function of
the particle positions.
For resampling schemes which are measurable functions of the particles and the weights, and
kernels C(p) whose entries are measurable functions of p, the density (S4) is a measurable
function of the particle positions, the ancestor indices, and the indices of the reference.
The forward pass of Algorithm S1 is an s-finite kernel.
The joint distribution of the variables of Algorithm S1 is an s-finite kernel.
The kernel of Algorithm S1 is an s-finite kernel.
The weights at time t depend on the ancestor indices only through those at time t - 1.
The weights at time t depend on the particle positions only through those at the times up
to t.
Under the condition of Definition S1 on the resampling schemes, with at least one particle and
for Markov kernels C(p), the forward pass is a Markov kernel.
If each C(p) is reversible with respect to p, the numerator of the target density at
(x_1^{b_1}, …, x_T^{b_T}) times the density of steps (a) and (b) of Algorithm S1, with c drawn
from C(B_t(·|x_{t+1}))(b_t, ·), is the numerator of the density (S4), times N^{-T}. The indices
b_t and c_t = a_t^{b_{t+1}} are exchanged by means of the probability r_t(a_t) / (N W_t^{c_t})
of (b_{t+1}, a_t) and of the reversibility of C(B_t(·|b_{t+1})) with respect to
B_t(·|b_{t+1}).
If each C(p) is reversible with respect to p, the density of x_{1:T} ∼ π followed by
steps (a) and (b) of Algorithm S1, with c drawn from C(B_t(·|x_{t+1}))(b_t, ·), is the density
(S4) at (y, a, b).
The pointwise identity of the proof of Lemma S1: with the kernels K_{t,j,j} of one of the six
selection rules, the density of x_{1:T} ∼ π followed by steps (a) and (b) of Algorithm S1 is the
density (S4). The kernels K_{t,j,j} are reversible with respect to B_t(·|j), because the
identity kernel, the Gibbs kernel, and, by Lemma 1, the forced move F_p are reversible with
respect to p.
The kernels of each selection rule, with the probabilities (S3), are measurable functions of the particle positions and the ancestor indices.