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
-~----------~----~----~----~------~----~------~--~---
