@Karthikeya: You accept that your for-loop generates a random integer between 0 and 2^d - 1, right? Then take a look at http://en.wikipedia.org/wiki/Rejection_sampling. Basically, you reject any random integer that exceeds b-a. The probability that you reject a number is 1 - (b - a + 1) / (2^d - 1). Call this r. Then the average number of integers rejected is r + r^2 + r^3 + ... = r / (1 - r), so the average number of integers required to produce one [a, b] sample is 1 + r / (1 - r) = 1 / (1 - r) = (2^d - 1) / (b - a + 1).
Dave On Feb 26, 12:40 pm, karthikeya s <karthikeya.a...@gmail.com> wrote: > Assuming we have an implementation of RANDOM(0.1), how can we > implement RANDOM(a.b) - i.e. given we have a function that returns 0 > OR 1 both with a probability of 1/2, how can we implement a function > that returns integers from a to b (b > a), all with a probability of 1/ > n, where n = (b-a+1) > > my soln: > 1.we can run random(0,1) b-a times....and sum up all the values > generated........that is what i thought.......but smone told me that > it is not correct coz sum follows binomial distribution, thus don't > have equally like chance > > 2.on some site: > > RANDOM(a,b) > range = b - a; > d = the number of binary bits %range has > do > for(i = 1 to d): > i th bit of integer res = rand(0,1); > while(res >range); > return (a + res); > > Each time of while loop need O(log(b-a)) time, and the expectation of > that while loop is constant. Therefore, it takes time O(log(b- > a))..........how does he say that "expectation of that while loop is > constant"........m weak with probability.....plz enlighten me.... -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
