@Snehal: If p has a finite binary representation, of say n bits, then generate a sequence of up to n unbiased random numbers, continuing the sequence as long as the ith random number agrees with the ith bit to the right of the binary point. When the ith number disagrees with the ith bit, return that ith number. If the computation continues until even the nth number matches the nth bit, then start over.
Example: Suppose that the binary representation of p is 0.101101. If the first unbiased random number is 1, generate the second number. If the second number is 0, continue to the third number. If the third number is 0, return 0. If p does not have a finite binary representation, e.g., if p = 1/3 or sqrt(1/2) and you are not using a finite precision floating point representation, then the algorithm will terminate with probability 1. Dave On Oct 8, 2:44 am, snehal jain <learner....@gmail.com> wrote: > Given a unbiased function that generates 0 and 1 with equal > probability write a function biasedrandom that genreates 0 with > probability p and 1 with probability 1-p. -- 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.
