Sequential Monte Carlo Samplers

Problem Set-Up

This is all taken from Sequential Monte Carlo samplers. We have a collection of target distributions $${\pi }_n(x)=\frac{{\gamma }_n(x)}{Z_n}$$ and we would like to sample from them sequentially in order to approximate expectations.

Importance Sampling

We write target expectations using the Importance Sampling (IS) trick for a proposal density ${\eta }_n$ $${\mathbb{E}}_{{\pi }_n}[\varphi ]={\int }_E\varphi (x){\pi }_n(x)dx=\frac{1}{Z_n}{\int }_E\varphi (x){\gamma }_n(x)dx=\frac{1}{Z_n}{\int }_E\varphi (x)w_n(x){\eta }_n(x)dx$$ $$Z_n={\int }_E{\gamma }_n(x)dx={\int }_E{w}_n(x){\eta }_n(x)dx$$ where we have defined importance weights as $$w_n(x)=\frac{{\gamma }_n(x)}{{\eta }_n(x)}$$ Therefore importance sampling uses the following particle approximation $${\eta }_n^N(dx)=\frac{1}{N}\sum _{i=1}^N{\delta }_{X_n^{(i)}}(dx)$$ Plugging this into the two expressions above we obtain $$\begin{array}{r}{\mathbb{E}}_{{\pi }_n}[\varphi ]=\frac{{\mathbb{E}}_{{\eta }_n}[\varphi w_n]}{{\mathbb{E}}_{{\eta }_n}[w_n]}\approx \frac{{\mathbb{E}}_{{\eta }_n^N}[\varphi w_n]}{{\mathbb{E}}_{{\eta }_n^N}[w_n]}=\frac{\sum _{i=1}^N\varphi (X_n^{(i)})w_n(X_n^{(i)})}{\sum _{i=1}^N{w}_n(X_n^{(i)})}=\sum _{i=1}^N\varphi (X_n^{(i)})W_n(X_n^{(i)})\end{array}$$ where we have defined the normalized importance weights $$W_n(X_n^{(i)})=\frac{w_n(X_n^{(i)})}{\sum _{j=1}^N{w}_n(X_n^{(j)})}$$

Sequential Importance Sampling

In importance sampling, for each different target ${\pi }_n$ we would sample the particles afresh from ${\eta }_n$. This assumes that we can sample from ${\eta }_n\approx {\pi }_n$ and that we can evaluate ${\eta }_n$ in order to evaluate the unnormalized IS weights $$w_n(x)=\frac{{\gamma }_n(x)}{{\eta }_n(x)}$$ In Sequential Importance Sampling (SIS) we start using IS at $n=1$ but then we build ${\eta }_n$ from the previous iteration. Specifically we do this:

• At time $n=1$ our target is ${\pi }_1$ and we use an IS proposal ${\eta }_1$ which we choose to approximate well ${\pi }_1$ (often we choose ${\eta }_1={\pi }_1$). This means we sample particles $X_1^{(1:N)}$ from ${\eta }_1$ and then compute the IS unnormalized weights $$w_1(X_1^{(i)})=\frac{{\gamma }_1(X_1^{(i)})}{{\eta }_1(X_1^{(i)})}$$
• Suppose that at time $n-1$ we had a set of particles $\{X_{n-1}^{(i)}\}$ sampled from ${\eta }_{n-1}$. Our target at time $n$ is ${\pi }_n$. In order to propose a new set of particles we use a Markov Kernel $K_n(x^{\prime }\mid x)$. We call the resulting distribution ${\eta }_n$. Notice that this distribution can be found using the property that a kernel $K_n$ operates on measures on the left $${\eta }_n={\eta }_{n-1}{K}_n⟹{\eta }_n(x^{\prime })={\int }_E{\eta }_{n-1}(x)K_n(x^{\prime }\mid x)dx$$ Once we have sampled from the kernel to move the particles forward $X_n^{(i)}\sim K_n(\cdot \mid X_{n-1}^{(i)})$, we need to compute the weights to account for the discrepancy of sampling from ${\eta }_n$ rather than ${\pi }_n$ $$w_n(X_n^{(i)})=\frac{{\gamma }_n(X_n^{(i)})}{{\eta }_n(X_n^{(i)})}$$ However notice we can only do this if we can evaluate ${\eta }_n$.

