How to calculate probability of choosing from pool with replacement and at least 2 are the same?

Question

From a group of 1000 numbers with replacement (1 ... 1000), 40 numbers are chosen evenly, How can I find the probability that 2 (at least) chosen numbers are equal?

I thought the following: for the first number if I compare it with any other, the probability that they are equal is 1/1000, right? (The first number is given, so in the group there is only one equal number), so I thought that comparing 2 would be 1/1000 that they are equal and then I did the comparison between all the possible pairs of my 40 numbers, that would be 780 comparisons and if each has a 1/1000 chance of being the same numbers, the total probability would be 780/1000 = 78%.

But i know im wrong somewhere, I'm doing a simulation with Python (code) and it gave me around 54.5% success.

Answer 1

It's often easier to calculate the complement event and then do 1- that. Here the complement event is that no two numbers are equal.

The first number is arbitrary, so there is no chance of it being duplicated, or 1000/1000

The second number has 999/1000 chance of being different from the first number

Continuing onwards, we get $$\frac {1000P40} {1000^{40}}$$ ways of picking 4 numbers

Doing the compliment, $$1-\frac {1000P40} {1000^{40}}$$ gets us via wolframalpha to roughly $54.64\%$, which meshes well with your experimental data

Answer 2

You have to account for 2 being equal and the rest (38) all being unequal, 3 being equal and the rest all (37) being unequal and so on.

The probability is:

$$p = {40 \choose 2} \frac{1}{1000}\left(\frac{999!}{(999-38)! 1000^{38}}\right)+{40 \choose 3} \left(\frac{1}{1000}\right)^2\left(\frac{999!}{(999-37)! 1000^{37}}\right)+\dots$$

Which can be written as:

$$p = \sum\limits_{i=2}^{39}{40 \choose i} \left(\frac{1}{1000}\right)^{i-1}\left(\frac{999!}{(999-40+i)!1000^{999-40+i}}\right)$$

---

EDIT: As @Alan points out in the comment, much easier to calculate the complement probability.