Jump to content
BrainDen.com - Brain Teasers
  • 0

Random Number API - Part 1...


Anza Power
 Share

Question

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?

Link to comment
Share on other sites

11 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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}. :thumbsup:

Edited by gavinksong
Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.
Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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?

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...