If rand5 is truly random, then the average number of iterations is 25/21 ~ 1.19. Thus, the average number of rand5 calls to generate one rand7 number is approximately 2.38. Since the probability of n or more iterations is (4/25)^(n-1), the probability that the process will iterate indefinitely is zero. You can decrease the average number of iterations by generating more rand5 numbers in each iteration. For example, with 6 rand5 numbers, the average number of iterations is 15625/15624 ~ 1.000064, but the average number of rand5 numbers to generate one rand7 number is approximately 6.00038. I believe that Soumya's rejection method is the best possible.
Dave On Jun 28, 8:58 am, Senthilnathan Maadasamy <senthilnathan.maadas...@gmail.com> wrote: > @Saumya, This is a great approach. But it still has a small problem since > there is a non-zero probability (though small) that we need to repeat this > experiment infinitely many times to get a single random number in [1,7]. Is > this the best we can do? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