In general, we cannot evaluate ${\eta }_n$ because it is defined in terms of an integral with respect to $x_{1:n-1}$. Indeed consider ${\eta }_3$

$$\begin{array}{rl}{\eta }_3(x_3)& ={\int }_E{\eta }_2(x_2)K_3(x_3\mid x_2)d{x}_2\\ & ={\int }_E[{\int }_E{\eta }_1(x_1)K_2(x_2\mid x_1)d{x}_1]K_3(x_3\mid x_2)d{x}_2\\ & ={\int }_{E^2}{\eta }_1(x_1)K_3(x_3\mid x_2)K_2(x_2\mid x_1)d{x}_{1}d{x}_2\end{array}$$

In general ${\eta }_n$ will be $${\eta }_n(x_n)={\int }_{E^{n-1}}{\eta }_1(x_1)\prod _{k=1}^n{K}_k(x_k\mid x_{k-1})d{x}_{1:k-1}$$ which is clearly intractable.

SMC sampler

Since the problem is integration with respect to $x_{1:k-1}$ we “open up” the integral and instead consider its integrand. Rather than considering ${\eta }_n(x_n)$ which proposes a new set of particles $\{X_n^{(i)}\}$ from $\{X_{n-1}^{(i)}\}$ we consider the proposal distribution ${\eta }_n(x_{1:n})$ defined as $${\eta }_n(x_{1:n})={\eta }_1(x_1)\prod _{k=2}^n{K}_k(x_k\mid x_{k-1})$$ We would now like to perform importance sampling. To do this, we need to extend the target from ${\pi }_n(x_n)$ to ${\tilde{\pi }}_n(x_{1:n})$. We do this by introducing backward kernels $L_{n-1}(x_{n-1}\mid x_n)$ $${\tilde{\pi }}_n(x_{1:n})=\frac{1}{Z_n}{\tilde{\gamma }}_n(x_{1:n})=\frac{1}{Z_n}{\gamma }_n(x_n)\prod _{k=1}^{n-1}{L}_k(x_k\mid x_{k+1})$$ The IS weights would then become $$\begin{array}{rl}{w}_n(x_{1:n})& =\frac{{\tilde{\gamma }}_n(x_{1:n})}{{\eta }_n(x_{1:n})}\\ & =\frac{{\gamma }_n(x_n)\prod _{k=1}^{n-1}{L}_k(x_k\mid x_{k+1})}{{\eta }_1(x_1)\prod _{k=2}^n{K}_k(x_k\mid x_{k-1})}\\ & =\frac{{\gamma }_n(x_n)L_{n-1}(x_{n-1}\mid x_n)L_{n-2}(x_{n-2}\mid x_{n-1})\cdots L_1(x_1\mid x_2)}{{\eta }_1(x_1)K_n(x_n\mid x_{n-1})K_{n-1}(x_{n-1}\mid x_{n-2})\cdots K_2(x_2\mid x_1)}\\ & =\frac{{\gamma }_n(x_n)L_{n-1}(x_{n-1}\mid x_n)}{{\gamma }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}\cdot \frac{{\gamma }_{n-1}(x_{n-1})L_{n-2}(x_{n-2}\mid x_{n-1})\cdots L_1(x_1\mid x_2)}{{\eta }_1(x_1)K_{n-1}(x_{n-1}\mid x_{n-2})\cdots K_2(x_2\mid x_1)}\\ & =\frac{{\gamma }_n(x_n)L_{n-1}(x_{n-1}\mid x_n)}{{\gamma }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}\cdot w_{n-1}(x_{1:n-1})\\ & ={\tilde{w}}_n(x_n\mid x_{n-1})w_{n-1}(x_{1:n-1})\end{array}$$

