CODEWITHSUNDEEP
algorithmrandom
Vladimir Gamalyan
Vladimir Gamalyan

Reputation: 255

Shrink a random range from 0–2 to 0–1

A random generator produces values from the list: 0, 1, 2 (with equal probabilty for all three values).

How to get a random number, 0 or 1, with equal probability, from no more than ten uses of the generator.

Upvotes: 1

Views: 171

Answers (1)

Peter O.
Peter O.

Reputation: 32878

Your goal is ultimately to roll a 2-sided die given only a 3-sided die, using a fixed number of rolls of the 3-sided die.

However, this is impossible no matter how many rolls you do, since 2 does not divide 3 (and both are prime numbers). The best you can do here is keep rejecting 2's (and the probability of getting n 2's in a row is 1/3^n, a probability that shrinks rapidly with increasing n).

More generally, it's impossible to roll a k-sided die using a p-sided die using a fixed number of rolls of the p-sided die unless "every prime number dividing k also divides p" (see Lemma 3 in "Simulating a dice with a dice" by B. Kloeckner.

See also the following questions:

Upvotes: 4

Related Questions