Normalization and operation counts for particle backward smoothing

For any child value $x^{\mathrm{\prime }}$ at which a backward weight vector is required, the mode's admissibility condition gives $0<q_{t+1}^N(x^{\mathrm{\prime }})<\mathrm{\infty }$. For each index with $w_t^i=0$ the algorithm sets its backward probability to zero without evaluating its density; for each positive-weight index the score is finite and nonnegative. Summing over $i$ therefore gives ${\sum }_{i:w_t^i>0}{w}_t^i{f}_{t+1}(x^{\mathrm{\prime }}\mid x_t^i)\mathrm{/}{q}_{t+1}^N(x^{\mathrm{\prime }})=1$. Thus each required backward vector is a probability vector.

Suppose ${\sum }_j{\bar{w}}_{t+1\mathrm{\mid }T}^j=1$. For every $j$ with ${\bar{w}}_{t+1\mathrm{\mid }T}^j>0$, admissibility makes its score sum finite positive, and the associated vector $(b_t^{i,j}{)}_i$ sums to one by step 1.1. The raw update is ${\bar{w}}_{t\mathrm{\mid }T}^i={\sum }_{j:{\bar{w}}_{t+1\mathrm{\mid }T}^j>0}{\bar{w}}_{t+1\mathrm{\mid }T}^j{b}_t^{i,j}$. Summing over $i$ gives ${\sum }_{j:{\bar{w}}_{t+1\mathrm{\mid }T}^j>0}{\bar{w}}_{t+1\mathrm{\mid }T}^j=1$. Since ${\bar{w}}_{T\mathrm{\mid }T}=w_T$ sums to one, backward induction proves every update is already normalized; zero smoothing-weight terms are never evaluated.

At each of the $T$ backward times for one sampled path, the algorithm evaluates $N$ transition scores and scans $N$ probabilities; terminal sampling also scans $N$ entries. Storing the path costs $O(T+1)$, so $S$ paths take $O(SN(T+1))$ operations. In the all-marginals recursion, initialization and output cost $O(N(T+1))$, while each backward time evaluates one transition score and performs bounded arithmetic for each of the $N^2$ past/future particle pairs. The total is $O(N(T+1)+N^{2}T)=O(N+N^{2}T)$ because $N\ge 1$. For fixed $S$ this gives $O(N(T+1))$ path cost, and when $T\ge 1$ the bounds reduce to $O(SNT)$ and $O(N^{2}T)$.