# Why does the low variance resampling algorithm for particle filters work?

I am studying and coding particle filters and I am using the Low variance sampling algorithm suggested in the Probabilistic Robotics book. I understand the procedure for the algorithm. A random number r is picked from the interval (0, 1 / M) and a variable U, calculated based on r is used to navigate the sample space systematically. A variable c(cumulative sum) is initialized with the first weight, and incremented by adding weights until it is higher than U. Once the cumulative sum is higher than U, it picks the sample corresponding to the weight last added.

The problem that I have is that I don't see how this picks up a good sample set for the next iteration. This seems very random or at least favorable to lower valued weights. If the initial value of r is very low, U is also low initially and it may pick a sample whose weight is low, unless weight vector is sorted from high to low (Is it sorted?). However, this video suggests that particles with higher weight have a better chance of getting picked. The algorithm doesn't convey this idea to me. Please help if you have an explanation.

The algorithm can be understood by taking an example (using variables used in Probabilistic Robotics and algorithm in table 4.4 in page 110 in the same book).

Algorithm: (Couldn't get math mode to work inside code mode. Hence the picture.)

Consider $$M = 100$$

$$M^{-1} = 0.01$$

Let $$r = 0.005$$

So, $$U = 0.005, 0.015,......., 0.995$$ as loop progresses.

If the weight is assumed to be initialized with a value of 1/no. of particles, the first iteration of the algorithm will pick a particle, due to low value of U. Here no. of particles is 100. But in later iterations, the value of U will be larger and that would mean that by the time the value of c catches up with U, a lot of particles corresponding to lower weights will be skipped due to the inner while loop. At the same time, if c had a large increment due to large weight, it will take a while for U to catch up with c. This means the while loop will be skipped and high weight particle will be added to the output set multiple times. This is how high weight particles are picked by the algorithm. Also, the maximum value of U is 0.995, in this case. Even if r is higher, this maximum value will not exceed 1. This means, at some point, c will catch up with U resulting in selection of particles, assuming weights are normalized.

The algorithm does seek to favour picking samples with a greater weight.

If you think about the samples arranged in a line (actually a circle), and the length of each sample is proportional to it's weight. Then if you move along the line in small random increments and pick samples, because the higher weight samples are longer you will more often pick a higher weight sample.