Suppose you have a fair coin, that, when thrown, lands heads half the time and tails the other half. Design a procedure that makes a uniformly distributed random integer in the inclusive range [1, n].

If the size of the range is a power of two, the solution is obvious: build-up the number one bit a time. Otherwise, the problem gets more interesting.

The gut reaction to generate a number in a larger range that is a power of two, and then scale down somehow, doesn’t work: since we’re talking about discrete integers, any scaling down or modding will result in a non-uniform distribution:

The solution to this is a bit disappointing: generate a number in a larger range that is a power of two; if the number is also in the desired range, accept it; otherwise, start over.

---

I originally wrote this post a year ago. In the meantime, I found a great post on the topic: Darts, Dice, and Coins. Its author goes through simulating fair and loaded dice, biased coins, and ends with a the best presentation I’ve ever seen of The Alias Method, a very efficient way of simulating a loaded die.