This problem states that we are given a random number generator which generates uniform distribution of 0,…,n-1.
I was thinking about this for quite a long time and decided to look at the solution. It seems that the solution refers to problem 6.16. However, in solution for 6.16, the random generator is used in a loop to generate numbers between i and n-1 for i = 0 through k -1.
But I thought this is not allowed from the way problem 6.17 is stated. It states we are given only random generator to generate uniform numbers 0 to n-1 and that’s the only generator we can use.
With only this generator given, how do we generate uniform numbers is a smaller range (like from i though n-1)? Of course if we are able to generate in these smaller ranges, the solution becomes fairly simple. But how we generate within these smaller ranges? Note that using (our generator mod k) is not satisfactory since the distribution will not be uniform then.
So my question is, is there solution that solves the problem as stated, with only one uniform random generator in range 0,…,n-1?
I have the 1st edition of the book, I’m wondering if later editions have correct solution. Please don’t tell me the actual solution if it exists, i still want to try to solve it on my own, i just wanted to know if correct solution exists and how many calls (asymptotically) it makes to the random number generator.
Thanks,
Yev