silent-box - 3 months ago 16

Java Question

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.

Source (Stackoverflow)