where we have defined the incremental weight as $${\tilde{w}}_n(x_n\mid x_{n-1})=\frac{{\gamma }_n(x_n)L_{n-1}(x_{n-1}\mid x_n)}{{\gamma }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}$$

To summarize:

• Importance Sampling at time $n$ targets ${\pi }_n$. It samples particles $\{X_n^{(i)}\}$ afresh from a proposal ${\eta }_n$ and computes weights afresh as $w_n(X_n^{(i)})={\gamma }_n(X_n^{(i)})/{\eta }_n(X_n^{(i)})$. For this to work, however, we need to be able to find proposals ${\eta }_n\approx {\pi }_n$ which is in general very hard.
• Sequential Importance Sampling also targets ${\pi }_n$ at time $n$. It tries to fix the problem of finding ${\eta }_n$ by using a local Markov Kernel $K_n(\cdot \mid X_{n-1}^{(i)})$ to sample a new set of particles $\{X_n^{(i)}\}$ starting from $\{X_{n-1}^{(i)}\}$. This, at time $n$, gives rise to the following proposal distributions $${\eta }_n(x_n)={\int }_{E^{n-1}}{\eta }_1(x_1)\prod _{k=2}^n{K}_k(x_k\mid x_{k-1})d{x}_{1:k-1}$$ We can now sample from ${\eta }_n(x_n)$ but we cannot evaluate ${\eta }_n(\cdot )$ due to the integral with respect to $x_{1:k-1}$. Evaluating ${\eta }_n$ is needed to compute the IS weights $$w_n(X_n^{(i)})=\frac{{\gamma }_n(X_n^{(i)})}{{\eta }_n(x_n)}$$
• SMC Samplers overcomes the problem of integrating over $x_{1:k-1}$ by working with the integrand directly. The proposal and the target distributions are then ${\eta }_n(x_{1:n})$ and ${\tilde{\pi }}_n(x_{1:n})$. Notice the difference with respect to IS and SIS: In IS and SIS we get new particles at each time step, that is at time step $n-1$ we have $X_{n-1}^{(1:N)}$ and at time step $n$ we have $X_n^{(1:N)}$. In an SMC sampler, instead, we extend the particles at time $n-1$ $X_{1:n-1}^{(1:N)}$ by sampling from a kernel $X_n^{(i)}\sim K_n(\cdot \mid X_{n-1}^{(i)})$ and then appending this to the current particles to obtain $X_{1:n}^{(1:N)}$. Since we have appended $X_n^{(1:N)}$ to the previous particles, we need to update the weights and these are updated using an incremental weight $${\tilde{w}}_n(x_n\mid x_{n-1})=\frac{{\gamma }_n(x_n)L_{n-1}(x_{n-1}\mid x_n)}{{\gamma }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}$$ Importantly, this requires us to introduce backwards kernels which essentially allow us to approach the problem from an auxiliary variable perspective.

Since the variance of the weights increases as ${\eta }_n$ and ${\tilde{\pi }}_n$ become further apart, one often resamples the particles according to $${\tilde{\pi }}_n^N(d{x}_{1:n})=\sum _{i=1}^N{W}_n^{(i)}{\delta }_{X_{1:n}^{(i)}}(d{x}_{1:n})$$

The algorithm is summarized below.

A few notes:

