Random behavior of int function in Java
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. Two thirds of the generated numbers are below the bottom half of n. Not that this is received 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 from the faction used. Maybe someone sheds some light on him.
PS: I got this problem from Effective Java book by Joshua Bloch.
source to share
The problem is in the modulus (%), which leads to uneven distribution of numbers.
For example, imagine MAX_INT is 10 and n = 7, the mod statement will map the values 8, 9, and 10 to 1, 2, and 3, respectively. This will cause the numbers 1, 2, and 3 to have double the probability of all other numbers.
One way to solve this problem is to check the output rnd.nextInt()
and try again as long as it is greater than N.
source to share
You would get 50-50 if you only stored Math.abs (rnd.nextInt ()) values in the range [0..2 / 3 (Integer.MAX_VALUE)]. For the rest of the numbers 1/3 * Integer.MAX_VALUE due to modulation you will get a lower number in the range from [0..1 / 3 Integer.MAX_VALUE].
In general, numbers in the range [0..1 / 3 Integer.MAX_VALUE] have a double chance of appearing.
source to share
The class is Random
designed to generate pseudo-random numbers. This means that they are elements of a specific sequence that are evenly distributed. If you don't know the sequence, they seem to be random.
Having said that, the problem is that you've messed up the uniform distribution that you get using the modulus operator. When coding horror, there is a very nice article that explains this problem, albeit for a slightly different problem. Now you can find the solution to your problem along with the proof here .
source to share
As noted above, getRand does not generate uniformly distributed random numbers in the range [0, n].
In general, suppose 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) for getRand (n) is defined as follows:
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 midpoint of the range [0, aM / b] = aM / 2b
By integrating the PDF in the "first half" range [0, n / 2], we get that the probability (P) that gets R and (n) less than n / 2 is given by:
P = a / b
Examples:
a = 2, b = 3. P = 2/3 = 2/3 = 0.66666 ... as calculated by an expert.
a = 4, b = 7. P = 4/7 = 0.5714 ... close to the computational poll result.
source to share