Posts
This Question is asked in different formats like simulate rand7() using rand5() function.
There is no right answer to this question if interviewer specifies that 7 sided die should have equal probability to al the numbers on it(i.e. 1-7). This is because 5 and 7 are coprime and there is no direct mapping available between coprimes.
There are several solutions which creates a biased 7 sided die.
Sol1:
Throw 5 sided die 7 times. sum will be between 7 and 35, with equal probable numbers. Then take the module 7 of the sum and add 1 to it.
This solution will produce biased die because probability of 1 is higher here.
Sol2:
rand7() = ((ran5() + rand5() + rand5() + rand5() + rand5() - 5) % 7) + 1
Categories
FollowersBlog Archive
Jobs
Find more freelance jobs
|
Saturday, January 10, 2009
Subscribe to:
Post Comments (Atom)
|
Popular Posts
|
It can be done!!!! What if we want to simulate a 2 sided die with a 5 sided die? Just roll, and ignore any value above 2. That is, we role our 5 side die until we get a value of 1 or 2. The first roll, both numbers have a 1/5 probability of appearing. There is a 3/5 probability that neither appear. There is a 3/5*1/5 probability that the first roll is above 2, and the second roll is 1. Similarly for the second roll being 2. Continuing this pattern, we see that both 1 and 2 have an equal probability of appearing first. Of course it could happen that 1 and 2 NEVER come up, but we can ignore this as it has probability 0 of happening.
ReplyDeleteUsing this same line of reasoning, we can always simulate a n sided die with a k sided die as long as n < k. However, with a k sided die, we can also simulate a k^2 sided die (just role it twice, there are k^2 possible outcomes). In fact, we can simulate a k^m sided die with a k sided die. So suppose n > k. Then for some integer m, we have k^m>n. Since our k sided die can simulate a k^m sided die, and a k^m sided die can simulate an n sided die, we can simulated
So we have the following generalization: we can simulate a k sided die with an n sided die for any k and n.