It seems crazy to me that there's no way to produce unbiased numbers in an arbitrary range without rejection sampling and a loop. Is there a proof of this?
Efficiently Generating a Number in a Range
21–30 of 41 posts
Re: Efficiently Generating a Number in a Range
#22In TXR Lisp, the algorithm I put in place basically finds the tightest power-of-two bounding box for the modulus, clisp the pseudo-andom number to that power-of-two range, and then rejects values outside of the modulus.
Example: suppose we wanted values in the range 0 to 11. The tightest power of two is 16, so we generate 4 bit pseudo-random numbers in the 0 to 15 range. If we get a value in the 12 to 15 range, we throw it away and choose another one.
The clipping to the power-of-two bounding box ensures that we reject at most 50% of the raw values.
I don't bother optimizing for small cases. That is, under this 4 bit example, each generated value that is trimmed to 4 bits will be the full output of the PRNG, a 32 bit value. The approach pays off for bignums; the PRNG is called enough times to cover the bits, clipped to the power-of-two box, then subject to the rejection test.
Re: Efficiently Generating a Number in a Range
#23It seems crazy to me that there's no way to produce unbiased numbers in an arbitrary range without rejection sampling and a loop. Is there a proof of this?
I'd expect it's possible by changing the generator at the lowest level, but it makes sense to me that you need a loop if you don't control the underlying generator.
Imagine you want to turn a random number in 1..4 into a random number in 1..3. The original is your only source of randomness, so the rest should be deterministic. Then each outcome in 1..4 has to map to exactly one number in 1..3, but there's no mapping that accepts all of 1..4 while still giving each of 1..3 an equal probability.
Re: Efficiently Generating a Number in a Range
#24It seems crazy to me that there's no way to produce unbiased numbers in an arbitrary range without rejection sampling and a loop. Is there a proof of this?
I'd expect it's possible by changing the generator at the lowest level, but it makes sense to me that you need a loop if you don't control the underlying generator. Imagine you want to turn a random number in 1..4 into a random number in 1..3. The original is your only source of randomness, so the rest should be deterministic. Then each outcome in 1..4 has to map to exactly one number in 1..3, but there's no mapping…
What if we allow the mapping function to be stateful?
Re: Efficiently Generating a Number in a Range
#25It seems crazy to me that there's no way to produce unbiased numbers in an arbitrary range without rejection sampling and a loop. Is there a proof of this?
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.
Re: Efficiently Generating a Number in a Range
#26Earlier quoted context omitted.
I'd expect it's possible by changing the generator at the lowest level, but it makes sense to me that you need a loop if you don't control the underlying generator. Imagine you want to turn a random number in 1..4 into a random number in 1..3. The original is your only source of randomness, so the rest should be deterministic. Then each outcome in 1..4 has to map to exactly one number in 1..3, but there's no mapping…
What if we allow the mapping function to be stateful?
I guess you could save up a few bits over repeated calls, but it can't help you always execute the first call with a single round of generation.
Re: Efficiently Generating a Number in a Range
#27It seems crazy to me that there's no way to produce unbiased numbers in an arbitrary range without rejection sampling and a loop. Is there a proof of this?
Trivial proof. Pigeon hole principle.
Double-precision Floats have more values between 0.0 and 1.0, than between 1.0 and 2.0. In fact, roughly half of ALL double-precision floats exist between -1.0 and 1.0, a very small minority of them exist between 1.0 and 2.0.
To generate unbiased random numbers between 0.0 and 2.0, it therefore requires you to either reject a significant amount of numbers in the 0.0 to 1.0 range, or perform some kind of many-to-few mapping in the 1.0 to 2.0 range.
----------
With regards to arbitrary INTEGER ranges, the proof is even easier. A random bitstream has 2^number-of-bits possible random values. Which does NOT divide evenly into an arbitrary integer range.
For example, 5-random bits will represent 32-different values. There's no way to map 32-values and divide them evenly into 0-9 (10 numbers).
Re: Efficiently Generating a Number in a Range
#28Earlier quoted context omitted.
What if we allow the mapping function to be stateful?
I guess you could save up a few bits over repeated calls, but it can't help you always execute the first call with a single round of generation.
Could it cap the maximum number of generator calls though? Rejection sampling is technically O(infinity) because you could reject an unbounded number of times. This isn't a problem in practice but it sure is theoretically annoying. With a cap on the maximum number of calls, it would be O(1).
Re: Efficiently Generating a Number in a Range
#29Earlier quoted context omitted.
xoshiro's response: http://pcg.di.unimi.it/pcg.php
Interesting read, thanks! The deflection about xoshiro is not particularly convincing, though. It's much more likely that you'll want to multiply your random stream by a multiple of 57 than you'll want to xor it with a 43-bit-shifted version of itself. He also doesn't appear to counter the complaint about the generator getting stuck around 0: http://www.pcg-random.org/posts/xoshiro-repeat-flaws.html The other parts o…
His "attack" is literally a brute force of 32 bits of state. It would not scale to PCG with 128 bits of internal state.
Re: Efficiently Generating a Number in a Range
#30This is well-timed. I don't know much about different random number generators but I do know that we recently had an problem where RNG was a serious performance bottleneck.
Would you mind talking a little bit more about the scenario and bottleneck? If you're concerned about anonymity you can just email me directly. I'm working on a research project to examine real world scenarios when the fastest cryptographic PRNGs are legitimately insufficient; your case might be useful.