Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a series of tasks where when one task finishes the next task runs, until all of the tasks are done. I need to find the probability that everything will be finished at different points in time. How should I approach this? Is there a way to find this in polynomial time?

The pdfs for how long individual tasks will run have been found experimentally and are not guaranteed to follow any particular type of distribution.

share|improve this question
add comment

2 Answers

If the durations of the different tasks are independent, then the PDF of the overall duration is indeed given by the convolution of the PDFs of the individual task durations.

For efficient numerical computation of the convolutions, you probably want apply something like a Fourier transform to them first. If the PDFs are discretized and of bounded support, as one would expect of empirical data, you can use a Fast Fourier Transform. Then just multiply the transformed PDFs together and take the inverse transform.

share|improve this answer
add comment

I don't know if that is what you are looking for, but if $X_1,\ldots,X_n$ are i.i.d. random variables with mean $\mu$ and (finite) variance $\sigma^2$, then $$ {\rm P}\bigg(\sum\limits_{i = 1}^n {X_i } \le t \bigg) = {\rm P}\bigg(\frac{{\sum\nolimits_{i = 1}^n {X_i } - n\mu }}{{\sigma \sqrt n }} \le \frac{{t - n\mu }}{{\sigma \sqrt n }}\bigg), $$ and the random variable $\frac{{\sum\nolimits_{i = 1}^n {X_i } - n\mu }}{{\sigma \sqrt n }}$ converges to the standard normal distribution as $n \to \infty$. Now, you can estimate the unknown parameters $\mu$ and $\sigma^2$ (assuming the variance is finite), so if $n$ is sufficiently large, you are actually done.

For further details see this (note the subsection Density functions).

share|improve this answer
    
Unfortunately, I don't have enough variables to use the Central Limit Theorem. Most cases there will probably only be 2 or 3 and there is no guarantee about their distribution's –  Statler Dec 21 '10 at 3:45
    
Are the variables i.i.d.? –  Shai Covo Dec 21 '10 at 4:05
    
no, unfortunately not. They are defiantly not identically distributed, and probably not independent in most cases. I am willing to live with restricting it to independent variables though, if it is necessary to have a solution. –  Statler Dec 21 '10 at 4:15
1  
If there are only 2 or 3, you can just numerically integrate the pdfs. This doesn't depend upon the distributions being the same, nor even independence. –  Ross Millikan Feb 19 '11 at 20:07
add comment

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.