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.
Sampling with replacement would be:
1.Calculate cumulative sum of p for each tuple over the list.
2.Draw random numbers from [0, 1) and see which bucket on the cumulative sum each random number falls into, the element corresponding to that bucket is replicated as a new particle for the next round.
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.
Sampling without replacement would be:
1.Calculate cumulative sum of p for each tuple over the list.
2.Generate a list of floating numbers in an arithmetic sequence, where the i-th element equals i * (1 / N). Use this as the random numbers to plug into the cumulative sum buckets. You can imagine it as slicing the cumulative sum p list with a railing that has equal distance bars. Again, each bucket's corresponding element is replicated to become a new particle.
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
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.