Must the inner sampler produce exact proposal draws?

No; proper weighting allows an approximate sample with a correctly coupled weight.

Does finite inner computation necessarily change the target?

Not under the valid NSMC construction and its assumptions.

AI Glossary / Probabilistic machine learning / Advanced

Nested sequential Monte Carlo

Definition

Nested sequential Monte Carlo, or NSMC, uses Monte Carlo procedures inside a sequential Monte Carlo algorithm to construct proposals that would otherwise be difficult to sample from. The inner procedure returns samples together with coupled weights or normalizing-constant estimates. Under the required conditions, these approximate proposals support a valid outer sampling algorithm for the intended target distribution.

What it means

A particle filter represents uncertain states with candidates called particles. When each state has many interacting components, proposing a plausible new state can itself become a substantial inference problem. A simple proposal may produce mostly unsuitable candidates, leaving almost all weight on very few particles.
NSMC delegates that difficult proposal problem to another sampling procedure. The extra computation aims to improve proposals. However, putting one sampler inside another is not sufficient by itself. The inner output and its weight must be linked correctly so that the outer algorithm accounts for the approximation instead of silently changing its statistical target.

How it works

The outer sampler advances through a sequence of target distributions. For each relevant ancestor particle, an inner procedure approximates a proposal tailored to the target and ancestor history. It also supplies the accompanying normalizing-constant estimate used in selection or weighting. Inner SMC can serve this role.
The central requirement is proper weighting. For an unnormalized distribution q, an output pair (X, W) must have W nonnegative and satisfy E[W h(X)] = integral of h(x)q(x) for suitable test functions h. This requires a relationship between the sample and weight; an unbiased estimate of the normalizing constant alone is insufficient.
The original formulation establishes convergence with a finite inner population as the outer population increases, under stated regularity conditions. The inner budget still affects accuracy and efficiency. A valid target is not the same as exact finite-population answers, and normalized Monte Carlo estimates need not be unbiased. Backward simulation can help generate inner trajectories without relying only on heavily duplicated ancestral paths.

Three practical examples

A spatial sensor model estimates many linked hidden states at each time step. An inner sampler can build a proposal across spatial components, while the outer sampler processes successive observations. Whether nesting helps depends on the model's dependency structure and available computation.
A simulated environmental monitoring system represents uncertain conditions across a grid. Proposals informed by current measurements may be more useful than blindly propagating the previous state. The model still needs validation when measurements are sparse or systematically biased.
An engineering study explores sequential inference for a network of interacting components. It can compare nested and simpler particle methods at equal computational budgets, recording estimation error, runtime, and sensitivity to inner and outer population sizes.

Think of it this way

Imagine a planning team asking a smaller team to investigate each difficult option. The smaller team returns both a suggested option and information about how its investigation weighted the possibilities. The main team cannot treat every suggestion as equally representative just because it came from a detailed investigation.

Worked example

This example demonstrates the weighting principle underlying NSMC; it is not a full time-series filter. Let unnormalized proposal masses be q(A) = 1 and q(B) = 3, so the normalized proposal assigns probabilities 1/4 and 3/4.
An inner procedure draws two candidates independently from a uniform distribution over A and B. Each candidate receives importance weight q(x)/0.5: weight 2 for A and 6 for B. It returns one candidate chosen proportionally to those weights, together with W, their average.
The four equally likely candidate pairs are AA, AB, BA, and BB. Their W values are 2, 4, 4, and 6. Their conditional probabilities of returning A are respectively 1, 1/4, 1/4, and 0. Therefore, the overall probability of returning A is (1 + 1/4 + 1/4 + 0)/4 = 3/8, which differs from the exact proposal probability 1/4.
Nevertheless, the weighted identity holds: E[W × indicator(X = A)] = [2 × 1 + 4 × 1/4 + 4 × 1/4 + 6 × 0]/4 = 1. Similarly, E[W × indicator(X = B)] = 3. These match the unnormalized masses, and E[W] = 4 matches their sum.
The sample alone is not an exact proposal draw, but the sample-weight pair is properly weighted. Discarding W would lose that property. Across independent repeated inner runs, the ratio of accumulated weighted A indicators to accumulated weights converges to 1/4. A ratio from a small finite number of runs is not guaranteed to equal 1/4 or be unbiased.

Illustrative case study

Fictional company Elm Sensors evaluates inference methods for a simulated spatial monitoring network. Its analysts compare a simple particle filter with an NSMC implementation while controlling the total evaluation budget. They vary inner and outer population sizes separately and repeat experiments using several random seeds.
They first test against a small model whose target probabilities can be calculated accurately, then assess larger simulations. A method that appears stable but fails the small-model comparison is investigated before further use. This invented scenario describes a validation plan; no accuracy improvement, speed advantage, or deployment outcome is claimed.

Common misconceptions and mistakes

Nested SMC is not the same as the distinct method called nested sampling. Nor does every algorithm containing two particle filters implement the proper-weighting construction described here.
A larger inner population cannot compensate automatically for too few outer particles. Treating a noisy estimate as exact, separating it from the sample with which it was generated, or omitting an outer correction can invalidate inference. Finally, effective sample size alone does not capture every issue: duplicated trajectories, biased models, and unreliable observations can remain important.

Business use

Consider NSMC when conventional proposals struggle in a valuable sequential inference problem and the state has structure an inner sampler can exploit. Compare results under equal time or computation budgets, including simpler alternatives. Document both particle budgets and validate against tractable cases so computational sophistication is supported by evidence of useful inference.

Check your understanding

What is the unweighted probability of returning A in the example?

Answer: 3/8.

What is E[W × indicator(X = A)]?

Answer: One.

Why keep the weight with the sample?

Answer: Their joint relationship restores the required weighted identity.

Related terms

Sequential Monte Carlo
Importance sampling
particle filter
proper weighting
normalizing constant
backward simulation
particle degeneracy

Learn next

Study properly weighted importance samples, then compare inner and outer particle budgets in a small sequential model with a known reference solution.

Sources

Naesseth, Lindsten, and Schön, Nested Sequential Monte Carlo Methods (2015), Definition 1 consulted: https://proceedings.mlr.press/v37/naesseth15.pdf . Two-state calculation and Elm Sensors scenario are original illustrations.

Previous: Nested sampling algorithm Next: Nesterov accelerated gradient