A problem about expected value

Question

Some students have a list of processes to execute sequentially but the running of a process may fail during execution, so the probability that a process $x$ will be executed successfully is $Px$.

Assume that the execution takes one second to be run to compute the answer for each process, if the program crashes, it will take 3 seconds more for the students to re-run it and in this case, the execution should be re-run starting from the first process.

You are given the probability that each process will be executed successfully, What is the number of seconds expected to pass all processes without crushing ?

I couldn't figure out how to determine the expected value to run all the processes successfully. I know it is something like $E(x) = Px \times (1) + (1 - Px) \times (1 + 3 + E(x)) $ and I think it is depending on the previous process to be run successfully but I failed to get the right answer..

Answer 1

Let the expected number of seconds waited be $E(X)$. Then the expected value is given by $$E(X)=Px(1)+(1-Px)(3+E(Y)+E(X))$$ Where $Y$ is the amount of time taken for the process to crash. I assume that this is uniformly distributed between $0$ and $1$, so $E(Y)=0.5$. Solving this then gives $$E(X)=\frac{3.5-2.5Px}{Px}=\frac{7-5Px}{2Px}$$

Answer 2

We can write

$$ \begin{align} E(x) &= \sum_{i = 0}^{\infty} \left(\text{probability that the process terminates succesfully after $(i+1)$ attempts}\right)\\ &\times(\text{amount of time needed to complete the process in exactly $(i+1)$-th attempts}) =\\ &=\sum_{i = 0}^{\infty}\left((1-P_x)^i\cdot P_x)\cdot ((1+3)\cdot i+1)\right)=\\ &=P_x \cdot \left(\sum_{i = 0}^{\infty}4i\cdot (1-P_x)^i + \sum_{i = 0}^{\infty} (1-P_x)^i\right)=\\ &=P_x\cdot \left( 4\cdot \frac{1-P_x}{P_{x}^2}+\frac{1}{1-(1-P_x)} \right)=\\ &=4\cdot\frac{1-P_x}{P_{x}}+1=\\ &=\frac{4-3P_x}{P_{x}}. \end{align} $$

Answer 3

So, like in the other answers, I will assume that all processes succeed with the same probability $p:=P_x$. Let $E:=E(X)$ denote the desired expected value. Also, to see the influence of the delay after a crash ($3$ seconds), let's call it $d$. The probability for completing all processes successfully after $n$ seconds is $p^n$. If the whole sequence crashes at process $k \le n$, which will happen with a probability of $(1-p)p^{k-1}$, it already took $k$ seconds and will take another $d+E$ to complete the whole task successfully. In total, we have:

\begin{align} E &= (1+d+E)(1-p) + (2+d+E)(1-p)p + \cdots + (n+d+E)(1-p)p^{n-1} + np^n\\ &= \sum_{k=0}^{n-1}(1+d+k+E)(1-p)p^{k} + np^n\\ &= \sum_{k=0}^{n-1}(1+d+k+E)p^{k} - \sum_{k=0}^{n-1}(1+d+k+E)p^{k+1} + np^n\\ &= \sum_{k=0}^{n-1}(1+d+k+E)p^{k} - \sum_{k=1}^{n}(d+k+E)p^{k} + np^n\\ &= 1+d+E + \sum_{k=1}^{n-1}p^{k} - (d+n+E)p^{n} + np^n\\ &= 1+d+E + \sum_{k=1}^{n}p^{k} - (1+d+E)p^{n}\\ &= E(1-p^n) + (1+d)(1-p^n) + p\sum_{k=0}^{n-1}p^{k} \end{align}

Solving this for $E$, we get

\begin{align} E &= \frac{(1+d)(1-p^n)}{p^n} + \frac{p(1-p^n)}{(1-p)p^n} = \frac{(1+d)(1-p^n)(1-p) + p(1-p^n)}{(1-p)p^n}\\ &= \frac{(1-p+d-dp+p)(1-p^n)}{(1-p)p^n} = \frac{(1+d-dp)(1-p^n)}{(1-p)p^n}\\ &= \frac{1-p^n}{p^n} \left(d+\frac{1}{1-p}\right) \end{align}

Added:

For $n=1$, this results in the formula that @simonet gave.

If the probabilities of the processes differ, the formula will not be that simple. For example, if we have two processes with probabilities $p_1$ and $p_2$ to succeed, and the students have to successfully complete process $1$ first, it's easy to see that the expected total time to successfully complete both processes becomes $$ E=\frac{1-p_1p_2}{p_1p_2}\left(d+\frac{1+p_1}{1-p_1p_2}\right)$$ This is clearly not symmetric, and we see that to minimize the expected time, we'd be better off to take the risky process first.