Average Tries needed for conditionally looping probability problem

Question

I beg your pardon for the undescriptive title and it's lack of proper jargon. All of this has been quite a few years in the past for me.

Here is my problem displayed in image form: Paint Skills

---

As you can probably see, I want to know how to calculate the average tries needed to reach a "Done" state in a problem where you go back to the previous stage upon failure.

Stage 1: 1/14 odds at being Done in Stage 1, 13/14 odds to move to Stage 2.

Stage 2: 1/3 odds to move to Stage 3, 2/3 odds to have to move back to Stage 1.

Stage 3: 1/4 odds at being Done, 3/4 odds to move back to Stage 2.

I have legitimately no idea on how to approach this, as I can't think of a way to express the possibility of being stuck in loop between the stages and how many times you'd have to go through them for a success.

Add in the fact, that I need to know the average amount of times you are at each step because I want to know the associated cost, and I am completely lost.

I hope some kind soul here can enlighten me :)

---

Best wishes, kahntesy

Answer 1

Labelling the nodes $1,2,3$ as $A, B, C$, we proceed step by step, eg

With $1$ step from $A$, we are either done, or with Pr = $\frac{13}{14}$, we reach $B$

Framing equations for movement step by step, for # of steps we get

$\displaylines{A = 1 +13B/14\\B = 1+C/3 + 2A/3\\C =1 +3B/4}$

Solving, we get $A = 167/11, B = 168/11, C = 137/11$

Answer 2

First, note that there is no way you can do it in an even amount of tries. Moreover, there is 1/14 chance to finish in one try. If not, then you have 13/14 chance to go to stage 2, from which you have 1/3 odds to go back to stage 3, and 2/3 odds to go back to stage 1. As a result, for any $n\geq 1$, the probability that you'll finish in exactly $2n+1$ tries is given by $$ p(2n+1)= \frac{13}{14}\left(\frac13\cdot\frac14+ \frac23\cdot\frac{1}{14}\right)\sum_{k=0}^{n-1}\begin{pmatrix}n-1\\ k\end{pmatrix}\left(\frac{1}{3}\cdot\frac34\right)^{k}\left(\frac23\cdot \frac{13}{14}\right)^{n-1+k}\\ = \frac{13}{14}\cdot\frac{33}{252}\cdot\left( \frac{73}{88}\right)^n, $$ because, it's a $\frac{13}{14}$ chance we go to step two, and then we know we'll go back to step two $n$ more times in total. So, first, choose in what step you'll be done. Going from step two to step three and then finishing the game has probability $\frac13\cdot\frac14$ while going from step two to step one and then finishing the game has probability $\frac23\cdot\frac{1}{14}$.

Moreover, for the rest $n-1$ times we'll visit step two, we choose $k$ of them to be for step three and $n-k+1$ to be on step one. Since going to step one from step two has a probability of $13/14$, and then from step two back to step one has probability $2/3$, and since these will happen $n-k+1$ times we multiply accordingly.

Since $p(1)= \frac14$, you may check that $$ \sum_{n=1}^\infty p(n)= 1. $$

Now, the average is given by $$ \sum_{n=1}np(n)= p(1)+ \sum_{n=1}^\infty (2n+1)p(2n+1)= \frac14+ \frac{429}{3528}\sum_{n=1}^\infty (2n+1)\left(\frac{73}{88}\right)^n\\ =\frac14+ \frac{858}{3528}\sum_{n=1}^\infty n\left( \frac{73}{88}\right)^n+ \frac{429}{3528}\sum_{n=1}^\infty \left(\frac{73}{88}\right)^n\\ =\frac14 + \frac{858}{3528}\frac{\frac{73}{88}}{\left( 1-\frac{73}{88}\right)^2}+ \frac{429}{3528}\left( \frac{1}{1-\frac{73}{88}}-1\right)\\ = \frac14+ \frac{858}{3528} \frac{73\cdot 88}{15^2}+ \frac{429}{3528}\frac{73}{15}\approx 3.1562, $$ so you'll need a little more than three tries.

Answer 3

In my view, the argument based on states (as in the posted solution of @trueblueanil) is the best. Just as a sanity check, here is an alternate solution:

Note that the probability of finishing on the first trial is $\frac 1{14}$. If you survive the first trial (probability $\frac {13}{14}$) you are in stage $\#2$. From this point, your probability of surviving the next two trials is $$\rho_s=\frac 23\times \frac {13}{14}+\frac 13\times \frac 34= \frac {73}{84}$$

And, of course, the probability of being done after the next two trials is $$\rho_d=1-\rho_s=\frac {11}{84}$$

Clearly, having survived the first trial, you now have a Geometric Distribution with expectaton $\frac 1{\rho_d}=\frac {84}{11}$. Thus the answer is $$\boxed {1 +\frac {13}{14}\times 2\times \frac {84}{11}=\frac {167}{11}}$$

Note that the factor of $2$ arises because each "trial" for stage $\#2$ is two ordinary trials.

To do it out completely: note that the probability of being done in exactly $2n+1$ trials (for $n≥1$) is $$p_{2n+1}=\frac {13}{14}\times \rho_s^{n-1}\times \rho_d$$

It is now easy to compute the answer:

$$\boxed {E=\frac {1}{14}+\frac {13}{14}\times \rho_d\times \sum_{n=1}^{\infty} (2n+1)\times \rho_s^{n-1}=\frac {167}{11}}$$

which, of course, matches the result given by the state based method.

Might be worth remarking that, technically, the argument via states is incomplete as it assumes existence. The computational methods employed here demonstrate existence.