We have the following situation:
We are trying to find the path to a coffee shop. We have 3 streets when we exit our home and only one takes us to the coffee shop. If we take the 1st street, we make 20 min until the coffee shop. If we take the 2nd street, we will make 40 min and it will takes us back home. If we choose the 3rd street we will make 60 min and it will takes us back home. We choose a street randomnly and hope it will take us at the coffee shop. We can't rely on previous experiences when choosing a door.

What is the expected average time in minutes to get to the coffee shop?

  • 1
    $\begingroup$ The admonition not to "rely on previous experiences" makes this a truly artificial problem! IMHO it's more interesting to answer the version in which you can remember which routes failed. $\endgroup$ – whuber Jul 16 '19 at 14:41

This is a common interview question with many variants, such as cave escape, monsters, etc. involved in it. We let $X$ be the arrival time. If you happen to choose door 2 or 3, you'll just lose some time and start from the beginning, e.g., if we choose door 2, after losing 40 minutes, we'll still have the same expectation because everything has been reset.

So, if we choose door 2 with probability $1/3$, our expected arrival time becomes $E[X]+40$, and it is $E[X]+60$ for door 3. Therefore, we'll have the following recursive equality for solving $E[X]$: $$E[X]=\frac{1}{3}20+\frac{1}{3}(E[X]+40)+\frac{1}{3}(E[X]+60)$$

A slight modification of this problem would be to remember the last path we used, which is more realistic because we came back using that path. Let $X_i$ be the expected time of arrival after we use door $i$ (clearly $X_1=0$). We can modify the recursive formula as follows: $$E[X]=\frac{1}{3}20+\frac{1}{3}(E[X_2]+40)+\frac{1}{3}(E[X_3]+60)$$ Now, we also need to write recursive formulas for $X_i$. For example, expected time of arrival after we use door $2$ is either $20$ minutes or expected time of arrival after using door $3$ plus overhead of door $3$, and similarly for the door $2$, i.e.: $$\begin{align}E[X_2]&=\frac{1}{2}20+\frac{1}{2}(E[X_3]+60)\\E[X_3]&=\frac{1}{2}20+\frac{1}{2}(E[X_2]+40)\end{align}$$ These three equations can be solved easily to obtain $E[X]$.

One other modification would be @whuber's comment where all the past is remembered. In this case, we're out in at most three steps. Our choices are finite: $\{(1),(2,1),(3,1),(2,3,1),(3,2,1)\}$, which corresponds to $\{20,60,80,120,120\}$ minutes with probabilities $\{1/3,1/6,1/6,1/6,1/6\}$, respectively. Assuming all unused doors are equally likely.


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.