Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

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

share|improve this answer
    
Thank you, this is a good start. Unfortunately, the interesting part for me is when $l/t$ is not small... –  Petar Ivanov Nov 24 '11 at 6:37

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

share|improve this answer
    
Thank you, this is a good start. Unfortunately, the interesting part for me is when l/t is not small... –  Petar Ivanov Nov 24 '11 at 6:37

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.

share|improve this answer
    
Please avoid double posting where possible; you should be able to edit your existing answer. –  Yemon Choi Apr 27 '12 at 19:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.