Dependencies

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})\).

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\).

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\).

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]\).

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\).

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.

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.

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.

For every \(t \in [T]\), \(\mathbb {P}_{\mathbf{x}}(\tilde{x}_t = x_t) = \sum _S Q_t(\mathbf{1}_S)\), where the sum is over the classes \(S \subseteq [N]\) of indices whose particles at time \(t\) are equal.

Let \(x_{1:T} \sim \pi \) and run Algorithm 1 with measurable kernels as in Algorithm 1. The expectation of an integrable function of \((x_{1:T}, \tilde{x}_{1:T})\), or of a bounded measurable function of \((\mathbf{x}, b_{1:T}, l_{1:T})\), is the expectation, under the distribution of \(\mathbf{x}\) under \(\bar{\pi }\), of its expectation \(\mathbb {E}_{\mathbf{x}}\) given \(\mathbf{x}\), which is integrable. In particular, \(\mathbb {E}\{ f(x_t) f(\tilde{x}_t)\} \) is the expectation of \(Q_t(\varphi )\) with \(\varphi (i) = f(x_t^i)\). Similarly, \(\mathbb {P}(\tilde{x}_t \neq x_t)\) is the expectation of \(1 - \sum _S Q_t(\mathbf{1}_S)\), where the sum is over the classes \(S\) of Lemma 58. If \(f(x_t)^2\) is integrable under \(\pi \), then \(f(x_t) f(\tilde{x}_t)\) is integrable, because \(x_{1:T}\) and \(\tilde{x}_{1:T}\) both have the distribution \(\pi \).

For all \(i \in [N]\), \(C_{\mathbf{p},\mathbf{q}}(i, i) = q_i F_{\mathbf{p} \odot \mathbf{q}}(i, i)\), so that, for probability vectors \(\mathbf{p}\) and \(\mathbf{q}\), the entries of \(C_{\mathbf{p},\mathbf{q}}\) are nonnegative and \(C_{\mathbf{p},\mathbf{q}}\) is a Markov kernel.

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.

Let \(p\) be a probability vector and \(K\) a Markov kernel on \(I\), with \(q_j \mathrel {\vcenter {:}}=\sum _i p_i K(i, j)\) for \(j \in I\). Then, for every \(\varphi \colon I \to \mathbb {R}\),

In the setting of Lemma 5, if \(K(i, j) \geq q_j\) for all \(i \neq j\), then \(\langle \varphi , K\varphi \rangle _p \leq p(\varphi ) q(\varphi )\) for every \(\varphi \colon I \to \mathbb {R}\).

When a matrix is applied to the difference of two probability vectors, their total-variation distance is multiplied by at most the Dobrushin coefficient of the matrix. The Dobrushin coefficient of a product of two matrices, the columns of the second of which are probability vectors, is at most the product of their coefficients. If \(B_s(i \mid j) \geq \varepsilon W_s^i\) for all \(i\) and \(j\), then \(\beta _s \leq 1 - \varepsilon \).

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.

For weights \(p\) on a finite set \(I\), a function \(\varphi \colon I \to \mathbb {R}\), and a matrix \(K\) indexed by \(I\), \(p(\varphi ) \mathrel {\vcenter {:}}=\sum _{i \in I} p_i \varphi (i)\) and \(\langle \varphi , K\varphi \rangle _p \mathrel {\vcenter {:}}=\sum _{i, j \in I} p_i K(i, j) \varphi (i) \varphi (j)\).

For all \(p\), \(\varphi \), and \(\psi \), \(p(\varphi + \psi ) = p(\varphi ) + p(\psi )\).

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.

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.

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})\).

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)\).

For \(N \geq 1\), \(\bar{\pi }\) is a probability measure.

For a probability vector \(\mathbf{p}\), \(F_{\mathbf{p}}\) is a Markov kernel with \(F_{\mathbf{p}}(i, i) \leq p_i\). For \(\mathbf{u} \in [0, \infty )^N\), \(F_{\mathbf{u}}\) is a Markov kernel and \(u_i F_{\mathbf{u}}(i, j) = u_j F_{\mathbf{u}}(j, i)\) for all \(i, j \in [N]\).

