Not that I am trying to prove a point...but just trying to clarify what I said... A uniform random number generator, say rand_5() produces a value 2 with probability 1/5 it can produce a sequence of two 2s with probability (1/5)^2 it can produce a sequence of three 2s with probability (1/5)^3 .... therefore with a probability of (1/5)^n...the code may make 'n' calls to rand_5() with an infinitesimally small probability lim (n -> inf) (1/5)^n the code may never halt... although under limiting conditions it reaches zero for any given extremely large n value there is a possibility that the algorithm can take n steps if you are extremely 'unlucky' My only concern is that we are not able to state the 'worst-case' run-time for such rejection algorithms.
Having said that, all that I am posing is a question as to "whether we can do it with a provably finite number of steps (say < 10 calls to rand_5()) ? " - Karthik On Tue, Sep 8, 2009 at 5:12 PM, Dave<[email protected]> wrote: > > Manish, your first approach doesn't work. You will notice that b1, b2, > and b3 each are 0 2/5 of the time and 1 3/5 of the time, so the return > value is not uniformly distributed. > > For approach 2, what do you have to do if you want an exactly uniform > distribution as a result? Or what would the code look like for one of > your non-exact methods? > > Dave > > On Sep 8, 1:32 pm, manish bhatia <[email protected]> wrote: >> I can think of 2 appraches. >> >> [1] Similar to something already suggested. Just adding my 2 cents. >> >> 1 to 7 digits can be represented by 3 bits. So going by that, >> >> int rand_1_7() { >> b1 = rand_1_5()*(7/5) > (7/2) ? 1 : 0; >> b2 = rand_1_5()*(7/5) > (7/2) ? 1 : 0; >> b3 = rand_1_5()*(7/5) > (7/2) > 1 : 0; >> return (b1*4 + b2*2 + b3*1); >> >> } >> >> [2] What we are trying to do is map numbers 1 to 5 to numbers 1 to 7. Of >> course mapping 5 items to 7 items is not straight forward. So lets not map >> items, but map transitions. Suppose an imaginary initial state x. Now when >> we call rand_1_5(), we have one of the following transition, >> 1) x -> 1 >> 2) x -> 2 >> 3) x -> 3 >> 4) x -> 4 >> 5) x -> 5 >> Now, lets call rand_1_5() again, and remember the last transition, viz. >> 1) x -> 1 -> 1 >> 2) x -> 1 -> 2 >> .... >> 24) x -> 5 -> 4 >> 25) x -> 5 -> 5 >> >> So we have 25 transitions. Divide it by 7, we get 4 as remainder and 3 as >> quotient i.e. if we each number 1 to 7, three of these 25 transitions each, >> we get 4 unused transitions. Lets take it to next level. We get 25*5 = 125 >> transitions. Divide by 7, we get 6 unused transitions. Still another level, >> get us 125*5 = 625 transition, divide by 7, we get 2 as remainder. So >> nearest we get is, 625*5*5 = 15624. Dividing by 7, we get 1 as remainder. So >> in 15625 transitions, (by calling rand_1_5() 6-times), we can assign 2232 >> unique-transitions to each on of 1,2,..,7. With just 1 un-assigned >> transition, we get 1/15625 part-error, or 0.0064% error. >> >> Comments? >> >> On Sep 7, 10:56 am, ankur aggarwal <[email protected]> wrote: >> >> > Given a random number generator that generates numbers in the range 1 to >> > 5, how can u create a random number generator to generate numbers in the >> > range 1 to 7. (remember that the generated random numbers should follow a >> > uniform distribution in the corresponding range) >> >> Love Cricket? Check out live scores, photos, video highlights and >> more. Click herehttp://cricket.yahoo.com > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
