Hint for Markov chain problem

Question

Prove that if a Markov Chain has $M$ states and if state $j$ can be accessed from state $i$, then it can be reached in $M$ steps or less. I am trying to show if $P_{ij}^n = 0$ for all $n \leq M$ then $P_{ij}^n = 0$ for all natural numbers. I am trying to figure out how to "decompose" $n > M$ into factors less than M, but the fact that this is matrix multiplication makes it harder.

Answer 1

Hint. It seems that you can proceed by using a pigeonhole argument of sorts:

Proposition: Any minimal path from $i$ to $j$ must not contain any state more than once. Argument: Suppose the minimal path from $i$ to $j$ contains some state $k$ (at least) twice. Then, because the process is memoryless, the path of the process after the last entry to $k$ could have taken after the first entry to $k$, avoiding re-entry into $k$.

Since there are only $M$ states in all, and no state need be entered more than once, the minimal path from $i$ to $j$ (assuming it exists) requires no more than $M$ steps (including initial and final state).