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 {p_{1}...p_{k}} 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)

Posted

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 {p

_{1}...p_{k}} 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?

## Share this post

## Link to post

## Share on other sites