(Proof of Theorem 4.2.11) (a) Show that an ergodic Markov chain with M states must contain a cycle with τ <>M states. Hint: Use ergodicity to show that the smallest cycle cannot contain M states.
(b) Let .e be a fixed state on this cycle of length τ . Let T (m) be the set of states accessible from .e in m steps. Show that for each m ≥ 1, T (m) ⊆ T (m + τ ). Hint: For any given state j ∈ T (m), show how to construct a walk of m + τ steps from .e to j from the assumed walk of m steps.
(c) Define T (0) to be the singleton set {.e} and show that T (0) ⊆ T (τ ) ⊆ T (2τ ) ⊆ ··· ⊆ T (nτ ) ⊆ ··· .
(d) Show that if one of the inclusions above is satisfied with equality, then all subsequent inclusions are satisfied with equality. Show from this that at most the first M - 1 inclusions can be satisfied with strict inequality and that T (nτ ) = T ((M - 1)τ ) for all n ≥ M - 1.
(e) Show that all states are included in T ((M - 1)τ ).
(f) Show that P(M-1)2+1 > 0 for all i, j.
Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.