Consider as probability matrix a matrix $M \in [0,1]^{n \times n}$ while every row sums up to $1$.

Statement: Consider a $2\times 2$ probability matrix $M' \in [0,1]^{2 \times 2}$. Show, that the following holds: $$\exists \text{ probability matrix } M : M^2 = M' \iff \operatorname{Trace}(M') \geq 1$$

I showed $\implies$, i.e. when $M'$ is square of another probability matrix, then one can show, that the trace must be greater or equal to one.

But I got stuck at the $\impliedby$ part. Any tipps?

So far considering user68061's answer: Let $M' = \begin{pmatrix} x & (1-x) \\ (1-y) & y \end{pmatrix}$ and $M = \begin{pmatrix} a & (1-a) \\ (1-b) & b \end{pmatrix}$, then $M^2 = \begin{pmatrix} a^2+(1-a)(1-b) & a(1-a)+b(1-a) \\ a(1-b)+b(1-b) & b^2+(1-a)(1-b)\end{pmatrix}$.

Hence we need to solve

$x = a^2+(1-a)(1-b),\ y=b^2+(1-a)(1-b)$ where $x+y \geq 1$.

But somehow I think I am missing the trickery in calculation to get this solution..can you help?

  • $\begingroup$ Anyone knows this trickery? Or a neat solution which is not brute force? $\endgroup$ – merkenN Jan 12 '14 at 20:42

I don't know the nice way to do it, but you can brute force it. Consider probability matrix $ \left( \begin{array}{cc} a & 1-a \\ b & 1-b \\ \end{array} \right) $ is a probability matrix $ \left( \begin{array}{cc} a^2+b(1-a) & a(1-a)+(1-a)(1-b) \\ ab+b(1-b) & b(1-a)+(1-b)^2 \\ \end{array} \right) $. So you need to show, that the equation $x=a^2 + b(1-a); y=b(1-a)+(1-b)^2$ has a solution in $a,b$ for $x+y \geq 1$. This can be solved directly (look at $x+y$, find $a-b$ then just substitute to the first equation)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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