Let $\mathcal{P}$ be stochastic matrix of order n.
If there is $k > 0$ such that $\mathcal{P}^k(j, i) > 0$, then there is $r \leq (n-1)$ such that $\mathcal{P}^r(j, i) > 0$.
My attempt:
Define $A_1 = \{k \in \{1, \dots, n\} : \mathcal{P}(j, k) > 0\}$.
Then, if $i \in A_1$, we conclude the proof.
If $i \notin A_1$, there is some $m \in A_1$ such that $\mathcal{P}^{k-1}(m, i) > 0$.
I don't know if this kind of construction will take me somewhere. Can someone help me?
On
I got the answer!
Suppose there is no $r \in \{1, \dots, n-1\}$ such that $P^r(j, i) > 0$. So $r \geq n$ (we know there is some $r$ that it happens).
Then there are $i_1, \dots i_r$ such that
$0 < \leq P(j, i_1)P(i_1, i_2)\dots P(i_r, i)$.
As $r \geq n$, there is some $m_1$ and $m_2$ such that $i_{m_1} = i_{m_2}$. Then you can "cut" the path from $i_{m_1}$ to $i_{m_2}$. Doing that, you find a path from $j$ to $i$ with less than $n$ steps, as we want.
If $k\leq (n-1)$ you're done.
Otherwise, $k\geq n$. You know that it's possible to reach state $j$ from $i$ in at most $k$ steps with positive probability. By pigeon-hole principle, you have to visit at least one state twice in those $k$ steps (since $k\geq n$). If you now delete the loop to that path, you've necessarily reduced the number of steps to a path of length $k_2<k$. If still $k_2\geq n$, you can again delete the loop. It follows that after a finite number of deletions, you'll have a $k_r<n$, which completes the proof.