1
$\begingroup$

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[365] = 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[0]))
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

Comments:

1, I notice that I am exactly 1 of the required answer for the expectation. Also, I notice that the u[1] 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[0] to u[366]. Any ideas?

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

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Minus One-Twelfth
    Mar 1, 2019 at 14:38
  • $\begingroup$ Are you sure the SD isn't $12.19$? (Or even closer to $12.1918122028037979705912451563\ldots$.) $\endgroup$
    – whuber ♦
    Mar 1, 2019 at 17:24
  • $\begingroup$ @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: $\endgroup$
    – user11128
    Mar 3, 2019 at 2:18
  • $\begingroup$ To format properly I put my attempted code in the original answer. $\endgroup$
    – user11128
    Mar 3, 2019 at 2:23
  • 2
    $\begingroup$ The standard deviation of the u array is not going to give you the standard deviation of the random variable in question. $\endgroup$
    – Minus One-Twelfth
    Mar 3, 2019 at 2:28

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.