5 Comparison of the selection rules
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')\).
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]\),
By the backward recursion of the marginal distributions of the pairs \((b_t, l_t)\) and the definition of \(D_{t,j,j'}\).
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\).
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.
By backward induction on (7), as in the proof of Theorem 1 in Section S1.
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.
The event \(\{ \tilde{x}_t = x_t\} \) is the disjoint union of the events \(\{ b_t \in S, l_t \in S\} \) over these classes.
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\} })\).
Sum the probabilities of the trajectories of the backward chain of the pairs over the trajectories with given states at one time or at two consecutive times.
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 \).
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.
As in the proof of Theorem 1 in Section S1, with \(\varphi (i) \mathrel {\vcenter {:}}=f(x_t^i)\), \(\mathbb {E}_{\mathbf{x}}\{ f(x_t) f(\tilde{x}_t)\} = Q_t(\varphi )\), whose expectation under the distribution of \(\mathbf{x}\), which does not depend on the selection rule, is the expectation in Theorem 61. The first claim therefore follows from Lemma 57. The second claim follows in the same way, with Lemma 58.
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.
This is the part of the proof of Corollary 1 in Section S1 which holds given the particle positions.
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.
As in the proof of Corollary 1 in Section S1, the inequalities of Lemma 62 are integrated under the distribution of \(\mathbf{x}\) under \(\bar{\pi }\), which does not depend on the selection rule.
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]\).
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 \).
The total-variation distance between two columns of a product of two matrices is at most the Dobrushin coefficient of the first factor times the total-variation distance between the corresponding columns of the second. The last claim follows from \(\frac{1}{2} \sum _i |B_s(i \mid j) - B_s(i \mid j')| = 1 - \sum _i \min \{ B_s(i \mid j), B_s(i \mid j')\} \).
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\).
This is the part of the proof of Proposition 2 in Section S1 which holds given the particle positions.
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}\).
As in the proof of Proposition 2 in Section S1, the bounds of Lemma 66 are integrated under the distribution of \(\mathbf{x}\) under \(\bar{\pi }\), which does not depend on the selection rule. Under the condition on \(m_{s+1}\), \(B_s(i \mid j) \geq \varepsilon W_s^i\) for all \(i, j \in [N]\), so that \(\beta _s \leq 1 - \varepsilon \) by Lemma 65.
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\} \).
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.
This is the part of the proof of Proposition 3 in Section S1 which holds given the particle positions.
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.
As in the proof of Proposition 3 in Section S1, the inequality of Lemma 69 is integrated under the distribution of \(\mathbf{x}\) under \(\bar{\pi }\), which does not depend on the selection rule. Because the particles at time \(t\) are almost surely pairwise distinct, \(\mathbb {P}_{\mathbf{x}}(\tilde{x}_t = x_t) = \mathbb {P}_{\mathbf{x}}(l_t = b_t)\) almost surely.
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'\).
By (4) and (5).
With two particles, \(C_{\mathbf{p},\mathbf{p}} = F_{\mathbf{p}}\) for every probability vector \(\mathbf{p}\).
As in the proof of Proposition 4 in Section S1, let \(p_1 \geq p_2\), the other case being symmetric. Then \(C_{\mathbf{p},\mathbf{p}}(1, 2) = p_2 + p_1 (p_2 / p_1)^2 = p_2 / p_1\) and \(C_{\mathbf{p},\mathbf{p}}(2, 1) = 1\), which are the entries of \(F_{\mathbf{p}}\) by (4).
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 )\).
As in the proof of Proposition 4 in Section S1, \(B_t(\cdot \mid j) = \mathbf{W}_t\) for all \(j \in [N]\) and \(t \in [T-1]\). By Lemma 72, \(C_{\mathbf{W}_t, \mathbf{W}_t} = F_{\mathbf{W}_t}\), so that, by Lemma 49, \((b_{1:T}, l_{1:T})\) has the probability \(\prod _t W_t^{b_t} F_{\mathbf{W}_t}(b_t, l_t)\) given \(\mathbf{x}\).
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)\).
By (4) and (5), the current index is never kept under the kernels \(F_{\mathbf{W}_T}\), \(F_{B_t(\cdot \mid j)}\), and, for CM-BS, \(K_{t,j,j'}\). Under M-BS, \(\mathbb {P}_{\mathbf{x}}(l_T = b_T) = 0\) and, for \(t {\lt} T\), the probability of \(\{ l_t = b_t\} \) is that of \(\{ l_{t+1} \neq b_{t+1}\} \) divided by \(N\). The formula follows by induction on \(T - t\).