Resampling schemes and degeneracy

When the weights collapse

Weights multiply from day to day. A particle that explains a few observations badly gets a tiny weight, and tiny weights never recover. After enough days one particle carries nearly all the weight and the rest are wasted work. This is weight degeneracy, and the effective sample size $1/\sum\tilde w^{2}$ measures it. On SPY with $1000$ particles and no resampling, the effective sample size is $960$ after the first day, $368$ after ten, $52$ after fifty, and about $1.3$ after $250$ days. A filter that has collapsed to one particle is a single guess, not a cloud.

Resampling cures degeneracy: draw a new cloud of $N$ particles in which a particle with weight $\tilde w_i$ is expected to appear $N\tilde w_i$ times, then give every copy the same weight $1/N$. There are several ways to do the draw. Multinomial resampling draws $N$ independent uniform numbers. Systematic resampling draws one uniform $u$ and uses $N$ evenly spaced pointers $(u+i)/N$ on the cumulative weights. Stratified resampling draws one uniform in each of the $N$ equal slices. Residual resampling first gives every particle its whole copies, $\lfloor N\tilde w_i\rfloor$, and draws only the leftover. Systematic is the cheapest and the most used.

• Resample when the ESS is low: a common rule is $\mathrm{ESS}<N/2$. Resampling every day wastes diversity.
• Systematic uses one random number: pointers $(u+i)/N$ on the cumulative weights give a cheap, low-noise draw.
• The price is impoverishment: many copies of a few particles leave the cloud with little variety, which the next propagation step must rebuild.

Lab · what's graded

• Expected copies15 pts
• A systematic pointer10 pts
• Collapsed weights15 pts
• Distinct survivors10 pts
• Should we resample today10 pts
• Systematic resampling10 pts
• Match the schemes15 pts
• Why resample at all15 pts