Homework 5

1. A group of $n \ge 4$ people are comparing their birthdays (as usual, assume their birthdays are independent, are not February 29, etc.).

   (a) Let $I_{ij}$ be the indicator r.v. of $i$ and $j$ having the same birthday (for $i \lt j$). Is $I_{12}$ independent of $I_{34}$? Are the $I_{ij}$'s independent?

   (b) Explain why the Poisson Paradigm is applicable here even for moderate $n$, and use it to get a good approximation to the probability of at least 1 match when $n=23$.

   (c) About how many people are needed so that there is a 50% chance (or better) that two either have the same birthday or are only 1 day apart? (Note that this is much harder than the birthday problem to do exactly, but the Poisson Paradigm makes it possible to get fairly accurate approximations quickly.)

Solution

1 (a)

$I_{12}$ is independent of $I_{34}$, since knowing that persons 1 and 2 having the same birthday provides absolutely no information about persons 3 and 4.

However, $I_{ij}$ are not entirely independent, as knowing that $I_{12}$ and $I_{23}$ does tell us that person 1 and 3 must have the same birthday.

1 (b)

Checklist for the applying the Poisson Paradigm:

1. events $I_{ij}$ where $i \lt j$, $P(I_{ij}) = \frac{1}{365}$
2. large number of trials $\binom{n}{2}$; when $n=23$, $\binom{23}{2} = 253$
3. small $p = \frac{1}{365}$

As the events $I_{ij}$ are weakly independent, we can approximate this r.v. with a Poisson distribution.

Let $X \sim Pois(\mu)$.

\begin{align} \mu &= \binom{n}{2} ~ p \\ &= \frac{n(n-1)}{2} ~ \frac{1}{365} \\ &= \frac{n(n-1)}{730} \\ &\approx 0.693 & \quad \text{when } n = 23 \\\\ \therefore P(X \ge 1) &= 1 - P(X = 0) \\ &= 1 - e^{-0.693} ~ \frac{0.693^0}{0!} \\ &= 1 - e^{-0.693} \\ &\approx 0.500 \end{align}

1 (c)

We are interested in the case where $I_{ij}$ is where 2 people have the same birthday, or 1 day apart.

This means that $I_{ij} = 1$, and so $P(I_{ij}=1) = \frac{3}{365}$.

We can approximate this with $Pois(\mu = \frac{n(n-1)}{2} ~ \frac{3}{365})$, and so $\mu = \frac{3n(n-1)}{730}$.

\begin{align} P(X \ge 1) &= 1 - P(X=0) \\ &= 1 - e^{-\frac{3n(n-1)}{730}} ~ \frac{\left(\frac{3n(n-1)}{730}\right)^0}{0!} \\ &= 1 - e^{\frac{-3n^2+3n}{730}} \\\\ 1 - e^{\frac{-3n^2+3n}{730}} &= \frac{1}{2} \\ \frac{-3n^2+3n}{730} &= log\left(\frac{1}{2}\right) \\ &= - log ~ 2 \\ 3n^2 -3n - 730 ~ log ~ 2 &= 0 \end{align}

---