Problem: Prove that if the number of states in a Markov Chain is $M$, and if state $j$ can be reached from state $i$, then it can be reached in $M$ steps or less.
I'm attempting to prove this by induction on $M$ (I realize there are other, perhaps, 'better' ways of doing it), but I'm stuck and unsure if it will work out. Here's what I have so far:
Base case: if $M=1$, then there is one state which can reach itself in $0 \leq 1=M$ steps.
Induction: Assume that for a Markov chain with $M$ states, where $1\leq M \leq k$, if $i$ can reach $j$ then it can do so in $M$ steps or less, and suppose we have a chain with $M=k+1$ states where state $i$ can reach state $j$. If $i$ can reach $j$ in one step, i.e. $P_{ij}>0$, we are done. Otherwise, suppose the shortest path $i$ can take to reach $j$ is $$i \rightarrow \ell_1 \rightarrow \ldots \rightarrow \ell_{n-1} \rightarrow j.$$ If we restrict our state space so that it excludes $j$, then we have a chain with $M-1$ states, where (assuming $i$ can still reach $j$) we know that $i$ can reach $\ell_{n-1}$ in $M-1$ steps or less, by the inductive hypothesis. It follows that $i$ can reach $j$ by taking at most $M-1$ steps to $\ell_{n-1}$, plus one more step to $j$, which is a total of at most $M$ steps.
For this to work, we need $\ell_{n-1}$ to still be reachable from $i$ in the smaller Markov chain. Is there a way we can guarantee this? Thanks!
