Show that every Markov chain with M <>∞ states contains at least one recurrent set of states. Explaining each of the following statements is sufficient.

(a) If state i1 is transient, then there is some other state i2 such that i1 → i2 and i2 /→ i1.

(b) If the i2 of (a) is also transient, there is a third state i3 such that i2 → i3, i3 /→ i2; that state must satisfy i3 /= i2, i3 /= i1.

(c) Continue iteratively to repeat (b) for successive states, i1, i2, ... . That is, if i1, ... , ik are generated as above and are all transient, generate ik+1 such that ik → ik+1 and ik+1 /→ ik. Then ik+1 /= ij for 1 ≤ j ≤ k.

(d) Show that for some k ≤ M, k is not transient, i.e., it is recurrent, so a recurrent exists.

Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.