# Resample-move algorithm for Sequential Monte Carlo

I'm reading about the resample-move strategy, originally by Gilks and Berzuini, but my question will use the slightly more verbose description from the review of Doucet and Johansen, section 4.4, PDF page 29.

In this algorithm, weighted particles that summarize an underlying distribution of interest are first resampled to evenly weight them using any of the standard methods (multinomial, stratefied, etc.). This resampling step does not move particles, but possibly removes some and duplicates others. Following this resampling step, the particles are then jittered (moved) using a Markov transition kernel, whose ideal invariant is the overall posterior distribution.

Letting $x_k$ denote the particles of the $k^\text{th}$ time-step for $k=1,...,n$, the Markov kernel for the newest time-step is written $K_n(x_{1:n}'|x_{1:n})$ with invariant distribution $p(x_{1:n}|y_{1:n})$ where $y_1,...,y_n$ are the data at each time-step. Given a lag constant $L$ and setting $x_{1:n-L}'=x_{1:n-L}$, the Gibbs based kernel $$K_n(x_{1:n}'|x_{1:n})=\delta_{x_{1:n-L}}(x_{1:n-L}') \prod_{k=n-L+1}^n p(x_k'|y_{1:n},x_{1:k-1}',x_{k+1:n})$$ is given as an example.

My question is in two parts:

1. The authors write $p(x_k'|y_{1:n},x'_{1:k-1},x_{k+1:n})=p(x_k'|y_k,x_{k-1}',x_{k+1})$ in passing. Is this simplification always true?

2. I'm having conceptual trouble with $p(x_k'|y_k,x_{k-1}',x_{k+1})$. I understand the dependence on $y_k$ and $x_{k-1}'$. But how and why should the proposal $x_k'$ depend on the future value $x_{k+1}$?

I did not check the papers of Gilks and Berzuini and Doucet and Johansen but assume they are dealing with a state space (or hidden Markov) model that writes as $$f(x_{1:n},y_{1:n})=p(x_1)p(y_1|x_1)\prod_{t=2}^n p(x_t|x_{t-1})p(y_t|x_t)$$ in which case $$p(x_t'|y_{1:n},x'_{1:t-1},x_{t+1:n})=p(x_t'|y_t,x_{t-1}',x_{t+1})$$ is indeed true: the primary sequence $(x_t)$ is a Markov chain and the secondary sequence $(y_t)$ is made of independent draws given the primary sequence $(x_t)$. As for the puzzling nature of$$p(x_t'|y_t,x_{t-1}',x_{t+1})$$there may be two sources of confusion:

1. one is a dependence on "future" values like $x_{t+1}$, but dependence and independence do not consider dynamics: if $x_{t+1}$ depends on $x_t$ then $x_{t}$ depends on $x_{t+1}$;
2. another one is the apparent paradox of generating the value at time $t$ by conditioning on the next value at time $t+1$. The paradox is resolved by considering that the conditioning is on the value at time $t+1$ generated at the previous iteration, hence available.
• Both were sources of confusion, much appreciated! – Ian Hincks Jan 18 '18 at 14:56

I can't add much to the second part of the above answer, but FWIW here are some more details about the assumptions that are typical for state space models or hidden Markov models using the notation from one of your linked documents.

$p(x_k'|y_{1:n},x'_{1:k-1},x_{k+1:n})=p(x_k'|y_k,x_{k-1}',x_{k+1})$ when you have conditionally independent observations and Markov states:

1. $p(y_{1:n} \mid x_{1:n}) = \prod_{t=1}^n g(y_t \mid x_t)$
2. $p(x_{1:n}) = \mu(x_1) \prod_{t=2}^n f(x_t \mid x_{t-1})$.

\begin{align*} p(x_k'|y_{1:n},x'_{1:k-1},x_{k+1:n}) &= \frac{ p(x_k', y_{1:n},x'_{1:k-1},x_{k+1:n}) }{ p(y_{1:n},x'_{1:k-1},x_{k+1:n}) } \\ &= \frac{p(y_{1:n}\mid x'_{1:k},x_{k+1:n})p(x'_{1:k},x_{k+1:n}) }{ \int p(y_{1:n}\mid x'_{1:k},x_{k+1:n)}p(x'_{1:k},x_{k+1:n}) dx_k' } \\ &= \frac{ \prod_{i=1}^k g(y_i \mid x_i')\prod_{j=k+1}^n g(y_j \mid x_j) p(x'_{1:k},x_{k+1:n}) }{ \int \prod_{i=1}^k g(y_i \mid x_i')\prod_{j=k+1}^n g(y_j \mid x_j) p(x'_{1:k},x_{k+1:n}) dx_k' } \tag{1} \\ &= \frac{ \prod_{i=1}^k g(y_i \mid x_i')\prod_{j=k+1}^n g(y_j \mid x_j) \mu(x_1')\prod_{t=2}^kf(x'_t \mid x_{t-1}') f(x_{k+1} \mid x_k') \prod_{s=k+2}^n f(x_s \mid x_{s-1}) }{ \int \prod_{i=1}^k g(y_i \mid x_i')\prod_{j=k+1}^n g(y_j \mid x_j) \mu(x_1')\prod_{t=2}^k f(x'_t \mid x_{t-1}') f(x_{k+1} \mid x_k') \prod_{s=k+2}^n f(x_s \mid x_{s-1})dx_k' } \tag{2} \\ &= \frac{g(y_k \mid x_k') f(x_{k}'\mid x_{k-1}')f(x_{k+1}\mid x_k') }{ \int g(y_k \mid x_k') f(x_{k}'\mid x_{k-1}')f(x_{k+1}\mid x_k') dx_k' } \tag{cancellations} \\ &= \frac{p(y_k, x_{k+1},x_k'\mid x_{k-1}')}{p(y_k, x_{k+1}\mid x_{k-1}') } \\ &= p(x_k'\mid y_k,x_{k-1}' x_{k+1}). \end{align*}

It's less messy if you just say \begin{align*} p(x_k'|y_{1:n},x'_{1:k-1},x_{k+1:n}) &\propto p(y_{1:n},x'_{1:k},x_{k+1:n}) \end{align*} plug in (1) and (2), mind the apostrophe/tick marks, and drop everything that doesn't have an $x_k'$ in it.