Random Number API - Part 1...

[Anza Power]

You are a programmer, you want to make a function rand(n) that takes an integer n>1 and returns a random integer in the range {1...n} with uniform probability.

At you disposal is a binary random number generator which generates 0's and 1's with equal probability (a fair coin) you can use it as many times as you want.

Can you do this and guarantee your program won't run forever?

[witzar]

Suppose there is such algorithm.

Then there exists an integer k such that computing rand(3) is guaranteed to use binary generator at most k times.
Let m be an integer <=k and let's assume that the algorithm uses binary generator exactly m times.
Effectively binary generator generates a binary sequence of length m.
Since there is no other randomness in the algorithm except the binary generator,
each such sequence determines the final result of rand(3).
Therefore we can assign to each sequence the result of rand(3), which is an element of the set {1, 2, 3}.
Since we have 2^m sequences and 2^m is not divisible by 3, there has to be a result of rand(3)
that is assigned to more sequences than some other result.
But each sequence is equally probable, so some result will occur more frequently that some other result.
This is true for any integer m <=k.
This proves that such an algorithm cannot exist.

[James33]

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

Just generate a random binary number with the same number of digits as n, if the result is higher than n then discard and repeat. It is inevitable that this will end but there is no upper bound on the time taken.

[phil1882]

we do it like the card shuffling algorithm.

stage 1 split the "deck"; the numbers 1 to n; in half roughly

stage 2 generate a binary 0 or 1 for each number.

stage 3 if 0 0 for two cards or 1 1, they stay in same order. else they reverse order.

repeat (log[2] n) +1 times.

select the first card.

exe: 1 2 3 4 5 6 7 8 9 10 11

(1 2 3 4 5 6) (7 8 9 10 11)

0 1 1 1 0 1 0 1 0 0 1

result 1

1 7 2 8 9 3 10 4 11 5 6

(1 7 2 8 9 3) (10 4 11 5 6)

0 1 0 0 0 1 1 0 0 1 0

result 2

10 1 4 7 2 11 5 8 9 6 3

(10 1 4 7 2 11) (5 8 9 6 3)

1 1 1 0 0 0 0 1 0 1 1

result 3

5 10 1 8 9 4 6 7 3 2 11

(5 10 1 8 9 4) (6 7 3 2 11)

1 1 0 0 0 0 1 1 1 1 0

result 4

5 6 10 7 3 1 2 8 9 11 4

done. 5 is our number.

[gavinksong]

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

Just generate a random binary number with the same number of digits as n, if the result is higher than n then discard and repeat. It is inevitable that this will end but there is no upper bound on the time taken.

Also, increment the random binary number by 1 (before comparing with n).

The function returns a random number in the range {1...n}.

Edited August 6, 2013 by gavinksong

[James33]

Suppose there is such algorithm.

Then there exists an integer k such that computing rand(3) is guaranteed to use binary generator at most k times.

Let m be an integer <=k and let's assume that the algorithm uses binary generator exactly m times.

Effectively binary generator generates a binary sequence of length m.

Since there is no other randomness in the algorithm except the binary generator,

each such sequence determines the final result of rand(3).

Therefore we can assign to each sequence the result of rand(3), which is an element of the set {1, 2, 3}.

Since we have 2^m sequences and 2^m is not divisible by 3, there has to be a result of rand(3)

that is assigned to more sequences than some other result.

But each sequence is equally probable, so some result will occur more frequently that some other result.

This is true for any integer m <=k.

This proves that such an algorithm cannot exist.

I don't think that the logic there quite works. Certain results could be ignored (conditional on what has been generated) to make everything divisible by 3.

[witzar]

You can draw a diagram of the algorithm in form of decision tree.

