Probability brain teaser with infinite loop

Question

I found this problem and I've been stuck on how to solve it.

A miner is trapped in a mine containing 3 doors. The first door leads to a tunnel that will take him to safety after 3 hours of travel. The second door leads to a tunnel that will return him to the mine after 5 hours of travel. The third door leads to a tunnel that will return him to the mine after 7 hours. If we assume that the miner is at all times equally likely to choose any one of doors, what is the expected length of time until he reaches safety?

The fact that the miner could be stuck in an infinite loop has confused me. Any help is greatly appreciated.

Answer 1

Let $T$ be the time spent in the mine. Conditioning on the first door the miner chooses, we get $$ \mathbb{E}[T]=\frac{1}{3}\cdot3+\frac{1}{3}(5+\mathbb{E}[T])+\frac{1}{3}(7+\mathbb{E}[T])$$ so $$ \mathbb{E}[T]=5+\frac{2}{3}\mathbb{E}[T].$$ If $\mathbb{E}[T]$ is finite, then we can conclude that $\mathbb{E}[T]=15$.

To see that $\mathbb{E}[T]$ is finite, let $X$ be the number of times the miner chooses a door. Then $ \mathbb{P}(X\geq n)=(\frac{2}{3})^{n-1}$ for $n=1,2,3,\dots$, hence $$ \mathbb{E}[X]=\sum_{n=1}^{\infty}\mathbb{P}(X\geq n)=\sum_{n=1}^{\infty}\Big(\frac{2}{3}\Big)^{n-1}<\infty$$ And since $T\leq 7(X-1)+3$, we see that $\mathbb{E}[T]<\infty$ as well.

Answer 2

Let $t$ be the expected time to get out. If he takes the second or third door he returns to the same position as the start, so the expected time after he returns is $t$. Therefore we have $$t=\frac 13(3) + \frac 13(t+5)+\frac 13(t+7)\\\frac 13t=5 \\t=15$$

Answer 3

With probability $1$ he will eventually take the correct door so, $$3*\frac11$$

The wrong doors can be combined, $$ +6*\frac23 $$

and repeated $$ +6*(\frac23)^2 $$

and repeated $$ +6*(\frac23)^3 $$

...

This is can be written as a geometric series

$$3 +\sum (6 * (\frac23)^n)$$

Which is known to simplify to $$ 3+ 4/ (1-\frac23)$$

$$= 3+4*3 $$

$$ = 15$$

---

This result seems to generalize. For $K$ doors with paths length $A,B,C,...N$ if only $A$ leads out and all other doors lead back to the choice you get $$A + \sum(B*(\frac{1}{K})^n) + \sum(C*(\frac{1}{K})^n) + ...\sum(N*(\frac{1}{K})^n)$$

Which becomes $$A+(\frac{\frac BK}{1-\frac1K})+(\frac{\frac CK}{1-\frac1K})+...(\frac{\frac NK}{1-\frac1K}))$$

$$=A +\frac BK * K + \frac CK * K + ...\frac NK * K$$

$$=A+B+C+...N$$

Going randomly is equivalent of taking each door once. Weird.

Answer 4

A probability tree reveals that the miner can expect to spend 9 hours to reach safety. Suppose he chooses Door 7, with probability 1/3; he returns to the start and chooses Door 5 with p = 1/2; he returns and chooses Door 3 with p = 1. Then his path would take take 7 + 5 + 3 = 15 hours with p = (1/3)(1/2)(1) = 1/6. The other possible paths are 7 + 3 = 10, p = 1/6; 5 + 7 + 3 = 15, p = 1/6; 5 + 3 = 8, p = 1/6; and 3, p = 2/6. If T is the rv "time to exit", then its expectation is E(T) = 15*(1/6) + 10*(1/6) + 15*(1/6) + 8*(1/6) + 3*(2/6) = 54/6 = 9 hours.

Answer 5

This is a different approach, using the expected time taken for the miner to pass through $n$ doors.

Let $n$ be the number of doors the miner opens and let $P(T=t)$ be the probability the miner takes $t$ hours to exit. For $n=3$, the sequence of doors the miner opens is one of $(2,2,1),(2,3,1),(3,2,1),(3,3,1)$. These sequences correspond to $P(5+5+3)=\frac{1}{3^3}$, $P(5+7+3)=\frac{2}{3^3}$ and $P(7+7+3)=\frac{1}{3^3}$. The numerator of the second probability is $2$ because there are $2$ ways to have $t=15$. The figure below is a graph of the PMF of P(t).

If the miner passes through $n$ doors, of which $k$ are door-$2$, then he will pass $n-1-k$ times through door-$3$. The $-1$ term accounts for him passing through door-$1$. Then, in general, $P(5k+7(n-1-k)+3)=\frac{1}{3^n}\binom{n-1}{k}$. This is because there is a $\frac{1}{3^n}$ probability of picking each sequence of doors, but $\binom{n-1}{k}$ ways to pick that sequence. The miner can pass through door-$2$ between $0$ and $n-1$ times, so $0\leq k\leq n-1$.

$\mathbb{E}[T]=\sum tP(t)$

At $n$, the expected value, $\mathbb{E}[T]$, is:

$$ \begin{aligned} \mathbb{E}[T]&=\sum _k tP(t) \\ &=\sum_{0\leq k\leq n-1}\frac{5k+7(n-1-k)+3}{3^n}\binom{n-1}{k} \\ &=\frac{1}{3^n}\left[(7n-4)\sum\binom{n-1}{k}-2\sum k\binom{n-1}{k}\right] \\ &=\frac{1}{3^n}\left[2^{n-1}(7n-4)-2^{n-1}(n-1)\right] \\ &=\frac{2^{n-1}(6n+3)}{3^n} \end{aligned} $$

Then, the expected value over all $n$ is:

$$ \begin{aligned} \mathbb{E}[T]&=\sum_{n\in\mathbb{Z^+}} \frac{2^{n-1}(6n+3)}{3^n} \\ &=15 \end{aligned} $$