• The particle estimate of the $n$th target is $${\pi }_n^N(dx)=\sum _{i=1}^N{W}_n(X_{1:n}^{(i)}){\delta }_{X_n^{(i)}}(dx)$$
• It is helpful to remember the distributions of $X_n^{(i)}$ and $X_{1:n}^{(i)}$ (using sloppy notation) $$\begin{array}{rl}{X}_n^{(i)}& \sim {\int }_{E^{n-1}}{\eta }_1(x_1)\prod _{k=2}^n{K}_k(x_k\mid x_{k-1})d{x}_{1:k-1}\\ X_{1:n}^{(i)}& \sim {\eta }_1(x_1)\prod _{k=2}^n{K}_k(x_k\mid x_{k-1})\end{array}$$
• The optimal backward kernel takes us back to IS on $E$ $$L_{n-1}^{\text{opt}}(x_{n-1}\mid x_n)=\frac{{\eta }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}{{\eta }_n(x_n)}$$ It is difficult to use this kernel as it relies on ${\eta }_{n-1}$ and ${\eta }_n$ which are intractable (indeed it is the reason why we went from SIS to SMC samplers).
• Sub-optimal kernel: substitute ${\pi }_n$ for ${\eta }_n$. This is motivated by the fact that, if ${\eta }_n$ is a good proposal for ${\pi }_n$ then they should be sufficiently close. First, rewrite the optimal kernel $$L_{n-1}^{\text{opt}}(x_{n-1}\mid x_n)=\frac{{\eta }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}{{\eta }_n(x_n)}=\frac{{\eta }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}{{\displaystyle {\int }_E{\eta }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})d{x}_{n-1}}}$$ Now substitute ${\pi }_n$ and ${\pi }_{n-1}$ for ${\eta }_n$ and ${\eta }_{n-1}$ respectively. $$L_{n-1}(x_{n-1}\mid x_n)=\frac{{\pi }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}{{\displaystyle {\int }_E{\pi }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})d{x}_{n-1}}}$$ The incremental weights become $$\begin{array}{rl}{w}_n(x_n\mid x_{n-1})& =\frac{{\gamma }_n(x_n)L_{n-1}(x_{n-1}\mid x_n)}{{\gamma }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}\\ & =\frac{{\gamma }_n(x_n){\pi }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})}{{\gamma }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1}){\displaystyle {\int }_E{\pi }_{n-1}(x_{n-1})K_n(x_n\mid x_{n-1})d{x}_{n-1}}}\end{array}$$

IS Measure Theory

Suppose ${\pi }_1:\mathcal{E}\to [0,1]$ is our target probability distribution and ${\eta }_1:\mathcal{E}\to [0,1]$ is our IS proposal probability distribution. Suppose that they admit density with respect to the Lebesgue measure $dx$ on $(E,\mathcal{E})$ $$\frac{d{\pi }_1}{dx}=\frac{{\tilde{p}}_{{\pi }_1}(x)}{{\displaystyle {\int }_E{\tilde{p}}_{{\pi }_1}(y)dy}}=p_{{\pi }_1}(x)\frac{d{\eta }_1}{dx}(x)=\frac{{\tilde{p}}_{{\eta }_1}(x)}{{\displaystyle {\int }_E{\tilde{p}}_{{\eta }_1}(y)dy}}=p_{{\eta }_1}(x)$$ Suppose that ${\pi }_1\ll {\eta }_1$ then the Radon-Nikodym derivative of ${\pi }_1$ with respect to ${\eta }_1$ exists $$\frac{d{\pi }_1}{d{\eta }_1}=\frac{w_1(x)}{{\displaystyle {\int }_E{w}_1(x)d{\eta }_1(x)}}$$ We can the approximate the expectation as follows $$\begin{array}{rl}{\mathbb{E}}_{{\pi }_1}[\varphi ]& ={\int }_E\varphi (x)d{\pi }_1(x)\\ & ={\int }_E\varphi (x)\frac{d{\pi }_1}{d{\eta }_1}(x)d{\eta }_1(x)\\ & ={\int }_E\varphi (x)\frac{d{\pi }_1}{d{\eta }_1}(x)\frac{d{\eta }_1}{dx}(x)dx\\ & =\frac{{\displaystyle {\int }_E\varphi (x)w_1(x)p_{{\eta }_1}(x)dx}}{{\displaystyle {\int }_E{w}_1(x)d{\eta }_1(x)}}\\ & =\frac{{\displaystyle {\int }_E\varphi (x)w_1(x)p_{{\eta }_1}(x)dx}}{{\displaystyle {\int }_E{w}_1(x)\frac{d{\eta }_1}{dx}(x)dx}}\\ & =\frac{{\displaystyle {\int }_E\varphi (x)w_1(x)p_{{\eta }_1}(x)dx}}{{\displaystyle {\int }_E{w}_1(x)p_{{\eta }_1}(x)dx}}\end{array}$$

