Calculating the probability of at least 2 duplicates in a world with 400 tiles and 50 objects? Java

Question

First of all I want to let you know that I have been searching for some days now for an answer or something that could perhaps help me out a bit but I couldn't find anything so I am asking here.

I have in my Java code:

An arraylist of 50 objects.
Random X and Y elements put into each object in the arraylist.
Method checking if there are duplicates.

So based on the amount of duplicates(Not sure about this part but other people I know seem to do it like this) I need to calculate the probability of at least 2 objects having the same coordinates in a world of 400 tiles/choices (20x20). The world of 400 tiles does not exist yet in my code but I have to calculate it by thinking of that.

The probability should be something like 0.95xx in the end of having at least a duplicate.

So I know I have to calculate the probability of getting NO duplicates and do: (1 - P(NoDupes)). But how do I calculate P(NoDupes)?

Thanks in advance

Answer 1

After reading this a few times I think what you're asking is:

Given a 20x20 grid, what is the probability that there will be at least one collision when inserting 50 random points?

If this is indeed what you are asking then a simple way of coming up with an answer is by the following logic:

The first object cannot collide with anything since it is the first. So the chance of no collision here is 400/400 = 1.
The second object can only collide with the first object. So the chance of no collision is 399/400.
The third object can collide with the first or the second. So the chance here is 398/400.
...
The nth object can collide with any of the previous n-1 objects. So the chance here is (400-(n-1))/400 (or if n is greater than 400 the chance is just 0).

The chance of no collision for n objects is then just the product (400/400)(399/400)...((400-(n-1))/400)
The chance of at least one collision is then as you correctly said 1 - P(No Collision).

Answer 2

HINT: Think of this problem as drawing elements from a set of 400 with replacement. The 2-d coordinates are a distraction.

Then compute 1 - P(NO DUPES) - P(1 DUPE) - P(2 DUPES)