Figuring out N = 23 Birthday Problem - Probability

Question

I am incredibly frustrated so please excuse me.

I know I can just run the computations but I am struggling to figure out algebraically how I can figure out that n = 23 whereby it takes a minimum of 23 people required for the possibility of 2 people having a birthday on the same day within a year to roughly equal 1/2.

Could someone please help me with this.

I have used the standard notation below which will calculate the given probability of the event not occurring:

$$\frac {1}{2} = \frac{365!}{365^n(365-n)}$$

However I cannot for the life of me figure out how to do the reverse algebraically.

Additionally, I have looked at a number of other forums and I have not found one discussing this aspect.

Thanks

Answer 1

Using probability approximations :

$P$(no collision among $n$ people) = (1 - $\frac{1}{365}) \times (1-\frac{2}{365})\times ...\times (1-\frac{n-1}{365}) = \prod_{i = 1}^{n-1}(1-\frac{i}{365})$

$1 - i < e^{-i}$ via Taylor series and if $\frac{i}{N} << 1$ (which is often the case in crypto) $e^{-\frac{i}{N}} \sim 1-\frac{i}{N}$.

So we can write :

$\prod_{i = 1}^{n-1}(1-\frac{i}{365}) \approx \prod_{i = 1}^{n-1}e^{-\frac{i}{365}} = e^{-\frac{1+2+...+n-1}{365}}=e^{-\frac{n(n-1)}{2 \times 365}}$.

$P$(having at least one collision among $n$ people) $=1-e^{-\frac{n(n-1)}{2 \times 365}}$

if we set the probability to be exactly $0.5$ :

$0.5 = 1-e^{-\frac{n(n-1)}{2 \times 365}}$

$0.5 = e^{-\frac{n(n-1)}{2 \times 365}}$

$ln(\frac{1}{2}) = -\frac{n(n-1)}{730}$

$n(n-1) = 730 \times ln(2)$

Now you have two ways :

1. Resolve it considering a polynomial in $n$
2. Use approximation for $n >> 1$ : $n^2 \approx n(n-1)$

Using 1 :

$n^2 - n - 730 \times ln(2) = 0$ gives two roots but we consider only the positive : $n_1 = 23$ with $\Delta = (-1)^2 - 4 \times 1 \times (-730) \times ln(2) \approx 2025$.

Finally we might say to have exactly 0.5 probalility of collision we need 23 people.

Notes :

• as stated @lulu you should try to find the minimal $n$ for a probability of at least $0.5$,
• this is an approximation, you should find a real close and inferior to 23,
• there are other methods, I recall doing it with Stirling years ago.