Let r_ij(n)=P(X_n = j | X_0=i) be the n-step transition probability of a given homogeneous discrete-time Markov chain with m states. We have shown that r_ij(n) satisfies the following recursion for n>=2:

Question

r_ij(n) = sum_(k=1)^(m) r_ik(n-1)*p_kj
For each of the following, decide whether it is also a valid recursion formula for r_ij(n).

1. r_{ij}(n)=\sum _{k=1}^ m p_{ik}r_{kj}(n-1) for n>=2

2. r_{ij}(n)=\sum _{k=1}^ m r_{ik}(n-2)r_{kj}(2) for n>=3

3. r_{ij}(n)=\sum _{k=1}^ m \sum _{\ell =1}^ m r_{ik}(n-2)p_{k\ell }p_{\ell j} for n>=3

Answer 1

yes,
yes
yes