Hi, I may post some DSA / interview questions I find interesting (even if you would be unlikely to see it in an interview) from some of the books I own / codeforces / leetcode etc.
This question comes from Elements of Programming Interviews in Java written by Lee, Aziz, and Prakash.
4.10 Generate Random Uniform Numbers
How would you implement a random number generator that generates a random integer i between a and b inclusive, given a random number generator that produces a zero or one with equal probability?
ALL values in range [a,b] inclusive should be equally likely.
Hint Given: How would you mimic a three-sided coin with a two-sided coin?
So you are given a 0/1 generator which gives you one of 0 or 1 at a 50% chance with each call to it: int zeroOrOne = generator().
My hint is this: What does b - a represent, and how can you limit the number of calls to the generator?
This is my first post!
Top comments (1)
I'll add a short explanation here:
You can only generate 0/1 so this should clue you in to the fact that the random number generated at the end will be in binary for example if we rolled twice the possibilities are: 01, 10, 00,11 (0,1,2,3). Since we will use 1-indexing we can just add 1 to the result to get a number in range [1,4] inclusive.
In fact you might notice that this formula works perfectly whenever we get a range in the form [1, 2^n - 1].
But we won't get these ranges often so we need a more general solution.
We can note the total number of numbers in the range as (b - a + 1) :: (4 - 1 + 1) = 4
But what if we got a range like [56, 103,421]? 56 is only made of 6 bits (111000) while 103,421 is made of 17 bits (11001001111101101) if we generate a number < 17 bits we miss out on a huge chunk of valid numbers. But if we generate 17 bits every time we add a large chunk of invalid numbers (everything in range [(103,422 - 56), 131,071] is invalid
Remember that ALL values in the range [56, 103,421] must be EQUALLY likely. So here's how we will do this.
103,421 - 56 = 103,365 (11001001110000101) 17 bits so we will generate a 17 bit number however what if we happened to get 17 0's in a row? Well that's still just 0 with some leading 0's.
And note that assuming the generator is perfectly 50/50 to get 0/1 that 17 0's is equally as likely as 17 1's (and any other combination of 17 0/1's).
So we can generate our 17 bit number and just add our lower bound to it right?
0 + 56 would represent the first valid position and 103,365 would represent the last since 103,365 + 56 = 103,421.
But there is a problem. What if we did in fact generate 17 1's (11111111111111111) = 131,071
that is way past our upper bound of 103,421 and adding 56 to it certainly won't put it in range.
So, we do it again, and again, and again until we get a number that when added to 56 is within our range. Here's where probability plays a part in this problem: what is the probability P that when we generate 17 random bits we get a number <= 103,421 - 56?
Well, we can count the # of invalid numbers and the total numbers that can be made with 17 bits is 131,072, so we can use both of these to find the valid range.
131,071 - 103,421 + 1 = 27,651 Invalid numbers
131,072 total possible numbers could be made using 17 bits
27,651 / 131,072 = 0.21 or about 21% chance we roll an invalid number after 17 calls to generator().
Therefore P = 100 - 21 = 79% chance that we will get a valid number on each INDIVIDUAL group of 17 rolls.
While 21% failure seems high remember that these are individual rolls so the probability of failing multiple times in a row begins to get very slim very fast.
As shown in the book if we wanted to determine the probability that we fail 10 times in a row we can just do (27,651/131,072)^10 = 1.29 × 10^-38. (1 in 77.5 undecillion) LOL
So as you can see this method is effective for generating a number within a given range by trying to limit the number of bad rolls we get (limiting total calls to generator).
This was implemented using a do-while loop in Java in the book ill paste it here for you to see.
For simplicity assume generator() is the generation function in the same class that can be called freely by uniformRandom.
int uniformRandom(int lowerBound, int upperBound) {int numberOfOutcomes = upperBound - lowerBound + 1;
int result;
do {
result = 0;
for (int i = 0; (1 << i) < numberOfOutcomes; ++i) { //One iteration per bit (17 in example) i grows from 1, 10, 100, 1000, etc.. until 17 bits (1000000000000000)
result = (result << 1) | generator(); //Append the result of generator to result as the new Least significant bit
}
} while (result >= numberOfOutcomes) //Only break out when we have an n-bit number < numberOfOutcomes
return result + lowerBound;
}