mardi 27 juin 2017

design a random(5) using random(7)

Given a random number generator random(7) which can generate number 1,2,3,4,5,6,7 in equal probability(i.e., the probability of each number occurs is 1/7). Now we want to design a random(5) which can generate 1,2,3,4,5 in equal probability(1/5).

There is one way: every time we run random(7), only return when it generates 1-5. If it is 6 or 7, run again until it is 1-5.

I am a little confused. The first question is:

How to proof the probability of each number occurs is 1/5 in mathematical way? For example, assume probability of returned number 1 is P(1). If B means 'the selected number is in 1-5' and A means 'select 1', then according to conditional probability, P(1) = P(A|B) = P(AB) / P(B). Obviously P(B) is 5/7. But if P(1)=1/5, P(AB) should be 1/7, why? I think P(A)=1/7. Is there anywhere wrong?

The second question is, this method will run until random(7) not return 6 or 7. What if it runs for a long time not returning 1-5? I know the chance is very very small but is there any way to prevent it?

Thanks!




Aucun commentaire:

Enregistrer un commentaire