Now suppose you have samples $\{X_1^{(1:N)}\}\sim {\eta }_1$ then we can construct the particle approximation $${\eta }_1^N(dx)=\frac{1}{N}\sum _{i=1}^N{\delta }_{X_1^{(i)}}(dx)$$ Substituting this into the expression for the expectation we get $$\begin{array}{rl}{\mathbb{E}}_{{\pi }_1}[\varphi ]& =\frac{{\mathbb{E}}_{{\eta }_1}[\varphi w_1]}{{\mathbb{E}}_{{\eta }_1}[w_1]}\\ & \approx \frac{{\mathbb{E}}_{{\eta }_1^N}[\varphi w_1]}{{\mathbb{E}}_{{\eta }_1^N}[w_1]}\\ & =\frac{{\displaystyle \frac{1}{N}\sum _{i=1}^N{\int }_E\varphi (x)w_1(x){\delta }_{X_1^{(i)}}(dx)}}{{\displaystyle \frac{1}{N}\sum _{i=1}^N{\int }_E{w}_1(x){\delta }_{X_1^{(i)}}(dx)}}\\ & =\frac{{\displaystyle \sum _{i=1}^N\varphi (X_1^{(i)})w_1(X_1^{(i)})}}{{\displaystyle \sum _{i=1}^N{w}_1(X_1^{(i)})}}\\ & =\sum _{i=1}^N\varphi (X_1^{(i)})W_1(X_1^{(i)})\end{array}$$ where $$W_1(X_1^{(i)})=\frac{w_1(X_1^{(i)})}{{\displaystyle \sum _{j=1}^N{w}_1(X_1^{(j)})}}$$

SIS Proposal

Now let $K_n:E\times \mathcal{E}\to [0,1]$ be a Markov Kernel. Then this kernels can operate on the left with measures. $${\eta }_n={\eta }_{n-1}{K}_n⟹{\eta }_n(A)={\int }_E{K}_n(x,A)d{\eta }_{n-1}(x)={\int }_{E}d{\eta }_{n-1}(x){\int }_A{K}_n(x,dy)$$ Denote by $K_{n,x}:\mathcal{E}\to [0,1]$ the probability measure in the second argument of the kernel, i.e. $K_{n,x}(A)=K_n(x,A)$ Suppose that $K_{n,x}$ admits a density with respect to the Lebesgue measure $$\frac{d{K}_{n,x}}{dy}(y)=k_n(y\mid x)$$ Then the new measure can be written as $$\begin{array}{rlrl}{\eta }_n& ={\int }_E\frac{d{\eta }_{n-1}}{dx}[{\int }_A{K}_n(x,dy)]dx& & {\eta }_{n-1}\ll dx\\ & ={\int }_E\frac{d{\eta }_{n-1}}{dx}[{\int }_{A}d{K}_{n,x}(y)]dx& & \text{def }{K}_{n,x}\\ & ={\int }_E{p}_{{\eta }_{n-1}}(x)\left[{\int }_A\frac{d{K}_{n,x}(y)}{dy}dy\right]dx& & K_{n,x}\ll dy\\ & ={\int }_E{p}_{{\eta }_{n-1}}(x)[{\int }_A{k}_n(y\mid x)dy]dx\\ & ={\int }_E{\int }_A{p}_{{\eta }_{n-1}}(x)k_n(y\mid x)dydx\\ & ={\int }_A[{\int }_E{p}_{{\eta }_{n-1}}(x)k_n(y\mid x)dx]dy\end{array}$$ Then by definition we must have that the expression in parenthesis is indeed the density of ${\eta }_n$ with respect to $dy$ $$\frac{d{\eta }_n}{dy}={\int }_E{p}_{{\eta }_{n-1}}(x)k_n(y\mid x)dx$$ Or more precisely, identifying $x=x_{n-1}$ and $y=x_n$ we have $$p_{{\eta }_n}(x_n)=\frac{d{\eta }_n}{d{x}_n}(x_n)={\int }_E{p}_{{\eta }_{n-1}}(x_{n-1})k_n(x_n\mid x_{n-1})d{x}_{n-1}$$ Indeed we have $${\eta }_n(A)={\int }_{A}d{\eta }_n(x_n)={\int }_A\frac{d{\eta }_n}{d{x}_n}d{x}_n={\int }_A{p}_{{\eta }_n}(x_n)d{x}_n$$

