Re:How to pick a random number from 1-10
by frankmcsherry on Saturday June 29, 2019 @09:53PM
(#20315913)
Rejection sampling isn't the best way to go.
With b bits you are subdividing the (0,1) interval into 2^b regions, and only need more bits if one of the 9 multiples of 0.1 land in the interval you've picked. As b increases this probability drops exponentially.
It's a fair point that the number of "numbers" depends on how low the entropy of the source is, but in the link the probability of collision wasn't massive.
But the original post described rejection sampling (once you got your bits from the larger/smaller trick).
Re:How to pick a random number from 1-10
by frankmcsherry on Saturday June 29, 2019 @10:40PM
(#20316029)
Absolutely! I read the von Neumann extractor and presumed too much. For fun, you can reduce the numbers asked by getting a batch of k people, and if all numbers are dissimilar you get a draw from k!
The OP is silly though; if you know the distribution there are way better techniques. They don't seem to worry about how they measure it.
Thus, I recant "around 20, 40, 60 or more" and replace it by "around 9, 18, 27 or more" numbers. Probability that you have to reject any resulting hex digit is obviously 3/8.