The Birthday Paradox – Proof

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

Above statement is briefly The Birthday Paradox. If you need more information kindly see
Short Version or the Long Version and if you prefer video then Birthday Paradox – Youtube

This article is about the Proof of the same and not the explanation.The proof of this seemingly counter intuitive result has always baffled me.

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

$Pr[\exists i\neq j:r_{i}=r_{j}]\geq\frac{1}{2}$

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

You may download the tex file here.

Written on July 21, 2012