Explicit values for two particles and for uniform probabilities

In Sections 4.2 and 4.3 of the paper, explicit values are given for the gains γ_t(j, j') of M-BS and CM-BS with two particles and for the probabilities that the indices of the output and of the reference coincide when the final weights and the backward-sampling probabilities are uniform. These values are stated and proved here.

theorem CSMC.gain_MBS_of_ne {n : ℕ} {ι : Type u_1} [Fintype ι] [DecidableEq ι] (W : ι → ℝ) (B : Fin n → Matrix ι ι ℝ) (s : Fin n) {j j' : ι} (hjj' : j ≠ j') : gain B (SelectionRule.MBS.kernels W B) s j j' = 0

For j ≠ j', the gain of M-BS is zero (Section 4.2).

theorem CSMC.sum_mul_sub_forced_fin_two {p : Fin 2 → ℝ} (hp : IsProbVector p) : ∑ i : Fin 2, p i * (p i - forced p i i) = 2 * (1 - max (p 0) (p 1)) ^ 2

For a probability vector p on two indices, ∑_i p_i (p_i - F_p(i, i)) = 2 (1 - max_i p_i) ^ 2.

theorem CSMC.gain_fin_two {n : ℕ} (W : Fin 2 → ℝ) {B : Fin n → Matrix (Fin 2) (Fin 2) ℝ} (hB : ∀ (s : Fin n) (j : Fin 2), IsProbVector fun (i : Fin 2) => B s i j) (s : Fin n) (j j' : Fin 2) : gain B (SelectionRule.MBS.kernels W B) s j j = 2 * (1 - max (B s 0 j) (B s 1 j)) ^ 2 ∧ gain B (SelectionRule.CMBS.kernels W B) s j j = 2 * (1 - max (B s 0 j) (B s 1 j)) ^ 2 ∧ (j ≠ j' → gain B (SelectionRule.CMBS.kernels W B) s j j' = 2 * min (B s 0 j * B s 0 j') (B s 1 j * B s 1 j'))

For two particles, γ_t(j, j) = 2 (1 - max_i B_t(i|j)) ^ 2 for M-BS and CM-BS, and γ_t(j, j') = 2 min_i B_t(i|j) B_t(i|j') for CM-BS and j ≠ j' (Section 4.2).

theorem CSMC.coincidence_uniform {n N : ℕ} (hN : 2 ≤ N) {W : Fin N → ℝ} {B : Fin n → Matrix (Fin N) (Fin N) ℝ} (hW : ∀ (i : Fin N), W i = 1 / ↑N) (hB : ∀ (s : Fin n) (i j : Fin N), B s i j = 1 / ↑N) (t : Fin (n + 1)) : ∑ i : Fin N, marg W B (SelectionRule.CMBS.kernels W B) t i i = 0 ∧ ∑ i : Fin N, marg W B (SelectionRule.BS.kernels W B) t i i = 1 / ↑N ∧ (t ≠ Fin.last n → ∑ i : Fin N, marg W B (SelectionRule.FMBS.kernels W B) t i i = 1 / ↑N) ∧ ∑ i : Fin N, marg W B (SelectionRule.MBS.kernels W B) t i i = (1 - (-1 / ↑N) ^ (n - ↑t)) / (↑N + 1)

If the final weights and the backward-sampling probabilities are uniform on N ≥ 2 indices, the probability P_𝐱(l_t = b_t) that the indices of the output and of the reference coincide at time t is zero under CM-BS, 1/N under BS and, for t < T, under FM-BS, and (1 - (-1/N) ^ (T - t)) / (N + 1) under M-BS (Section 4.3). With T = n + 1 and t the time t.val + 1 of the paper, T - t = n - t.val.