Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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. $$

share|improve this answer
1  
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.