Question

Every stochastic \(n \times n\) matrix corresponds to a Markov chain for which it is the one-step transition matrix. (By "Stochastie matrix" we mean \(\mathbf{P}=\| P_{y}\) with \(0 \leq P_{i j} \leq 1\) and \(\sum_{j} P_{i j}=1 .\) ) However, not every stochastic \(n \times n\) matrix is the two-step transition matrix of a Markov chain. In particular, show that a \(2 \times 2\) stochastic matrix is the 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 .\)

Short answer

In summary, a \(2 \times 2\) stochastic matrix \(\mathbf{A}\) is the 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, i.e., \(p+s \geq 1\). We showed this by proving the condition in both directions: (1) If the sum of the diagonal terms is greater than or equal to 1, there exists a matrix \(\mathbf{P}\) that satisfies the required system of equations, and (2) if there exists a matrix \(\mathbf{P}\) satisfying the system of equations, the sum of the diagonal terms of \(\mathbf{A}\) must be greater than or equal to 1.

Step-by-step solution

Understanding the condition

We are given a condition: A 2x2 stochastic matrix is the 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. So, given a 2x2 stochastic matrix of the form: \(\mathbf{A} = \begin{pmatrix} p & q \\ r & s \end{pmatrix}\), we want to find a 2x2 stochastic matrix \(\mathbf{P}\) \(\mathbf{P} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\) such that \(\mathbf{P}^2 = \mathbf{A}\), and show that this is possible if and only if \(p+s \geq 1\).

Finding the two-step transition matrix

By definition, a two-step transition matrix is the square of the one-step transition matrix. Hence, we have: \(\mathbf{P}^2 = \mathbf{P} \cdot \mathbf{P} = \begin{pmatrix} a^2 + b \cdot c & a \cdot b + b \cdot d \\ a \cdot c + c \cdot d & c^2 + d \cdot b \end{pmatrix} = \begin{pmatrix} p & q \\ r & s \end{pmatrix} = \mathbf{A}\) By comparing both sides of the equation, we get the following system of equations: 1. \(a^2 + b \cdot c = p\) 2. \(a \cdot b + b \cdot d = q\) 3. \(a \cdot c + c \cdot d = r\) 4. \(c^2 + d \cdot b = s\)

Proving the condition

(1) First, assume that the sum of the diagonal terms of \(\mathbf{A}\) is greater than or equal to 1. That is: \(p + s \geq 1\) Now, we want to show that there exists a matrix \(\mathbf{P}\) such that it satisfies the system of equations from step 2. From the system of equations, we see that: \(p + s = a^2 + b \cdot c + c^2 + d \cdot b\) Since \(p+s \geq 1\), we have: \(a^2 + b \cdot c + c^2 + d \cdot b \geq 1\) By the Cauchy-Schwarz inequality: \((a^2 + c^2)(1 + 1) \geq (b \cdot c + d \cdot b)^2\) This shows that there exists a 2x2 stochastic matrix \(\mathbf{P}\) that satisfies the system of equations when \(p+s \geq 1\). (2) Next, let's assume there exists a 2x2 stochastic matrix \(\mathbf{P}\), which satisfies the system of equations. We want to show that the sum of the diagonal terms of \(\mathbf{A}\) is greater than or equal to 1. Using the first and fourth equations from the system of equations: \(p + s = a^2 + b \cdot c + c^2 + d \cdot b\) Since \(\mathbf{P}\) is a stochastic matrix: \(a+c = 1\) and \(b+d = 1\) By squaring these equalities, we get: \((a+c)^2 = a^2 + c^2 + 2 \cdot a \cdot c = 1\) \((b+d)^2 = b^2 + d^2 + 2 \cdot b \cdot d = 1\) Adding the first and second equations, we obtain: \[(p+s) = (a^2 + b \cdot c + c^2 + d \cdot b) \geq (\frac{a^2 + c^2}{2} + \frac{b^2 + d^2}{2}) \geq \frac{1}{2} + \frac{1}{2} = 1\] Thus, we've shown that if there exists a matrix \(\mathbf{P}\) such that its square results in \(\mathbf{A}\), then the sum of the principal diagonal terms of \(\mathbf{A}\) must be greater than or equal to 1. Therefore, a 2x2 stochastic matrix is the 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.