(Whenever you use the binary generator, the algorithm forks.
For those who insist that some results may be disregarded, assume that in such case both subtrees of a given node are identical.)
Each node of the tree has either zero or two child nodes (such tree is called full binary tree).
Each path from the root to the leaf node (node with zero children) has length at most k (depth of each leaf is <=k).
Each leaf has assigned a result of rand(3).
For the sake of simplicity of calculations, we can modify the algorithm (obtaining an equivalent one)
in such way that each path from root to leaf is of length k (thus obtaining perfect tree).
To achieve this we can "pretend" that we perform further calculations in case the result is set after using binary generator less then k times. In terms of a diagram, we attach perfect binary subtree to each leaf of depth <k and assign to each new leaf the same value of rand(3) the original leaf had, so that the decision tree becomes a perfect binary tree of length k.
It has 2^k leaves, and each leaf has assigned a result of rand(3) it yields.
Since each leaf is equally probable and since number of leaves is not divisible by 3, some result occurs more frequent than some other result.

[BobbyGo]

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

Just generate a random binary number with the same number of digits as n, if the result is higher than n then discard and repeat. It is inevitable that this will end but there is no upper bound on the time taken.

This seems like it would work. There is only one issue I can see that that might come up. Although it is unlikely, there is a small chance that all of the random binary numbers could be 0. Either there should be a check to discard it or have 1 added before comparing it to n.

[James33]

By not run forever, do you mean that we must be able to fix a time at which the algorithm will certainly have terminated by? If you mean that it just has to end at some point then

Just generate a random binary number with the same number of digits as n, if the result is higher than n then discard and repeat. It is inevitable that this will end but there is no upper bound on the time taken.

This seems like it would work. There is only one issue I can see that that might come up. Although it is unlikely, there is a small chance that all of the random binary numbers could be 0. Either there should be a check to discard it or have 1 added before comparing it to n.

True, I was just giving an outline of what I would do because I don't think it is what the OP as it has no upper bound on time taken.

[Anza Power]

Suppose there is such algorithm.

Then there exists an integer k such that computing rand(3) is guaranteed to use binary generator at most k times.

Let m be an integer <=k and let's assume that the algorithm uses binary generator exactly m times.

Effectively binary generator generates a binary sequence of length m.

Since there is no other randomness in the algorithm except the binary generator,

each such sequence determines the final result of rand(3).

Therefore we can assign to each sequence the result of rand(3), which is an element of the set {1, 2, 3}.

Since we have 2^m sequences and 2^m is not divisible by 3, there has to be a result of rand(3)

that is assigned to more sequences than some other result.

But each sequence is equally probable, so some result will occur more frequently that some other result.

This is true for any integer m <=k.

This proves that such an algorithm cannot exist.

I don't think that the logic there quite works. Certain results could be ignored (conditional on what has been generated) to make everything divisible by 3.

Actually it is correct.

Let's assume the upper bound is 8 calls, but if your algorithm sees 10001 then it returns 3, then we say that all 2^3 = 8 sequences of the form 10001xxx result in 3.

Congratulations to witzar...

[phil1882]

lets say we run the algorithm 3 times.

001 1

011 3

010 2

110 3

100 2

101 1

and if we get 0 or 7 we discard them. and run the algorithm 3 more times.

now potentially this algorithm could run forever.

you could get 0 indefinitely or 1 indefinitely.

but if the algorithm ever does halt, it will halt with perfect uniformity.

that is we will have generated either a 1 2 or 3 with equal likely hood.

[Anza Power]

lets say we run the algorithm 3 times.

001 1

011 3

010 2

110 3

100 2

101 1

and if we get 0 or 7 we discard them. and run the algorithm 3 more times.

now potentially this algorithm could run forever.

you could get 0 indefinitely or 1 indefinitely.

but if the algorithm ever does halt, it will halt with perfect uniformity.

that is we will have generated either a 1 2 or 3 with equal likely hood.

In practice yeah that would be the best solution since the probability of running forever goes to 0 exponentially fast.

However the question here is: can you guarantee the number of "dice throws" you need beforehand?