RAVI proof of convergence for del Moral SMC

RAVI is a framework for reasoning about probabilistic programs which denote marginal distributions (even intractable ones).

Inference algorithms typically fall into this category: for example, in sampling importance resampling (SIR), we care about the sampling distribution of the final returned particle. SIR exposes a joint distribution, whose density is:

$$ P(\{q_i\}_{i = 1}^N, k; P', Q', y) = \prod_{i=1}^N Q'(q_i; y) \times \frac{w_k}{\frac{1}{N} \sum_{i=1}^N w_i} $$

where \( w_k = \frac{P'(q_k, y)}{Q'(q_k; y)} \).

SIR runs importance sampling to generate a particle population (the samples \( q_i \sim Q' \)), and then samples a single particle using a categorical selection (\( k \)) over the importance weights.

Conditional sampling importance resampling (CSIR) exposes a joint distribution over the auxiliary random choices which SIR takes. The density of CSIR is given by:

$$ Q(\{q_i\}_{i = 1}^{N - 1}, k; P', Q', q_k, y) = \prod_{i=1}^{N -1} Q'(q_i; y) \times \frac{1}{N} $$

CSIR involves sampling an index from a uniform categorical over \( N \) choices (the index of the returned particle), and then sampling a population (\( q_i \sim Q' \)) around the chosen particle.