4 Validity
The extended distribution of Andrieu et al. (2010) is defined on the particle positions \(\mathbf{x}\mathrel {\vcenter {:}}=(x_t^n)_{t \in [T], n \in [N]}\), the ancestor indices \(a\mathrel {\vcenter {:}}=(a_t^n)_{t \in [T-1], n \in [N]}\), and a final index \(b_T \in [N]\), which have joint density
The trajectory traced back from \(b_T\) is \((x_1^{b_1}, \dotsc , x_T^{b_T})\), with genealogy \(b_t \mathrel {\vcenter {:}}=a_t^{b_{t+1}}\) for \(t \in [T-1]\).
Indices \(b_{1:T}\) are those traced back from \(b_T\) if and only if \(a_t^{b_{t+1}} = b_t\) for every \(t \in [T-1]\).
By backward induction on \(t\).
Let \(x_{1:T} \sim \pi \) and run steps (a) and (b) of Algorithm 1. The variables \((\mathbf{x}, a, b_{1:T})\) have the density
On the set where \(a_{t-1}^{b_t} = b_{t-1}\) for \(2 \leq t \leq T\), which is the set where \(b_{1:T}\) is traced back from \(b_T\), this density is \(\bar{\pi }(\mathbf{x}, a, b_T)\), whereas it vanishes elsewhere.
As in the proof of Lemma 3 in Section S1, the factors \(m_1(x_1^{b_1})\) and \(m_t(x_{t-1}^{b_{t-1}}, x_t^{b_t})\) of (1) complete the products over \(n\), because \(x_{t-1}^{b_{t-1}} = x_{t-1}^{a_{t-1}^{b_t}}\). By the definition of the weights, \(g_t(x_t^{b_t}) = W_t^{b_t} \sum _{i=1}^N g_t(x_t^i)\). The identity \(\prod _{t=1}^T W_t^{b_t} = W_T^{b_T} \prod _{t=2}^T W_{t-1}^{a_{t-1}^{b_t}}\) then completes the products of the weights over \(n\).
As a function of \((a, b_T)\), \(\bar{\pi }(\mathbf{x}, a, b_T)\) is the product of
and of \(W_T^{b_T} \prod _{t=1}^{T-1} \prod _{n=1}^N B_t(a_t^n \mid n)\). For \(N \geq 1\), the second factor sums to one over \((a, b_T)\). The density \(\bar{\pi }\) is measurable.
By Lemma 20, \(W_{t-1}^{a_{t-1}^n} m_t(x_{t-1}^{a_{t-1}^n}, x_t^n) = B_{t-1}(a_{t-1}^n \mid n) \sum _{k=1}^N W_{t-1}^k m_t(x_{t-1}^k, x_t^n)\). The sum over \((a, b_T)\) is the product of the sums of \(\mathbf{W}_T\) and of the \(B_t(\cdot \mid n)\).
For \(N \geq 1\), \(\bar{\pi }\) is a probability measure.
By the first part of Lemma 41, \(\bar{\pi }\) is the image of the joint distribution of \(x_{1:T} \sim \pi \) and of the variables of steps (a) and (b) of Algorithm 1, which is a probability measure.
Let \(x_{1:T} \sim \pi \) and run steps (a) and (b) of Algorithm 1. Then \((\mathbf{x}, a, b_T) \sim \bar{\pi }\), with \(x_{1:T}\) the trajectory traced back from \(b_T\). Under \(\bar{\pi }\), conditionally on \(\mathbf{x}\), the indices \(b_T\) and \(a_t^n\), \(t \in [T-1]\), \(n \in [N]\), are independent, with the distributions \(\mathbf{W}_T\) and \(B_t(\cdot \mid n)\), respectively.
This proof is not ours and is provided for completeness and ease of reference. The first part 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). As in the proof of Lemma 3 in Section S1, the density of the variables generated by steps (a) and (b) of Algorithm 1 is (6) on the set where \(a_{t-1}^{b_t} = b_{t-1}\). As a function of \((a, b_T)\), the density (6) is proportional to \(W_T^{b_T} \prod _{t,n} W_{t-1}^{a_{t-1}^n} m_t(x_{t-1}^{a_{t-1}^n}, x_t^n)\). The three claims of the statement follow from Lemma 43.
Let \(x_{1:T} \sim \pi \) and run steps (a) and (b) of Algorithm 1. Integrals with respect to the joint distribution of \(x_{1:T}\), \(b_{1:T}\), \(\mathbf{x}\), and \(a\) are integrals over \(\mathbf{x}\) of sums over \((a, b_T)\) of the density (6) times the integrand, evaluated at the indices \(b_{1:T}\) traced back from \(b_T\) and at \(x_{1:T} = (x_1^{b_1}, \dotsc , x_T^{b_T})\).
The reference trajectory is read off the particles with the indices \(b_{1:T}\). By Lemma 38, the density of the variables of steps (a) and (b) of Algorithm 1, times the target density, is (6) on the set where the indices are traced back from \(b_T\) and zero elsewhere.
Let \(x_{1:T} \sim \pi \) and run steps (a) and (b) of Algorithm 1. The joint distribution of \(x_{1:T}\) and \((\mathbf{x}, a, b_T)\) is that of the trajectory traced back from \(b_T\) and of \((\mathbf{x}, a, b_T) \sim \bar{\pi }\). In particular, \((\mathbf{x}, a, b_T) \sim \bar{\pi }\). Under \(\bar{\pi }\), the conditional distribution of \((a, b_T)\) given \(\mathbf{x}\) has the mass function \(W_T^{b_T} \prod _{t, n} B_t(a_t^n \mid n)\).
Given the particle positions, the pairs \((b_t, l_t)\) form the backward Markov chain on \([N]^2\) with initial distribution \(W_T^{j} K_T(j, j')\) and transitions \(B_t(i \mid j) K_{t,j,j'}(i, i')\) from \((j, j')\) at time \(t + 1\) to \((i, i')\) at time \(t\).
The probability of the indices \(b_{1:T}\) and \(l_{1:T}\) is \(W_T^{b_T} K_T(b_T, l_T) \prod _{t=1}^{T-1} B_t(b_t \mid b_{t+1}) K_{t,b_{t+1},l_{t+1}}(b_t, l_t)\). Its marginal distributions at each time are given by backward recursion.
The first part holds by definition. The second part follows from Lemma 22.
For measurable kernels \(K_T\) and \(K_{t,j,j'}\), integrals with respect to the backward passes and to the backward chain of the pairs \((b_t, l_t)\) given \(\mathbf{x}\) are sums over the indices, weighted by their probabilities.
The three kernels are defined by mass functions with respect to the counting measure, which are measurable functions of \(\mathbf{x}\).
Fix \(\mathbf{x}\) and let \(b_T \sim \mathbf{W}_T\) and the ancestor indices \(a_t^n \sim B_t(\cdot \mid n)\), \(t \in [T-1]\), \(n \in [N]\), be independent. Then the indices traced back from \(b_T\), \(b_t = a_t^{b_{t+1}}\), have the probabilities \(W_T^{b_T} \prod _{t=1}^{T-1} B_t(b_t \mid b_{t+1})\). If \(l_{1:T}\) is then drawn by steps (c) and (d) of Algorithm 1, \((b_{1:T}, l_{1:T})\) has the probabilities of the backward chain of the pairs \((b_t, l_t)\). If \(K_{t,j,j'}(i, \cdot ) = B_t(\cdot \mid j')\) for all \(j \neq j'\) and \(t \in [T-1]\), the same holds with \(l_t \sim K_{t, l_{t+1}, l_{t+1}}(a_t^{l_{t+1}}, \cdot )\) in Algorithm 1.d.
Sum over the ancestor indices at the earliest time first, and proceed by induction on \(T\). Under the product of the distributions \(B_t(\cdot \mid n)\), \(n \in [N]\), the index \(a_t^j\) has the distribution \(B_t(\cdot \mid j)\). For \(j \neq j'\), the indices \(a_t^j\) and \(a_t^{j'}\) are independent. For the usual implementation, if \(l_{t+1} \neq b_{t+1}\), the distribution \(B_t(\cdot \mid l_{t+1})\) of \(a_t^{l_{t+1}}\) is invariant for \(K_{t, l_{t+1}, l_{t+1}}\), by (3) with \(j = j'\), and equals \(K_{t, b_{t+1}, l_{t+1}}(b_t, \cdot )\) by hypothesis.
Let \(x_{1:T} \sim \pi \) and run Algorithm 1. The joint distribution of \(x_{1:T}\) and \((\mathbf{x}, b_{1:T}, l_{1:T})\) is that of \((x_1^{b_1}, \dotsc , x_T^{b_T})\) and \((\mathbf{x}, b_{1:T}, l_{1:T})\), where \(\mathbf{x}\) has its distribution under \(\bar{\pi }\) and, given \(\mathbf{x}\), \((b_{1:T}, l_{1:T})\) has the probabilities of the backward chain of the pairs \((b_t, l_t)\). If \(K_{t,j,j'}(i, \cdot ) = B_t(\cdot \mid j')\) for all \(j \neq j'\) and \(t \in [T-1]\), the same holds with the usual implementation of Algorithm 1.d.
By Lemma 42, integrals with respect to the joint distribution are integrals over \(\mathbf{x}\) of sums over \((a, b_T)\) of the density (6) times the integral with respect to the backward pass, at the indices traced back from \(b_T\) and at \(x_{1:T} = (x_1^{b_1}, \dotsc , x_T^{b_T})\). By the second part of Lemma 43, given \(\mathbf{x}\), \((a, b_T)\) has the distribution of Lemma 47. The probabilities of \((b_{1:T}, l_{1:T})\) then follow from Lemma 47.
Let \(x_{1:T} \sim \pi \) and run Algorithm 1. Conditionally on \(\mathbf{x}\), \(b_T \sim \mathbf{W}_T\) and, given \(b_T\), \(l_T \sim K_T(b_T, \cdot )\). For \(t \in [T-1]\), conditionally on \(\mathbf{x}\) and \((b_{t+1:T}, l_{t+1:T})\), \(b_t \sim B_t(\cdot \mid b_{t+1})\) and, given \(b_t\), \(l_t \sim K_{t, b_{t+1}, l_{t+1}}(b_t, \cdot )\). If \(K_{t,j,j'}(i, \cdot ) = B_t(\cdot \mid j')\) for all \(j \neq j'\) and \(t \in [T-1]\), the same holds with \(l_t \sim K_{t, l_{t+1}, l_{t+1}}(a_t^{l_{t+1}}, \cdot )\) in Algorithm 1.d.
As in the proof of Lemma 4 in Section S1, by Lemma 41, conditionally on \(\mathbf{x}\) and on the variables at the times \(s {\gt} t\), the ancestor indices \(a_t^n\), \(n \in [N]\), are independent, with the distributions \(B_t(\cdot \mid n)\), so that \(b_t = a_t^{b_{t+1}} \sim B_t(\cdot \mid b_{t+1})\). With the usual implementation, if \(l_{t+1} \neq b_{t+1}\), then \(a_t^{l_{t+1}}\) is independent of \(b_t\), with the distribution \(B_t(\cdot \mid l_{t+1})\), which is invariant for \(K_{t,l_{t+1},l_{t+1}}\).
For kernels as in Algorithm 1, the probability of \((b_{1:T}, l_{1:T})\) given the particle positions does not change when \(b_{1:T}\) and \(l_{1:T}\) are exchanged.
The initial distribution \(W_T^i K_T(i, j)\) is symmetric in \((i, j)\), by the reversibility of \(K_T\). At time \(t \in [T-1]\), the transition from \((j, j')\) to \((i, i')\) has the probability \(B_t(i \mid j) K_{t,j,j'}(i, i')\), which, by (3), does not change when \((i, j)\) and \((i', j')\) are exchanged.
A Markov kernel is reversible with respect to a distribution if and only if the joint distribution of the current and the next states does not change when the two are exchanged.
The two measures agree on products of measurable sets, which generate the product \(\sigma \)-algebra.
For measurable kernels \(K_T\) and \(K_{t,j,j'}\) as in Algorithm 1, the kernel defined by Algorithm 1 is a Markov kernel. Given \(\mathbf{x}\), the distribution of the backward chain of the pairs \((b_t, l_t)\) does not change when \(b_{1:T}\) and \(l_{1:T}\) are exchanged. Let \(x_{1:T} \sim \pi \) and run Algorithm 1, with output \(\tilde{x}_{1:T}\). The joint distribution of \((x_{1:T}, \tilde{x}_{1:T})\) is that of \(((x_t^{b_t})_{t \in [T]}, (x_t^{l_t})_{t \in [T]})\), where \(\mathbf{x}\) has its distribution under \(\bar{\pi }\) and, given \(\mathbf{x}\), \((b_{1:T}, l_{1:T})\) has the probabilities of the backward chain of the pairs.
The output is \(\tilde{x}_t = x_t^{l_t}\), so that the joint distribution is the image of that of Lemma 48.
For any kernels \(K_T\) and \(K_{t,j,j'}\) as in Algorithm 1, the Markov kernel defined by Algorithm 1 is reversible with respect to \(\pi \). In particular, it leaves \(\pi \) invariant.
As in the proof of Proposition 1 in Section S1, by Lemma 49 and Lemma 50, conditionally on \(\mathbf{x}\), the distribution of \((b_{1:T}, l_{1:T})\) does not change when \(b_{1:T}\) and \(l_{1:T}\) are exchanged, so that \((x_{1:T}, \tilde{x}_{1:T})\) and \((\tilde{x}_{1:T}, x_{1:T})\) have the same distribution. By Lemma 51, this is the reversibility of the Markov kernel defined by Algorithm 1 with respect to \(\pi \).