Challenge – Equal Probability between 1 and 7

Question: Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

Challenge: Do you know the answer to this question? Post in the comments. Let’s see who is up for the challenge. Answers will be posted February 26th.

Let’s think of this like a decision tree. Each rand5() will be a decision. After 2 tries, we have 25 possible solutions. We try to get maximum bunches of 7 as we can (1 – 21, 3 sets of 7). If we get any of the other values, we just try again. Since the probability of getting each of 21 values are the same every time, trying again won’t affect their probabilities.

Equal Probability 1 to 7

int rand7() {
    while (1) {
        int num = 5*(rand5()-1) + rand5();
        if (num < 22) return ((num % 7) + 1);
    }
}

That was fun, right? Anyone up for another challenge? Watch out for it next tuesday (March 1st).

82 Comments

82 Responses

  1. someone says:

    How about (rand5() + (rand5() %4) -1)

  2. Gustavo says:

    int rand7() {
    double pot = log(7) / log(5);
    return pow(rand5(), pot);
    }
    // r7 = r5 ^ (ln7/ln5)

  3. shubham says:

    We have R5() method which returns randomly between 1 to 5 so we can make use of it such that the probability remains equal for all 1 to 7.
    int R7()
    {
    int x,y1,y2,y3;
    x=R5();
    y1=R5();
    y2=R5();
    y3=R5();
    return (x+((y1+y2+y3)%3));
    }
    After getting one random value (x) between 1 to 5, we need a random value between 0 to 2 with equal probability. So we get modulus by 3. But since between 1 and 5 probability of getting 1 and 2 is 2/5 each and getting 0 is 1/5 so we fetch random number (y1,y2,y3) 3 times and add them and finally mod by 3 so we get 0,1,2 with equal probability. We add these random value between 0 to 2 with another random number (x) between 1 to 5 which we found separately.

  4. What’s the point? If you really want the result to be truly random between 1 and 7, why not just use rand7. Rand5 is really irrelevant.

  5. laxatives says:

    Am I missing something? Why can’t you just multiply rand5() * 7/5? I just Monte Carloed this and each value [1,7] was 20000+/- 300

  6. MMS says:

    how about
    rand7()
    {
    rand5() + rand5()%3;
    }

  7. Simply divide the random number between 1 to 5, by 5.
    This make it a random float between 1/5 to 1.

    Then multiply this float number by 7 which makes it between 1 and 7.

    Thus
    float i = Math.round(random()*7/5);

  8. sarah says:

    another approach could be to convert down your random 5 into random binary. 3 random binary and you can convert into a 0 to 7 value. then if you have zero re-run, otherwise return the 1 to 7 value.

  9. I meant —–>>

    (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5()-7)%7

  10. How about —–>>

    (rand5()+rand5()+rand5()+rand5()+rand5() – 5)%7 ??

    That will give you a random number from 0 to 34 with an equal probability that it is any one of those numbers and then modulo 7 an equal probability that it is a number from 0 to 6 …

    The problem with some of the solutions is I don’t think there is an equal probability the number will be 0 to 6 …

  11. Guru says:

    If trying again is an option, then why not just tries twice rand5() as below

    rand7(){
    x = rand5();

    y = 3
    while(y<3){
    y = rand5() – 1; /
    }
    // x = 1,2,3,4,5
    // y = 0,1,2
    return x+y;
    }

  12. Greg says:

    Oops, meant 7 is a prime number and 35 is a multiple of 7, not 35 is prime.

  13. Greg says:

    7 and 5 are both prime.

    How about …
    return (rand5() * 7) % 7

    rand5() * 7 generates random number between 0 and 35 with equal probability (assuming infinite precision). Since there is equal probability of any number between 0 and 35, and because 35 is both a prime number and a multiple of 7, taking the modulo with the prime number (7) generates a random number between 0 and 7 with equal probability.

  14. Doggie says:

    @navz

    You are right it generating all the numbers but there are NOT the same probability of occurring

    Calculate the chance of each of the values happening and see.

  15. navz says:

    rand7()
    {
    k=(rand5()*rand5())%7;
    if(k!=7)
    return k+1; //generates 7
    else
    return k; //generates 1,2,3,4,5,6
    }

    where rand5() generates 1/2/3/4/5
    rand7() generates 1/2/3/4/5/6/7

  16. kvh says:

    The short answer is, if you want a program that is guaranteed to halt, it is not possible. You can only get sample spaces with 5^n outcomes, which is never divisible by 7 exactly (prime factorization), so the best you can do is an approximation.

  17. How about… two tries of rand5() into a base-5 number, which will return 1 – 25 evenly distributed.

    Very roughly:

    function rand7(){

    function rand25() {

    var assemb = 10 * (rand5()-1) + (rand5()-1)
    var second = (assemb – assemb % 10) / 10;
    var first = assemb – (second * 10);
    var rand25 = 5 * second + first + 1;

    return rand25;

    }

    while(1) {
    var testIt = rand25()
    if ( testIt < 22 ) return ( testIt % 7 + 1 )
    }
    }

  18. Doggie says:

    Zhiming, we are not talking about rand in terms for float here. We are only looking at integers. Maybe the question is a little unclear about that.

    int rand7();

    In your case, if we divide by 2, we won’t have an int always and that throws things off.

  19. zhiming says:

    float rand7()
    {
    float a = rand5();
    float b = (a * 3 -1 )/2;
    return b;
    }

  20. Doggie says:

    Hi Manoj,

    I am not sure how k2 &(k2-1) == k2 is checking for perfect square. 9 is a perfect square. ( 9 & 8 ) != 9.

    Even if we replace that with a proper check for perfect square, I don’t think your function provides proper rand6().
    k1 = {0,1,2,3,4} each with equal probability.
    k2 = { {0,0,0,0,0}, {0,1,2,3,4}, {0,2,4,6,8}, {0,3,6,9,12}, {0,4,8,12,16} } each with equal probability.
    k2 is a perfect square 15 out of 25 times (0,1,4,9,16). Your function will return 5, 60% of the time.

    Reading your explanation, you mentioned replacing every 6th number repeated with a 5. How times do you have run this? If you have to run it until a number appears the 6th time, that would be too many tries. Under what situation will you return one of the other numbers?

  21. Manoj says:

    (with corrections)
    First I would implement rand6 and then rand7

    Solution:
    rand5 generates 0 1 2 3 4 equally likely.

    so every 6th time a number, say 4, is repeated i replace it with 5.

    Thus for every 6th repetition of a number by rand5() I force the function to return 5.

    rand6(){
    k1=rand5();
    k2=rand5() * k1;

    //is k2 a perfect square
    if(k2 &(k2-1) == k2) return 5.
    }

    proof: use probability and you will find probability of 5 is same as probability of either of 0 1 2 3 4.

    use the same logic and implement rand7 using ran6.

    }

  22. Aram Alipoor says:

    this is when you want to make random between 1 – 7 :

    int rand7(){
    k = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5();
    return k / 5;
    }

    but if you want to extend it for any number :

    int rand_any_number_using_rand5(int new_base)
    {
    for(int i = 1; i < new_base; i++)
    {
    k += rand5();
    }
    return k / new_base;
    }

  23. Woody says:

    This is my method written in Java. I assume 7 times of rand5() invoking will get a even distribution of 35. then mod 7.

    import java.util.Random;

    public class Rand {
    Random r = new Random();
    int rand7() {
    int s = r.nextInt(5);
    for (int i = 0; i < 6; i++) {
    s += r.nextInt(5);
    }
    return s%7;
    }
    public static void main(String[] args) {
    new Rand().start();

    }
    private void start() {
    int[] count = {0,0,0,0,0,0,0};
    int d = 1000;
    int c = 0;
    while(true){
    int i = rand7();
    count[i]++;
    c++;
    if (c == d) {
    c = 0;
    for (int j = 0; j < count.length; j++) {
    System.out.print(count[j] + ",");
    }
    System.out.println();
    }
    }

    }
    }

    Here is my result after running thousands, millions
    77858,77310,77523,76907,76496,76458,76448,

    572537,571818,571256,570103,569654,571263,571369,

    6124993,6124855,6118048,6103199,6110062,6118427,6123416

  24. teepark says:

    should’ve used the word “integer” in the question somewhere.

    rand5()*1.4

  25. Doggie says:

    You are right. I missed a -1 in the code. Updated now

  26. Haw-Bin Chai says:

    I don’t see how the posted solution is correct.

    * num will always be in the range 6..30 .
    * (num < 22) gives the range 6..21 . This is a range of 16 values. How is the modulo 7 of this be an even distribution?

  27. Adding up 7 of the 1..5 variables makes the distribution of the distribution of the total mod 7 flat to about 3 decimal places, adding up 11 gives 4 places, and so on, up to about 50, which gives around 21 decimal place equality.

  28. Posted solution is equivalent to mine and the other that I have identified as correct.

    The algorithm I posted that uses the random numbers from 1-5 to determine the winner of a game between the numbers from 1-7 has an interesting property: Suppose you find that the randoms from 1-5 that your are getting are not actually evenly distributed — as long as they are independent and identically distributed, the game algorithm gives evenly distributed answers. Suppose your purchasing team finds another cheaper source of random numbers, but it does not give randoms from 1-5, it gives hex digits or hypergeometric or binomials or log normals or whatever, you can plug it into the game algorithm and you will still get uniformly distributed answers from 1-7 out, no change in the client algorithm.

    The question of how many randoms from 1..7 one must add up before mod(total, 7) is ‘close enough’ to uniformly distributed to work is one that I would like to figure out. I wonder if using 10 or 20 or so would get the probabilities essentially equal as close as we could tell from a few billion tests. Anyone know? I may try to work that out.

  29. Doggie says:

    The solution is up. Any thoughts?

  30. Here’s another approach that is also unbiased:

    Start a game between the seven numbers and start each number with a score of zero.

    a. Add a random base 5 digit to each number’s score.

    b. Remove any number that does not have the highest score from the game.

    c. If there is only one number with the highest score, that is your random number.

    d. If more than one number is still in the game,
    go back to step a.

    This takes at least seven calls to rand 1..5 to finish, so it is not so efficient, but it has a great
    feel of fairness to it.

  31. The algorithm by Chris Lomont and the one by me obviously give equal probability to each of the seven results when they return, and repeat the same process until they do return, so it is pretty hard to see how they could not be fair. The more interesting question is whether or not my recursive function ‘guarantees’ that it will return before time runs out or the stack overflows, or whatever. There is some small probability of that, with a recursion happening about once in each 6 calls. Even python, which I wrote mine in (v 2.6), and which does not do tail call optimization, will let one recurse a little function like that for hundreds of levels on typical computers. That puts the probability of the stack crashing down around the probability of not finishing the computation because a meteorite hits your computer, which I suppose any algorithm must bear as an acceptable risk.

  32. Paddy3118 says:

    Anyone else with proof, empirical or otherwise, for their algorithms?

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>