# 12 - Birthday Paradox, Euler approximation, Big box problem

## Birthday Paradox
If we have some room with 23 people, what is the probability that some pair of people share the same birthday

There are $d=365$ days in a year
There are $n=23$ people
Equally likely that any given person has a birthday on any given day

$S = \{(b_1, b_2,..., b_n): b_1,...,b_n \in \{1,2,3,...,d\}\}$
$|S| = d^n$

$Pr(w) = \frac{1}{|S|} = \frac{1}{d^n}$ For each individual outcome in the set $S$

$E_n = \text{There are two people with the same birthday}$
$E_n = \text{There exist} i,j \in \{1,...,n\}, i\neq j \text{ and } b_i=b_j$

$Pr(E_n)$

**Exercise 1**
What if $n>d$
If the number of people are more than the number of days in a year, than by the pigeon hole principle, two people must have the same birthday.

$Pr(E_n) = 1$

**Exercise 2**
We assume that $n = 2$

$Pr(E_2) = \frac{E_2}{|S|} = \frac{d}{d^2} = \frac{1}{d}$

$E_2 = \{(1,1), (2,2), (3,3), ..., (d, d)\}$, $|E| = d$

**Back to solving for n**

$Pr(E_n) = \frac{|E_n|}{|S|} = \frac{|E_n|}{d^n}$

Solve for $E_n$ using the compliment rule
$\bar{E_n} = \text{Everyone has a different birthday} = \text{There is no pair } i, j \in \{1,...,n\}, i\neq j, b_i = b_j$
$|\bar{E_n}| = d \times d-1 \times d-2 \times ... \times d-n + 1$ Pick one day to start, then any day except that one etc

$Pr(E_n) = 1 - \bar{(E_n)} = 1 - \frac{|\bar{E_n}|}{d^n} =1 - \frac{d(d-1)...(d-n+1)}{d^n} = 1- \frac{d!}{(d-n)!d^n}$

When $d=365$
$Pr(E_{23}) \approx 0.507$
$Pr(E_{22}) \approx 0.476$

As an explanation, there are $\binom{23}{2} = 253$ pairs of people. With so many pairs, it gives a decent intution as to why those numbers are so big.

## Euler identity approximation
$1-x \leq e^{-x}$ for any real number $x$

$Pr(\bar{E_n}) = \frac{d(d-1)(d-2)(d-3)...(d-n+1)}{d^n} = \frac{d}{d} \times \frac{d-1}{d} \times ... \times \frac{d-n+1}{d}$
$=1\times (1-\frac{1}{d}) \times ... \times (1-\frac{n-1}{d})$
$\approx e^0 \times e^{\frac{-1}{d}} \times ... \times e^{\frac{n-1}{d}}$
$\approx e^{-(\frac{1}{d} + \frac{2}{d} + ... + \frac{n-1}{d})}$
$\approx e^{\frac{1}{d}(1+2+...+n-1)} \approx e^{-\frac{1}{d}\frac{n(n-1)}{2}}$

Note: $\frac{n(n-1)}{2} = \binom{n}{2} = \text{The number of pairs of people}$

## Big box problem
- There are two piles of money with $x and $y $x < y, x, y \in \{1,2,3,...,100\}$ You don't know x nor y
- There are two boxes and place $x$ dollars under one box and $y$ dollars under another, you don't know which is which
- You look under one of the boxes of your choosing and observe some number of money $a$
- You have to decide whether to keep that, or keep what's under the other box
- The way this game is "won" is if you leave with $y$ dollars

The game can be won 50% of the time if you pick a box and stick with it. 50% of the time you will choose correctly

**Better strategy**

1. Pick a uniformly random number $z \in \{0.5, 1.5, 2.5, ... 99.5\}$
2. Pick a random box and look under it and see $$a$
3. If $a < z$ then take the other box, otherwise keep the box

What is the sample space for this?
$S = \{(x,y,z),(y,x,z)\}$
$S = \{(x,y,0.5),(x,y,1.5)... (x,y,99.5) ,(y,x,0.5), (y,x,1.5),..., (y,x,99.5)\}$

$Pr(w) = \frac{1}{|S|} = \frac{1}{200}$

First item in each triple is the first box you chose, you want to choose y

$W = \text{You leave with y dollars}$
$Pr(w) = \frac{|W|}{|S|}$

Define two sets
$W_a = \text{You keep the first box}$
$W_b = \text{You switch boxes}$

$W_a \cap W_b = \emptyset$

$|W| = |W_a| + |W_b|$ (The sum rule)

$Pr(w)=\frac{|W_a|}{200} + \frac{|W_b|}{200}$

For $W_a$ The number of values of z that are smaller than y is y

For $W_b$, these are the scenarios where we pick a box and the cash under the box is greater than or equal to $z$

For $W_b$, these are the scenarios where we pick a box and the cash

$Pr(w) = \frac{y}{200} + \frac{100-x}{200} = \frac{1}{2} + \frac{y}{200} + \frac{-x}{200} = \frac{1}{2} + \frac{y-x}{200}\geq \frac{1}{2} + \frac{1}{200}$

###### tags: `COMP2804` `Probability`