3
$\begingroup$

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.

2 Answers 2

5

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.

0

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

  • 0
    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's2010-12-21
  • 0
    Are the variables i.i.d.?2010-12-21
  • 0
    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.2010-12-21
  • 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.2011-02-19