statisticsrandomparticle-filter

Difference between sampling with replacement vs without replacement in particle filter


For the re-sampling process of a simple particle filter, what is the difference between sampling with replacement vs sampling without replacement in terms of statistical biases and practical implications?

I believe the without replacement re-sampling method I have in mind is not the same as the usual statistic method of sampling without replacement.

In a more concrete context:

After the simulate and observe processes of particle filter, I end up with a list of two-element tuples (s, p), with length N. Whereas, s represent a state which I believe in with a probability of p.

This is with replacement because each random number is independent of another, every old particle has a chance equal to p to be chosen, regardless of how many new particles has already be generated.

This is without replacement because once a bucket's chosen arithmetic sequence is used up, it would never be chosen again.

Practical example:

N = 8

(s, p) list: (A, 0.1), (B, 0.2), (C, 0.3), (D, 0.4)

with replacement, assume random numbers are: 0.2, 0.8, 0.4, 0.7, 0.6, 0.3, 0.9, 0.1, new list particle becomes B, D, C, D, C, B, D, A

without replacement, the arithmetic sequence is: 0.125, 0.25, 0.375, 0.5, 0.625, 0.75, 0.875, 0.99999999, new particle list becomes B, B, C, C, D, D, D, D


Solution

  • I believe the "without resampling" method you have described is wrong, since it guarantees that if the first element has a smaller likelihood than 1 / N, then it will not get chosen and hence those states will get automatically rejected by the algorithm.

    Contrast the first element with the middle element, which can still get chosen even if its likelihood is less than 1 / N. This means the algorithm is biased against the first element toward the middle.

    This is not something you want in a resampling step; everything should have a fair nonzero chance to propagate. Otherwise, you lose the probabilistic correctness guarantees.