Let \(t \in [T-1]\). For M-BS and CM-BS, \(\gamma _t(j, j') \geq 0\) for all \(j, j' \in [N]\). Under either rule, \(\mathbb {P}_{\mathbf{x}}(l_t = b_t)\) is smaller than under FM-BS by at least \(\sum _{j, j'} \mathbb {P}_{\mathbf{x}}(b_{t+1} = j, l_{t+1} = j') \gamma _t(j, j')\), where \(\mathbb {P}_{\mathbf{x}}\) and \(\gamma _t\) are those of that rule.

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 Gibbs kernel \(K(i, \cdot ) = p\) and the identity kernel are reversible with respect to \(p\). The Gibbs kernel is a Markov kernel when \(p\) is a probability vector. The entries of a Markov kernel are at most one. For the Gibbs kernel \(K(i, \cdot ) = q\), \(\langle \varphi , K\varphi \rangle _p = p(\varphi ) q(\varphi )\). For the identity kernel, \(\langle \varphi , \varphi \rangle _p = p(\varphi ^2)\). For every matrix \(K\) indexed by \(I\) and every \(i \in I\), \(\langle \mathbf{1}_{\{ i\} }, K\mathbf{1}_{\{ i\} } \rangle _p = p_i K(i, i)\).

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.

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.

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.

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\).

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.

The expectations \(\mathbb {E}_{\mathbf{x}}\{ \varphi (b_t, b_{t+1}) \varphi (l_t, l_{t+1})\} \) are nondecreasing from M-BS to FM-BS, BS, and AT. The probabilities \(\sum _j \mathbb {P}_{\mathbf{x}}(b_{t+1} = l_{t+1} = j) \sum _i B_t(i \mid j) K_{t,j,j}(i, i)\) are nondecreasing from M-BS to FM-BS, BS, and AT, and at most as large under CM-BS as under FM-BS.

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.

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.

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.

For kernels as in Algorithm 1, \(\mathbb {E}_{\mathbf{x}}\{ \varphi (b_t, l_t)\} = \sum _{i, i'} \mathbb {P}_{\mathbf{x}}(b_t = i, l_t = i') \varphi (i, i')\) and

In particular, \(\mathbb {P}_{\mathbf{x}}\{ (l_t, l_{t+1}) \neq (b_t, b_{t+1})\} = 1 - \sum _j \mathbb {P}_{\mathbf{x}}(b_{t+1} = l_{t+1} = j) \sum _i B_t(i \mid j) K_{t,j,j}(i, i)\). If the particles at time \(t\) are pairwise distinct, then \(\sum _S Q_t(\mathbf{1}_S) = \sum _i Q_t(\mathbf{1}_{\{ i\} })\).

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.

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 \(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).

For \(N \geq 1\), the forward pass of Algorithm S1, with \(c\) drawn from Markov kernels, is a Markov kernel.

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.

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.

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).

A probability vector on \(I\) has nonnegative entries which sum to one. A Markov kernel on \(I\) is a matrix with nonnegative entries whose rows sum to one, that is, an element of Matrix.rowStochastic. A matrix \(K\) is reversible with respect to \(p\) if \(p_i K(i, j) = p_j K(j, i)\) for all \(i, j \in I\). The Gibbs kernel with respect to \(p\) is defined by \(K(i, \cdot ) = p\) for every \(i \in I\).

Let \(p\) be a probability vector on \(I\) and \(i \in I\). Then \(p_j \leq 1\) for all \(j \in I\), \(\sum _{j \neq i} p_j = 1 - p_i\), and \(p_j = 0\) for all \(j \neq i\) if \(p_i = 1\). A nonnegative vector which is not zero has a positive sum, and, divided by this sum, is a probability vector.

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.

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 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.

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 target distribution \(\pi \) is a probability measure.

Of two Markov kernels on \(I\) which are reversible with respect to \(p \geq 0\), the one with the larger off-diagonal entries has the smaller quadratic form \(\langle \varphi , K\varphi \rangle _p\), for every \(\varphi \colon I \to \mathbb {R}\).

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]\).

For a Markov kernel \(K\) reversible with respect to \(p\), \(\langle \varphi , K\varphi \rangle _p = \sum _i p_i \varphi (i)^2 - \frac{1}{2} \sum _{i, j} p_i K(i, j) \{ \varphi (i) - \varphi (j)\} ^2\). For a probability vector \(p\), \(p(\varphi )^2 \leq p(\varphi ^2)\). If, moreover, the Markov kernel \(K\) is reversible with respect to \(p\), then \(p(\varphi )^2 - \langle \varphi , K\varphi \rangle _p \leq p(\varphi ^2) - p(\varphi )^2\), that is, minus the lag-one autocovariance of \(\varphi \) is at most its variance.

For \(t \in [T]\), the probability \(\mathbb {P}_{\mathbf{x}}(\tilde{x}_t = x_t)\) under BS exceeds that under FM-BS by an amount between \(0\) and \(\prod _{s=t}^{T-1} \beta _s\).

Let \(t \in [T-1]\) and let \(f \colon \mathsf{X}^2 \to \mathbb {R}\) be measurable with \(\int f(x_t, x_{t+1})^2 \pi (x_{1:T}) \mathrm{d}x_{1:T} {\lt} \infty \). Then

If, moreover, the particles at time \(t\) and those at time \(t + 1\) are almost surely pairwise distinct under \(\bar{\pi }\), then the probabilities of \(\{ (\tilde{x}_t, \tilde{x}_{t+1}) \neq (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.

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 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\).

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.

With \(\mathbf{p} \odot \mathbf{q} \mathrel {\vcenter {:}}=(p_1 q_1, \dotsc , p_N q_N)\), \(C_{\mathbf{p},\mathbf{q}}(i, \cdot ) \mathrel {\vcenter {:}}=\mathbf{q} + q_i \{ F_{\mathbf{p} \odot \mathbf{q}}(i, \cdot ) - \delta _i\} \), \(i \in [N]\).

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]\).

For kernels \(K_{t,j,j}\) as in Algorithm S1, the distribution (S4) of \((\mathbf{x}, a, b_{1:T})\) has the density

For a probability vector \(\mathbf{p}\) on \([N]\),

and \(F_{\mathbf{p}}(i, \cdot ) \mathrel {\vcenter {:}}=\delta _i\) if \(p_i = 1\). For \(\mathbf{u} \in [0, \infty )^N\), \(F_{\mathbf{u}} \mathrel {\vcenter {:}}=F_{\mathbf{u} / (u_1 + \dotsb + u_N)}\) if \(\mathbf{u} \neq \mathbf{0}\) and \(F_{\mathbf{0}}(i, \cdot ) \mathrel {\vcenter {:}}=\delta _i\).

For every \(t \in [T]\) and \(\varphi \colon [N] \to \mathbb {R}\), \(Q_t^{\textsf{M-BS}{}}(\varphi ) \leq Q_t^{\textsf{FM-BS}{}}(\varphi ) \leq Q_t^{\textsf{BS}{}}(\varphi ) \leq Q_t^{\textsf{AT}{}}(\varphi )\) and \(Q_t^{\textsf{CM-BS}{}}(\varphi ) \leq Q_t^{\textsf{FM-BS}{}}(\varphi )\), where the superscripts indicate the selection rule.

For every \(\varphi \colon [N] \to \mathbb {R}\), \(Q_T(\varphi ) = \langle \varphi , K_T \varphi \rangle _{\mathbf{W}_T}\) and, for \(t \in [T-1]\),

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]\),

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 )\).

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 )\).

