3

I have the following piece of code:

public class Main {
private static final Random rnd = new Random();

private static int getRand(int n) {
    return (Math.abs(rnd.nextInt())%n);
}

public static void main(String[] args) {
    int count=0, n = 2 * (Integer.MAX_VALUE/3);
    for(int i=0; i<1000000; i++) {
        if(getRand(n) < n/2) {
            count++;
        }
    }
    System.out.print(count);
}
}

This always gives me a number close to 666,666. Meaning two-thirds of the numbers generated are below the lower half of n. Not that this is obtained when n = 2/3 * Integer.MAX_VALUE. 4/7 is another fraction that gives me a similar spread (~5714285). However, I get an even spread if n = Integer.MAX_VALUE or if n = Integer.MAX_VALUE/2. How does this behavior differ with the fraction used. Can somebody throw some light on it.

PS: I got this problem from the book Effective Java by Joshua Bloch.

1

4 Answers 4

4

The problem is in the modulo (%) operator which results in an uneven distribution of numbers.

For example, imagine MAX_INT is 10, and n = 7, the mod operator will map the values 8, 9 and 10 to 1, 2 and 3, respectively. This will result that the numbers 1, 2 and 3 will have double the probability of all other numbers.

One way to solve this is by checking the output of rnd.nextInt() and try again while it's bigger than N.

2
  • Yes, if we run the code without the %n, count will be 1/3 of the number of loops (exactly what we are expecting: 1/3 * 1/2 * Integer.MAX_VALUE)
    – xdola
    Dec 25, 2014 at 1:12
  • Awesome. This was the answer I was looking for. While everyone was quick to point out that % is the culprit, this answer accurately describes why its the culprit. That explains why a fraction of 2/3 gives 2/3 of the numbers in the lower half of n.
    – n3o
    Dec 25, 2014 at 1:15
2

You would get 50-50 if you kept only values of Math.abs(rnd.nextInt()) in the range of [0..2/3(Integer.MAX_VALUE)]. For the rest 1/3*Integer.MAX_VALUE numbers, due to modulo you will get a smaller number in the range of [0..1/3 Integer.MAX_VALUE].

All in all, numbers in the range of [0..1/3 Integer.MAX_VALUE] have double the chance to appear.

1

The Random class is designed to generate pseudo-random numbers. That means they are elements of a defined sequence that have an uniform distribution. If you don't know the sequence, they seem to be random.

Having said that, the problem is that you mess up the uniform distribution you get by using the modulus operator. On coding horror, there is a very nice article that explains this issue, although for a slightly different problem. Now, you can find a solution to your problem along with a proof here.

1
  • The fact that it's pseudo random isn't really relevant here; because it has a uniform distribution, statistics such as this will always check out if you eg. directly use nextInt(n)
    – Vitruvie
    Dec 25, 2014 at 1:11
0

As observed above, getRand does not generate uniformly distributed random numbers over the range [0, n].

In general, suppose that n = a * Integer.MAX_VALUE / b, where a/b > 0.5

For ease of writing, let M = Integer.MAX_VALUE

The Probability Density Function (PDF) of getRand(n) is given by:

PDF(x) = 2/M for 0 < x < (b-a)M/b

   =  1/M   for  (b-a)M/b < x < aM/b

n/2 corresponds to the mid-point of the range [0, aM/b] = aM/2b

Integrating the PDF over the 'first-half' range [0, n/2] we find that the probability (P) that getRand(n) is less than n/2 is given by:

P = a/b

Examples:

a=2, b=3. P = 2/3 = 2/3 = 0.66666... as computed by the questioner.

a=4, b=7. P = 4/7 = 0.5714... close to the questioner's computational result.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.