After a particle filter has weighted its particles, it resamples: it draws a new set of the same size, in which heavy particles appear several times and light ones may vanish; afterwards all weights are equal again. A popular way to draw, low-variance (or systematic) resampling, needs only one random number.
Lay the n weights end to end along a line from 0 to W = \sum_i w_i: particle 0 covers [0, C_0), particle 1 covers [C_0, C_1), and so on, where C_i = w_0 + \dots + w_i is the running sum (a particle with weight 0 covers nothing). Now place a comb of n equally spaced teeth along the line, the first shifted by the offset u:
Tooth p_k picks the particle whose stretch contains it: the first index i with C_i > p_k.
The offset u, with 0 \le u < 1, would normally be drawn at random; here it is given. Write low_variance_resample(weights, u) that returns the list of the n picked particle indices, in the order of the teeth k = 0, 1, ..., n-1.
Examples
Input: weights = [0.1, 0.4, 0.2, 0.3], u = 0.5
Output: [1, 1, 2, 3]
Explanation: the teeth are at 0.125, 0.375, 0.625 and 0.875; the running sums are 0.1, 0.5, 0.7, 1.0.
Particle 0 (weight 0.1) falls between two teeth and is not picked; particle 1 is picked twice.
Input: weights = [1, 0, 1, 2], u = 0.0
Output: [0, 2, 3, 3]
Explanation: W = 4, the teeth are at 0, 1, 2 and 3; the running sums are 1, 1, 2, 4.
The tooth at 1 is not inside particle 0's stretch [0, 1), and particle 1's stretch is empty,
so it picks particle 2.
Constraints
- every weight is at least 0 and their sum is positive; the weights need not add up to 1
0 <= u <= 0.999
Goals
- Resample a weighted particle set with one offset and equally spaced pointers
- Find which particle's stretch each pointer falls in with a running cumulative sum
- See why heavy particles are copied and light ones disappear