DATA 605 Week10 Discussion

Absorbing Markov Chains (Chapter 11 - Section 11.2) - Question 9

Solution:

To reach from State-1 to State-5, there are many possible ways:

\(1\) \(step\) \(\Rightarrow\) \(\left[ 1 \rightarrow 5 \right]\)
\(2\) \(step\) \(\Rightarrow\) \(\left[ 1 \rightarrow (2, 3, 4) \rightarrow 5 \right]\)
\(3\) \(step\) \(\Rightarrow\) \(\left[ 1 \rightarrow (2, 3) \rightarrow 4 \rightarrow 5 \right]\)
\(4\) \(step\) \(\Rightarrow\) \(\left[ 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \right]\)

Let \(E\) represent the number of steps

\(E\) (\(1\) \(step\)) \(=\) \(1.(\frac{1}{4})\) = \(\frac{1}{4}\)
\(E\) (\(2\) \(step\)) \(=\) \(2.(\frac{1}{4}.\frac{1}{3}+\frac{1}{4}.\frac{1}{2}+\frac{1}{4}.1)\) = \(\frac{11}{12}\)
\(E\) (\(3\) \(step\)) \(=\) \(3.(\frac{1}{4}.\frac{1}{3}.1 + \frac{1}{4}.\frac{1}{3}.\frac{1}{2}+ \frac{1}{4}.\frac{1}{2}.1)\) = \(\frac{3}{4}\)
\(E\) (\(4\) \(step\)) \(=\) \(4.(\frac{1}{4}.\frac{1}{3}.\frac{1}{2}.1)\) = \(\frac{1}{6}\)

Exptected number of steps to go from State-1 to State-5 is:

\(E\) (\(1\) \(step\)) + \(E\) (\(2\) \(step\)) + \(E\) (\(3\) \(step\)) + \(E\) (\(4\) \(step\))

(\(\frac{1}{4}\) + \(\frac{11}{12}\) + \(\frac{3}{4}\) + \(\frac{1}{6}\)) = (\(\frac{3}{12}\) + \(\frac{11}{12}\) + \(\frac{9}{12}\) + \(\frac{2}{12}\)) = \(\frac{25}{12}\) = \(2.0833\)

Therefore the expected number of steps to reach state five is \(2.0833\)