Particle smoothing, backward simulation, and Rao–Blackwellized filters

Let $T\ge 0$ be finite, let $({\mathsf{Z}}_t,{\mathcal{Z}}_t)$ be standard-Borel spaces for $0\le t\le T$, and for $1\le t\le T$ let $M_t:{\mathsf{Z}}_{t-1}⇝{\mathsf{Z}}_t$ be probability kernels, with the kernel convention of Measure kernel and probability kernel. For $1\le t\le T$, define the path-extension kernel from ${\mathsf{Z}}_{0:t-1}$ to ${\mathsf{Z}}_{0:t}$ by ${\bar{M}}_t(z_{0:t-1},A)={\int }_{{\mathsf{Z}}_t}{\mathbf{1}}_A(z_{0:t-1},z_t)M_t(z_{t-1},d{z}_t)\mathrm{.}$ Then ${\bar{M}}_t$ is a probability kernel and ${\mathsf{Z}}_{0:t}$ is standard Borel. Its ordered iterates append the nonlinear states with the original transition law.

Assume AC. Let $Z_t$ take values in a standard-Borel space $({\mathsf{Z}}_t,{\mathcal{Z}}_t)$ and let $U_t\in {\mathbb{R}}^{d_t}$ for a finite horizon $0\le t\le T$, where each $d_t$ is a positive integer. For $1\le t\le T$, let $Y_t\in {\mathbb{R}}^{p_t}$ with each $p_t$ a positive integer; observations begin at time $1$. The nonlinear component has initial probability ${\mu }_0$ and transition probability kernels $M_t(z_{t-1},d{z}_t)$; its transition does not depend on $U_{t-1}$. Given the entire nonlinear path $z_{0:T}$, write ${\mathsf{Z}}_{0:t}={\prod }_{s=0}^t{\mathsf{Z}}_s$ with its finite-product sigma-algebra and specify Borel maps $m_0:{\mathsf{Z}}_0\to {\mathbb{R}}^{d_0},P_0:{\mathsf{Z}}_0\to {\mathbb{R}}^{d_0\times d_0},$ and, for $1\le t\le T$, $A_t:{\mathsf{Z}}_{0:t}\to {\mathbb{R}}^{d_t\times d_{t-1}},Q_t:{\mathsf{Z}}_{0:t}\to {\mathbb{R}}^{d_t\times d_t},C_t:{\mathsf{Z}}_{0:t}\to {\mathbb{R}}^{p_t\times d_t},R_t:{\mathsf{Z}}_{0:t}\to {\mathbb{R}}^{p_t\times p_t}\mathrm{.}$ Require $P_0(z_0)$ and $Q_t(z_{0:t})$ to be symmetric positive semidefinite, meaning $v^{T}Pv\ge 0$ for every matching vector $v$, and $R_t(z_{0:t})$ to be symmetric positive definite, meaning $v^T{R}_{t}v>0$ for every nonzero $v$. Conditional on $Z_{0:T}=z_{0:T}$, the linear component and observations have the finite linear-Gaussian model, with the transition and observation equations for $1\le t\le T$: $U_0\sim N(m_0(z_0),P_0(z_0)),U_t=A_t(z_{0:t})U_{t-1}+{\xi }_t,Y_t=C_t(z_{0:t})U_t+{\epsilon }_t,$ where the centered Gaussian noises ${\xi }_t\sim N(0,Q_t(z_{0:t}))$ and ${\epsilon }_t\sim N(0,R_t(z_{0:t}))$ are mutually independent over time and independent of $U_0$, under that conditional law. For every fixed path $z_{0:T}$ these are exactly the hypotheses of Linear-Gaussian state-space models with independent noises with deterministic matrices.

This hierarchical conditionally linear-Gaussian model is the input class for the Rao–Blackwellized filter below: it samples the nonlinear path and keeps the conditional Gaussian law of $U_t$ analytically. It does not include a nonlinear transition whose law depends on $U_{t-1}$, nor does it assert that the marginal nonlinear process remains Markov after conditioning on all observations. Such models need their own marginal transition and backward kernels. A state-space filtering or smoothing law is a data-indexed regular conditional-distribution version as in Filtering, predictive, and smoothing laws in a finite-horizon state-space model; no pointwise uniqueness on null data histories is imposed.