Let \(\mathbf{p}\) and \(\mathbf{q}\) be probability vectors on \([N]\). For all \(i, i' \in [N]\), \(p_i C_{\mathbf{p},\mathbf{q}}(i, i') = q_{i'} C_{\mathbf{q},\mathbf{p}}(i', i)\). For \(i \neq i'\), \(C_{\mathbf{p},\mathbf{q}}(i, i') \geq q_{i'}\). For every \(\varphi \colon [N] \to \mathbb {R}\), \(\langle \varphi , C_{\mathbf{p},\mathbf{q}} \varphi \rangle _{\mathbf{p}} \leq \mathbf{p}(\varphi ) \mathbf{q}(\varphi )\).

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.

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 \).

The kernel \(F_{\mathbf{p}}\) is reversible with respect to \(\mathbf{p}\). For \(i \neq j\), \(F_{\mathbf{p}}(i, j) \geq p_j\). For every \(\varphi \colon [N] \to \mathbb {R}\), \(\langle \varphi , F_{\mathbf{p}} \varphi \rangle _{\mathbf{p}} \leq \mathbf{p}(\varphi )^2\).

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.

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.

With two particles, \(C_{\mathbf{p},\mathbf{p}} = F_{\mathbf{p}}\) for every probability vector \(\mathbf{p}\).

The Dobrushin coefficients of the backward-sampling probabilities are \(\beta _s \mathrel {\vcenter {:}}=\max _{j, j' \in [N]} \frac{1}{2} \sum _{i=1}^N |B_s(i \mid j) - B_s(i \mid j')|\), \(s \in [T-1]\).

