Exercise 1.62 (Birthday problem)

Question

In the birthday problem, we assumed that all 365 days of the year are equally likely (and excluded February 29). In reality, some days are slightly more likely as birthdays than others. For example, scientists have long struggled to understand why more babies are born 9 months after a holiday. Let $\mathbf{p}=\left(p_{1}, p_{2}, \ldots, p_{365}ight)$ be the vector of birthday probabilities, with $p_{j}$ the probability of being born on the $j$ th day of the year (February 29 is still excluded, with no offense intended to Leap Dayers).
The kth elementary symmetric polynomial in the variables $x_{1}, \ldots, x_{n}$ is defined by
$$
e_{k}\left(x_{1}, \ldots, x_{n}ight)=\sum_{1 \leq j_{1}<j_{2}<\cdots<j_{k} \leq n} x_{j_{1}} \ldots x_{j_{k}}
$$
This just says to add up all of the $\left(\begin{array}{l}n \ k\end{array}ight)$ terms we can get by choosing and multiplying $k$ of the variables. For example, $e_{1}\left(x_{1}, x_{2}, x_{3}ight)=x_{1}+x_{2}+x_{3}, e_{2}\left(x_{1}, x_{2}, x_{3}ight)=x_{1} x_{2}+$ $x_{1} x_{3}+x_{2} x_{3}$, and $e_{3}\left(x_{1}, x_{2}, x_{3}ight)=x_{1} x_{2} x_{3} .$
Now let $k \geq 2$ be the number of people.
ewline
(a) Find a simple expression for the probability that there is at least one birthday match, in terms of $\mathbf{p}$ and an elementary symmetric polynomial.
ewline
(b) Explain intuitively why it makes sense that $P$ (at least one birthday match) is minimized when $p_{j}=\frac{1}{365}$ for all $j$, by considering simple and extreme cases.
ewline
(c) The famous arithmetic mean-geometric mean inequality says that for $x, y \geq 0$,
$$
\frac{x+y}{2} \geq \sqrt{x y}
$$
This inequality follows from adding $4 x y$ to both sides of $x^{2}-2 x y+y^{2}=(x-y)^{2} \geq 0$.
Define $\mathbf{r}=\left(r_{1}, \ldots, r_{365}ight)$ by $r_{1}=r_{2}=\left(p_{1}+p_{2}ight) / 2, r_{j}=p_{j}$ for $3 \leq j \leq 365 .$ Using the arithmetic mean-geometric mean bound and the fact, which you should verify, that
$$
e_{k}\left(x_{1}, \ldots, x_{n}ight)=x_{1} x_{2} e_{k-2}\left(x_{3}, \ldots, x_{n}ight)+\left(x_{1}+x_{2}ight) e_{k-1}\left(x_{3}, \ldots, x_{n}ight)+e_{k}\left(x_{3}, \ldots, x_{n}ight),
$$
show that
$P($ at least one birthday $\operatorname{mat} \operatorname{ch} \mid \mathbf{p}) \geq P($ at least one birthday match $\mid \mathbf{r})$,
with strict inequality if $\mathbf{p} 
eq \mathbf{r}$, where the "given $\mathbf{r} "$ notation means that the birthday probabilities are given by $\mathbf{r}$. Using this, show that the value of $\mathbf{p}$ that minimizes the probability of at least one birthday match is given by $p_{j}=\frac{1}{365}$ for all $j$.

fifthist x · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item $1 - k!e_{k}\left(\overrightarrow{p}ight)$

\item Consider the extreme case where $p_{1} = 1$ and $p_{i} = 0$ for $i 
eq 1$. 
Then, the probability that there is at least one birthday match is $1$. 
In general, if $p_{i} > \frac{1}{365}$ for a particular $i$, then a 
birthday match is more likely, since that particular day is more likely to be 
sampled multiple times. Thus, it makes intuitive sense that the probability of 
at least one birthday match is minimized when $p_{i} = \frac{1}{365}$.

\item First, consider $e_{k}\left(x_{1},...,x_{n}ight)$. We can break up this 
sum into the sum of three disjoint cases.
  \begin{enumerate}
    \item Sum of terms that contain both $x_{1}$ and $x_{2}$. This sum is given 
    by $x_{1}x_{2}e_{k-2}\left(x_{3},...,x_{n}ight)$

\item Sum of terms that contain either $x_{1}$ or $x_{2}$ but not both. 
    This sum is given by $\left(x_{1} + x_{2}ight)e_{k-1}\left(x_{3},...,x_{n}ight)$

\item Sum of terms that don't contain either $x_{1}$ or $x_{2}$. This sum 
    is give by $e_{k}\left(x_{3},...,x_{n}ight)$
  \end{enumerate}

Thus,

$$e_{k}(x_{1},...,x_{n}) = x_{1}x_{2}e_{k-2}(x_{3},...,x_{n}) + (x_{1} + 
  x_{2})e_{k-1}(x_{3},...,x_{n}) + e_{k}(x_{3},...,x_{n})$$

Next, compare $e_{k}\left(\overrightarrow{p}ight)$ and 
  $e_{k}\left(\overrightarrow{r}ight)$. Expanding the elementary symmetric 
  polynomials, it is easy to see that the only difference between the two are 
  the terms that contain either the first, the second or both terms from 
  $\overrightarrow{p}$ and $\overrightarrow{r}$ respectively.

Notice that because $r_{1} = r_{2} = \frac{p_{1} + p_{2}}{2}$, the sum of the 
  terms with only $r_{1}$ and only $r_{2}$ but not both is exactly equal to 
  $(p_{1} + p_{2})e_{k-1}(x_{3},...,x_{n})$. Thus, the only difference between 
  $e_{k}\left(\overrightarrow{p}ight)$ and $e_{k}\left(\overrightarrow{r}ight)$ 
  are the terms $p_{1}p_{2}e_{k-2}(x_{3},...,x_{n})$ and 
  $r_{1}r_{2}e_{k-2}(x_{3},...,x_{n})$.

By the arithmetic geometric mean inequailty, 
  $r_{1}r_{2}e_{k-2}(x_{3},...,x_{n}) \geq p_{1}p_{2}e_{k-2}(x_{3},...,x_{n})$. 
  Hence, $1 - k!e_{k}(\overrightarrow{p}) \geq 1 - k!e_{k}(\overrightarrow{r})$.

In other words, given birthday probabilities $\overrightarrow{p}$, we can 
  potentially reduce the probability of having at least one birthday match by 
  taking any two birthday probabilities and replacing them with their average. 
  For a minimal probability of at least one birthday match then, all  values 
  $p_{i}$ in $\overrightarrow{p}$ must be equal, so that averaging any $p_{i}$ 
  and $p_{j}$ does not change anything.

\end{enumerate}

Exercise 1.62 (Birthday problem)

Answers

Comments

Exercise 1.62 (Birthday problem)

Answers

Comments

Add answer