Suppose $P$ is the transition matrix of some homogeneous finite Markov chain with state space $Ω=\{1,2,…,n\}$, then $P(x,y)$ is the probability that the next state is $y$ if the current state is $x$. $P$ has a directed graph representation. Define a graph $G=(V,E)$ with $V=Ω$ and $E⊆Ω×Ω$, and let $(x,y)∈E$ iff $P(x,y)>0$. Suppose $P = \left( {\begin{array}{*{20}{c}} 0&{0.5}&{0.5}\\ 0&{0.5}&{0.5}\\ 0&{0.5}&{0.5} \end{array}} \right)$, the corresponding graph $G$ is like
Now the question is to prove,
$P^r (x,y)>0$ iff there exists a path in $G$ (may contain duplicate edges) of length $r$ from $x$ to $y$.
Here $P^r (x,y)>0$ is the element at $x$th row and $y$th column of $P^r$. Anyone can help prove this very intuitive theorem? Thank you!
It seems straightforward.
If $P^r(x,y)>0$ then there's a path of $r$ edges between $x$ and $y$, since each edge is given by $P(x,y)$, where it's a directed edge between $x$ and $y$, then the chance of arriving from $x$ to $y$ after $r$ steps where you start at $2$ or $3$ is $P^r(x,y) = (0.5)^r$, and if $x$ is 1 then the probability is zero for $r>1$, and $0.5$ for $r=1$.
This arguement also proves the claim for the other direction for this matrix.
If you want to prove the general theorem I don't think this claim is true, you would need to use Kolmogorov-Chapman identity: