silent-box silent-box - 3 months ago 16
Java Question

Java random intersection in a range: unexpected results

Please consider this piece of code:

private static final Random RANDOM = new Random();

public static void main(String[] args) {

long distinct = IntStream.range(0, 600)
.map(i -> RANDOM.nextInt(600))
.distinct()
.count();

System.out.println("intersection %:" + (double) (600 - distinct) / 600 * 100);
}


I'm generating a random int in a range of (0-600) 600 times, naively expecting to have 0% intersection. Real results are ~ 37%.

Is there a math formula to calculate intersection probability, having range of random ints and the number of invocations? I don't really like to trust this empirical 37% on my calculations

Answer

Java's Random.nextInt() is guaranteed to have an uniform distribution, not to be unique everytime you call it.

Thus, the intersection probability is the same kind of calculation than the birthday problem (https://en.wikipedia.org/wiki/Birthday_problem). I'm sorry I don't have the whole formula from the top of my head, but it might be easily found with a little research (or even calculating yourself).

EDIT2 :

The wikipedia page already contained everything you needed : Look at the part collision counting.