11

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.)

Community
  • 1
Paul Uszak
  • 494
  • 3
  • 17
  • 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. – Michael R. Chernick Dec 22 '16 at 01:07
  • If N<=1,000,000 then at least 1 match has probability = 1 and so 0 matches has probability=0. – Michael R. Chernick Dec 22 '16 at 01:15
  • 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. – Michael R. Chernick Dec 22 '16 at 01:23
  • 5
    @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. – whuber Dec 22 '16 at 01:42

1 Answers1

13

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$).

whuber
  • 281,159
  • 54
  • 637
  • 1,101
  • 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. – Michael R. Chernick Dec 22 '16 at 02:11
  • My question would be how large does N have to be to reach 100% confidence. I think it is something like 10^18. – Michael R. Chernick Dec 22 '16 at 02:17
  • 2
    @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. – Pere Dec 22 '16 at 11:40
  • Thanks I wasn't quite sure about that. But by 10^18 that probability is exceedingly small for a single match in the example and the confidence could be 99.999... %. I had a feeling that to get 100% for the number of days that large would make one of the computatiion close to dividing by 0 as shown in Bill Huber's equation 2. – Michael R. Chernick Dec 22 '16 at 12:59
  • @Michael With $N=10^{18}$ and $k=10^6-1$, $p(k,N)=1-4.99999\times 10^{-7}$, which is $99.99995\%$. Note that the approximations $p(k,N)\approx 1-\exp(-k^2/(2N))\approx k^2/(2N)$ are excellent for $N\gg k$. – whuber Dec 22 '16 at 15:52
  • @whuber I think the $-k^2/(2N^2)$ in the third paragraph should be $-k^2/(2N)$. I'm right? – Pere Dec 22 '16 at 16:29
  • 1
    @Pere Yes, thank you for sighting that. I'll fix it right away. It made no difference to the rest of the post. – whuber Dec 22 '16 at 19:02
  • 2
    @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. – Michael R. Chernick Dec 22 '16 at 23:28