Birthday problem among k people

Question

Consider a group of $n$ people. Assume that each person's birthday is drawn uniformly at random from the $365$ possibilities. What is the smallest value of such that the expected number of pairs of distinct people with the same birthday is at least one?.

My approach using indicator random variable:

$X_{\bf i, j, i \neq j} = \begin{cases} &1 \qquad \text{ if ith and jth person having same birthday} \\ &0 \qquad \text{ if ith and jth person NOT having same birthday } \ \end{cases} \\\\$

$ \begin{align*} & E(X_{i,j}) = 1*P(X_{i,j}) + 0*\left ( 1 - P(X_{i,j}) \right ) \\ & \Rightarrow E(X_{i,j}) = P(X_{i,j}) \\ & \Rightarrow \text{Overall E} = \sum E_{i,j} \\ \\ \hline \\ &\text{ We need } E \geq 1 \\ &\Rightarrow \left [ \sum_{i=1}^{k}\sum_{j=i+1}^{k}E_{i,j} \right ] \geq 1 \\ &\Rightarrow \left [ \sum_{i=1}^{k}\sum_{j=i+1}^{k}P_{i,j} \right ] \geq 1 \\ &\Rightarrow \left [ \sum_{i=1}^{k}\sum_{j=i+1}^{k}\left ( \frac{1}{365} \right ) \right ] \geq 1 \\ &\Rightarrow \left ( \frac{1}{365} \right ) \left [ \sum_{i=1}^{k}\sum_{j=i+1}^{k}1 \right ] \geq 1 \\ & \Rightarrow \left ( \frac{1}{365} \right )\left [ \sum_{i=1}^{k-1}1 \right ] \geq 1\\ & \Rightarrow \left ( \frac{1}{365} \right )\left [ \frac{k.(k-1)}{2} \right ] \geq 1\\ & \Rightarrow k^2 - k - 730 \geq 0\\ & \Rightarrow k = \left \lceil \frac{1+ \sqrt{1+4*730}}{2} \right \rceil = \left \lceil 27.52 \right \rceil = 28 \\ \\ \end{align*}$

I hope there may be other ways to do this problem and there are other variations to this problem as well (a few are in Kenneth Rosen Book). Please help if there exist other methods.

Thanks!

Answer 1

I will leave you to judge whether this is the same answer as yours:

• With $d=365$ days, the probability a particular pair share a birthday is $\frac1{d}$

• With $n$ people, there are ${n \choose 2}= \frac{n(n-1)}{2}$ pairs of people so the expected number of pairs sharing a birthday is $\frac{n^2-n}{2d}$

• This is greater than $1$ when $n > \frac{1 +\sqrt{1+8d}}{2}$ or $n < \frac{1 -\sqrt{1+8d}}{2}$, though for this question the answer should be positive so $k \gt 27.523\ldots$ and an integer

Note that you might get a slightly different answer if your question was looking for the expected number of days to be shared to be at least $1$:

• The probability a particular day is shared is $1-\frac{(d-1)^n}{d^n} - n\frac{(d-1)^{n-1}}{d^n} $

• The expected number of shared days is $d-(n+d-1)\left(1-\frac{1}{d}\right)^{n-1}$

For the same $k$ and $d$ this expected number is slightly smaller than the earlier expression, as three people and so three pairs might share a single day.

It is also harder to treat analytically, but here it will be greater than $1$ when $k \gt 28.175\ldots$, not surprisingly marginally more than the original version of the question