Probability: Escaping Prisoner Question

Question: A prisoner in a dark dungeon discovers three tunnels leading from his cell. Unbeknownst to him, the first tunnel reaches a dead end after 50 feet and the second tunnel reaches a dead end after 20 feet, but the third tunnel leads to freedom after 100 feet. Each day, the prisoner picks a tunnel at random and crawls along it. If he reaches a dead end he has to crawl back to his cell.

(The darkness is so complete that he might try the same tunnel on successive days).

Find the expected distance that he crawls to reach freedom.

My Guess: I know that each tunnel has a probability of ⅓ of being chosen.

If Distance to freedom = 100(X) + 40(Y) + (100)(Z), where X = number of times he tries tunnel 1, Y = number of times he tries tunnel 2, and Z = number of times he tries tunnel 3 (=1 since it leads him to freedom).

Then E(D) = E(100X + 40Y + 100) = 100E(X) + 40E(Y) + 100.

I'm not sure if this logic is correct, and I'm a little confused on how to find E(X) and E(Y).

Thanks!

Solution 1:

Hint: Use the total expectation formula to condition of prisoner choice.

If $X$ is the distance traveled and $T_1,T_2,T_3$ are the events that the prisoner chooses tunnel $1,2$ and $3$ respectively, then:

$$E[X]=E[X|T_1]P(T_1)+E[X|T_2]P(T_2)+E[X|T_3]P(T_3)$$

Now $E[X|T_1]=100+E[X]$, $E[X|T_2]=40+E[X]$, and $E[X|T_3]=100$

• in the first case after traveling 100ft the prisoner is in the same situation as in the beginning, so it takes on average E[X] distance again to get out

• in the second case it takes only 40ft for the prisoner to be in the same situation as in the beginning

• in the third case it takes 100ft for the prisoner to get out

and $P(T_1)=P(T_2)=P(T_3)=\frac{1}{3}$

So you can solve for $E[X]$

Solution 2:

Let's assume he picks the tunnels with equal likelihood, i.e. $\frac{1}{3}$ each.

So, the prisoner definitely has to crawl that 100 feet to freedom at some day, but he can be crawling (for nothing) in those other tunnels as well with a likelihood of $\frac{2}{3}$ each day and for a distance of 70 feet on average on such a lost day.

OK, so let $P(i)$ be the probability of the prisoner crawling for $i$ days for nothing before reaching freedom, so $P(i) = (\frac{2}{3})^i * \frac{1}{3}$

And let $D(i)$ be the expected distance the prisoner crawls on $i$ lost days, so $D(i) = i*70$

We thus get:

$E(D) = 100 + \Sigma_{i=1}^{\infty} P(i)*D(i) = 100+ \Sigma_{i=1}^{\infty}(\frac{2}{3})^i * \frac{1}{3} * i * 70 = 100+ 70*\frac{1}{3}*\frac{2}{3}*\Sigma_{i=1}^{\infty}i*(\frac{2}{3})^{i-1}= 100+\frac{140}{9}*\frac{1}{(1-\frac{2}{3})^2} = 100+140=240$

Solution 3:

I'll add another answer that I think is the simplest, and here is how I got to it:

I noticed that the answer (240 feet) was exactly the sum of going through (and back) both the 'dead-end' tunnels (100 feet and 40 feet respectively) and going through the 'freedom' tunnel once (100 feet) and I figured that was probably not a coincidence.

Now, using @Momo's method, I quickly realized that indeed: whatever the lengths of the tunnels are, and no matter how many tunnels there are (though still with exactly one leading to freedom), if each tunnel is picked with equal probability, then the expected distance in the end will be the sum of the distances traveled by going through each tunnel once.

OK, but even with Momo's method, there is still some algebra involved to get to this result, and I figured that there must be an even simpler argument for this result, and after some further thinking, I found it:

Given that no matter how many days it takes for the prisoner to get out, it is true that each day the prisoner picks each tunnel with equal likelihood (this is true while the prisoner has not escaped yet, as well as when the prisoner has escaped). It thus follows that the expected number of times the prisoner goes through a tunnel is the same for each tunnel as well. But since we know the prisoner that escapes goes through the freedom tunnel exactly once, the prisoner is expected to go through each other tunnel exactly once as well!

Solution 4:

Ok, so here's what I believe to be the quickest answer to this problem:

Set up a random variable $E$ which represents the expected number of feet before he actually finds his way to the end of the tunnel. There is a one-third chance of picking each tunnel, and as the problem states, he has to crawl back, meaning double the length of the tunnel each time he chooses. However, one tunnel, the one that leads him to success, isn't doubled. Thus, we set up the equation:

$$E=\tfrac13\cdot100+\tfrac13(E+100)+\tfrac13(E+40).$$

This is because, first, there is a $\frac13$ chance the task ends after $100$ feet. However, for the other two tunnels, he fails. If he fails, he returns back to the starting position, meaning he is in them same situation he was at before, $E$, as well as the number of feet that he had just traveled.

Solving this equation, we multiply both sides by $3$:

$$3E=100+E+100+E+40.$$ Combining like terms, we get $3E=2E+240$ and, subtracting $2E$ from both sides, we are left with $$E=240.$$

Thus, the blind prisoner will have to crawl, on average, $240$ feet to reach freedom.