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$
    – Aaron Montgomery
    Commented Oct 18, 2019 at 3:21
  • $\begingroup$ Imagine this is an interview question where I am not provided any calculator. How should I proceed? $\endgroup$
    – Idonknow
    Commented Oct 18, 2019 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$
    – Aaron Montgomery
    Commented Oct 18, 2019 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$
    – Aaron Montgomery
    Commented Oct 18, 2019 at 3:29
  • $\begingroup$ @AaronMontgomery Actually I am not sure. That is why I seek help from MSE community. $\endgroup$
    – Idonknow
    Commented Oct 18, 2019 at 3:29

3 Answers 3

Reset to default
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
    Commented Oct 18, 2019 at 3:28
  • $\begingroup$ I think this is clean as the answer will possibly get. $\endgroup$
    – Aaron Montgomery
    Commented Oct 18, 2019 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
    Commented Oct 18, 2019 at 3:34
  • $\begingroup$ @saulspatz You are talking about my approach? $\endgroup$
    – Idonknow
    Commented Oct 18, 2019 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
    Commented Oct 18, 2019 at 3:39
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
    Commented Oct 18, 2019 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
    Commented Oct 18, 2019 at 14:23
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .