Condition for a stochastic matrix to be a second order transition probability matrix of a DTMC.

Question

Let $A$ be a $2\times 2$ stochastic matrix $$A=\left( \begin{array}{cc} 1-a & a \\ b & 1-b\\ \end{array}\right). $$ Then A is a second order transition probability matrix of a DTMC, i.e. there is a DTMC with probability matrix P such that $P^{2}=A$ iff $a+b\leq 1$.

Attempt. The desired property holds iff $$A=\left( \begin{array}{cc} 1-a & a \\ b & 1-b\\ \end{array}\right) = \left( \begin{array}{cc} 1-p & p \\ q & 1-q\\ \end{array}\right)^2 $$ for some $p,~q\in [0,1]$, that is $a=2p-pq-p^2,~b=2q-pq-q^2$ for some $p,~q\in [0,1]$. I am not sure how this leads to the equivalent desired condition $a+b\leq 1$.

Thank you in advance.

Answer 1

If $a = 2p - pq - p^2$ and $b = 2q - pq - q^2$, then we can add these together to get $$a+b = 2p+2q - 2pq - p^2 - q^2 = 2(p+q) - (p+q)^2 = (p+q)(2-p-q).$$ But $x(2-x)$ is at most $1$ for any $x$, so $a+b$ can be at most $1$. We could also be clever with our algebra and write $$a+b = 2p+2q - 2pq - p^2 - q^2 = 1 - (p+q-1)^2$$ from which you can see that $a+b$ can be at most $1$, and is only exactly $1$ when $p+q=1$.

---

That's half of the implication; the other half is trickier, because it requires you to solve these two equations for $p$ and $q$. However, notice that $$\frac{a}{b} = \frac{2p-pq-p^2}{2q-pq-q^2} = \frac{p}{q}.$$ So we can take one of these equations and write it as $$a = 2p - p\left(\frac ba \cdot p\right) - p^2 \implies \left(1 + \frac ba\right)p^2 - 2p + a = 0$$ which is a quadratic equation with solutions $$p = \frac{2 \pm \sqrt{4 - 4a - 4b}}{2 + \frac{2b}{a}} \implies p = \frac{a}{a+b}\left(1 \pm \sqrt{1-a-b}\right).$$ So we can always solve for $p$ and get a real number if $a+b \le 1$.

Answer 2

Your equations imply \begin{align*} a + b = (1-p)(p+q) + (1-q)(p+q), \end{align*} maximising the function $$ F(p,q) = (1-p)(p+q) + (1-q)(p+q) $$ over the unit square, formally using Lagrangian multipliers or by heuristically guessing straight from symmetry this is maximised on the set $ p + q = 1$ and so $$ a + b = F(p,q) \leq 1. $$ Edit I have run out of time a little and I hope to come back to this but this is what I have so far for showing the equivalence in the other direction, it needs more work and also handling of the degenerate cases where $a$ or $b$ is equal to zero, I have posted it in the hope it will still help.

Let $$ A = \begin{pmatrix} 1 - a & a \\ b & 1-b \end{pmatrix} $$ then we can we find the eigenvalue, eigenvector pairs $$ \lambda_1 = 1,\; \; v_1 = 1 $$ and $$ \lambda_2 = 1 - (a+b), \; \; v_2 = (-\frac{a}{b}, 1) $$ so we can use the usual spectral decomposition to write $A$ as $$ A = \mathbf{V}\mathbf{D}\mathbf{V}^{-1} $$ now assuming $a+b \leq 1$ we have \begin{align} P &= \begin{pmatrix} 1 & -\frac{a}{b} \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \sqrt{1 - (a+b)} \end{pmatrix} \begin{pmatrix} 1 & -\frac{a}{b} \\ 1 & 1 \end{pmatrix}^{-1} \\ &= \begin{pmatrix} 1 & -\frac{a}{b} \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & \sqrt{1 - (a+b)} \end{pmatrix}\frac{1}{a+b} \begin{pmatrix} b & a \\ -b & b \end{pmatrix} \\ \end{align} Working all this through gives $$ \begin{bmatrix} \frac{a}{a+b}\sqrt{1-(a+b)} + \frac{b}{a+b} & \frac{a}{a+b} - \frac{a}{a+b}\sqrt{1-(a+b)}\\ \frac{b}{a+b} - \frac{b}{a+b}\sqrt{1-(a+b)} & \frac{b}{a+b}\sqrt{1-(a+b)} + \frac{a}{a+b} \end{bmatrix} $$ which after a bit of checking a tidying should be equivalent to a matrix of the form $$ \begin{pmatrix} p & 1 - p \\ 1 - q & q \end{pmatrix}. $$