Given a function rand7(), write a function which rand10() uniformly

Question

Can i have an efficient solution for the above problem.... I tried to figure out the problem from this website http://www.ihas1337code.com/2010/11/rejection-sampling.html but couldn't get the reason idx = col + (row-1)*7; why are they multiplying with 7....

we could have done this also (rand7() * rand7()) % 10... or multiplying with any other number, because at the end we have to do mod 10 which will give the results within 10 only....

why they have made the solution so difficult.. Please explain and your thoughts on it...

And what does uniformly means in the question?

Thanks..

Answer 1

(rand7() * rand7()) % 10

won't do, since some values will be more probable than others.

Lets compare the probability of for instance getting a 1 and getting a 2:

To get a 1:

• rand7() * rand7() would need to equal 1, 11, 21, 31 or 41.
• This can be achieved in the following ways: 1*1, 3*7 or 7*3.
• That is, 3 times out of 49 you'll get a 1

To get a 2:,

• rand7() * rand7() would need to equal 2, 12, 22, 32 or 42.
• This can be achieved in the following ways: 1*2, 2*1, 3*4, 4*3, 2*6, 6*2, 6*7, 7*6.
• That is, 8 times out of 49 you'll get a 2!

---

Their solution solves this by letting each number (from 1 through 10) be equally probable: Each number occurs 4 times in the 49 possible outcomes, (9 outcomes are discarded and result in a re-sampling).

---

As a matter of fact, the implementation of Random.nextInt(int n) does something similar:

int bits, val;
do {
    bits = next(31);
    val = bits % n;
} while (bits - val + (n-1) < 0);    // re-sample until in range.
return val;

This actually uses a rand2 to implement a randN.

Answer 2

It's the base conversion of a two-digit base-7 number into a base-10 number. And it's exactly the way you would extend this to the solution to the

Generalized problem

Implementing a randA() function using randB(), for B,A > 1.

Solution

1. Generate sufficiently many (ceil(ln(A)/ln(B))) base-B digits

2. Ensure uniform distribution: If number > A*floor(pow(B,ceil(ln(A)/ln(B)))/A) reject it and continue with 1, else continue with 3

3. Base convert the resulting number into base-A, choose least significant digit to be result of randA()

JavaScript-Example

// This function returns a randN function. Usage 
// example rand7=randn(7); rand7(); rand7()
function randn(i) {
    return function () {return Math.floor(Math.random() * i);};
}

// Given a random generator for numbers 0..b-1 this
// function returns a random generator for numbers 0..a-1

function randA(b, randB, a) {
    var digits=Math.ceil(Math.log(a)/Math.log(b));
    var maxNum=a*Math.floor(Math.pow(b, digits)/a)-1;
    return function() {
        var s;
        var number;
        do {
            s="";

            // Step 1
            for ( var i=0; i<digits; i++ )
                s += randB();

            number=parseInt(s, b);
            
        } while (number>maxNum); // Step 2

        return number%a; // Step 3
    };
}
// generates a rand8() number generator
rand8=randA(2,randn(2),8);
// generates array containing random numbers 0..7
[rand8(), rand8(), rand8()]