Randomness

Take a look at the following puzzle:

“Given a function which produces a random integer from 1 to 5, write one that produces a random integer from 1 to 7″

I immediately thought of this:

...
function naiveRand(){
 return (given() + given()) % 7 + 1;
}
...

It is obviously not random enough, you can guess that there are more chances of getting 7 than the other numbers, the number of combinations is 25, each one of these resulting in an integer between 1 and 7,  but there are more ways of getting 7 than any other number, see:

1 : 4 chances: 5+2, 2+5, 3+4, 4+3
2 : 3 chances: 3+5, 5+3, 4+4	
3 : 3 chances: 4+5, 5+4, 1+1	
4 : 3 chances: 1+2, 2+1, 5+5	
5 : 3 chances: 3+1, 1+3, 2+2	
6 : 4 chances: 1+4, 4+1, 2+3, 3+2
7 : 5 chances: 5+1, 1+5, 4+2, 2+4, 3+3

More graphically:

Recalculate

That is clearly not the picture of a uniform distribution, so what if we add few more invocations to given()? Something like this would do the trick:

function newRand(){
 return (
 given() +
 given() +
 given() +
 given() +
 given() +
 given() 
 ) % 7 + 1;
}
Recalculate

The number of combinations is 5^6 (15625) and as you can see in the graphic above, it seems pretty random, but if you count the number of opportunities to get each integer from 1 to 7 you’ll find this:

1 : 2229
2 : 2224
3 : 2224
4 : 2229
5 : 2238
6 : 2243
7 : 2238

Number 6 is slightly more likely to come out. So how can this task be achieved? I spent around an hour trying to think of a better solution, but I couldn’t.
So I googled the question and I found a couple of posts with similar answers, none of them was a better approach, until I found Simon’s, which I think is more elegant and totally random, or at least as random as the given function should be:

function simonsRand(){
 var randtab = [
   [1,1,1,2,2],
   [2,3,3,3,4],
   [4,4,5,5,5],
   [6,6,6,7,7],
   [7,0,0,0,0]
 ];
 var r = 0;
 while(r == 0)
   r = randtab[ givenRand() -1][ givenRand() -1];
 return r;
}

He makes a 5×5 table and uses just two executions of given() to produce a [i,j] position. Then repeats each integer from 0 to 7 exactly 3 times which is the best way to fill the table with minimum wasted spaces, if we hit 0, just repeat. We end up with 1/25 possibilities of hitting each position.

As you can see, both newRand() and simonsRand() produce similar results on a large scale, but Simon’s approach uses a lot less given() executions.

Recalculate



  • phil F

    Why not simply:
    rand() {
    return givenRand() + (givenRand() % 3);
    }

    ?