# The Birthday Paradox – Proof

### “In a room of just 23 people there’s a 50% chance of two people having the same birthday.”

Short Version or the Long Version and if you prefer video then Birthday Paradox – Youtube

Following below I present the simplest possible proof of the same with least amount of clutter and redundancy.

Credit of this proof goes to Prof. Dan Boneh. I love how simple it is. My LaTeX skills are still nascent so please bear with me. Do notify in case of inaccuracies.

## Theorem:

Notations used:
n = number of people
r = birthday of a given individual
Pr= Probability
B= number of days in a year (not incl. feb 29th)
given,
n = 23, which can be rewritten as — $n=1.2*B^{\frac{1}{2}}$  (Since $B=365\Rightarrow n=1.2*B^{\frac{1}{2}}\approx23$)

let * $r_{1}\cdots r_{n}\epsilon$ *{1…B} be IID integers

## Proof: $\Pr[\exists i\neq j:r_{i}=r_{j}]$ $=1-Pr[\forall i\neq j:r_{i}\neq r_{j}]$ $=1-\frac{(B-1)}{B}\frac{(B-2)}{B}\cdots\frac{(B-n+1)}{B}$ $=1-\prod_ {i=1}^{n-1}(1-\frac{i}{B})$ $wkt,\forall x\geq0,1-x\leq e^{-x}$ $=1-\prod_ {i=1}^{n-1}e^{\frac{-i}{B}}$ $=1-e^{-\frac{1}{B}\sum\limits _{i=1}^{n-1}i}$ $=1-e^{-\frac{1}{B}\frac{n(n-1)}{2}}$ $\geq1-e^{-\frac{n^{2}}{2B}}$ $\geq1-e^{-0.72}$ (since $n=1.2B^{\frac{1}{2}}\Rightarrow\frac{n^{2}}{2}=0.72B\Rightarrow\frac{n^{2}}{2B}=0.72)$ $\geq0.513$

QED