4
$\begingroup$

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

2 Answers 2

6

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

  • 1
    See http://math.stackexchange.com/questions/31174/logarithm-of-a-markov-matrix/31184#31184 for related questions.2011-04-12
3

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.

  • 0
    About $n$th roots of Markov matrices, see the recent thread http://math.stackexchange.com/questions/31174. (And thanks for the kind words.)2011-04-17