3 Conditional sequential Monte Carlo
Let \(\mathsf{X}\) be a measurable space, equipped with a \(\sigma \)-finite measure \(\mathrm{d}x\). Consider a Markov chain on \(\mathsf{X}\) with initial density \(m_1(x_1)\) and transition densities \(m_t(x_{t-1}, x_t)\), \(2 \leq t \leq T\), with respect to \(\mathrm{d}x\), and potential functions \(g_t \colon \mathsf{X}\to (0, \infty )\), \(t \in [T]\). The target distribution has density
where \(Z\in (0, \infty )\).
The target distribution \(\pi \) is a probability measure.
The density integrates to \(Z/ Z= 1\).
The normalized weights are \(W_t^n \mathrel {\vcenter {:}}=g_t(x_t^n) / \sum _{i=1}^N g_t(x_t^i)\), \(n \in [N]\), which form the probability vector \(\mathbf{W}_t \mathrel {\vcenter {:}}=(W_t^1, \dotsc , W_t^N)\). For \(t \in [T-1]\) and \(i, j \in [N]\), the backward-sampling probabilities are
Where the denominator vanishes, \(B_t(\cdot \mid j) \mathrel {\vcenter {:}}=\mathbf{W}_t\).
For \(N \geq 1\), \(\mathbf{W}_t\) and \(B_t(\cdot \mid j)\) are probability vectors. Where the denominator of (2) is positive, \(B_t(i \mid j)\) is given by (2). For \(N \geq 1\), \(g_t(x_t^i) = W_t^i \sum _{k=1}^N g_t(x_t^k)\) and \(W_t^i m_{t+1}(x_t^i, x_{t+1}^j) = B_t(i \mid j) \sum _{k=1}^N W_t^k m_{t+1}(x_t^k, x_{t+1}^j)\), also where the sum vanishes.
The potential functions are positive. Where the sum vanishes, each of its nonnegative terms vanishes.
Consider a Markov chain on a finite set, backwards in time, given by an initial distribution at time \(T\) and transition probabilities from time \(t + 1\) to time \(t\), \(t \in [T-1]\). The probability of a trajectory of this chain is the product of the initial probability of its state at time \(T\) and of its transition probabilities. The marginal distributions of the chain are defined by backward recursion from the initial distribution.
If the transition probabilities from each state sum to one, then the probabilities of the trajectories which are at a given state at time \(t\) sum to the marginal probability of this state at time \(t\).
Sum over the states at the times \(s {\lt} t\), then over those at the times \(s {\gt} t\), by induction.
At fixed particle positions, the kernels of Algorithm 1 are Markov kernels on \([N]\): \(K_T\), reversible with respect to \(\mathbf{W}_T\), and, for \(t \in [T-1]\) and \(j, j' \in [N]\), \(K_{t,j,j'}\), such that, for all \(i, i' \in [N]\),
In the first five rules, \(K_{t,j,j'}(i, \cdot ) = B_t(\cdot \mid j')\) for \(j \neq j'\), so that the indices of the output and of the reference are drawn independently once they differ. For AT, \(K_T(i, \cdot ) = \mathbf{W}_T\) and \(K_{t,j,j}(i, \cdot ) = \delta _i\). For FM-AT, \(K_T = F_{\mathbf{W}_T}\) and \(K_{t,j,j}(i, \cdot ) = \delta _i\). For BS, \(K_T(i, \cdot ) = \mathbf{W}_T\) and \(K_{t,j,j}(i, \cdot ) = B_t(\cdot \mid j)\). For FM-BS, \(K_T = F_{\mathbf{W}_T}\) and \(K_{t,j,j}(i, \cdot ) = B_t(\cdot \mid j)\). For M-BS, \(K_T = F_{\mathbf{W}_T}\) and \(K_{t,j,j} = F_{B_t(\cdot \mid j)}\). For CM-BS, \(K_T = F_{\mathbf{W}_T}\), \(K_{t,j,j} = F_{B_t(\cdot \mid j)}\), and, for \(j \neq j'\), \(K_{t,j,j'} = C_{B_t(\cdot \mid j), B_t(\cdot \mid j')}\).
Proposition 53 applies to the six selection rules, because the identity kernel, the Gibbs kernel, and, by Lemma 12, \(F_{\mathbf{p}}\) are reversible with respect to \(\mathbf{p}\), whereas, for \(j \neq j'\), the kernels \(K_{t,j,j'}(i, \cdot ) = B_t(\cdot \mid j')\) satisfy (3), and so do the kernels \(K_{t,j,j'} = C_{B_t(\cdot \mid j), B_t(\cdot \mid j')}\) of CM-BS, by the first part of Lemma 16. The kernels are measurable functions of the particle positions.
The hypotheses of Algorithm 1 hold by the reversibility of the identity kernel and of the Gibbs kernel, by Lemma 12, and by the first part of Lemma 16. The kernels are Markov kernels by Lemmas 11 and 15. They are measurable functions of \(\mathbf{W}_T\) and \(B_t\), which are measurable functions of the particle positions (Lemma 35).
A kernel to a finite set is defined by its mass function, as a density with respect to the counting measure. A kernel on a product with a countable factor is defined by its sections at the elements of this factor. Given a finite set of coordinates and a map to configurations in \(\mathsf{X}\), a kernel is defined under which the coordinates outside this set are those of the image of the map, whereas those in this set are drawn independently from \(\mathrm{d}x\).
For the kernel defined by a measurable mass function, the measure of each point is its mass. Integrals with respect to this kernel are sums weighted by the masses. It is a Markov kernel if the masses sum to one. A kernel on a product defined by s-finite sections is s-finite. If the sections are Markov kernels, so is the kernel. Integrals with respect to the kernel under which a finite set of coordinates is redrawn are the marginal integrals over these coordinates (MeasureTheory.lmarginal), evaluated at the image of the map.
The identities follow by direct computation. For s-finite sections, decompose the kernel as a sum over the elements of the countable factor.
Consider a product measure and a finite set of coordinates. A factor which does not depend on the coordinates in this set comes out of the marginal integral over them. The marginal integral of a product of factors, each of which depends on a single coordinate in this set and on the coordinates outside it, is the product of the integrals of the factors over their coordinates.
Integrate over one coordinate at a time.
Draw the coordinates outside a finite set independently from \(\mathrm{d}x\), then redraw the coordinates in this set with the kernel of Definition 26. Then all the coordinates are independent with distribution \(\mathrm{d}x\).
The integral over all the coordinates is the integral over the coordinates outside the set of the marginal integral over the set.
Consider variables drawn in steps, with a product measure, and a product of nonnegative factors, one per step. If each factor does not depend on the variables of the later steps and integrates to one over the variables of its step, the product integrates to one over all the variables. Sums are the case of the counting measure. In particular, the density of a Markov chain integrates to one.
The proof is by induction on the number of steps, with the variables of the last step integrated first. The factors of the earlier steps do not depend on these variables, so that they come out of this integral.
If the initial distribution and the transition probabilities of a backward Markov chain on a finite set are probability vectors, the probabilities of its trajectories sum to one. If they are, moreover, measurable functions of a variable, the probabilities of the trajectories are the mass function of a Markov kernel.
Sum over the state at the earliest time first, and conclude by induction on the number of time steps.
Given the reference trajectory \(x_{1:T}\) and kernels \(K_T\) and \(K_{t,j,j'}\) as in (3), which are functions of the particle positions: (a) Draw \(b_1, \dotsc , b_T\) independent uniforms on \([N]\). (b) Set \(x_1^{b_1} \mathrel {\vcenter {:}}=x_1\) and draw \(x_1^n \sim m_1\) for \(n \neq b_1\). For \(t = 2, \dotsc , T\), set \(a_{t-1}^{b_t} \mathrel {\vcenter {:}}=b_{t-1}\) and \(x_t^{b_t} \mathrel {\vcenter {:}}=x_t\), then, for \(n \neq b_t\), draw \(a_{t-1}^n \sim \mathbf{W}_{t-1}\) and \(x_t^n \sim m_t(x_{t-1}^{a_{t-1}^n}, \cdot )\). (c) Draw \(l_T \sim K_T(b_T, \cdot )\). (d) For \(t = T - 1, \dotsc , 1\), draw \(l_t \sim K_{t, b_{t+1}, l_{t+1}}(b_t, \cdot )\). (e) Return \(\tilde{x}_{1:T} \mathrel {\vcenter {:}}=(x_1^{l_1}, \dotsc , x_T^{l_T})\). For the first five rules, Algorithm 1.d is usually implemented as \(l_t \sim K_{t, l_{t+1}, l_{t+1}}(a_t^{l_{t+1}}, \cdot )\), from the ancestor of the particle selected at time \(t + 1\).
Summed over the ancestor indices \(a_{t-1}^{1:N}\) with \(a_{t-1}^{b_t} = b_{t-1}\), a product over \(n \neq b_t\) of functions of \(a_{t-1}^n\) is the product over \(n \neq b_t\) of their sums over \([N]\).
Expand the product of the sums.
For \(N \geq 1\), the forward pass, steps (a) and (b) of Algorithm 1, is a Markov kernel. For measurable Markov kernels \(K_T\) and \(K_{t,j,j'}\), so are the backward pass, steps (c) and (d) of Algorithm 1, and its usual implementation.
By Lemma 33, the sum over the ancestor indices of the density of the forward pass is the product over the coordinates \((t, n)\) with \(n \neq b_t\) of \(m_1(x_1^n)\) for \(t = 1\) and of \(\sum _{k=1}^N W_{t-1}^k m_t(x_{t-1}^k, x_t^n)\) for \(t \geq 2\). Each factor integrates to one over \(x_t^n\), because the weights sum to one, and does not depend on the positions at the later times. The product therefore integrates to one, by Lemma 30 with the times as steps. The mass functions of the backward passes are the probabilities of the trajectories of backward Markov chains, with initial distribution \(K_T(b_T, \cdot )\) and transition probabilities \(K_{t,b_{t+1},j}(b_t, \cdot )\) from \(j\) at time \(t + 1\), or \(K_{t,j,j}(a_t^j, \cdot )\) for the usual implementation. Lemma 31 applies to these chains.
The entries of the Gibbs kernel and of \(F_{\mathbf{p}}\), of \(F_{\mathbf{u}}\), and of \(C_{\mathbf{p},\mathbf{q}}\) are measurable functions of \(\mathbf{p}\), of \(\mathbf{u}\), and of \((\mathbf{p}, \mathbf{q})\), respectively. The weights, the backward-sampling probabilities, and the kernels of the six selection rules are measurable functions of the particle positions.
The entries are obtained from the coordinates by arithmetic operations, maxima, finite sums, and case distinctions on measurable sets. For the kernels of the selection rules, these functions are composed with \(\mathbf{W}_T\) and \(B_t\), which are measurable functions of the particle positions.