For a markov chain, suppose $a, b, c, d$ are any 4 states and $x, y, z$ are periods $\ge 0$
Show that $P_{ad}^{x+y+z} \ge P_{ab}^{x}P_{bc}^{y}P_{cd}^{z}$
The notation reads: $P_{ab}^{x}$ is the probability of going from states $a$ to $b$ in $x$ periods. $P$ is the probability transition matrix and $S$ is the state space. $a,b,c,d \in S$
I use matrix multiplication technique.
The left hand side can be rewritten: $P_{ad}^{x+y+z} = (P^xP^yP^z)_{ad}$
Replicating matrix multiplication of $P^xP^yP^z$ thru summation (not sure if this is correct):
$$\sum_{f = 1}^s(\sum_{t = 1}^{s}P_{at}^xP_{tf}^y)P_{fd}^r$$
where $f \text{ and } t$ are indices of summation (add up all the states of these $s$ x $s$ matrices).
And since $b \in t$ and $c \in f$
we can say: $$\sum_{f = 1}^s(\sum_{t = 1}^{s}P_{at}^xP_{tf}^y)P_{fd}^r \ge P_{ab}^{x}P_{bc}^{y}P_{cd}^{z}$$
My main problem is not understanding if the double summation is written correctly. Please explain in any case.