Support relation for Markov chain

Question

Let $X$ be a finite set and suppose that for all $x \in X$, $P_x$ is a probability measure on $X$ (so we have a Markov transition).

We can define a relation $R$ on $X$ by $xRy$ if and only if $P_x(y)>0$.

Is it true that if $R$ is transitive, then for all $x,y$ $$P_x(y) = \sum_{w \in X}P_w(x)P_x(w) = E_{P_x}(P(y)),\tag{1}$$ where the last term means the expectation of $w \mapsto P_w(y)$ with respect to $P_x$?

(Note that $R$ is transitive just in case $xRy$ and $yRz$ imply $xRz$.)

I have verified that the answer is yes in case $P_x(y)=0$ or $1$, but I am stuck on the case $0<P_x(y)<1$. I have also observed that (1) is equivalent to $$E_{P_x}(f) = E_{P_x}(E_P(f))$$ for all random variables $f$, but I'm not sure this is helping. I think I might be missing a simple calculation trick, so any hints are appreciated.

Answer 1

Let $M$ denote the square matrix indexed by $X$ and with $(x,y)$ entry equal to $P_x(y)$. You asked:

Is it true that if $R$ is transitive, then for all $x,y$ $$P_x(y) = \sum_{w \in X}P_w(y)P_x(w)?$$

(Note that I have fixed a typo and removed the unnecessary part.)

By the definition of matrix multiplication, your question is equivalent to the following:

Is it true that if the non-zero entries of a stochastic matrix $M$ form a transitive relation, then $$ M=M^2\tag{2}? $$ (A stochastic matrix is a matrix whose rows sum to $1$ and whose entries are non-negative, i.e., a matrix that can arise as the transition matrix of a markov chain.)

Phrased this way, it is clear that the answer is "no" in general. Here is an explicit counterexample:

$$ M=\frac{1}{4}\begin{pmatrix}2&2\\3 & 1\end{pmatrix}. $$ Indeed, $M$ is the transition matrix for a Markov chain with states $\{1,2\}$ such that from $1$ we flip a fair coin to decide whether to move or stay, and from $2$ we flip a biased coin such that we only have a one in four chance to stay put. Moreover, we calculate that $$ M^2=\frac{1}{16}\begin{pmatrix}10&6\\9 & 7\end{pmatrix}\not=M. $$

Finally, note that the condition you have verified (when $P_x(y)\in\{0,1\}$ for all $x,y$) is equivalent to saying that $M$ is a $\{0,1\}$-matrix, which (since all rows sum to $1$ and all entries are non-negative) forces $M$ to be a permutation matrix. In particular $M$ is invertible (since every permutation has an inverse), so we can cancel an $M$ from both sides of $(2)$ to see that $M$ is the identity matrix - so it is way too restrictive of a condition to be interesting!