3

enter image description here

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?

Community
  • 1
Mario Zelic
  • 319
  • "Any ideas?" Yes: compute $e_x=P(\text{exits without visiting}\ 6\mid X_0=x)$ for every $x$ in ${3,4,5}$, these solve a linear system and you are after $e_5$. – Did Jan 22 '18 at 23:11
  • 1
    For example, $e_5=\frac12e_3$ (why?), $e_3=\frac13e_3+\frac13e_4+\frac13e_5$ (why?) and $e_4=\frac12+\frac12e_3$ (why?), hence... – Did Jan 22 '18 at 23:14
  • Why we don't need the $e_1,e_2$?? Plus i don't quite understand how the above linear system is constructed... – Mario Zelic Jan 22 '18 at 23:39
  • Markov property after one step of the chain. And $e_1$ and $e_2$ are not needed since after a step $3\to2$ one must pass by $3$ again before exiting the labyrinth or visiting $6$. – Did Jan 22 '18 at 23:58
  • Did you apply the general theory in the answer you accepted, to compute the desired mean exit time? How did it go? – Did Jan 24 '18 at 17:58

2 Answers2

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.

honeybadger
  • 1,125
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$.

amd
  • 53,693