A square matrix is called a stochastic matrix if all of its elements satisfy 0= pi, j = 1 and, furthermore

for all i. Every stochastic matrix is the transition probability matrix for some Markov chain; however, not every stochastic matrix is a valid two- step transition probability matrix. Prove that a 2 × 2 stochastic matrix is a valid two- step transition probability matrix for a two- state Markov chain if and only if the sum of the diagonal elements is greater than or equal to 1.

Pij