Re:Efficiently Generating a Number in a Range
by frankmcsherry on Wednesday July 25, 2018 @02:12PM
(#17611429)
You don't need rejection sampling, but you do need a loop. It is easier to see that a finite number of samples is not sufficient:
If you have only a probability distribution defined by a product space where all distinguishable events have probability p^i, for some finite i, then any subset of the distinguishable events accumulate to a probability r * p^i for some integral r. If your goal is a probability that is not an integral multiple of p^i, you are out of luck with a finite number of samples.
If you have only a probability distribution defined by a product space where all distinguishable events have probability p^i, for some finite i, then any subset of the distinguishable events accumulate to a probability r * p^i for some integral r. If your goal is a probability that is not an integral multiple of p^i, you are out of luck with a finite number of samples.