Example 4.5.1 showed how to find the expected first passage times to a fixed state, say 1, from all other nodes. It is often desirable to include the expected first recurrence time from state 1 to...

Example 4.5.1 showed how to find the expected first passage times to a fixed state, say 1, from all other nodes. It is often desirable to include the expected first recurrence time from state 1 to return to state 1. This can be done by splitting state 1 into 2 states, first an initial state with no transitions coming into it but the original transitions going out, and second, a final trapping state with the original transitions coming in.

a) For the chain on the left side of Figure 4.6, draw the graph for the modified chain with 5 states where state 1 has been split into 2 states.

b) Suppose one has found the expected first-passage-times v_j
for states j = 2 to 4 (or in general from 2 to M). Find an expression for v₁, the expected first recurrence time for state 1 in terms of v₂, v₃, . . . v_M
and P₁₂, . . . , P_1M.

Example 4.5.1

(Expected first-passage time). First-passage times, i.e., the number of steps taken in going from one given state, say i, to another, say 1, are frequently of interest for Markov chains, and here we solve for the expected value of this random variable. Since the first-passage time is independent of the transitions after the first entry to state 1, we can modify the chain to convert the final state, say state 1, into a trapping state (a trapping state i is a state from which there is no exit, i.e., for which P_ii
= 1). That is, we modify P11 to 1 and P1j to 0 for all j ≠ 1. We leave P_ij
unchanged for all i ≠ 1 and all j (see Figure 4.6). This modification of the chain will not change the probability of any sequence of states up to the point that state 1 is first entered.