Question

Let P be a \(3 \times 3\) Markov matrix and define \(\mu(\mathbf{P})=\max _{i_{1}, i_{2}, f}\left[P_{i_{1}, j}-P_{i_{2}, j}\right]\) Show that \(\mu(\mathbf{P})=1\) if and only if \(\mathbf{P}\) has the form $$ \left(\begin{array}{lll} 1 & 0 & 0 \\ 0 & p & q \\ r & s & t \end{array}\right) \quad(p, q \geq 0, p+q=1 ; \quad r, s, t \geq 0, r+s+t=1) $$ or any matrix obtained from this one by interchanging rows and/or columns.

Short answer

In summary, for a given 3x3 Markov matrix \(\mathbf{P}\), \(\mu(\mathbf{P})=1\) if and only if \(\mathbf{P}\) has the form: \[ \left(\begin{array}{lll} 1 & 0 & 0 \\ 0 & p & q \\ 0 & r & s \end{array}\right) \] where \(p, q, r, s \geq 0\) and \(p+q=1, r+s=1\), or any matrix obtained from this form by interchanging rows and/or columns. This was shown by first interpreting the definition of Markov matrix and μ(P), and then proving both directions of the "if and only if" statement.

Step-by-step solution

Understanding the definition of Markov matrix and μ(P)

A Markov matrix is a square matrix P with non-negative entries in which each row sums to 1, i.e., \(\sum_{j=1}^{n} P_{ij} = 1\) for each i. In this case, we are given a 3x3 Markov matrix. Furthermore, we are given the definition of μ(P) as: \[\mu(\mathbf{P})=\max _{i_{1}, i_{2}, f}\left[P_{i_{1}, j}-P_{i_{2}, j}\right]\] This means that μ(P) is the maximum difference between any two entries of P in the same column.

Prove that if μ(P) = 1, then P must have the specific form or a row/column interchanged version of that form

Suppose μ(P) = 1, then there exists two elements in the same column of P with the maximum difference of 1. WLOG, let this column be the first column and these two elements be P_11 and P_21. Now, since \(P_{11} - P_{21} = 1\), we must have either \(P_{11} =1\) and \(P_{21} = 0\), or \(P_{11} = 0\) and \(P_{21} = 1\). Let's assume \(P_{11} =1\) and \(P_{21} = 0\). Now, since the sum of each row in a Markov matrix must equal 1, we have: \(P_{12} + P_{13} = 0\) and \(P_{22} + P_{23} = 1\) The only possibility for the first equation is \(P_{12} = P_{13} = 0\). Then, since the sum of the elements in the second row equals 1, and \(P_{21} = 0\), we must have two non-negative numbers \(p\) and \(q\) such that \(P_{22} = p, P_{23} = q\) and \(p + q = 1\). Next, for the third row, since \(P_{31} = 1-P_{11} - P_{21} = 0\), there must be three non-negative numbers \(r,s,t\) such that \(P_{32} = r, P_{33} = s, P_{34} = t,\) and \(r + s + t = 1\). Thus, we get the specific form of P: \[\left(\begin{array}{lll} 1 & 0 & 0 \\ 0 & p & q \\ 0 & r & s \end{array}\right)\] where \(p,q,r,s \geq 0\) and \(p+q=1, r+s=1\). If we had started with \(P_{11} = 0\) and \(P_{21} = 1\), we would simply obtain the matrix with interchanged first two rows. Further interchanges of rows and/or columns result in other equivalent forms.

Prove that if P has the specific form or a row/column interchanged version, then μ(P) = 1

Suppose P has the specific form or a row/column interchanged version of that specific form. Then, it can be verified that the maximum difference between any two entries of P in the same column is 1. For example, if P has the form as given in Step 2, then the maximum difference in the first column is \(\max\{P_{11} - P_{21}, P_{11} - P_{31}, P_{21} - P_{31}\} = \max\{1 - 0, 1 - 0, 0 - 0\} = 1\). Similarly, one can verify that μ(P) = 1 for an interchanged row/column version of P. Hence, if P has the specific form or a row/column interchanged version, then μ(P) = 1. By completing these steps, we proved that μ(P) = 1 if and only if P has the specific form or any matrix obtained from this one by interchanging rows and/or columns.