0
$\begingroup$

The following question is taken from an interview book assuming that no calculator is provided.

Question: There are $25$ people at a party. One person asks everybody to annouycne their birthday, and for anyone who has the same birthday as someone to raise a hand. How many hands do you expect to see raised? For example, if John, Jon, Stephen and Mark all have the same birthday, January $15$, but nobody else at the aprty has a matching birthday, the count of hands is four.

My attempt:

Let $X$ be the number of hands raised. Then for every $2\leq x\leq 25,$ we have $$P(X=x) = \frac{\binom{25}{x}}{365^{x-1}}.$$ It follows that $$E(X) = \sum_{x=2}^{25}xP(X=x) = \sum_{x=2}^{25}x\frac{\binom{25}{x}}{365^{x-1}}.$$ I have no idea how to compute the series in closed form.

Answer given in the book is $1.59$.

EDITED: from wolfram alpha, my sum is $1.697$, which is different from the answer given.

It would be good if someone can point out flaw in my sum.

$\endgroup$
8
  • $\begingroup$ It's a finite series, so the punch line will eventually be to use a calculator, right? Why not just do that here? $\endgroup$ Oct 18 '19 at 3:21
  • $\begingroup$ Imagine this is an interview question where I am not provided any calculator. How should I proceed? $\endgroup$
    – Idonknow
    Oct 18 '19 at 3:24
  • $\begingroup$ Is it clear that such a method should exist? It very well may, though I don't see it immediately. But do you have a reason to believe this should be doable for this problem? $\endgroup$ Oct 18 '19 at 3:28
  • $\begingroup$ I suppose to get a good estimate, you can discard all but the first 2 or 3 terms, since they'll be tiny. $\endgroup$ Oct 18 '19 at 3:29
  • $\begingroup$ @AaronMontgomery Actually I am not sure. That is why I seek help from MSE community. $\endgroup$
    – Idonknow
    Oct 18 '19 at 3:29
3
$\begingroup$

The probability that a given person raises his hand is the probability that someone else at the party has the same birthday as he does: $$1-\left({364\over365}\right)^{24}$$ The expected number of hands raised is $$25-25\left({364\over365}\right)^{24}\approx1.593,$$ by linearity of expectation.

$\endgroup$
6
  • $\begingroup$ This is actually how the book solves it too. But I am wondering whether my approach is correct... $\endgroup$
    – Idonknow
    Oct 18 '19 at 3:28
  • $\begingroup$ I think this is clean as the answer will possibly get. $\endgroup$ Oct 18 '19 at 3:32
  • 1
    $\begingroup$ @Idonknow It doesn't look right to me. For one thing, when you look at the probability that $4$ people raise their hands, you only seem to be considering that they all have the same birthday, not that there are two pairs of people with the same birthday. $\endgroup$
    – saulspatz
    Oct 18 '19 at 3:34
  • $\begingroup$ @saulspatz You are talking about my approach? $\endgroup$
    – Idonknow
    Oct 18 '19 at 3:37
  • $\begingroup$ Since $24 \ll 365$, a simpler approximation would be $P(\text{raise hand}) = 24/365$ which gives the expected number as $25 \times 24 / 365 \approx 25 \times 24 / 360 = 25 \times 2 / 30 = 5/3 = 1.67$ $\endgroup$
    – antkam
    Oct 18 '19 at 3:39
1
$\begingroup$

In one of the comments you ask how to approximate this when this is given as an interview question and you don't have your calculator. Well, the birthday problem is well-known, and it is indeed well known that with 23 people the chance of there being two people sharing a birthday is about $50$%. So, with 25 people here should be a chance of a little over $50$% that two or more people share a birthday, meaning that the expected number of hands is defintely above $1$. On the other hand, the probability of there being three or more is a good bit lower. So, eyeballing that, you'd end up with something above $1$ though still well below $2$. Personally I would have guessed in the $1.2$ or $1.3$ neighborhood, so I am a bit surprised it's close to $1.6$, but I bet my answer would've satisfied the interviewer. :)

$\endgroup$
1
$\begingroup$

Apparently the flaw in your formula is that while estimating the probability of a group of $x$ people with the same birthday, you neglect to account for the fact that in order for the size of the group to be exactly $x,$ nobody else among the $25$ people can have the same birthday as these $x$ people. The probability that nobody else has the same birthday is $\left(\frac{364}{365}\right)^{25-x},$ so a more accurate sum is

$$E(X) = \sum_{x=2}^{25}x\frac{\binom{25}{x}364^{25-x}}{365^{24}}.$$

What was surprising to me is that according to Wolfram Alpha, this gives exactly the correct answer: https://www.wolframalpha.com/input/?i=sum+x+%2825+choose+x%29364%5E%2825-x%29%2F365%5E24+for+x+%3D+2+to+25

The reason this is surprising is that one would think you have to account for cases where there is a group of $3$ and a group of $2,$ or three groups of $2,$ and so forth. But I think the derivation of this summand is not literally $xP(X=x),$ but $xE(\text{number of cliques of size $x$}),$ where \begin{multline}E(\text{number of cliques of size $x$}) =\\ (\text{number of subsets of size $x$})P(\text{a given subset of size $x$ is a clique}) \end{multline} where a "clique" is a subset who all have the same birthday which they do not share with anyone else.


To evaluate that sum (i.e., the correct one) without a calculator, I think the easiest method is to convert it back to the original problem and then observe that that problem is solved by evaluating $$25\left(1 - \left(\frac{364}{365}\right)^{24}\right),$$ so you now have a much simpler calculation. As a first approximation, $$\left(\frac{364}{365}\right)^{24} = \left(\frac{365-1}{365}\right)^{24} \approx \frac{365-24}{365} = 1 - \frac{24}{365}. $$ Then since $\frac{24}{365} \approx \frac{24}{360} = \frac1{15},$ we're looking for something slightly less than $\frac1{15} = 0.0666\ldots.$ The number we want is at least $1\%$ smaller but not $2\%$ smaller. So let's say it's $0.066$ to keep the number of significant digits small. So now we have $$ 25(1 - (1 - 0.066)) = 25(0.066) = 0.165. $$ This is a little high. The fault is mainly in the first approximation.

$\endgroup$
2
  • $\begingroup$ Wow, nice! In this case, how should I define the random variable that will answer the question? I suppose that my random variable defined in my post is incorrect? $\endgroup$
    – Idonknow
    Oct 18 '19 at 14:20
  • $\begingroup$ I once wrote a Java applet to calculate $P(X=x).$ It's quite computationally intensive, not the sort of thing you would ever want to do by hand. $\endgroup$
    – David K
    Oct 18 '19 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.