11
$\begingroup$

Assume a planet with a very very long year of $N$ days. There are 1 million aliens at a party in a room, and no one at all shares a birthday. What can be inferred about the size of $N$?

(This more compact question supersedes this poorly phrased one.)

$\endgroup$
  • $\begingroup$ The birthday problem tells you the value of N where the probability of at least one match is greater than a specified value. When p=1/2 it is surprising to intuition that this gives n=23.. This assumes that each birthday has the same uniform probability (1/365). Nonuniformity only makes n smaller. Now in your problem it seems that N replace 365 and I assume the uniformity assumption is maintained. $\endgroup$ – Michael Chernick Dec 22 '16 at 1:07
  • $\begingroup$ If N<=1,000,000 then at least 1 match has probability = 1 and so 0 matches has probability=0. $\endgroup$ – Michael Chernick Dec 22 '16 at 1:15
  • $\begingroup$ So when N>1,000,000 the probability of at least 1 match has probability <1 and hence the probability of zero matches starts increasing. $\endgroup$ – Michael Chernick Dec 22 '16 at 1:23
  • 5
    $\begingroup$ @Michael Please reserve comments for requests for clarification and other incidental discussions, and try to post just one at a time: there is good reason for the character limit. If you find yourself discussing something substantial that requires multiple comments, you're probably trying to answer the question, so you might as well post an answer. $\endgroup$ – whuber Dec 22 '16 at 1:42
13
$\begingroup$

Assuming all birthdays are equally likely and the birthdays are independent, the chance that $k+1$ aliens do not share a birthday is

$$p(k;N) = 1\left(1-\frac{1}{N}\right)\left(1-\frac{2}{N}\right)\cdots\left(1-\frac{k}{N}\right).$$

Its logarithm can be summed asymptotically provided $k$ is much smaller than $N$:

$$\log(p(k;N)) = -\frac{k(k+1)}{2N} - \frac{k + 3k^2 + 2k^3}{12N^2} - O(k^4 N^{-3}).\tag{1}$$

To be $100-100\alpha\%$ confident that $N$ is no less than some value $N^{*}$, we need $(1)$ to be greater than $\log(1-\alpha)$. Small $\alpha$ ensure $N$ is much larger than $k$, whence we may approximate $(1)$ accurately as $-k^2/(2N)$. This yields

$$-\frac{k^2}{2N} \gt \log(1-\alpha),$$

implying

$$N \gt\frac{-k^2}{2\log(1-\alpha)} \approx \frac{k^2}{2\alpha}=N^{*}\tag{2}$$

for small $\alpha$.

For instance, with $k=10^6-1$ as in the question and $\alpha=0.05$ (a conventional value corresponding to $95\%$ confidence), $(2)$ gives $N \gt 10^{13}$.

Here's a more expansive interpretation of this result. Without approximating in formula $(2)$, we obtain $N=9.74786\times 10^{12}$. For this $N$ the chance of no collision in a million birthdays is $p(10^6-1, 9.74786\times 10^{12})=95.0000\ldots\%$ (computed without approximation), essentially equal to our threshold of $95\%$. Thus for any $N$ this large or larger it's $95\%$ or more likely there will be no collisions, which is consistent with what we know, but for any smaller $N$ the chance of a collision gets above $100 - 95= 5\%$, which starts to make us fear we might have underestimated $N$.

As another example, in the traditional Birthday problem there is a $4\%$ chance of no collision in $k=6$ people and $5.6\%$ chance of no collision in $k=7$ people. These numbers suggest $N$ ought to exceed $360$ and $490$, respectively, right in the range of the correct value of $366$. This shows how accurate these approximate, asymptotic results can be even for very small $k$ (provided we stick to small $\alpha$).

$\endgroup$
  • $\begingroup$ I wasn't prepared to give an answer like this. With numbers this large approximations might be easier to compute. Wikipedia gives the generalized birthday problem showing approximations and bounds on N with k people (aliens). I had the same formula as your first equation. $\endgroup$ – Michael Chernick Dec 22 '16 at 2:11
  • $\begingroup$ My question would be how large does N have to be to reach 100% confidence. I think it is something like 10^18. $\endgroup$ – Michael Chernick Dec 22 '16 at 2:17
  • 1
    $\begingroup$ @MichaelChernick For 100% confidence N goes to infinite. For any finite year and for any party with 2 or more aliens, the probability of two aliens with the same birthday is always greater than 0. $\endgroup$ – Pere Dec 22 '16 at 11:40
  • 1
    $\begingroup$ @Pere Yes, thank you for sighting that. I'll fix it right away. It made no difference to the rest of the post. $\endgroup$ – whuber Dec 22 '16 at 19:02
  • 2
    $\begingroup$ @Paul Uszak I think your comment about Pere's answer (now deleted) was much too harsh. I think his answer was given in good faith. He was trying to be helpful to you by providing useful approximations. He later saw whuber's answer and decided that it was more complete and agreed to delete his answer. His comment about not expecting a detailed answer was not meant the way you interpreted it. This is a difficult problem. You even had to rewrite the post to make it understandable. I am sure he does not take solving a problem like this as a joke. $\endgroup$ – Michael Chernick Dec 22 '16 at 23:28

protected by kjetil b halvorsen Mar 25 '18 at 13:06

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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