 # Markov Chains and Conditional Probability: Easy rat in the maze problem Why is the following soluti Brock Byrd 2022-07-03 Answered
Markov Chains and Conditional Probability: Easy rat in the maze problem
Why is the following solution to this problem incorrect,
A rat is trapped in a maze with three doors and some hidden cheese. If the rat takes door one, he will wander around the maze for 2 minutes and return to where he started. If he takes door two, he will wander around the maze for 3 minutes and return to where he started. If he takes door three, he will ind the cheese after 1 minute. If the rat returns to where he started he immediately picks a door to pass through. The rat picks each door uniformly at random. How long, on average, will the rat wander before finding the cheese?
1. Construct a graph with three vertices: X, Y, Z, each of which represents a door in the original problem.
2. Add edges between every vertex, including self-loops, each of which has a weight of 1/3.
3. Take the stationary distribution to be (1/3, 1/3, 1/3). It is unique because the probability transition question for the graph in (1) is regular (i.e., its limit is just the same matrix with all entries equal to 1/3)
4. Compute the expected time as $21/3+31/3+1\cdot 1/3=2$
The correct answer is 6. I know that the set-up is completely wrong and that I should use conditional probability, but is there a way to do it like this? The main issue is that we don't know the total time spent in the maze (this is kind of what we need to find) so I can see that it doesn't really make sense to take this approach.
You can still ask an expert for help

## Want to know more about Discrete math?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Perman7z
Step 1
The rat's sojourn time may be modeled by a Markov chain with transition matrix
$P=\left(\begin{array}{ccccc}0& \frac{1}{3}& \frac{1}{3}& 0& \frac{1}{3}\\ 0& 0& 0& 1& 0\\ 0& 1& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1\end{array}\right).$
Let Q be the matrix whose entries are the expected number of visits to a transient state starting from another transient state, then since $‖Q{‖}_{1}=\underset{1⩽i⩽t}{sup}\sum _{j=1}^{t}{Q}_{ij}=\frac{2}{3}<1$, the series
$N=\sum _{k=0}^{\mathrm{\infty }}{Q}^{k}$
converges to
$\left(\begin{array}{cccc}3& 2& 1& 2\\ 3& 3& 1& 3\\ 3& 3& 2& 3\\ 3& 2& 1& 3\end{array}\right).$
Step 2
The expected number of steps before being absorbed when starting in a transient state are given by the entries of the vector
$\mathbf{t}=N\mathbf{1}=\left(\begin{array}{c}8\\ 10\\ 11\\ 9\end{array}\right).$
It follows that the expected soujourn time is 8.

We have step-by-step solutions for your answer!