States visit order in a Markov chain

Question

Ok so we have a labyrinth with 6 possible states plus the exit position and we want to visit the state number 5, but not the death trap(6) and then exit the labyrinth through exit state, starting state is 1 as shown. The transition probabilities are given below:

$p_{exit/exit}=1 $ , $p_{66}=1 ,p_{12}=1 , p_{21}=p_{23}=1/2 , p_{32}=p_{34}=p_{35}=1/3,p_{43}=p_{47}=1/2,p_{56}=p_{53}=1/2$ Ok so i am trying really hard to calculate this. What i have so far is this(i think):

P(visit on exit before 6|$X_0=5$)

But i am really having a hard time calculating this probability since after position 5 we could visit positions 1,2,3 and 4 infinite times before we reach the exit positions. Any ideas?

Answer 1

[Expanding on Did’s comments]

Define $e_k = \Pr(\text{exits safely}\mid X_0=k)$. Using the usual method of conditioning on the first step, we compute $$e_3 = \sum_{k=1}^5\Pr(\text{exits without visiting 6}\mid X_1=k)\Pr(X_1=k\mid X_0=3).$$ By the Markov property, $\Pr(\text{exits safely}\mid X_1=k) = \Pr(\text{exits safely}\mid X_0=k)$, so we have $$e_3 = \frac13 e_2+\frac13 e_4+\frac13 e_5.$$ However, $e_2=e_3$ because the system must always enter state $3$ before exiting or hitting the trap, therefore $$e_3 = \frac13 e_3+\frac13 e_4+\frac13 e_5.$$ Similar calculations produce $e_4 = \frac12 e_3+\frac12$ and $e_5 = \frac12 e_3$. Solve the resulting system of linear equations for $e_5$.

Answer 2

This is related to the canonical form of Transition Matrix of absorbing Markov chains.

The general theory is as follows: Let $ P = \begin{pmatrix}Q&R\\0&I_r\\ \end{pmatrix}$ be a transistion matrix with have t transient states and r absorbing states,

where $Q$ is a t-by-t matrix, $R$ is a nonzero t-by-r matrix, $0$ is an r-by-t zero matrix, and $I_r$ is the r-by-r identity matrix.

Thus, Q describes the probability of transitioning from some transient state to another while R describes the probability of transitioning from some transient state to some absorbing state.

The value of $P^n$ is given by \begin{pmatrix}Q^n&(I-Q)^{-1}R\\0&I_r\\ \end{pmatrix}

The matrix $(I-Q)^{-1}$ is called the fundamental matrix $F$ and $FR$ gives the probability of eventual absorption into an absorbing state from a transient state.