SMC Proposal

The proposal in the SMC sampler is not given by $${\eta }_n={\eta }_{n-1}{K}_n.$$ Indeed in SMC we don’t simply propose $X_n^{(i)}$. We propose $X_n^{(i)}$ and then we append it to $X_{1:n-1}^{(i)}$ which was generated according to ${\eta }_{n-1}$ and so on.

SMC Steps

• Step $n=1$: Our target is ${\pi }_1$ and proposal ${\eta }_1$ is given. Sample $X_1^{(1:N)}\sim {\eta }_1$. Weights are RN-derivative $$w_1\propto \frac{d{\pi }_1}{d{\eta }_1}$$
• Step $n=2$: Move particles forward using kernel $K_2:E\times \mathcal{E}\to [0,1]$. We sample $X_2^{(i)}\sim K_2(\cdot \mid X_1^{(i)})$. Marginally, each new particle $X_n^{(i)}$ is distributed as $$X_2^{(i)}\sim {\eta }_2={\eta }_1{K}_2$$ Which can be written as $$\begin{array}{rl}{\eta }_2(A)& ={\int }_{E}d{\eta }_2\\ & ={\int }_{E}d({\eta }_1{K}_2)\\ & ={\int }_E{K}_2(x_1,A)d{\eta }_1(x_1)\\ & ={\int }_E{\int }_A{K}_2(x_1,d{x}_2){\eta }_1(x_1)\\ & ={\int }_E\left[{\int }_A\frac{d{K}_2(x_1,\cdot )}{d{x}_2}d{x}_2\right]\frac{d{\eta }_1(x_1)}{d{x}_1}d{x}_1\\ & ={\int }_E[{\int }_A{k}_2(x_2\mid x_1)d{x}_2]p_{{\eta }_1}(x_1)d{x}_1\\ & ={\int }_E{\int }_A{k}_2(x_2\mid x_1)p_{{\eta }_1}(x_1)d{x}_{2}d{x}_1\\ & ={\int }_A[{\int }_E{k}_2(x_2\mid x_1)p_{{\eta }_1}(x_1)d{x}_1]d{x}_2\end{array}$$ where we can see that the density of ${\eta }_2$ is $$\frac{d{\eta }_2}{d{x}_2}(x_2)={\int }_E{k}_2(x_2\mid x_1)p_{{\eta }_1}(x_1)d{x}_1.$$ In SMC we then append $X_2^{(i)}$ to $X_1^{(i)}$ to get $X_{1:2}^{(i)}$ so our aim is now to find a measure for it.

