Question

The question is to compute or estimate the following probabilty.

Suppose that you have $N$ (e.g. $30$) tasks, each of which repeats every $t$ min (e.g. $30$ min) and lasts $l$ min (e.g. $5$ min). If the tasks started at uniformly random point in time yesterday, what is the probability that there is a time today at which at least $m$ (e.g. $10$) of the tasks run.

Answer 1

Probability that a task Is operating at a given instant = l/t.

Probability that a task isn’t operating at a given instant = (t-l)/t.

Probability that at least m of N tasks are operating at a given instant is C(N,i)[ (l/t)^i][(t-l)/t]^(N-i) summed for i=m to N where C(N,i) is the combination of N objects taken i at a time.

Integrate the sum over (0,t] . Result is (((t-l)^N)/t^(N-1))∑i=m to N [C(N,i)(l/(t-l))^i] which further simplifies to

(((t-l)^N)/t^(N-1))[(t/(t-l))^N – ((t/(t-l))^m)]

This further simplifies to t[1-((t-l)/t)^(N-m)]

We only have to compute the probability for one interval of length t since the start times for each task has fixed period t and task lasts for same interval l. So if the event of m tasks happening in an instant over an interval of length t doesn’t happen once, it never happens.

Answer 2

Prob that a task is occuring at any given point in time in interval t is l/t. Prob that a task is not occurring at any given point in time in interval t = (t-l)/t

Prob that at least m of N events occur at any given point in interval is sum of binomial probabilities : (N!/i!(N-i)!) (l/t)^i*((t-l)/t)^(N-i) summed over i=m to N.

Then you have to integrate 1-this sum over the range (0,t]. Then you have to take 1- this integral.

This should give probability for a given interval of length t. Then you have to figure out how many intervals there are of length t in the day (suppose there are T) and using the probability previously calculated as p do another binomial calculation for 1 minus the probability that none of the T intervals have an instant in time where m or more tasks are running.

Answer 3

Each block of $t$ minutes today will have the same pattern of tasks. Think of the middle point of a task as a uniform random variable on the unit circle. Then, $m$ tasks overlap if their corresponding random variables fall within a ball of radius $l/t$. This is a continuous generalization of the birthday problem.

If instead of the unit circle, the variable fell on the unit interval $[0,1]$, the case $m=2$ has a simple solution in Feller Vol II. (p. 42):

$$p(\text{At least }2\text{ tasks coincide}) = \begin{cases} 1-\left[1-(N-1)\frac{l}{t}\right]^N & \text{if } \frac{l}{t} < \frac{1}{N-1} \\ 1 & \text{if } \frac{l}{t} \geq \frac{1}{N-1}. \end{cases} $$

If $l/t$ is small, you can probably approximate the probability you are looking for with this probability. In this case, you could also find approximations using the discrete birthday problem (see Wolf Schwarz, Comparing Continuous and Discrete Birthday Coincidences: “Same-Day” versus “Within 24 Hours”, The American Statistician, 2010). This may allow you to treat the case $m>2$.

Answer 4

Consider a circle of length $t+\ell$. Then I think your problem is asking if I drop $N$ points uniformly at random onto that circle, what is the probability that at least $m$ of them are in an interval of length $\ell$. When $m/(N-m) >> \ell / t$, so that the tail event that there are $m$ points in a fixed interval of size $\ell$ is exponentially small, you can use the union bound

$$ N \sum_{j\ge m} (t/(t+\ell))^{N-j} (\ell/(t+\ell))^j \binom{N}{j}$$.

You could also consider using the Brownian bridge (from $(0,0)$ to $(1,1))$ approximation of the partial sum $\sum_{j=1}^k X_j$ where $X_j$ is the distance between the $j$th and $j+1$st points in say the clockwise direction, with a particular chosen first point $p$. Then the question roughly becomes what is the chance that there is some $s \in [0,1]$ such that $B_{s + \ell/(\ell + t)} - B_s$ exceeds $m/N$. So for instance if $m/N \le \ell / (t + \ell) + o(\sqrt{\ell / (t + \ell)})$ then this probability should be very close to $1$.