I've got a server in which about 100 times per day a specific event happens. We now wanted to number those events using the unix time in milliseconds (the number of milliseconds that have passed since 1970-01-01). A colleague of mine said that would cause overlaps if events happen in the same millisecond, but I thought the chance of overlapping would not be very high. We can't figure out how to calculate the chance of overlap though. This is our reasoning so far:
- every 24 hours has
24 hours * 60 minutes * 60 seconds * 1000 milliseconds= 86,400,000 possible numbers. - if one event has happened the chance of the second one overlapping is
1/86,400,000. - the chance of the third event overlapping is
2/86,400,000.
And here is where we're stuck; I don't think we can simply add the first chance 1/86,400,000 to the second chance of 2/86,400,000, because that would mean repeating this pattern could lead to a chance of more than 100% with less than 86,400,000 events per day. For example. Let's say that the event has happend 43,200,000 times already (half the number of milliseconds) and we still have no overlap. Another one happening would have a chance of 50%. But that is also false, because if it already happened so many times, and the still haven't overlapped, they are all in the past and only the last one could have happened in the same millisecond.
As you can see we're math's noobs and we're totally stuck. Could anybody help us out calculating the chance of two events happening in the same millisecond if we have 100 randomly timed events per day?
And further; what is the chance of two events happening in the same millisecond calculated over a full year?
Best Answer
This is essentially the classical Birthday Problem, which asks for a number $n$ of people with uniformly distributed birthdays the probability that at least two share a birthday (in an annual calendar of $d$ days). In this problem, the people are replaced by events ($n_0 = 100$) and the days are replaced by the millisecond intervals ($d_0 = 8.64 \cdot 10^7$).
The probability of an overlapping event (common birthday) on any given day is $$P(n, d) = \frac{d!}{d^n (n - d)!} ,$$ and in the regime $n \ll d$ (which certainly applies for our $n_0$ and $d_0$) this quantity is well-approximated by $$P(n, d) \approx 1 - \exp\left(\frac{n^2}{2 d}\right) .$$
Substituting our particular values, the probability is $$P(n_0, d_0) \approx 5.79 \cdot 10^{-5} .$$
Since this is probability is very small, the probability of an overlap occuring in a given year of $365$ days is $$1 - (1 - P(n_0, d_0))^{365} \approx 365 P(n_0, d_0) \approx 2.11\% .$$
(Instead of using the above approximations, one can use a suitable CAS to compute exact values for these figures, which to three significant figures respectively work out to be $5.73 \cdot 10^{-5}$ and $2.07\%$.)