Expected waiting time for $n$ successive successful tasks

Question

Let's assume we have $n$ assignments $a_1$, $a_2$, $\cdots$, $a_n$.

Each assignment $a_i$ can be done with probability $0<p_i<1$ in a time $t_i>0$.

But if you fail in the $i$-th task ($i < n$), then you have to begin from the start. Thus, for the complete process to be consider a success, the last $n$ final tasks must be successful for the first time.

For example, for $n=1$, succeeding in the complete task in $k$ steps corresponds to failing $k-1$ times and then managing to do the task $t_1$.

• Because the expected number of steps is $\frac{1}{p}$ and each of the failed tasks takes $\frac{t_1}{2}$ (using a uniform law), I think the expected time is: $$\left(\frac{1}{p_1}-1 \right) \cdot \frac{t_1}{2} +t_1 = \frac{t_1(1+p_1)}{2p_1}$$
• My first attempt was to find the law of the waiting time and then calculate the expected value : $$\sum_{k=1}^{+\infty} \left(\frac{(k-1)t}{2}+t \right)(1-p)^{k-1}p = \frac{t(1+p)}{2p} $$
• I wasn't able to find a formula for $n\geq 2$.

Answer 1

As far as I know, the general technique to solve such questions is as follows. For all $i =1,2,\dots, n$, let $s_i$ denote the time taken when the $i^{\text{th}}$ task fails. This might be equal to $t_i$, depending upon your problem setup. Also, for all $i = 1,2,\dots, n$, let $A_i$ denote the event that all assignments until the $i^{\text{th}}$ one have been successfully completed (in a row). Let $T$ denote the random time to complete all the tasks. We have the following recursion. \begin{align*} \mathbb{E}[T|A_{i-1}] & = \mathbb{E}[T|A_{i-1}, \text{Task } i\text{ succeeds}] \cdot p_i + \mathbb{E}[T|A_{i-1}, \text{Task } i\text{ fails}] \cdot (1 - p_i) \\ & = (\mathbb{E}[T|A_i] + t_i) \cdot p_i + (\mathbb{E}[T] + s_i) \cdot (1 - p_i). \end{align*} Starting with $\mathbb{E}[T|A_n] = 0$, you can backtrack to obtain an equation for $\mathbb{E}[T|A_0] = \mathbb{E}[T]$, then solve for $\mathbb{E}[T]$. I doubt the equation will be pretty unless the values of $p_i, t_i$ and $s_i$ are nice in some way.

Answer 2

If I understand correctly, when we fail at task $i$, the time we spend on it before failure is uniformly distributed on $[0,t_i]$.

We can get the total expected time by linearity of expectation, so we only have to work out the expected time spent on each task $i$.

Note that for that purpose, all the preceding tasks are irrelevant – it doesn’t matter how often we need to try them to get up to task $i$. Neither does it matter which of the remaining tasks we fail on. The expected time spent performing task $i$ is

$$ E_i=(1-p_i)\frac{t_i}2+p_it_i+\left(1-\prod_{j=i}^np_j\right)E_i\;, $$

since with probability $1-p_i$ we fail and spend $\frac{t_i}2$, with probability $p_i$ we succeed and spend $t_i$, and with probability $1-\prod_{j=i}^np_j$ we fail before completing the entire assignment and have to start over. Solving for $E_i$ and summing over $i$ yields the total expected time

$$ \frac12\sum_{i=1}^n\frac{t_i(1+p_i)}{\prod_{j=i}^np_j}\;. $$

For $n=1$, this reduces to your result.