Consider again the Markov chain with the following transition probability graph:

Question

This figure depicts a Markov chain with nine states, 1 through 9, which are represented as circles. In this figure, transitions are depicted by arrows from a circle (representing the source) to a circle (representing the destination); the source and the destination may be the same. The states 1, 2, 9, 3, and 4 are arranged in a row in this order at the upper-middle of the figure, while 5, 6, 7, and 8 are in the row below it. Above the first row of states are self-loops-arrows, which are circular arrows with both the tail and the head at the same state. There are arrows within states 1, 2, 9, 3, and 4; the self-loops for states 1, 2, 9, and 3 are labelled with the probability 1/3, while the self-loop for state 4 is labelled with the probability 1/4. Between the circles representing the states are transitions between consecutive circles in the row. There is an arrow from state 1 to 2 labelled with probability 5/9, from 2 to 9 with probability 2/3, from 9 to 3 with probability 2/3. There are also arrows from both 3 to 4 and from 4 to 3, with probabilities 1/3 and 1/2, respectively. Directly below the circle of state 1 there is state 5, and state 6 is at the immediate right of state 5. The transition from 1 to 5 has probability 1/9. Within states 5 and 6, state 5 has a self-loop arrow with label 3/4, state 6 has a self-loop arrow with label 1/3, the transition from 5 to 6 has probability 1/4 and from 6 to 5 has probability 2/3. The circle of state 7 is directly below state 3, and state 8 directly below state 4; both connected by arrows. States 7 and 8 are on the same row as 5 and 6. The transition from states 3 to 7 has probability 1/3 and from 4 to 8 has probability 1/4. There are self-loops arrows within states 7 and 8, both with probability 1.
Assuming that X0=9, what is the expected time until the Markov chain eventually reaches states 7 or 8?

Answer 1

To find the expected time until the Markov chain reaches states 7 or 8 starting from state 9, we can define the following system of equations:

Let Ei denote the expected time until reaching states 7 or 8 starting from state i.

E9 = 1 + (2/3)E3
E3 = 1 + (1/3)E7
E7 = 1

Substitute E7 = 1 into the equation for E3:

E3 = 1 + (1/3)(1) = 4/3

Substitute E3 = 4/3 into the equation for E9:

E9 = 1 + (2/3)(4/3) = 11/3

So, the expected time until the Markov chain eventually reaches states 7 or 8 starting from state 9 is 11/3 or approximately 3.67 time steps.