Java: Generating a random numbers with a logarithmic distribution

Question

I am attempting to generate a random numbers with a logarithmic distribution.

Where n=1 occurs half of the time, n=2 occurs a aurter of the time, n=3 occurs an eight of the time, etc.

    int maxN = 5;
    int t = 1 << (maxN); // 2^maxN
    int n = maxN -
            ((int) (Math.log((Math.random() * t))
            / Math.log(2))); // maxN - log2(1..maxN)
    System.out.println("n=" + n);

Most of the time, I am getting the result I need, however once every so often, I get a value of n that is larger than maxN.

Why is this so? The way I see it, the max value of Math.random() is 1.0;
therefore the max value of (Math.random() * t)) is t;
therefore the max value of log2(t) is maxN, since t = 2^maxN;

Where has my logic gone off track?

Thanks

Answer 1

If Math.random()*t is less that 1, then you will get a negative answer when you take Math.log(Math.random()*t), by the rules of Logarithms. This means that you will get a negative answer when you divide by Math.log(2) because that is 0.69314718055994530941723212145818. This is a negative number divided by a positive number. The answer is negative. maxN - a negative number = maxN + something positive, so n is greater than maxN. To fix this cast Math.random()*t to an int and add 1:

int n = maxN -
        ((int) (Math.log((int)((Math.random() * t)+1))
        / Math.log(2))); // maxN - log2(1..maxN)

Notice the cast inside the log, and the add of 1.

The purpose of adding one would be to avoid the 0. Can't take a log of 0. Also, without adding 1, you could never get maxN inside the log, because Math.random() never produces 1. This way, instead of getting 1 half, 2, a fourth, 3, and eighth, it just starts at 0. This gives 0, a half, 1 a fourth, 2 an eighth, etc.

Answer 2

logarithm of numbers less than 1.0 is negative. When the random number generated is such that it is less than 1.0, the expression ((int) (Math.log(Math.random() * t) / Math.log(2))) is a negative number and hence maxN - (the negative number) is more than maxN.

The following expression should give correct distribution.

n = Math.floor(Math.log((Math.random() * t) + 1)/Math.log(2))

Note that:

0.0 <= Math.random() <= 1.0
0.0 <= Math.random() * t <= t
1.0 <= (Math.random() * t) + 1 <= t + 1.0
0.0 <= Math.log((Math.random() * t) + 1) <= Math.log(t + 1.0)
0.0 <= Math.log((Math.random() * t) + 1)/Math.log(2) <= Math.log(t + 1.0)/Math.log(2)

Since t = 2^maxN,
Math.log(t + 1.0)/Math.log(2) is slightly larger than maxN.

So do a Math.floor and you get the correct result:
0.0 <= Math.floor(Math.log((Math.random() * t) + 1)/Math.log(2)) <= maxN

Answer 3

The problem is in the other end of the scale.

Consider what would happen if you get a very small random number.