6 Potential functions of the previous state and other resampling schemes
Let \(g_1 \colon \mathsf{X}\to (0, \infty )\) and \(g_t \colon \mathsf{X}^2 \to (0, \infty )\), \(2 \leq t \leq T\), be potential functions, and let the target distribution have density
where \(Z\in (0, \infty )\).
The normalized weights at the times \(t \geq 2\) are \(W_t^n \mathrel {\vcenter {:}}=g_t(x_{t-1}^{a_{t-1}^n}, x_t^n) / \sum _{i=1}^N g_t(x_{t-1}^{a_{t-1}^i}, x_t^i)\), \(n \in [N]\). For \(t \in [T-1]\), \(i \in [N]\), and \(x' \in \mathsf{X}\),
and \(B_t(i \mid j) \mathrel {\vcenter {:}}=B_t(i \mid x_{t+1}^j)\) for \(j \in [N]\). Where the denominator vanishes, \(B_t(\cdot \mid x') \mathrel {\vcenter {:}}=\mathbf{W}_t\). The kernels \(K_T\) and \(K_{t,j,j'}\) of the six selection rules are defined as in Section 2 of the main text, with these probabilities.
The target distribution \(\pi \) is a probability measure. Let \(N \geq 1\). Then \(\mathbf{W}_t\) and \(B_t(\cdot \mid x')\) are probability vectors. The weights are positive. Moreover, \(g_1(x_1^i) = W_1^i \sum _{k=1}^N g_1(x_1^k)\) and, for \(t \geq 2\), \(g_t(x_{t-1}^{a_{t-1}^i}, x_t^i) = W_t^i \sum _{k=1}^N g_t(x_{t-1}^{a_{t-1}^k}, x_t^k)\). Finally, \(W_t^i m_{t+1}(x_t^i, x') g_{t+1}(x_t^i, x') = B_t(i \mid x') \sum _{k=1}^N W_t^k m_{t+1}(x_t^k, x') g_{t+1}(x_t^k, x')\), also where the sum vanishes.
The potential functions are positive. Where the sum vanishes, each of its nonnegative terms vanishes.
For fixed ancestor indices, the weights and the backward-sampling probabilities (S3) are measurable functions of the particle positions. The kernels of the six selection rules, with the probabilities (S3), are measurable functions of the particle positions and of the ancestor indices.
The proof is that of Lemma 35, because the ancestor indices take finitely many values.
A resampling scheme at time \(t \in [T-1]\) is a distribution \(r_t\) on \([N]^N\), which may depend on the particles at time \(t\) and on their weights, such that, for every \(i \in [N]\), the expected number of indices \(n \in [N]\) with \(a_t^n = i\) under \(r_t\) is \(N W_t^i\). At each time \(t \in [T-1]\), the vector \(a_t\) of the indices of the ancestors at time \(t\) of the particles at time \(t + 1\) is drawn from a resampling scheme \(r_t\). Multinomial resampling is defined by \(r_t(a_t) = \prod _{n=1}^N W_t^{a_t^n}\).
The probabilities \(r_t(a_t)\) sum to one. For every \(c \in [N]\), their sum over the pairs \((b_{t+1}, a_t)\) with \(a_t^{b_{t+1}} = c\) is \(N W_t^c\). Multinomial resampling is a resampling scheme.
For the first part, sum the expected numbers over \(i \in [N]\). The sum over the pairs with \(a_t^{b_{t+1}} = c\) is the expected number of indices \(n\) with \(a_t^n = c\). Under multinomial resampling, the indices \(a_t^n\) are independent draws from \(\mathbf{W}_t\).
Given the reference trajectory \(x_{1:T}\) and kernels \(K_T\) and \(K_{t,j,j'}\) as in Algorithm 1, with the probabilities (S3) and functions of the particle positions and of the ancestor indices: (a) Draw \(b_1\) uniformly on \([N]\), set \(x_1^{b_1} \mathrel {\vcenter {:}}=x_1\), and draw \(x_1^n \sim m_1\) for \(n \neq b_1\). (b) For \(t = 1, \dotsc , T - 1\), draw \(c \sim B_t(\cdot \mid 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}} \mathrel {\vcenter {:}}=x_{t+1}\) and draw \(x_{t+1}^n \sim m_{t+1}(x_t^{a_t^n}, \cdot )\) for \(n \neq b_{t+1}\). (c) Run steps (c) to (e) of Algorithm 1. For each of the six selection rules, Algorithm S1.b is also considered with \(c\) drawn from the kernel \(K_{t,j,j}\) of the rule, with \(B_t(\cdot \mid x_{t+1})\) in place of \(B_t(\cdot \mid j)\), started from \(b_t\).
For \(N \geq 1\), the forward pass of Algorithm S1, with \(c\) drawn from Markov kernels, is a Markov kernel.
By Definition 79, the normalizing constant of the probabilities of \((b_{t+1}, a_t)\) is \(N W_t^c\), which is positive because the weights are positive. The density of the forward pass then integrates to one, by integration backwards in time.
For kernels \(K_{t,j,j}\) as in Algorithm S1, the distribution (S4) of \((\mathbf{x}, a, b_{1:T})\) has the density
Let \(x_{1:T} \sim \pi \) and run steps (a) and (b) of Algorithm S1, with \(c\) drawn from a kernel which is reversible with respect to \(B_t(\cdot \mid x_{t+1})\), as are the kernels \(K_{t,j,j}\) of the six selection rules with \(B_t(\cdot \mid x_{t+1})\) in place of \(B_t(\cdot \mid j)\). The density of \((\mathbf{x}, a, b_{1:T})\), which is \(\pi (x_1^{b_1}, \dotsc , x_T^{b_T})\) times the probabilities of the draws of steps (a) and (b) of Algorithm S1 and the densities of the particles other than those of the reference, is (S4).
As in the proof of Lemma S1 in Section S3, the probability of \((b_{t+1}, a_t)\) is \(r_t(a_t) / (N W_t^{c_t})\), with \(c_t \mathrel {\vcenter {:}}=a_t^{b_{t+1}}\). By the reversibility of \(K_{t,b_{t+1},b_{t+1}}\) with respect to \(B_t(\cdot \mid b_{t+1})\), the indices \(b_t\) and \(c_t\) can be exchanged in the product of \(W_t^{b_t} m_{t+1}(x_t^{b_t}, x_{t+1}^{b_{t+1}}) g_{t+1}(x_t^{b_t}, x_{t+1}^{b_{t+1}})\) and \(K_{t,b_{t+1},b_{t+1}}(b_t, c_t)\). The identity kernel and the Gibbs kernel are reversible with respect to every probability vector, as is the forced move, by Lemma 12.
Integrals with respect to the joint distribution of \(x_{1:T} \sim \pi \) and of the variables of steps (a) and (b) of Algorithm S1 are integrals over \(\mathbf{x}\) of sums over \((a, b_{1:T})\) of \(\pi (x_1^{b_1}, \dotsc , x_T^{b_T})\) times the density of these steps times the integrand, at \(x_{1:T} = (x_1^{b_1}, \dotsc , x_T^{b_T})\). Integrals with respect to the distribution (S4) are integrals over \(\mathbf{x}\) of sums over \((a, b_{1:T})\) of the density (S4) times the integrand.
As in Lemma 42, for each \(b_{1:T}\), the reference trajectory is read off the particles with the indices \(b_{1:T}\).
Let \(x_{1:T} \sim \pi \) and run steps (a) and (b) of Algorithm S1, with \(c\) drawn from the kernels \(K_{t,j,j}\) of one of the six selection rules. Then \(x_{1:T} = (x_1^{b_1}, \dotsc , x_T^{b_T})\) and \((\mathbf{x}, a, b_{1:T})\) has the density (S4). Conversely, if \((\mathbf{x}, a, b_{1:T})\) has the density (S4), then \((x_1^{b_1}, \dotsc , x_T^{b_T}) \sim \pi \).
As in the proof of Lemma S1 in Section S3, the probability of \((b_{t+1}, a_t)\) is \(r_t(a_t) / (N W_t^{c_t})\), with \(c_t \mathrel {\vcenter {:}}=a_t^{b_{t+1}}\). By the reversibility of \(K_{t,b_{t+1},b_{t+1}}\) with respect to \(B_t(\cdot \mid b_{t+1})\), the indices \(b_t\) and \(c_t\) can be exchanged in the factors at time \(t + 1\), which gives the density (S4) by Lemma 84.
The density (S4) is the product of a function of \((\mathbf{x}, a)\) and of
which is a probability distribution of \(b_{1:T}\). Hence the marginal density of \((\mathbf{x}, a)\) does not depend on the selection rule. Conditionally on \((\mathbf{x}, a)\), \(b_T \sim \mathbf{W}_T\) and, for \(t = T - 1, \dotsc , 1\), given also \(b_{t+1:T}\), \(b_t \sim K_{t,b_{t+1},b_{t+1}}(a_t^{b_{t+1}}, \cdot )\).
The kernels \(K_{t,j,j}\) of the six selection rules are Markov kernels for every probability vector \(B_t(\cdot \mid j)\), by Lemma 27. The sum of the second factor over \(b_1, \dotsc , b_{T-1}\), in this order, is therefore \(W_T^{b_T}\), whose sum over \(b_T\) is one. The distribution (S4) is thus that of \((\mathbf{x}, a)\), with the density of the first factor, followed by the backward Markov chain of the indices of the reference with the probabilities of the second factor. By the same sums, conditionally on \((\mathbf{x}, a)\), \(b_T \sim \mathbf{W}_T\) for all the kernels of Lemma 86.
For any kernels \(K_T\) and \(K_{t,j,j'}\) as in Algorithm S1, the Markov kernel defined by Algorithm S1 is reversible with respect to \(\pi \).
Let \(x_{1:T} \sim \pi \) and run Algorithm S1. The density (S4) with the Gibbs kernels is a function of \((\mathbf{x}, a)\) times \(W_T^{b_T} \prod _t B_t(b_t \mid b_{t+1})\). Given \((\mathbf{x}, a)\), \((b_{1:T}, l_{1:T})\) is the backward chain of the pairs of Definition 44, with the backward-sampling probabilities (S3). The joint distribution of \((x_{1:T}, \tilde{x}_{1:T})\) is therefore that of \(((x_t^{b_t})_t, (x_t^{l_t})_t)\), where \((\mathbf{x}, a)\) has its distribution under (S4).
As in the proof of Proposition S1 in Section S3, by Lemma 86, conditionally on \((\mathbf{x}, a)\), \(b_T \sim \mathbf{W}_T\) and \(b_t \sim B_t(\cdot \mid b_{t+1})\) given \(b_{t+1:T}\). The kernels of the backward pass of Algorithm 1 depend on \((\mathbf{x}, a)\) only.
Lemma 60 holds for Algorithm S1, with \((\mathbf{x}, a)\) in place of \(\mathbf{x}\) and the distribution (S4) in place of \(\bar{\pi }\).
Let \(\tilde{x}_{1:T}\) be the output of Algorithm S1 started from \(x_{1:T} \sim \pi \). Theorem 61, Corollary 63, and Propositions 67 and 70 hold with the probabilities (S3), with the distribution (S4) in place of \(\bar{\pi }\), and, in Proposition 67, with \(m_{s+1}(x, \cdot ) g_{s+1}(x, \cdot ) \geq \varepsilon m_{s+1}(x', \cdot ) g_{s+1}(x', \cdot )\) in place of the condition on \(m_{s+1}\).
As in the proof of Proposition S2 in Section S3, condition on \((\mathbf{x}, a)\) instead of \(\mathbf{x}\) in the proofs of these results, with \(\mathbb {P}_{\mathbf{x},a}\) and \(\mathbb {E}_{\mathbf{x},a}\) in place of \(\mathbb {P}_{\mathbf{x}}\) and \(\mathbb {E}_{\mathbf{x}}\).
Assume multinomial resampling, and that \(g_t(x_{t-1}, x_t)\) does not depend on \(x_{t-1}\) for \(2 \leq t \leq T\). Then, for \(x_{1:T} \sim \pi \) and any kernels as in Algorithm 1, the reference and the output have the same joint distribution under Algorithm S1 as under Algorithm 1.
As in the proof of Proposition S3 in Section S3, \((\mathbf{x}, b_{1:T})\) has the same distribution under both algorithms. Under both algorithms, \(l_{1:T}\) is drawn given \(\mathbf{x}\) and \(b_{1:T}\) with the same kernels.
Given the reference trajectory \(x_{1:T}\) and the kernels \(K_T\) and \(K_{t,j,j}\) of AT, FM-AT, BS, FM-BS, or M-BS, with the probabilities (S3): (a) Run steps (a) and (b) of Algorithm S1, with \(c \mathrel {\vcenter {:}}=b_t\) in Algorithm S1.b. (b) Draw \(l_T \sim K_T(b_T, \cdot )\). (c) For \(t = T - 1, \dotsc , 1\), draw \(l_t\) from the kernel \(K_{t,l_{t+1},l_{t+1}}\) started from the ancestor \(a_t^{l_{t+1}}\) of the particle \(l_{t+1}\). (d) Return \(\tilde{x}_{1:T} \mathrel {\vcenter {:}}=(x_1^{l_1}, \dotsc , x_T^{l_T})\).
The Markov kernel defined by Algorithm S2 leaves \(\pi \) invariant. With the kernels of AT and FM-AT, it is reversible with respect to \(\pi \).
As in the proof of Proposition S4 in Section S3, by Lemma 86 with the identity kernels, \(b_T \sim \mathbf{W}_T\) conditionally on \((\mathbf{x}, a)\). Because \(K_T\) leaves \(\mathbf{W}_T\) invariant, \(l_T \sim \mathbf{W}_T\) conditionally on \((\mathbf{x}, a)\). With \(l_{1:T}\) in place of \(b_{1:T}\) and the kernels \(K_{t,j,j}\) of the selection rule, \((\mathbf{x}, a, l_{1:T})\) then has the density (S4), so that \(\tilde{x}_{1:T} \sim \pi \) by Lemma 86. With the identity kernels of AT and FM-AT, the reversibility follows from that of \(K_T\), by Lemma 51.
With \(c\) drawn in Algorithm S2.a as in Lemma 86, from the kernel \(K_{t,j,j}\) of one of the six selection rules, with \(B_t(\cdot \mid x_{t+1})\) in place of \(B_t(\cdot \mid j)\), started from \(b_t\), the Markov kernel defined by Algorithm S2 leaves \(\pi \) invariant. In particular, the invariance holds with ancestor sampling in Algorithm S2.a.
The proof of Proposition 94 uses Algorithm S2.a only through \(b_T \sim \mathbf{W}_T\) conditionally on \((\mathbf{x}, a)\), which holds for all the kernels of Lemma 86, by Lemma 87. The joint distribution of \((\mathbf{x}, a)\) and \(b_T\) under the distribution (S4) therefore does not depend on the kernels. Because the backward pass from the ancestors depends on \(b_{1:T}\) only through \(b_T\), the variables \((\mathbf{x}, a, l_{1:T})\) have the same distribution as with \(c \mathrel {\vcenter {:}}=b_t\). The proof of Proposition 94 then applies.
On the state space \(\{ 0, 1\} \) with the counting measure, the uniform densities \(m_1 = m_{t+1}(x, \cdot ) = 1/2\) and the potential functions \(g_t(x) = x + 1\) define a Feynman–Kac model. The same densities with \(g_1(x) = x + 1\) and \(g_{t+1}(x, x') = x + x' + 1\) define a model of Section S3. With \(N = 2\) and the kernels of each selection rule, Propositions 53 and 88, the latter with multinomial resampling, apply to them.
The densities integrate to one. The potential functions are positive. The normalizing constant \(Z\) is a positive finite sum.