You have int rand1() which outputs 0 or 1 in equal probability.
You need to implement int randx(int x) which outputs 0,1,2,3,4,...,x, each value should in equal probability.
It is easy to set bits based on rand1 output for functions like rand3 or rand7. For rand3, just call rand1 twice and set bit 0 and 1 based on the output and 00,01,10,11 will have equal probability to get select (25%). But how about functions like rand4?
You have the right idea. You will need to generate a binary number bigger than the one you need by concatenating random bits. But then unless x+1 is a power of 2, you'll need to use rejection sampling to ensure each value is returned by randx with equal probability. To make the probabilily of rejection small, say less than 2^-p, the power of 2 you generate should have p+1 bits more than necessary. The method of rejection will look like:
int rand(int x) {
choose b such that m = 2^b >= x+1
let r_max = m - m mod (x+1)
do {
r = base-2 number of r pseudo-random bits
} while (r > r_max)
return r mod (x+1)
}
Note that when x+1 is a power of 2, the loop always executes exactly once. When it's not, the probability of each iteration depends on b. Adding 1 to b halves the probability of another iteration.
In this problem you will need to keep a few dummy outputs (rejection sampling, as @Gene pointed out) on which you repeat the experiment performed.
I have provided two implementations here. The first one is sub-optimal, but easier to understand. The second one is more optimal but a little more difficult. Finally, I've tried to outline a proof and linked to a Math StackExchange answer.
First Approach -
Step 1 - Run rand1() x + 1 times.
Step 2 - Check if the output is one-hot. By one-hot I mean, only 1 of the x + 1 runs results in 1 and all the others 0. If not so, repeat Step 1. Else go to Step 3.
Step 3 - Print index of 1 as your output.
The python code will look like this -
def randx(x):
choice = -1
while choice == -1:
for i in range(0, x+1):
c = rand1()
if c == 1 and choice == -1:
choice = i
elif c == 1 and choice != -1:
choice = -1
break
Second Approach -
Of course, the first method is sub-optimal. You can make this far better, but it will need a lot more code. Let's say we want to do a prediction between x+1 values (0 to x). You will need to carry out the experiment atleast k = ceil(log(x+1)) times. Now, each of the outcomes will have an equal probability of 1 / 2^k.
Out of these 2^k possibilities, assign some to numbers (due to our choice of k, you will see that you can assign a number to atleast half the possibilities). Call the other possibilities dummy output.
When you get a dummy output, you simply repeat the experiment. If you don't, you output the number corresponding to that output.
As an example, if x = 4, x + 1 = 5. Hence we need k = 3. Assign 0, 1, 2, 3, 4 their binary representations (000 to 101) and leave the remaining 3 as dummies. The pseudo code will look like this,
function randx(x):
choice = -1
runs = ceil(log(x+1))
while choice == -1:
output = 0
for i in range(0, runs):
output += pow(2, i)*rand1()
if output <= x:
choice = output
Why does this work?
We are giving all numbers equal probable events. If none of those events happen, we are simply repeating this experiment. If you look at the total probability of getting a number i,
Let p = 1 / 2^k
Let q = 1 - (x+1)*p
Total probability of getting i = p + q*p + q*q*p + q*q*q*p ...
= p/(1-q)
= 1/(x+1)
Hence this sums up to 1 / (x+1).
For a more complete explanation with MathJax, refer to https://math.stackexchange.com/questions/2356/is-it-possible-to-split-coin-flipping-3-ways