Assume the model of Conditionally linear-Gaussian state-space model and fix a nonlinear path $z_{0:T}$. Run Exact linear-Gaussian Kalman filter on the resulting deterministic linear-Gaussian model for a fixed observation path $y_{1:T}$. Write $m_{t\mathrm{\mid }t-1},P_{t\mathrm{\mid }t-1}$ and $m_{t\mathrm{\mid }t},P_{t\mathrm{\mid }t}$ for its predicted and updated moments, and define $v_t=y_t-C_t(z_{0:t})m_{t\mathrm{\mid }t-1},S_t=C_t(z_{0:t})P_{t\mathrm{\mid }t-1}{C}_t(z_{0:t}{)}^T+R_t(z_{0:t})\mathrm{.}$ Then $\mathcal{L}(U_t\mid Z_{0:T}=z_{0:T},Y_{1:t}=y_{1:t})$ has the Gaussian version $N(m_{t\mathrm{\mid }t},P_{t\mathrm{\mid }t})$ for every $0\le t\le T$. At time $t\ge 1$, the conditional observation density given the nonlinear path and earlier observations is ${\mathrm{\ell }}_t(z_{0:t};y_{1:t})=(2\pi {)}^{-p_t\mathrm{/}2}\det (S_t{)}^{-1\mathrm{/}2}\exp \text{\hspace{0.17em}⁣}(-\frac{1}{2}{v}_t^T{S}_t^{-1}{v}_t)\mathrm{.}$ Each $S_t$ is positive definite, each $P_{t\mathrm{\mid }t}$ is positive semidefinite, and ${\mathrm{\ell }}_t$ is finite, strictly positive, and Borel in the nonlinear path. For every $1\le t\le T$ whose observation evidence is finite positive, the conditional density of $Y_{1:t}$ given the nonlinear path is ${\prod }_{s=1}^t{\mathrm{\ell }}_s(z_{0:s};y_{1:s})$. Consequently the conditional law of $Z_{0:t}$ given $Y_{1:t}=y_{1:t}$ is the normalized Feynman–Kac path measure with path-extension transitions induced by $M_s$, initial potential $G_0\equiv 1$, and potentials $G_s(z_{0:s})={\mathrm{\ell }}_s(z_{0:s};y_{1:s})$. At $t=0$ it is the initial nonlinear law ${\mu }_0$.

