2
$\begingroup$

First off, I'm not a mathematician, so if I'm going about this in the wrong way, please let me know.

The problem

I have ~4.1 million timestamps (with second accuracy) when people logged into a website. They were collected over a period of ~50.5 million seconds. Some of these records are erroneous (one says that 7044 people logged in at the same second). Assuming an even distribution of logins, find n where the probability of n people logging in simultaneously < 50%

Current approach

This seems like the birthday problem could be adapted here. Given a "year" of 50.5M days, and 4.1M people the chance that two people will not share a birthday is negligible.

I found this post with a formula for triplets (three simultaneous birthdays), but is there a way to generalize it for n simultaneous birthdays? I'm guessing it's not as simple as changing the 3 in the equation to an n.

$\endgroup$
1
$\begingroup$

Suppose you had $N$ possible birthdays and $M$ people (with birthdays chosen independently and uniformly). The probability of $k$ people sharing a birthday seems difficult to calculate, but much easier is the expected number of (unordered) $k$-tuples sharing a birthday. Namely, there are ${M \choose k}$ possible $k$-tuples, the probability that a particular $k$-tuple share the same birthday is $N^{1-k}$, so the expected number is ${M \choose k} N^{1-k}$. The expected number of $k$-tuples is an upper bound on the probability of existence of such a $k$-tuple.

If $M$ is very large, ${M \choose k} \approx M^k /k!$ so the expected number of $k$-tuples is approximately $M^k N^{1-k}/k!$. Thus in your case with $M = 4.1 \times 10^6$, $N = 5.05 \times 10^7$ and $k = 7044$, the expected number is ridiculously small, about $9.5 \times 10^{-31722}$. Even with $k = 6$, the expected number is about $0.020$. On the other hand, for $k = 5$ the expected number is about $1.484$. So it seems likely that the maximum number of people sharing a birthday is $5$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's great, exactly what I was looking for. Thanks so much! $\endgroup$ – NoahL Jun 23 '17 at 16:08

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.