# Convolution of multiple probability density functions

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.

-

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.

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