I am trying to get around this problem of my own making. I want to generate 0 or 1 with another function(gr0_4()) which generates random number from 0 to 4.

I am wondering if I can approach this way:

a). if gr0_4() = 0 or 1 then I will use 0

b). if gr0_4() = 2 or 3 then I will use 1

c). if gr0_4() = 4 I will repeat the a) and b) steps.

Is my understanding correct that the "a" and "b" step each has 50% probability of happening?

def gr0_1():
  while True:
    x = gr0_4()
      if x == 0 or x == 1:
        return 0
      elif x == 0 or x == 1:
        return 1

What if I want to use gr0_1() to create gr1_7() i.e. create number between 1 to 7 with equal probability?

Can I use below reasoning to create that function gr1_1().

As 7 consists of 3 bits. I can generate each bit with equal probability using gr0_1(). So I will call gr0_1() three times and based on that value I get, I will set/unset the corresponding bits to generate a number between 1 to 7 including the numbers 1 and 7. However I can get the number 0 but I don't want that so I will repeat the process again. Will the probability of each number generation between 1 to 7 will be 1/7 in that case also?

Some simple mathematical calculation will be nice to answer this. I tried to read up on rejection sampling but couldn't understand much.


Yes, this is exactly rejection sampling and it works in the way you think it works, assuming that your initial procedure gr_04() generates the numbers $0$–$4$ with equal probability (you say it's random but you don't say it's uniform).

If $X$ is distributed uniformly on $\{0, \dots, 4\}$, then $\Pr(x\in\{0,1\}) = \Pr(x\in\{2,3\}) = 2/5$. With probability $1/5$, you'll have to try again but, on your second attempt, the probability of getting $0$ or $1$ is still equal to the probability of getting $2$ or $3$. The number of attempts you have to make before you get something in $\{0, \dots, 3\}$ is just a geometric random variable with parameter $p=4/5$ and this has expectation $(1-p)/p = 1/4$ so, on average, you'll have to make $5/4$ calls to gr_04(), including the one that succeeds.

The analysis of your second example is similar: your procedure generates each possible answer with the same probability and each attempt succeeds with probability $7/8$, so you'll need an average of $8/7$ calls to gr_01(), which means an average of $(8/7)(5/4)=10/7$ calls to gr_04().


Your Answer

