2
$\begingroup$

I have an event that will start exactly X times within a single 24 hour period.

Each event lasts Y milliseconds.

The start time of an individual event is uniform randomly distributed throughout the 24 hour period. The start time of each event is independent of the others.

What is the probability that at any point during the 24 hour period Z (or more) events are currently occurring and overlapping each other?

  • 0
    The information is incomplete. If there is always one event per day, no events will ever overlap (except perhaps around midnight), whereas if there are sometimes, $0$, $1$ and $2$ events per day, also with average $1$, there will be overlaps. Perhaps you have in mind that the number of events per day is Poisson-distributed?2012-04-11
  • 0
    @joriki: I have restated the question to be more precise.2012-04-11
  • 0
    If you want an exact answer, you might want to say something about what happens around midnight. Can events starting on the previous day extend into this day? Can events starting on this day extend into the next? If you're not worried about the small effects from this, you might also consider ignoring the remote possibility that there is more than one $Z$-fold overlap and just calculate the expected number of overlaps, which might be easier.2012-04-11
  • 0
    @joriki: In the restatement there is exactly one 24 hour period (no previous or next day). It is precisely the Z-fold overlap we are interested in (what is the chance 4 events are occuring at the same time).2012-04-11
  • 0
    So do I understand correctly that an event may start $Y/2$ milliseconds before the end of the single $24$-hour period, and only $Y/2$ milliseconds of it will be within that period, but an event cannot start $Y/2$ milliseconds before the period so that $Y/2$ milliseconds of it extend into the period?2012-04-11
  • 0
    @joriki: Yes, that is correct.2012-04-11

1 Answers 1

3

I doubt that you'll find an exact closed form. However, since the event duration $Y$ is measured in milliseconds and the time period $T$ in hours, it seems likely that for practical purposes only the leading term in an expansion in $q:=Y/T$ will be relevant.

In that case, the possibility of more than $Z$-fold overlap can be neglected, and the desired probability is just $\binom XZ$ times the probability $p$ that $Z$ uniformly distributed events overlap. Boundary effects will also be of higher order in $Y/T$ than the leading term, so we can neglect them and treat the time period as if it wrapped around at the ends.

Here are two different ways to determine $p$, and also the probability distribution of the lengths of the overlaps.

Let $p(L)$ be the probability density of an overlap of length $L$, that is, $p(L)\mathrm dL$ is the probability of an overlap of length between $L$ and $L+\mathrm dL$. For any given instant $t$ in $T$, the probability that the interval $[t,t+L]$ is entirely covered by a given one of the events is $(Y-L)/T$, so the probability that it is covered by all $Z$ events is $((Y-L)/T)^Z$. Integrating this over $t$ gives the measure of points followed by a fully covered interval of length $L$. But we can also obtain the same measure in another way: An overlap of length $L'\gt L$ leads to an interval of length $L'-L$ of points followed by a fully covered interval of length $L$. Integrating this over $L'$ from $L$ to $Y$ also gives the measure of points followed by a fully covered interval of length $L$. Thus we have

$$\int_L^Yp(L')(L'-L)\,\mathrm dL'=\int_0^T\left(\frac{Y-L}T\right)^Z\,\mathrm dt=T\left(\frac{Y-L}T\right)^Z\;.$$

Applying $-\mathrm d/\mathrm dL$ yields

$$\int_L^Yp(L')\,\mathrm dL'=Z\left(\frac{Y-L}T\right)^{Z-1}\;,\tag{1}$$

and then setting $L=0$ gives

$$p=Z\left(\frac YT\right)^{Z-1}\;.$$

To get the distribution of the overlap lengths, we can apply $-\mathrm d/\mathrm dL$ once more to $(1)$ to obtain

$$p(L)=\frac{Z(Z-1)}T\left(\frac{Y-L}T\right)^{Z-2}\;.$$

Another way to derive this result is to place the events one by one and keep track of the probability that an overlap of length $L$ with $0\lt L\le Y$ remains. With one event placed, the "overlap" is $L$ with probability $1$. If we place a second event, there's a window of size $2Y$ in which an overlap will occur, so an overlap will occur with probability $2q$, and its length ranges from $0$ to $Y$ with uniform probability, so the probability density is $2q/Y=2/T$ for $0\lt L\le Y$.

Generally, if there was an overlap of length $L'$ and we place another event, there's a probability $(Y-L')/T$ that the same overlap remains, and a probability $2L'/T$ that the overlap is reduced to a new value $L\gt0$, with uniform probability for all values $L\lt L'$. This gives a recurrence for the probability density $p_Z(L)$:

$$p_Z(L)=\frac{Y-L}Tp_{Z-1}(L)+\frac2T\int_L^Yp_{Z-1}(L')\,\mathrm dL'\;.$$

It's straighforward to check that the result derived above satisfies this recurrence with the initial condition $p_2(L)=2/T$.

  • 0
    This doesn't seem right to me. At the start, you say that the desired probability is $\binom XZ$ times probability $p$. However, for $X = 4$, $Z = 2$, $Y = 1$ and $T = 10$ (i.e. 4 events that go for one minute each, distributed evenly over 10 minutes), I get a final probability of two or more events overlapping of > 1. This doesn't make sense to me, as we can clearly see that 4 one-minute events can be spread over 10 minutes without any overlaps. What am I missing here?2012-08-23
  • 0
    @Chris: Right before the statement about the desired probability that you cite, I say that I'm only talking about the leading term in an expansion in $q:=Y/T$, and that this is OK because multiple overlap is negligible for events on the order of microseconds in a $24$-hour period. In your example multiple overlap is quite probable, and it's enough to make the approximation take the probability from the correct value slightly below $1$ to a value slightly above $1$.2012-08-23
  • 1
    Great, got it!! Thanks mate, that make perfect sense now. Great answer :)2012-08-24