32.2 Weighted uniform sampling
Most computer programming languages provide a primitive which allows us to sample uniformly a random integer in the range for any given natural number .
Let be a set of natural numbers and . Then there exists an algorithm to sample an according to its weighting in the set. That is, if is the random variable for which of the objects, then
The algorithm is this
while increment by 1
To prove that this algorithm satisfies the condition, we can check how many different values of are associated with each .
First we can examine an easier case, before tackling the more general one.
For we know that if that the value output will be (as so we will return ) and there are integer values in the range .
In the more general case that for we will output provided that and , as these are the values of for which is the greatest value for which , so we will increment a total of times, and thus we will return . As we are after, there are values in this interval.