# Characterization of two-step 2x2 stochastic matrices

Show that:

A 2 x 2 stochastic matrix is two-step transition matrix of a Markov chain if and only if the sum of its principal diagonal terms is greater than or equal to $1$.

-

Encode the Markov matrix $\begin{pmatrix}1-a & a\\ b & 1-b\end{pmatrix}$ by the couple $(a,b)$ with $a$ and $b$ between $0$ and $1$. The square of this matrix is encoded by the couple $$(a(2-a-b),b(2-a-b)),$$ hence the question is to determine for which $a$ and $b$ between $0$ and $1$, there exists $x$ and $y$ between $0$ and $1$ such that $$a=x(2-x-y),\qquad b=y(2-x-y).$$ If $x$ and $y$ exist, their sum $s$ solves $s(2-s)=a+b$ hence $(s-1)^2=1-a-b$, in particular $$a+b\le1.$$ Assume this condition holds. Then $s=1\pm\sqrt{1-a-b}$, hence $$x=a/(2-s)=a/(1\mp\sqrt{1-a-b}),$$ and $$y=b/(2-s)=b/(1\mp\sqrt{1-a-b}).$$ Since $1+\sqrt{1-a-b}$ is between $1$ and $2$, at least the choice $+$ in $\mp$ yields solutions $x$ and $y$ between $0$ and $1$.

Finally the Markov matrix $\begin{pmatrix}1-a & a\\ b & 1-b\end{pmatrix}$ is the square of a Markov matrix if and only if $$a+b\le1.$$

-
See math.stackexchange.com/questions/31174/… for related questions. – Did Apr 12 '11 at 20:23
Thanks a lot! – kira Apr 13 '11 at 4:08

Updated: I've revived my answer with an alternative solution. Despite Didier's excellent direct solution to the problem, I think there may be some benefit for students to also see the spectral point of view.

Begin with a two by two Markov matrix $P=\pmatrix{1-a&a\cr b&1-b}$ for any $0\leq a,b\leq 1$.

Every Markov matrix has eigenvalue 1 (with the eigenvector of all ones). The trace of our matrix $2-(a+b)$ is the sum of the eigenvalues so the other eigenvalue must be $\lambda:=1-(a+b)$. This eigenvalue satisfies $-1\leq \lambda \leq 1$. Our problem is to show that $P\$ has a Markov square root if and only if $\lambda\geq 0$.

## Sufficiency

The other eigenvalue of $P^2$ is $\lambda^2\geq 0$.

## Necessity

If $a+b=0$ then $P\$ is the identity matrix and the problem is trivial.

If $a+b\neq 0$, then we can diagonalize the matrix as $$P= \pmatrix{1&-a\cr 1&b} \pmatrix{1&0\cr 0&\lambda} \pmatrix{{b\over a+b}&{a\over a+b}\cr {-1\over a+b}&{1\over a+b}}$$ so that
\begin{eqnarray*} \sqrt{P} &=& \pmatrix{1&-a\cr 1&b} \pmatrix{1&0\cr 0&\sqrt{\lambda}} \pmatrix{{b\over a+b}&{a\over a+b}\cr {-1\over a+b}&{1\over a+b}}\cr &=& \pmatrix{\displaystyle{b+a\sqrt{\lambda} \over a+b}&\displaystyle{a(1-\sqrt{\lambda})\over a+b}\cr \displaystyle {b(1-\sqrt{\lambda} )\over a+b}&\displaystyle{a+b \sqrt{\lambda}\over a+b}}. \end{eqnarray*}

In fact $P\$ has two square roots of this type depending on which square root of $\lambda$ we take. If $0\leq \lambda\leq 1$, then one of its square roots satisfies $0\leq \sqrt{\lambda}\leq 1$ and this choice gives a Markov matrix $\sqrt{P}$ by the above formula. The other square root of $P\$ might also be Markov, or it might have some negative values.

Note that the diagonalization argument immediately shows the more general result that if $\lambda\geq 0$, then $P\$ is an $n$-step Markov transition matrix for any $n\geq 1$.

Granted, the two state Markov chain is especially simple as the transition matrix is always diagonalizable. This will fail, in general, even for three state chains. Nevertheless, the analysis of a Markov chain via the eigenvalues of its transition matrix is a powerful and important tool. I think every student should be exposed to this idea.

-
Pointing the OP to the square root of a transition matrix is unneeded and too difficult (note that you would want the square root to be a transition matrix as well and that this is not always true, see math.stackexchange.com/questions/31174/… for related problems). It seems to me that here, brute force is the way to go: parametrize $P$ by its two off-diagonal coefficients and write these as functions of the off-diagonal coefficients of $P^2$, this yield easily a necessary and sufficient condition. – Did Apr 12 '11 at 19:43
@Didier You are right. If you write up your comment as an answer, I'll delete mine. – Byron Schmuland Apr 12 '11 at 19:56
Done. If you could check my answer... – Did Apr 12 '11 at 20:22
About $n$th roots of Markov matrices, see the recent thread math.stackexchange.com/questions/31174. (And thanks for the kind words.) – Did Apr 17 '11 at 17:48