The Problem: Prove that if the number of States in a Markov Chain is M, and that state j can be reached from state i, then it can be reached in M steps or less.
The work: I assumed by contradiction that state i can reach state j more than M steps. We know that state i can reach to state j with a positive probability.Do I have to do cases in which we assume the Markov chain is irreducible or regular?
To be honest, I have no idea how to start with this proof. Can you guys give me some hints in order for me to understand how to complete this proof?
Thank you for all of your help.
Let $p_{ij}^{(n)}$ denote the probability that $P(X_n=j|X_0=i)$. We know that $S:=\{n\mid p_{ij}^{(n)}>0\}\neq \emptyset$. We have to show $\min S=M$ Suppose $\min S=k>M$. Then $p_{ij}^{(k)}>0$. Therefore there exist states $r_1,r_2,\ldots,r_{k-1}$ such that $$p_{ir_1}p_{r_1r_2}\cdots p_{r_{k-1}j}>0$$ Now among the $k$ steps $r_0:=i,r_1,r_2,\ldots,r_{k-1}$, we must have $r_m=r_n$ for some $m< n$ since $k>M$. But then $$p_{r_0r_1}\cdots p_{r_{m-1}r_m}p_{r_nr_{n+1}}\cdots p_{r_{k-1}j}>0\implies p_{ij}^{(k-n+m)}>0$$ Therefore $k-n+m\in S$ but $k-n+m<k$. This is a contradiction. Therefore $k\le M$