Ok so we saw that a uniform binary number generator (fair coin) isn't good for us when we want to generate stuff with probability 1/n where n isn't a power of 2.
So instead of a [0.5 , 0.5] generator, I am allowing you to customize your own random generator, namely you choose some k>1 and give me {p1...pk} and I will give you a random number generator that generates numbers between 1 and k with those probabilities.
What kind of generator do you choose and how will you use it to generate numbers with probability 1/n?
(note again I ask that your algorithm guarantee not to run for ever, as in for every n exists M such that you use the customized generator at most M times)
Question
Anza Power
You must solve before reading this one.
Ok so we saw that a uniform binary number generator (fair coin) isn't good for us when we want to generate stuff with probability 1/n where n isn't a power of 2.
So instead of a [0.5 , 0.5] generator, I am allowing you to customize your own random generator, namely you choose some k>1 and give me {p1...pk} and I will give you a random number generator that generates numbers between 1 and k with those probabilities.
What kind of generator do you choose and how will you use it to generate numbers with probability 1/n?
Link to comment
Share on other sites
5 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.