CSCE 411 Lecture 28

Lecture Slides

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

The Birthday Paradox

Suppose that there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} possible birthdays (in our case, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} is the subset of vectors in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N^k} that have distinct entries.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \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{align}}

Recall that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1+x \le \mathrm{e}^x} holds for all real numbers. Hence

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q \le \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q \le \tfrac{1}{2}} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q \le \exp \left( -\frac{k(k-1)}{2n} \right) \le \frac{1}{2}}

This is the case where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \ge \frac{1}{2} \left( 1 + \sqrt{1 + 8n\log{2}} \right)}

Since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k(k-1) = \tfrac{1}{4} (8n \log{2})}

This is surprisingly often.

The Hat Game

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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).