Define ${\eta }_{1:2}:=\eta \times K(x_1,\cdot )$ to be the following product measure on $\mathcal{E}\otimes \mathcal{E}$ $${\eta }_{1:2}(A\times B):=({\eta }_1\times K(x_1,\cdot ))(A\times B)={\eta }_1(A)K(x_1,B)A\times B\in \mathcal{E}\otimes \mathcal{E}{x}_1\in E$$ Since ${\eta }_1\ll d{x}_1$ and $K(x_1,\cdot )\ll d{x}_2$ by a standard result (see here and here) on product measures we have that ${\eta }_{1:2}\ll d(x_1\times x_2)$ and $$\begin{array}{rl}\frac{d{\eta }_{1:2}}{d(x_1\times x_2)}(x_{1:2})& =\frac{d({\eta }_1\times K(x_1,\cdot ))}{d(x_1\times x_2)}(x_{1:2})\\ & =\frac{d{\eta }_1}{d{x}_1}(x_1)\cdot \frac{dK(x_1,\cdot )}{d{x}_2}(x_2)\\ & =p_{{\eta }_1}(x_1)k_2(x_2\mid x_1)\end{array}$$ If we also define the extended target as the following product measure $${\pi }_{1:2}(A\times B)=(L_1(x_2,\cdot )\times {\pi }_2)(A,B)=L_1(x_2,A){\pi }_2(B)$$ then by the same arguments as above its Radon-Nikodym derivative will be given by $$\begin{array}{r}\frac{d{\pi }_{1:2}}{d(x_1\times x_2)}(x_{1:2})\\ & =\frac{d(L_1(x_2,\cdot )\times {\pi }_2)}{d(x_1\times x_2)}(x_{1:2})\\ & =\frac{d{L}_1(x_2,\cdot )}{d{x}_1}(x_1)\cdot \frac{d{\pi }_2}{d{x}_2}(x_2)\\ & =\ell (x_1\mid x_2)p_{{\pi }_2}(x_2)\end{array}$$ where $\ell$ is the density of $L$ with respect to $x_1$. As long as ${\pi }_{1:2}\ll {\eta }_{1:2}$ the weights are given by $$\begin{array}{rl}{w}_{1:2}(x_{1:2})& =\frac{d{\pi }_{1:2}}{d{\eta }_{1:2}}(x_{1:2})\\ & =\frac{d{\pi }_{1:2}}{d(x_1\times x_2)}\cdot \frac{d(x_1\times x_2)}{d{\eta }_{1:2}}(x_{1:2})& & \text{chain rule}\\ & =\frac{d{\pi }_{1:2}}{d(x_1\times x_2)}\cdot {\left(\frac{d{\eta }_{1:2}}{d(x_1\times x_2)}\right)}^{-1}(x_{1:2})& & \text{see below}\\ & =\frac{p_{{\pi }_2}(x_2)\ell (x_1\mid x_2)}{p_{{\eta }_1}(x_1)k_2(x_2\mid x_1)}\\ & =\frac{p_{{\pi }_2}(x_2)\ell (x_1\mid x_2)}{p_{{\pi }_1}(x_1)k_2(x_2\mid x_1)}\cdot \frac{p_{{\pi }_1}(x_1)}{p_{{\eta }_1}(x_1)}\\ & \propto \frac{{\tilde{p}}_{{\pi }_2}(x_2)\ell (x_1\mid x_2)}{{\tilde{p}}_{{\pi }_1}(x_1)k_2(x_2\mid x_1)}\cdot \frac{{\tilde{p}}_{{\pi }_1}(x_1)}{{\tilde{p}}_{{\eta }_1}(x_1)}\end{array}$$ where on line $3$ we have used the following fact and on line $5$ we have basically multiplied by $1=\frac{d{\pi }_1}{d{\pi }_1}=\frac{d{\pi }_1}{d{x}_1}\cdot {\left(\frac{d{\pi }_1}{d{x}_1}\right)}^{-1}$

• Step $n$: Target is ${\pi }_{1:n}$. Perform importance sampling using ${\eta }_{1:n}$ which is a product measure $${\eta }_{1:n}={\eta }_1\times K_n(x_{n-1},\cdot )\times \cdots \times K_2(x_1,\cdot )$$ with density given by the product rule $$\frac{d{\eta }_{1:n}}{d{x}_{1:n}}=p_{{\eta }_1}(x_1)\prod _{k=2}^n{k}_k(x_k\mid x_{k-1})$$ Similarly the extended target is a product measure $${\pi }_{1:n}={\pi }_n\times L_{n-1}(x_n,\cdot )\times \cdots \times L_1(x_1,\cdot )$$ with density $$\frac{d{\pi }_{1:n}}{d{x}_{1:n}}=p_{{\pi }_n}(x_n)\prod _{k=1}^{n-1}{\ell }_k(x_k\mid x_{k+1})$$ The weights are then given by $$w_{1:n}=\frac{d{\pi }_{1:n}}{d{\eta }_{1:n}}\propto \frac{{\tilde{p}}_{{\pi }_n}(x_n)\ell (x_{n-1}\mid x_n)}{{\tilde{p}}_{{\pi }_{n-1}}(x_{n-1})k_n(x_n\mid x_{n-1})}\cdot w_{1:n-1}$$