Exact forward sampling

Start again with the forward recursion (10)

$$p(s_t,x^t) = \sum_{s_{t-1}} p(x_t,s_t\vert s_{t-1}) p(s_{t-1}, x^{t-1})$$

and reformulate as

$$p(s_t\vert x^t) \propto \sum_{s_{t-1}} p(x_t,s_t\vert s_{t-1}) \, p(s_{t-1}\vert x^{t-1})$$

$$= \sum_{s_{t-1}} p(s_t\vert s_{t-1},x_t) \, p(x_t\vert s_{t-1}) \, p(s_{t-1}\vert x^{t-1}) \quad .$$

Approximate $p(s_{t-1}\vert x^{t-1}) \approx \sum_{i=1}^N w^i \, \delta(s_{t-1}-s^i)$ with $s^i \sim p(s_{t-1}\vert x^{t-1})$ and $w_i=1\over N$ , then

$$p(s_t\vert x^t) \propto \sum_i w^i p(x_t\vert s^i) \, p(s_t\vert s^i, x_t)$$

The normalisation is just $\sum_i w^i p(x_t\vert s^i)$ , so for we can sample from $p(s_t\vert x^t)$ according to this algorithm:

$$\mathtt 1. \mathtt{Sample}\quad i\sim \left(\frac{p(x_t\vert s^i)}{\sum_i p(x_t\vert s^i)}\right)$$

$$\mathtt 2. \mathtt{Sample}\quad s_t\sim p(s_t\vert s^i, x_t)$$ (24)

This requires to evaluate $p(x_t\vert s_{t-1})$ and sample from $p(s_t\vert s^i, x_t)$ . I.e. the algorithm generates a sequence of swarms of `particles' $\left(s_t^{(i)}\right)_{i=1}^N$ by recursively sampling according to (24).