# Variation on the Birthday Problem

You ask an audience one by one for their birthdays. How many people do you need to ask on average until you get your first overlap?

This sounded to me quite similar to a geometric distribution in terms of number of trials until first success, with the exception that we are sampling without replacement. I googled what the analogue of geometric distribution is for not replacing and came across the negative hyoergeometric distribution. We would presumably want its expectation but I'm not sure how to fit it to my problem or if this is even the right lines to be pursuing.

Answer should be 23.62 with standard deviation 12.91

Edit: on reflection I'm doubting the negative hypergeometric idea even more since whilst I could consider drawing $$n$$ balls (people) of which $$N=1$$ are of the right colour (same birthday) and $$M=n-1$$ are of the wrong colour (different birthday), I can't see how to fit 365 into the problem?

Code attempt (Python):

import numpy as np

u = np.zeros(366)
u = 1
print(u)
for i in range(364,-1,-1):
u[i] = 1 + (1 - i/365)*u[i+1]
print(i, u)
print("Expected number of questions: {}".format(u))
print("Array length: {}".format(len(u)))
print("Standard deviation: {}".format(np.std(u)))


Ouput: Expected number of questions: 24.61658589

Array length: 366

Standard deviation: 4.17342901622

1, I notice that I am exactly 1 of the required answer for the expectation. Also, I notice that the u entry in my array is the desired answer. However, I think I am right in having an array of length 366 since we should be going from u to u. Any ideas?

2, I have no idea what is going wrong with the standard deviation???

• Let $u_k$ be the expected number of additional people you have to ask if you have already asked $k$ people and not received a match yet (you are effectively interested in finding $u_0$, or equivalently $1+u_1$; note that $u_{365}=1$). The expected total number of people you must ask is $u_0$, or equivalently $1+u_1$. Now, note that for any $0\le k \le 364$, we have $u_{k} =1 + \left(1-\frac{k}{365}\right)u_{k+1}$. (Can you explain why?) You could use this to compute backwards (using a computer) $u_k$ in terms $u_{k+1}$, starting from $u_{365} = 1$, to get the value of $u_0$. Mar 1, 2019 at 14:38
• Are you sure the SD isn't $12.19$? (Or even closer to $12.1918122028037979705912451563\ldots$.)
– whuber
Mar 1, 2019 at 17:24
• @MinusOne-Twelfth my reasoning: between going from $u_{k+1}$ and $u_k$, we have to actually ask a question hence the "1+". However, we can't just model by $u_k=1+u_{k+1}$ since this would be answering the question "how many people do you need to ask until you've asked 365 people"! Instead we actually learn something after each question and so $\frac{365-k}{365}$ is the probability of not getting a match i.e. of having to ask that additional question. Does that sound right? I'll put my code below: Mar 3, 2019 at 2:18
• To format properly I put my attempted code in the original answer. Mar 3, 2019 at 2:23
• The standard deviation of the u array is not going to give you the standard deviation of the random variable in question. Mar 3, 2019 at 2:28

I would approach this in the other direction, and let $$p(i)$$ be the probability the first match is with the $$i$$th person and $$q(i)$$ the probability you do not have a match after $$i$$ people. Then you can say

• $$p(0)=0$$ and $$q(0)=1$$
• $$p(n+1)=\frac{n}{365}q(n)$$ and $$q(n+1)=q(n)-p(n+1)$$

There are other choices producing the same result such as

• $$p(1)=0$$ and $$p(2)=\frac{1}{365}$$
• $$p(n+1) =\frac{(366-n)n}{365(n-1)}p(n)$$ for $$n\ge2$$

You end up with $$p(367)=0$$ and $$p(366)=\frac{365!}{365^{365}}$$ - and I suspect your calculation may have ignored this very small number for $$p(366)$$.

The mean is then $$\sum\limits_{n=1}^{366} n\, p(n) \approx 24.61659$$ close to what you found and the standard deviation is $$\sqrt{\sum\limits_{n=1}^{366} n^2\, p(n) -\left(\sum\limits_{n=1}^{366} n\, p(n)\right)^2 } \approx 12.19181$$ as whuber found.