CSCE 411 Lecture 28

Lecture Slides

« previous | Friday, November 2, 2012 | next »

The Birthday Paradox

Suppose that there are $n$ possible birthdays (in our case, $n=365$) and $k$ people in a room. How likely is it that two of the $k$ people have the same birthday?

Assume that birthdays are uniformly and independently distributed over $N=\{1,\ldots ,n\}$.

If person $a$ has a birthday $b_{a}\in N$, then $(b_{1},\ldots ,b_{k})$ are all of the birthdays of all people in the room.

Thus the event $(b_{1},\ldots ,b_{k})$ has probability ${\tfrac {1}{n^{k}}}$

Let us calculate the probability $q$ of the event that all $k$ people have a different birthday. We are interested in the complementary event where 2 or more people share the same birthday: $p=1-q$

Suppose that $E$ is the subset of vectors in $N^{k}$ that have distinct entries.

${\begin{aligned}\left|E\right|&=n(n-1)\dots (n-k+1)=\prod _{i=0}^{k-1}(n-i)\\q&={\frac {\left|E\right|}{n^{k}}}={\frac {1}{n^{k}}}\prod _{i=0}^{k-1}(n-i)=\prod _{i=1}^{k-1}\left(1-{\frac {i}{n}}\right)\\p&=1-q=1-\prod _{i=1}^{k-1}\left({\frac {n-i}{n}}\right)\end{aligned}}$

Recall that $1+x\leq \mathrm {e} ^{x}$ holds for all real numbers. Hence

$q\leq \prod _{i=1}^{k-1}\mathrm {e} ^{-{\frac {i}{n}}}=\exp \left(-\sum _{i=1}^{k-1}{\frac {i}{n}}\right)=\exp \left(-{\frac {k(k-1)}{2n}}\right)$

Let's estimate the probability that $q\leq {\tfrac {1}{2}}$.

$q\leq \exp \left(-{\frac {k(k-1)}{2n}}\right)\leq {\frac {1}{2}}$

This is the case where

$k\geq {\frac {1}{2}}\left(1+{\sqrt {1+8n\log {2}}}\right)$

Since $k(k-1)={\tfrac {1}{4}}(8n\log {2})$

This is surprisingly often.

The Hat Game

$n$ players, each of them assigned a red or blue hat at random.

Players simultaneously guess the colors of their own hats. Passing is allowed.

At least one correct guess and no incorrect guesses leads to a WIN!

• A player gets no information about his own hat from looking at his teammates hats
• No strategy can guarantee victory

Easy strategy: 1 person guesses, everyone else passes

Better Strategy

For n = 3, if you see two different colors, say the other color. If you see two different colors, pass.

configuration	Guesses
BBB	RRR
BBR	PPR
BRB	PRP
BRR	BPP
RBB	RPP
RBR	PBP
RRB	PPB
RRR	BBB

Probability of success is now 75%

However, there were 6 correct and 6 incorrect guesses (higher concentration of incorrectness in the edge cases).