Identify the error in the problem related to birthday paradox.

Question

Consider the simple problem below. I know solution method 1 is correct. But where am I going wrong in methods 2 and 3?

Three people each choose a random number between 1 and 100. What is the probability that no two of them have picked the same number?

Method 1:

Each person has to choose a different number from the previous person.

$\therefore P = \frac{100}{100} \times \frac{99}{100} \times \frac{98}{100} = 0.9702$

Method 2:

$P($No two persons choose same number$) = 1 - P($At least two persons choose same number$)$

Number of pairs of two persons = $\binom{3}{2}$ = 3

$P($At least two persons choose same number$)$ = P(1st pair chooses same number OR 2nd pair chooses same number OR 3rd pair chooses same number)

$\therefore P = 1 - (\frac{1}{100}+\frac{1}{100}+\frac{1}{100}) = 0.97$

Method 3:

$P($No two persons choose same number$) = 1 - P($Each pair of two persons choose different numbers$)$

Number of pairs of two persons = $\binom{3}{2}$ = 3

$P($Each pair of two persons choose different numbers$)$ = P(1st pair chooses different numbers AND 2nd pair chooses different numbers AND 3rd pair chooses different numbers)

$\therefore P = \frac{99}{100}\times\frac{99}{100}\times\frac{99}{100} = 0.970299$

Answer 1

Method 2: Every time you count that a pair chose the same number, you are also counting the possibility all three of them choose the same number. That way you count the case all three chose the same number 3 times so to correct for that you need to subtract $2P(\textrm{All three chose the same number}).$ $$P=1-\left(\frac{1}{100}+\frac{1}{100}+\frac{1}{100}+2\cdot\frac{1}{100}\cdot\frac{1}{100}\right)$$

Method 3: As others have mentioned, these probabilities are not independent (see the overlap in the picture above) so you can't just multiply them like that. While method 2 had an easy fix, fixing this would simply lead you to method 1. $$P=P(\textrm{1st pair chooses different numbers})P(\textrm{3rd person chooses a different number from the other two})=\frac{99}{100}\cdot\frac{98}{100}$$

Answer 2

In solution #2, the case where all three people choose the same number is counted in all three of your cases. This is why you get a lower probability.

In solution #3, similarly because all three people could choose the same number, your probabilities are not independent, so you can't multiply them.

Answer 3

Method 2: P(At least two persons choose same number) = P(exactly two choose the same number) + P(exactly three choose the same number).

Method 3: P(no two persons choose the same number) --- this was done in a straightforward way in your Method 1; be that as it may, this would be (indirectly),

$1$ - P(exactly two people choose the same number) - P(exactly three people choose the same number).