I need help solving the following problem with a recurrence relation.

A miner is trapped in a mine with three doors. The first door will lead him to safety in two hours. The second door leads him back to the same place in three hours. The third door leads him to a maze which takes him back to the same place in 5 hours. However, if the miner ever travels through the third door again, it takes him only 1 hour to go back to the same place as he remembers how to get out of the maze. The three doors look the same and so the miner always chooses each of them with equal probability, independent of which door he has taken before. What is the expected time until the miner reaches safety?

I am trying to solve it by using Markov chain with 2 states, one which indicates the miner has gone through door 3 already and the other that he has not but I'm somewhat confused. Any help will be appreciated.

P.S. This is not homework but practice for an upcoming midterm.

  • $\begingroup$ Your idea that there are two states depending on whether he has gone through door 3 is the right one. Let $a$ be the expected duration to safety if he hasn't gone through door 3 and $b$ the expected duration if he has gone through door 3. What equations have you written? You should have one for each state, which gives two equations in two unknowns. $\endgroup$ – Ross Millikan Mar 12 '15 at 3:41

The state space is on the right track but there are 3 states to consider.

$$S_0\text{ - the initial state}$$ $$S_1\text{ - the original room after passing through the maze}$$ $$S_2\text{ - the exit}$$

With these the transition probabilities and times are straightforward:

$$\begin{align} P_{00}&=\frac{1}{3}&t=3\\ P_{01}&=\frac{1}{3}&t=2\\ P_{02}&=\frac{1}{3}&t=5\\ P_{10}&=0&t=N/A\\ P_{11}&=\frac{1}{3}&t=2\\ P_{12}&=\frac{2}{3}&t=1\\ P_{20}&=0&t=N/A\\ P_{21}&=0&t=N/A\\ P_{22}&=1&t=0\\ \end{align}$$

  • $\begingroup$ OP was right, there are only two states. He is in the entry, either having passed through the maze or not. Once he goes through the door, he will either come back to the start or escape. $\endgroup$ – Ross Millikan Mar 12 '15 at 3:44
  • $\begingroup$ @RossMillikan I disagree, there are 2 physical locations, but the original room can be in two separate states (been thru the maze or not) - I agree it can be simplified to 3 states and I will do so. $\endgroup$ – Dale M Mar 12 '15 at 3:48
  • $\begingroup$ I don't see where 3 comes from. You are in the room about to choose a door. There is only one location, but two states depending on your history. In the path or in the maze are just times spent to get back to the room. $\endgroup$ – Ross Millikan Mar 12 '15 at 3:51
  • $\begingroup$ @RossMillikan I see the confusion - I am counting the terminal state (escaped) and you are not $\endgroup$ – Dale M Mar 12 '15 at 3:54
  • $\begingroup$ OK, but you had six a bit ago. You are correct that your state 2 is absorbing. $\endgroup$ – Ross Millikan Mar 12 '15 at 3:59

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.