I am assuming that by random you mean uniformly at random (that
is, the probability of generating i is 1/5)
map the following pairs of numbers (1, 1), (1, 2), (1, 3), (1, 4), (1,
5), (2, 1), (2, 2) to 1, 2, .. , 7 respectively
let p_i denote the pair corresponding to the number i (e.g. p_1 = (1,
1))
use your random generator twice to output two numbers generated at
random from {1, .., 5}
if the generated pair is a p_i for some i, output i
otherwise repeat
what is the probability of outputting i? it's the probability of the
union of the following independent events: generating p_i on the first
iteration, generating p_i on the second iteration and the first
iteration did not generate a p_j for all j, etc.
you can actually compute the probability of outputting i (two events
such as generating p_i on iteration j and generating an invalid
pair on iteration j-1 are independent, so you get an infinite
geometric series whose value we know how to compute), but what you
really care about is the fact that the probability of outputting i =
probability of outputting j, for all i != j
so the new generator will generate one of {1, 2, .. , 7} uniformly at
random
On Jan 30, 8:57 pm, Jialin [EMAIL PROTECTED] wrote:
Question:
Given a program which can generate one of {1, 2, 3, 4, 5} randomly.
How can we get another generator which can generate one of
{1,2,3,4,5,6,7} randomly?
Thank you!
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~--~~~~--~~--~--~---