Assume AC, a finite-horizon Markov state-space model with standard-Borel states, dominated observation kernels, and data-indexed filtering and smoothing kernels as in Filtering, predictive, and smoothing laws in a finite-horizon state-space model. Fix an observation history $y_{1:T}$ in the full-measure set where the dominated filtering recursion Exact state-space filtering recursion under dominated observations applies. Write ${\eta }_t$ for the filtering law of $X_t$ given $y_{1:t}$. Suppose the transition kernel $M_{t+1}$ from time $t$ to $t+1$ has a product-measurable density $f_{t+1}(x^{\mathrm{\prime }}\mid x)$ with respect to a sigma-finite measure ${\lambda }_{t+1}$, meaning $M_{t+1}(x,A)={\int }_A{f}_{t+1}(x^{\mathrm{\prime }}\mid x){\lambda }_{t+1}(d{x}^{\mathrm{\prime }})$ for every state $x$ and measurable set $A$. Put $q_{t+1}(x^{\mathrm{\prime }})=\int f_{t+1}(x^{\mathrm{\prime }}\mid x){\eta }_t(dx),D_{t+1}=\{x^{\mathrm{\prime }}:0<q_{t+1}(x^{\mathrm{\prime }})<\mathrm{\infty }\}\mathrm{.}$ The backward conditional kernel is $B_t(x^{\mathrm{\prime }},A)=\{\begin{array}{ll}{\displaystyle \frac{{\int }_A{f}_{t+1}(x^{\mathrm{\prime }}\mid x){\eta }_t(dx)}{q_{t+1}(x^{\mathrm{\prime }})},}& x^{\mathrm{\prime }}\in D_{t+1},\\ {\eta }_t(A),& x^{\mathrm{\prime }}\mathrm{\notin }{D}_{t+1}\mathrm{.}\end{array}$ It is a probability-kernel version of the conditional law of $X_t$ given $X_{t+1}=x^{\mathrm{\prime }}$ and $y_{1:t}$. The finite-horizon smoothing kernel factors as ${\psi }_T(d{x}_{0:T})={\eta }_T(d{x}_T){\prod }_{t=T-1}^0{B}_t(x_{t+1},d{x}_t)$ for observation-almost every full history, with the product interpreted as successive backwards kernel integration. If the transition is supplied only as a probability kernel, the same factorization uses a supplied regular conditional kernel of $X_t$ given $(X_{t+1},Y_{1:t})$; no transition density is asserted in that case. Null-history values remain version-dependent.

Fix a finite horizon $T\ge 0$ and a requested path count $S\ge 1$, used in either mode below. In the particle mode, the inputs include a particle count $N\ge 1$ and normalized filtering clouds $\{(x_t^i,w_t^i):1\le i\le N\},w_t^i\ge 0,{\sum }_{i=1}^N{w}_t^i=1,$ for $0\le t\le T$, produced, for example, by Sequential importance resampling for Feynman–Kac path targets. Each $x_t^i$ is the time-$t$ coordinate of its stored particle path. Write $M_{t+1}$ for the model transition kernel and require a product-measurable density $f_{t+1}(x^{\mathrm{\prime }}\mid x)$ relative to a declared sigma-finite measure ${\lambda }_{t+1}$, meaning $M_{t+1}(x,A)={\int }_A{f}_{t+1}(x^{\mathrm{\prime }}\mid x){\lambda }_{t+1}(d{x}^{\mathrm{\prime }})$ for each measurable $A$. For each $t<T$, define the predictive score with zero-weight terms omitted: $q_{t+1}^N(x^{\mathrm{\prime }})={\sum }_{i:w_t^i>0}{w}_t^i{f}_{t+1}(x^{\mathrm{\prime }}\mid x_t^i)\mathrm{.}$ For particle-mode path sampling, define the set of reachable indices recursively by $R_T=\{j:w_T^j>0\}$. Descending from $t=T-1$ to $0$, require $q_{t+1}^N(x_{t+1}^j)\in (0,\mathrm{\infty })$ for every $j\in R_{t+1}$, and put $R_t={\bigcup }_{j\in R_{t+1}}\{i:w_t^i>0,f_{t+1}(x_{t+1}^j\mid x_t^i)>0\}\mathrm{.}$ These are exactly the indices that can be drawn with positive probability at the corresponding backward step. For the all-marginals mode below, require instead that $q_{t+1}^N(x_{t+1}^j)\in (0,\mathrm{\infty })$ whenever the current smoothing weight ${\bar{w}}_{t+1\mathrm{\mid }T}^j$ is positive. Thus no denominator is required for an omitted zero-weight term. At $T=0$ there are no denominator conditions.

In particle mode, repeat independently for $s=1,\dots ,S$:

1. Draw $I_T^s$ from $\{1,\dots ,N\}$ with probabilities $w_T^i$ and set ${\tilde{X}}_T^s=x_T^{I_T^s}$.
2. For $t=T-1,T-2,\dots ,0$, set $b_t^i=0$ without evaluating the density whenever $w_t^i=0$. For $w_t^i>0$, set $b_t^i({\tilde{X}}_{t+1}^s)=\frac{w_t^i{f}_{t+1}({\tilde{X}}_{t+1}^s\mid x_t^i)}{q_{t+1}^N({\tilde{X}}_{t+1}^s)}\mathrm{.}$ Draw $I_t^s$ from this probability vector, and set ${\tilde{X}}_t^s=x_t^{I_t^s}$.
3. Return the tuple ${\tilde{X}}_{0:T}^s=(x_0^{I_0^s},\dots ,x_T^{I_T^s})\mathrm{.}$ This is a draw from the particle backward approximation to the smoothing path law. The coordinates are selected by separate backward indices and need not be the stored forward ancestor history of any one particle. The particle path-sampling output is the list ${\tilde{X}}_{0:T}^1,\dots ,{\tilde{X}}_{0:T}^S$.

If an exact filtering kernel ${\eta }_T$ and supplied backward conditional kernels $B_t$ from Bayes factorization of the smoothing backward kernel are available for general transition kernels, there is a separate exact-kernel mode: draw $S$ conditionally independent paths, each by drawing $X_T\sim {\eta }_T$ and then drawing $X_t\sim B_t(X_{t+1},\cdot )$ successively backward. This mode uses the actual kernels; it does not evaluate a transition density or a kernel on particle singletons. It returns exact smoothing paths under the supplied conditional versions wherever their factorization holds.

An optional all-marginals mode computes particle smoothing weights instead of drawing paths. Initialize ${\bar{w}}_{T\mathrm{\mid }T}^j=w_T^j$. For $t=T-1,\dots ,0$, let $J_{t+1}=\{j:{\bar{w}}_{t+1\mathrm{\mid }T}^j>0\}$. For each $j\in J_{t+1}$ and $i$ with $w_t^i>0$, set $b_t^{i,j}=\frac{w_t^i{f}_{t+1}(x_{t+1}^j\mid x_t^i)}{q_{t+1}^N(x_{t+1}^j)};$ set $b_t^{i,j}=0$ without evaluating the density if $j\mathrm{\notin }{J}_{t+1}$ or $w_t^i=0$. Update ${\bar{w}}_{t\mathrm{\mid }T}^i={\sum }_{j\in J_{t+1}}{\bar{w}}_{t+1\mathrm{\mid }T}^j{b}_t^{i,j}\mathrm{.}$ For every active $j$, $(b_t^{i,j}{)}_{i=1}^N$ is a probability vector, so the raw updated values are nonnegative and already sum to one; explicit normalization leaves them unchanged. Return ${\sum }_i{\bar{w}}_{t\mathrm{\mid }T}^i{\delta }_{x_t^i}$ as the approximate smoothed marginal at time $t$. The algorithm makes no finite-particle accuracy, consistency, or long-time stability claim.

When a required density denominator is zero or infinite, the corresponding mode is inadmissible; the algorithm does not replace it with uniform weights. Zero filtering or smoothing weights are omitted before density evaluation, so no term evaluates $0\cdot \mathrm{\infty }$ or $0\mathrm{/}0$. For a general transition kernel, use an exact supplied backward conditional kernel as in the second mode, or provide a valid dominating-density interface. A fixed-lag target remains a truncated-observation target; see Fixed-lag particle smoother.

Use the conditionally linear-Gaussian model of Conditionally linear-Gaussian state-space model and a fixed observation path $y_{1:T}$. For each $0\le t\le T$, let ${\bar{P}}_t$ be the nonlinear path law generated by ${\mu }_0$ and the path-extension kernels from Nonlinear path extension is a probability kernel, and put $c_t(y_{1:t})={\int }_{{\mathsf{Z}}_{0:t}}{\prod }_{s=1}^t{\mathrm{\ell }}_s(z_{0:s};y_{1:s}){\bar{P}}_t(d{z}_{0:t}),c_0=1.$ Here ${\mathrm{\ell }}_s$ is the conditional observation density supplied by The Kalman filter is exact conditional on a nonlinear path. For the claim that the procedure targets the nonlinear filtering law at every prefix, assume $0<c_t(y_{1:t})<\mathrm{\infty }$ for every $t$; this is the finite-positive normalizer condition for the normalized Feynman–Kac target. The Kalman likelihood factorization identifies $c_t$ with the observation evidence density and the normalized path target with the exact conditional law of $Z_{0:t}$ given $Y_{1:t}=y_{1:t}$. The particle procedure itself uses finite positive per-particle likelihoods, so each of its empirical weight normalizers is finite positive. The particle state at time $t$ is the full nonlinear history $z_{0:t}$; finite products of the standard-Borel state spaces are standard Borel. Its transition appends a draw $z_t\sim M_t(z_{t-1},\cdot )$; the resulting path-extension probability kernel and standard-Borel path space are supplied by Nonlinear path extension is a probability kernel. Set the initial Feynman–Kac potential to $G_0\equiv 1$ and the time-$t$ potential to the conditional observation density $G_t(z_{0:t})={\mathrm{\ell }}_t(z_{0:t};y_{1:t})$ from The Kalman filter is exact conditional on a nonlinear path. Use the same path-extension kernel as target and proposal, so the initial and transition Radon–Nikodym weights are identically one. Run Sequential importance resampling for Feynman–Kac path targets with multinomial resampling to approximate the filtering law of the nonlinear path. Each particle stores alongside its path the conditional Gaussian moments of $U_t$.

Initialize $N\ge 1$ particles by drawing $z_0^i\sim {\mu }_0$ independently, setting $w_0^i=1\mathrm{/}N$, $m_{0\mathrm{\mid }0}^i=m_0(z_0^i)$, and $P_{0\mathrm{\mid }0}^i=P_0(z_0^i)$. For each $t=1,\dots ,T$:

1. Draw ancestor indices $J_t^1,\dots ,J_t^N$ independently with probabilities $(w_{t-1}^1,\dots ,w_{t-1}^N)$ and append independent transitions $z_t^i\sim M_t(z_{t-1}^{J_t^i},\cdot )$.
2. For each particle, abbreviate its appended path by $z_{0:t}^i$ and compute $m_{t\mathrm{\mid }t-1}^i=A_t(z_{0:t}^i)m_{t-1\mathrm{\mid }t-1}^{J_t^i},P_{t\mathrm{\mid }t-1}^i=A_t(z_{0:t}^i)P_{t-1\mathrm{\mid }t-1}^{J_t^i}{A}_t(z_{0:t}^i{)}^T+Q_t(z_{0:t}^i)\mathrm{.}$ Form $v_t^i=y_t-C_t(z_{0:t}^i)m_{t\mathrm{\mid }t-1}^i$ and $S_t^i=C_t(z_{0:t}^i)P_{t\mathrm{\mid }t-1}^i{C}_t(z_{0:t}^i{)}^T+R_t(z_{0:t}^i)$.
3. Set the incremental weight to the finite positive Gaussian density $a_t^i=(2\pi {)}^{-p_t\mathrm{/}2}\det (S_t^i{)}^{-1\mathrm{/}2}\exp \text{\hspace{0.17em}⁣}(-\frac{1}{2}(v_t^i{)}^T(S_t^i{)}^{-1}{v}_t^i),$ and normalize $w_t^i=a_t^i\mathrm{/}{\sum }_j{a}_t^j$.
4. Update the conditional Gaussian moments by $K_t^i=P_{t\mathrm{\mid }t-1}^i{C}_t(z_{0:t}^i{)}^T(S_t^i{)}^{-1},m_{t\mathrm{\mid }t}^i=m_{t\mathrm{\mid }t-1}^i+K_t^i{v}_t^i,P_{t\mathrm{\mid }t}^i=P_{t\mathrm{\mid }t-1}^i-K_t^i{S}_t^i(K_t^i{)}^T\mathrm{.}$

The procedure returns the weighted nonlinear particle paths and the Gaussian mixture ${\widehat{\pi }}_t^N(d{u}_t,d{z}_{0:t})={\sum }_{i=1}^N{w}_t^{i}N(d{u}_t;m_{t\mathrm{\mid }t}^i,P_{t\mathrm{\mid }t}^i){\delta }_{z_{0:t}^i}(d{z}_{0:t})\mathrm{.}$ Its conditional mean is ${\sum }_i{w}_t^i{m}_{t\mathrm{\mid }t}^i$ and its conditional covariance is ${\sum }_i{w}_t^i[P_{t\mathrm{\mid }t}^i+(m_{t\mathrm{\mid }t}^i-{\bar{m}}_t)(m_{t\mathrm{\mid }t}^i-{\bar{m}}_t{)}^T]$, where ${\bar{m}}_t={\sum }_i{w}_t^i{m}_{t\mathrm{\mid }t}^i$. These are moments of the finite mixture approximation; for finite $N$ the algorithm remains an approximation to the full nonlinear filter. It makes no general variance-reduction, convergence-rate, or long-time accuracy claim.

For every particle, $P_{t\mathrm{\mid }t-1}^i$ is positive semidefinite and $R_t(z_{0:t}^i)$ is positive definite, so $S_t^i$ is positive definite and the Kalman update and Gaussian density are defined. Conditional exactness of each Gaussian component is supplied by The Kalman filter is exact conditional on a nonlinear path. More precisely, each stored component is the conditional law of $U_t$ given its prefix $Z_{0:t}=z_{0:t}^i$ and $Y_{1:t}=y_{1:t}$. This follows by induction: at time zero it is the specified Gaussian law; at each later step the appended nonlinear transition is $M_t(z_{t-1},\cdot )$ and does not depend on $U_{t-1}$, so conditioning on the appended state does not change the parent Gaussian component, after which the Kalman prediction and observation update give the stated component. Equivalently, the Kalman lemma's conditional law given the full nonlinear path depends through time $t$ only on $z_{0:t}$; future nonlinear transitions are independent of $U_{0:t}$ and $Y_{1:t}$ given the prefix, depend only on the current nonlinear state, and integrate to one. Integrating over $z_{t+1:T}$ therefore leaves that same Gaussian law given the prefix. The mixture over nonlinear paths is still represented by finitely many particles.

Assume AC. Let $E_0,\dots ,E_T$ be compact metric spaces, let ${\mu }_0$ be a probability on $E_0$, and let $M_t$ be a Feller probability kernel from $E_{t-1}$ to $E_t$. Here Feller means that $x\mapsto M_{t}h(x):=\int h(x^{\mathrm{\prime }})M_t(x,d{x}^{\mathrm{\prime }})$ is continuous for every bounded continuous real $h$ on $E_t$. Let each potential $G_t:E_t\to \mathbb{R}$ be continuous and satisfy fixed bounds $0<c\le G_t(x)\le C<\mathrm{\infty }$. Let $P_t^M$ be the Markov path law and $Z_t=\int {\prod }_{s=0}^t{G}_s(x_s)P_t^M(d{x}_{0:t})$ the Feynman–Kac normalizer from Feynman–Kac path targets and normalizers. Since $P_t^M$ is a probability, $c^{t+1}\le Z_t\le C^{t+1}$, so the normalized path target exists. For the initial law and transitions use the bootstrap proposals ${\nu }_0={\mu }_0$, $R_t=M_t$, initial potential $G_0$, and multinomial resampling in Sequential importance resampling for Feynman–Kac path targets. Write ${\eta }_t$ for the last-state marginal of ${\gamma }_t\mathrm{/}{Z}_t$ and ${\eta }_t^N={\sum }_i{w}_t^i{\delta }_{X_t^i}$ for the particle filter's current weighted empirical measure. For every fixed $t\le T$, ${\eta }_t^N\Rightarrow {\eta }_t\text{in probability as }N\to \mathrm{\infty },$ where convergence in probability means that for every bounded continuous $h:E_t\to \mathbb{R}$, $\int hd{\eta }_t^N\to \int hd{\eta }_t$ in probability. This is a fixed-horizon, positive-bounded-potential result; it asserts no time-uniform bound and no particle central limit theorem.

For a finite horizon $T\ge 0$, fix an integer lag $L\ge 0$, a path count $S\ge 1$, and the normalized filtering particle clouds and transition inputs required by Particle backward simulator. For each time $t\in \{0,\dots ,T\}$, put $s_t=\min (t+L,T)$. Independently for each $t$, run the particle backward simulator using only the filtering clouds at times $0,\dots ,s_t$ and request $S$ paths. Retain their time-$t$ coordinates ${\tilde{X}}_t^{t,1},\dots ,{\tilde{X}}_t^{t,S}$ and return the empirical measure ${\widehat{\eta }}_{t\mathrm{\mid }{s}_t}^S=\frac{1}{S}{\sum }_{r=1}^S{\delta }_{{\tilde{X}}_t^{t,r}}\mathrm{.}$ In particle mode this empirical law approximates $\mathcal{L}(X_t\mid Y_{1:s_t}),$ not the full smoothing law $\mathcal{L}(X_t\mid Y_{1:T})$ unless $s_t=T$ or the two conditional laws happen to agree. The same procedure can use supplied exact backward kernels when the model has no transition density; for each $s_t$ it uses the supplied filtering kernel at $y_{1:s_t}$ and the backward kernels for the corresponding prefix histories. On histories where these kernels factor the truncated smoother, it samples that exact conditional law.

The procedure returns one truncated smoothing marginal per $t$. It does not assert a bound on the lag bias, a forgetting rate, or convergence to the full-data smoother for fixed $L$. Those conclusions require separate conditions on the model.

Assume the finite particle-mode inputs and denominator conditions of Particle backward simulator. The backward index probabilities at each step are nonnegative and sum to one. In the all-marginals recursion, the raw updated smoothing weights also sum to one, so the optional explicit normalization in the algorithm leaves them unchanged. Count one transition density evaluation and a bounded number of real arithmetic operations as unit cost, and sample from a categorical vector by a linear scan of its $N$ entries. Then drawing $S$ backward paths costs $O(SN(T+1))$ operations, including terminal draws, and computing all smoothed marginal weights costs $O(N+N^{2}T)$, including initialization and output. For $T\ge 1$ these are respectively $O(SNT)$ and $O(N^{2}T)$; for fixed $S$, path sampling costs $O(N(T+1))$.

Assume AC and a finite-horizon state-space model with compact metric state spaces $E_0,\dots ,E_T$, dominated observation kernels, and an observation history $y_{1:T}$ in the full-measure finite-positive set where Bayes factorization of the smoothing backward kernel applies. Let $g_t(x,y)$ be the specified product-measurable observation density relative to its sigma-finite observation measure, as in Exact state-space filtering recursion under dominated observations, and set $G_t(x)=g_t(x,y_t)$ for $1\le t\le T$ and $G_0\equiv 1$. Suppose each $G_t$ is continuous and there are constants $0<c\le 1\le C<\mathrm{\infty }$ such that $c\le G_t(x)\le C$ for every state and time. For each $0\le t<T$, let $M_{t+1}$ be the state transition from time $t$ to time $t+1$ and suppose it has a jointly continuous density $f_{t+1}(x^{\mathrm{\prime }}\mid x)$ relative to a Borel probability measure ${\lambda }_{t+1}$, meaning $M_{t+1}(x,A)={\int }_A{f}_{t+1}(x^{\mathrm{\prime }}\mid x){\lambda }_{t+1}(d{x}^{\mathrm{\prime }})$ for measurable $A$, with uniform bounds $0<a\le f_{t+1}(x^{\mathrm{\prime }}\mid x)\le b<\mathrm{\infty }$ for all $x,x^{\mathrm{\prime }}$. Write ${\eta }_t$ for the exact filtering-kernel value at $y_{1:t}$ and ${\psi }_T$ for the exact smoothing-kernel value at $y_{1:T}$. Use the model initial law as the initial proposal, these same $M_t$ as transition proposals, and these $G_t$ as potentials in the multinomial bootstrap particle filter. With $N\ge 1$ particles, independently draw $S_N\ge 1$ backward paths conditional on the resulting clouds, where $S_N\to \mathrm{\infty }$ as $N\to \mathrm{\infty }$. Let ${\widehat{\psi }}_T^N$ be the conditional law of one backward-simulated path given the clouds. For every continuous $\mathrm{\Phi }:E_0\times \cdots \times E_T\to \mathbb{R}$, ${\widehat{\psi }}_T^N(\mathrm{\Phi })\to {\psi }_T(\mathrm{\Phi })\text{in probability},\frac{1}{S_N}{\sum }_{s=1}^{S_N}\mathrm{\Phi }({\tilde{X}}_{0:T}^s)\to {\psi }_T(\mathrm{\Phi })\text{in probability}\mathrm{.}$ For a fixed number of simulated paths, their conditional path law is consistent but the empirical path average retains its Monte Carlo error. No time-uniform-in-$T$ convergence claim is made.