11
$\begingroup$

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!

$\endgroup$
1
7
$\begingroup$

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]$

$\endgroup$
13
  • $\begingroup$ Thank you! Do you mind elaborating a bit more? Since the LOTP is P(B) = Summation P(B|Ai)P(Ai), should I be finding the P(Freedom)? I'm confused as to how that would get me E(distance). Thanks! $\endgroup$
    – AZ0987
    Jan 14 '17 at 3:37
  • $\begingroup$ I added more information. Hope all is clear now. $\endgroup$
    – Momo
    Jan 14 '17 at 3:42
  • $\begingroup$ It is! I understand now. Thank you so much $\endgroup$
    – AZ0987
    Jan 14 '17 at 3:42
  • 1
    $\begingroup$ @Bram28: Technically, it is simpler to use your method to prove the finite expectation, because you can easily prove that the probability of crawling forever is $0$, and we conventionally exclude failure with probability $0$ when asking for expectation of something. This minor assumption is not removable. See the post I linked above which uses the same kind of computation to essentially prove the general case, after which we can freely use one-step analysis for any finite-state discrete Markov process. $\endgroup$
    – user21820
    Jan 14 '17 at 6:48
  • 1
    $\begingroup$ @Bram28: Your other answer is interesting, but ultimately equivalent to Momo's answer. One step is going down a tunnel and coming back if it doesn't lead to freedom, and $\frac13$ of the time you will escape, so the average total distance is $3$ times the average distance you crawl, which is simply the sum of the possible crawling distances for one step. Indeed the argument will fail for some infinite-state Markov processes; look at the comments below the linked post for example. $\endgroup$
    – user21820
    Jan 14 '17 at 7:02
2
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ @JohnBentin, how do you format it such that the E is fancy, and there is a multiplication dot in the equation? $\endgroup$
    – KMD
    Aug 18 '17 at 19:46
  • $\begingroup$ I would start with the first answer on this page $\endgroup$ Aug 18 '17 at 21:32
  • $\begingroup$ I think that you should edit your answer. The random variable is the number of feet he covers before he finds his way to escape. Its expectation $E$ is a determined quantity. $\endgroup$ Aug 18 '17 at 21:45
  • $\begingroup$ What do you mean when you say its expectation E is a "determined quantity?" $\endgroup$
    – KMD
    Aug 19 '17 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.