For BS and FM-BS, \(D_{t,j,j'}(\varphi ) = 0\). For AT, \(D_{t,j,j'}(\varphi )\) is the variance of \(\varphi \) under \(B_t(\cdot \mid j)\) if \(j = j'\) and zero otherwise, whereas, for M-BS and CM-BS, \(D_{t,j,j'}(\varphi ) \leq 0\).

Probabilities and expectations conditional on \(\mathbf{x}\) are denoted by \(\mathbb {P}_{\mathbf{x}}\) and \(\mathbb {E}_{\mathbf{x}}\). For \(\varphi \colon [N] \to \mathbb {R}\), \(t \in [T]\), \(s \in [T-1]\), and \(j, j' \in [N]\),

For a function \(\varphi \) of the indices at the times \(t\) and \(t + 1\), \(\mathbb {E}_{\mathbf{x}}\{ \varphi (b_t, b_{t+1}) \varphi (l_t, l_{t+1})\} \) is the expectation over \((b_{t+1}, l_{t+1}) = (j, j')\) of the expression (8), \(\sum _{i, i'} B_t(i \mid j) K_{t,j,j'}(i, i') \varphi (i, j) \varphi (i', j')\).

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 )\).

For \(N = 2\) and \(p_1, p_2 {\gt} 0\), \(F_{\mathbf{p}}(1, 2) = \min \{ 1, p_2 / p_1\} \) is the Metropolis acceptance probability.

For \(t \in [T-1]\) and \(j, j' \in [N]\), the gain is \(\gamma _t(j, j') \mathrel {\vcenter {:}}=\sum _{i=1}^N B_t(i \mid j) \bigl\{ B_t(i \mid j') - K_{t,j,j'}(i, i)\bigr\} \).

For \(N = 2\), \(\gamma _t(j, j) = 2\{ 1 - \max _i B_t(i \mid j)\} ^2\) for both M-BS and CM-BS. For \(j \neq j'\), \(\gamma _t(j, j') = 0\) for M-BS. For CM-BS, \(\gamma _t(j, j') = 2 \min _i B_t(i \mid j) B_t(i \mid j')\) for \(N = 2\) and \(j \neq 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.

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')}\).

If the probabilities \(\mathbf{W}_T\) and \(B_t(\cdot \mid j)\), \(t \in [T-1]\), \(j \in [N]\), are uniform, then \(l_t \neq b_t\) almost surely for every \(t \in [T]\) under CM-BS, whereas \(\mathbb {P}_{\mathbf{x}}(l_t = b_t) = 1/N\) under BS, and under FM-BS for \(t {\lt} T\). Under M-BS, \(\mathbb {P}_{\mathbf{x}}(l_t = b_t) = \{ 1 - (-1/N)^{T-t}\} / (N + 1)\).

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 \).

Let \(t \in [T-1]\) and assume that the particles \(x_t^1, \dotsc , x_t^N\) are almost surely pairwise distinct under \(\bar{\pi }\). For \(j, j' \in [N]\), let \(\gamma _t(j, j') \mathrel {\vcenter {:}}=\sum _{i=1}^N B_t(i \mid j) \{ B_t(i \mid j') - K_{t,j,j'}(i, i)\} \), with the kernels \(K_{t,j,j'}\) of M-BS. Then \(\gamma _t(j, j') \geq 0\) and

The same holds with CM-BS in place of M-BS, in both the kernels and the inequality.

Let \(N = 2\), and assume that, for \(s \in [T-1]\), \(m_{s+1}(x, x')\) does not depend on \(x\). Then, under CM-BS and conditionally on \(\mathbf{x}\) and \(b_{1:T}\), the indices \(l_1, \dotsc , l_T\) are independent, with \(l_t \sim F_{\mathbf{W}_t}(b_t, \cdot )\).

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}\).

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 \).

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.

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.

Let \(t \in [T]\). Then

where the expectation is taken under \(\bar{\pi }\). If there is \(\varepsilon \in (0, 1]\) such that \(m_{s+1}(x, \cdot ) \geq \varepsilon m_{s+1}(x', \cdot )\) for all \(x, x' \in \mathsf{X}\) and \(s \in [T-1]\), then the right-hand side is at most \((1 - \varepsilon )^{T-t}\).

Let \(t \in [T]\) and let \(f \colon \mathsf{X}\to \mathbb {R}\) be measurable with \(\int f(x_t)^2 \pi (x_{1:T}) \mathrm{d}x_{1:T} {\lt} \infty \). Then

and the first inequality also holds with CM-BS in place of M-BS. Moreover,

and the first inequality also holds with CM-BS in place of M-BS.