GATE CSE 2003 | Question: 60, ISRO2007-45

Question

A program consists of two modules executed sequentially. Let $f_1(t)$ and $f_2(t)$ respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by 

• A. $f_1(t)+f_2(t)$

• B. $\int_0^t f_1(x)f_2(x)dx$

• C. $\int_0^t f_1(x)f_2(t-x)dx$

• D. $\max\{f_1(t),f_2(t)\}$

Comments

https://en.wikipedia.org/wiki/Convolution_of_probability_distributions

---

For understanding convolution
https://www.youtube.com/watch?v=zbu8KQx9bqM

---

Part 2 of above video: The Sum of Independent Continuous Random Variables

---

https://courses.cs.washington.edu/courses/cse312/20su/files/student_drive/5.5.pdf

Answer 1

We assume the total time to be $‘t’$ units and $f1$ executes for $‘x’$ units.

Since, $f1(t)$ and $f2(t)$ are executed sequentially.
So, $f2$ is executed for $‘t – x’$ units.

We apply convolution on the sum of two independent random variables to get probability density function of the overall time taken to execute the program.

$f1(x) $*$ f2(t – x)$

Correct Answer: $C$

Comments

f1(t) * f2(t – x) ...  it should be f1(x) * f2(t – x)

Please correct it.

---

explain this line please

We apply convolution on the sum of two independent random variables to get probability density function of the overall time taken to execute the program.

 

---

@Pranabesh Ghosh 1 Can we think of it like this: Assuming module 1 gets implemented first at time t, it executes for f1(t) time units. Then at that point module 2 starts, so it will take f2(f1(t) + 1) time units, as module 1 finishes at f1(t) time step. So the final answer can be max(f1(t), f2(t)) as ultimately module 2 will finish at the highest time step.

---

@amitqy 

 Convolution Theorem(page 2): 5.5.pdf (washington.edu)

Answer 2

$f_k(t)$ denote the probability density function of time taken to execute module (Here k = 1, 2). Means probability that module k will take 5 unit of time is given by $f_k(5)$.

Now let us assume total execution time is  4 unit then it's probability will be given by  -->

$f_1(0)*f_2(4)$ + $f_1(1)*f_2(3)$ + $f_1(2)*f_2(2)$ + $f_1(3)*f_2(1)$ + $f_1(4)*f_2(0)$

(means for example if first module takes 3 unit then another module should take 1 unit of time(and both probabilities are independent because module execution is sequential) so it's probability is $f_1(3)*f_2(1)$  ).

If entire program execution time is t unit then we can write general formula for it's probability as

  $f_{total}(t) = $$\int_{0}^{t}$ $ f_1(x)*f_2(t-x)$dx$ $

which is also telling probability density at point 't' or $f_{total}(t)$ is our desired probability density function for entire program execution.

Answer is (C) part.

Comments

what will be the answer if the program modules execution is parallel not sequential???

---

But the question is asking about probability density function and (C) is the probability of the entire program execution. Probability density function must be just  f1(x)∗f2(t−x)  (without integration).

Can anyone please verify??

---

http://www.milefoot.com/math/stat/rv-sums.htm

Answer 3

Solution: C

Since the two modules execute sequentially. The total runtime of the program is the sum of runtime of the the two modules. Probability mass function of sum of two random variable is given by the convolution in the option C.

REFERENCE

Answer 4

A thorough work out:

So, option (C) is correct.