Live data from Hacker News

Efficiently Generating a Number in a Range

pcg-random.org

31–40 of 41 posts

Re: Efficiently Generating a Number in a Range

#31

Earlier quoted context omitted.

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).

I don't think so.

If you want a number in 1..3, and the generator provides numbers from 1..4, and you want a cap n, then you could model it as a generator that provides numbers in 1..4^n. There's never a way to split that space into three equal parts.

You always end up with unwanted extra possibilities that you still need to handle somehow.

Re: Efficiently Generating a Number in a Range

#32

In 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 th…

Off the top of my head, for a randomly chosen range of size n, you reject a throw with probability 1/4, right?

Re: Efficiently Generating a Number in a Range

#33
post #32

In 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 th…

Off the top of my head, for a randomly chosen range of size n, you reject a throw with probability 1/4, right?

It's unintuitive, but I believe the probability ends up being 1-ln(2) if you think of n as being uniformly random.

Re: Efficiently Generating a Number in a Range

#34

In 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 th…

This is referred to as “Bitmask” in the article.

Re: Efficiently Generating a Number in a Range

#35

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?

Proposition: There is no way, given some integer r and a sequence of iid random integer samples X1,X2,... uniformly distributed in [0,n) for some n>1, to always construct some finite k and function f : [0,n)^k -> [0,r) such that f(X1,...,Xk) is uniformly distributed over [0,r).

Proof: Suppose such a k and f exist. The distribution of U[0,n)^k is isomorphic to that of U[0,n^k) (just treat it like writing down a k-digit number in base n). And so f must be a function from a set of n^k things to a set of r things. By the pigeonhole principle there must be some integers x,y in [0,r) such that the preimage of x has size at least ceiling(n^k/ r) and the preimage of y has size at most floor(n^k/ r). By the fundamental theorem of arithmetic there exists (for any n,k) some r such that n^k/r is not an integer and so the probabilities of x,y (being proportional to the sizes of their fibres under f) are not equal.

————

The gist of this is that you always might need to loop (repeatedly sample) for some ranges and you might need to repeat arbitrarily many times.

One way is by rejection.

Another nice thing is if you want to generate a Bernoulli r.v. for some probability p a computable number, you lazily compute the bits of p simultaneously to a random sequence of bits (distributed as Bernoulli(1/2)) and compare the two. If your random sequence is definitely less than p then generate 0. If definitely greater then generate 1. If not sure then generate some more bits.

In this way any Bernoulli random variable may be generated from an infinite sequence of iid Bernoulli(1/2), and basically any probability space can be modelled in this way too. In this sense, all of probability can be built out of tosses of a fair coin)

Re: Efficiently Generating a Number in a Range

#36
I wonder if the "Bitmask with Rejection" method would be more efficient if you sometimes made the mask one bit larger than strictly necessary.

As it is, if you want a number in the range 0..8, you take 4 bits of randomness, giving you a number in 0..15. This is great, but 7/16 (43.75%) of the time you have to try again. This not only means more loop iterations, it also means you discard 4 bits of randomness, which may have been costly to generate.

If instead you took 5 bits of randomness, you'd be able to accept anything in 0..26 and would only have to reject 27..31, which means only rejecting 5/32 (15.625%) of the time.

0..8 is a particularly bad case, though. If you need numbers in the range 0..14, then it's not worth trying to use 5 bits.

Re: Efficiently Generating a Number in a Range

#37
post #32

Earlier quoted context omitted.

Off the top of my head, for a randomly chosen range of size n, you reject a throw with probability 1/4, right?

It's unintuitive, but I believe the probability ends up being 1-ln(2) if you think of n as being uniformly random.

n uniformly random from what distribution? Or are you taking a limit somewhere?

Re: Efficiently Generating a Number in a Range

#39
post #32

Earlier quoted context omitted.

Off the top of my head, for a randomly chosen range of size n, you reject a throw with probability 1/4, right?

It's unintuitive, but I believe the probability ends up being 1-ln(2) if you think of n as being uniformly random.

For any power of two m, then for any range size n (with m/2 < n <= m), the probability of rejection is (m-n)/m. If any n is equally probable, then the average rejection is equal to the rejection of the average n (= 3*m/4): (m/4)/m = 1/4. This is true for any power of two m. I stand my case!

Re: Efficiently Generating a Number in a Range

#40

return min + (max - min) / 2 Oh, you want a random number?

Or in O(1): return min Alternatively return max

> Or in O(1)

You mean in one instruction? The parent comment is O(1). The methods in the article are all O(1) too.

Post reply on HN