1.6.6 problem 62

(a)

$1-k!e_k\left({p\to }^{}\right)$

(b)

Consider the extreme case where $p_1=1$ and $p_i=0$ for $i\ne 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}$.

(c)

First, consider $e_k\left(x_1,...,x_n\right)$. We can break up this sum into the sum of three disjoint cases.

(a)

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\right)$

(b)

Sum of terms that contain either $x_1$ or $x_2$ but not both. This sum is given by $\left(x_1+x_2\right)e_{k-1}\left(x_3,...,x_n\right)$

(c)

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\right)$

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({p\to }^{}\right)$ and $e_k\left({r\to }^{}\right)$. 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 ${p\to }^{}$ and ${r\to }^{}$ 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({p\to }^{}\right)$ and $e_k\left({r\to }^{}\right)$ 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)\ge p_1{p}_2{e}_{k-2}(x_3,...,x_n)$. Hence, $1-k!e_k\left({p\to }^{}\right)\ge 1-k!e_k\left({r\to }^{}\right)$.

In other words, given birthday probabilities ${p\to }^{}$, 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 ${p\to }^{}$ must be equal, so that averaging any $p_i$ and $p_j$ does not change anything.