but maybe the explanation should be fuller so no steps are missed and the understanding is deepened. Treat each of the following thoughts individually. All these thoughts will come together at the end.
1) The "2" actually is in a more complex expression:
3) The smallest
Here's how you can demonstrate to yourself that a uniform distribution has the smallest
4) We can't predict what the distribution of weights will be.
5) We'd like all particles to have a chance of being chosen. If you never visit a particle it cannot be chosen. We want to assure that we can most likely visit each particle at least once.
6) We have chosen to represent weights as slices of a pie.
7) There are N original particles and N original weights. There are N pie slices. We are going to take N random samples.
Let's put these seven thoughts together.
Here's another way to look at it.
The weights divide up the wheel into N parts, each of which has a size proportional to the weight. If you picked N uniformly distributed random points on the edge of the wheel, each point would select a wedge with a probability proportional to the size (or weight), which is exactly what we want. The problem is that, to figure out which wedge is picked, you'd have to know the sum of the weights before it -- this is what we're trying to avoid.
Instead, we could look at the sequence of weights as a repeating signal - a waveform, like a radio signal - and sample it sufficiently often. The highest frequency in the signal corresponds to the largest weight, so the Nyquist sampling theorem says we only have to sample up to twice that to faithfully represent the original signal. Taking uniformly distributed samples at intervals that are always smaller than the critical frequency means we're sampling the signal faithfully, which means our output distribution is proportional to the signal.
answered 08 Mar '12, 23:45
This wheel implementation is just an optimization. It saves on computer time. If you already understand that some particles should be represented more than others based on their weights, you are getting the idea. If you know how to randomly resample particles based on their weights by some other method, then you've learned what you need to know about resampling. For you the wheel implementation may be saving on computer time while making you feel you are wasting your own time.
The wheel implementation is supposed to take less computer time than if you directly try to figure out which particle is represented by a random number from zero to one. The random number basically tells you what percentage of the way through the sum of all the weights you should go to locate the selected particle. Since weights for particles are not the same, for the most basic implementation you have to add particle weights until you get to the random percentage you've been tasked to find. Do this over and over again so particle filters can converge on a winning particle and it will consume computer time. Repeat the process numerous times through a journey and even more computer time gets consumed. Optimizing what you do often does add up to savings.
I don't understand where the constant 2 in 2 * max(w) comes from in the implementation. Could it be 1 or any number bigger than 2?
answered 08 Mar '12, 18:53
Yes, the Roulette Wheel could just be divided into equal segments...let's say 25 segments that are 15 degrees apart....so, you would have equal weighting and probability.
answered 08 Mar '12, 17:40
J Hal Grossman
I would think, if you want to minimize the number of value tested, but still give every particle on the wheel an statically equal chance then you should pick a step value so that your total re-sampling picks would makes one trip around the wheel on average.
Wsum = sum(w) # Sum of Wheel Values
N = #number of re-samples needed
StepAvg = Wsum / N #Average step value needed to make 1 loop around the wheel
Smax = 2 * StepAvg #The average random result would be half the the max value. Use Smax in place of 2*Wmax
If you would like to use a multiple number of loops around wheel then:
Smax = 2 * StepAvg * NumberOfWheelLoopsWanted.
(Two loops around the wheel would probability be a good balance between speed and a fair distribution)
answered 10 Mar '12, 12:17