Lecture 8 Notes: Markov Eigenvalues and Eigenvectors

6.262: Discrete Stochastic Processes 2/28/11 Lecture 8: Markov eigenvalues and eigenvectors Outline: • Review of ergodic unichains • Review of basic linear algebra facts • Markov chains with 2 states • Distinct eigenvalues for M > 2 states • M states and M independent eigenvectors • The Jordan form Recall that for an ergodic finite-state Markov chain, the transition probabilities reach a limit in the sense n = π where � that limn→∞ Pij π = (π1, . . . , πM) is a j strictly positive probability vector. Multiplying both sides by Pjk and summing over j, πk = lim n→∞ � j nP = Pij jk � πj Pjk j Thus � π is a steady-state vector for the Markov chain, i.e., � π=� π [P ] and � π ≥ 0. π where �e = (1, 1, . . . , 1)T In matrix terms, limn→∞[P n] = �e� is a column vector and � π is a row vector. The same result almost holds for ergodic unichains, i.e., one ergodic class plus an arbitrary set of tran­ sient states. The sole difference is that the steady-state vector is positive for all ergodic states and 0 for all transient states.   [PT ] [P ] =  [0]  [PT R]   [PR] where  P11 · · · [PT ] =  · · · · · · Pt1 . . .  P1t ···  Ptt The idea is that each transient state eventually has a transition (via [PT R]) to a recurrent state, and the class of recurrent states lead to steady state as before. Review of basic linear algebra facts Def: A complex number λ is an eigenvalue of a real square matrix [A], and a complex vector �v �= 0 is a right eigenvector of [A], if λ�v = [A]�v . For every stochastic matrix (the transition matrix of � a finite-state Markov chain [P ]), we have j Pij = 1 and thus [P ]�e = �e. Thus λ = 1 is an eigenvalue of an arbitrary stochas­ tic matrix [P ] with right eigenvector �e. An equivalent way to express the eigenvalue/eigenvector equation is that [P − λI]�v = 0 where I is the identity matrix. Def: A square matrix [A] is singular if there is a vector �v �= 0 such that [A]�v = 0. Thus λ is an eigenvalue of [P ] if and only if (iff) � 0. [P − λI] is singular for some �v = Let �a1, . . . , �aM be the the columns of [A]. Then [A] is singular iff �a1, . . . , �aM are linearly dependent. The square matrix [A] is singular iff the rows of [A] are linearly dependent and iff the determinant det[A] of [A] is 0. Summary: λ is an eigenvalue of [P ] iff [P − λI] is singular, iff det[P − λI] = 0, iff [P ]�v = λ�v for some � 0, and iff � � 0. �v = u[P ] = λ� u for some � u= For every stochastic matrix [P ], [P ]�e = �e and thus [P − I] is singular and there is a row vector π �= 0 such that � π [P ] = � π. This does not show that there is a probability vector � π such that � π [P ] = � π , but we already know there is such a probability vector (i.e., a steady-state vector) if [P ] is the matrix of an ergodic unichain. We show later that there is a steady-state vector π for all Markov chains. The determinant of an M by M matrix can be de­ termined as det A = � µ ± M � Ai,µ(i) i=1 where the sum is over all permutations µ of the integers 1, . . . , M. Plus is used for each even per­ mutation and minus for each odd. The important facet of this formula for us is that det[P − λI] must be a polynomial in λ of degree M. Thus there are M roots of the equation det[P −λI] = 0, and consequently M eigenvalues of [P ]. Some of these M eigenvalues might be the same, and if k of these roots are equal to λ, the eigenvalue λ is said to have algebraic multiplicity k. Markov chains with 2 states π1P11 + π2P21 = λπ1 π1P12 + π2P22 = λπ2 left eigenvector P11ν1 + P12ν2 = λν1 . P21ν1 + P22ν2 = λν2 right eigenvector det[P − λI] = (P11 − λ)(P22 − λ) − P12P21 λ1 = 1; λ2 = 1 − P12 − P21 If P12 = P21 = 0 (the chain has 2 recurrent classes), then λ = 1 has multiplicity 2. Otherwise λ = 1 has multiplicity 1. If P12 = P21 = 1 (the chain is periodic), then λ2 = −1. Otherwise |λ2| < 1. π1P11 + π2P21 = λπ1 π1P12 + π2P22 = λπ2 λ1 = 1; P11ν1 + P12ν2 = λν1 . P21ν1 + P22ν2 = λν2 λ2 = 1 − P12 − P21 Assume throughout that either P12 > 0 or P21 > 0. Then � � P12 21 c π (1) = P12P+P � , � ν (1) = (1 P +P 21 12 21 � , 1) �c P12 � π (2) = (1, −1) � ν (2) = , −P21 P12 +P21 P12 +P21 Note that � π (i)� ν (j) = δij . In general, if � π (i)[P ] = λi� π (i) and [P ]� ν (i) = λi� ν (i) for i = 1, . . . , M, then � π (i)� ν (j) = 0 if λi �= λj . To see this, λi� π (i)� ν (j) = � π (i)[P ]� ν (j) = � π (i)(λj � ν (j)) = λj � π (i)� ν (j) so if � πi or πi� νj = 0. Normalization (of either λi �= λj , then � � νi) can make � πi� νi = 1 for each i. Note that the equations (i) (i) (i) (i) P11ν1 + P12ν2 = λiν1 ; (i) (i) P21ν1 + P22ν2 = λiν2 can be rewritten in matrix form as [P ][U ] = [U ][Λ] [Λ] = � λ1 0 0 λ2 � where  (1) (2)  ν ν [U ] =  1(1) 1(2)  , ν2 ν2 and Since � π (i)� ν (j ) = δij , we see that  (1) (1)  π2    π1 (2) (2) π1 π2 (1) ν1 (2) ν1   = [I], (1) (2) ν2 ν2 so [U ] is invertible and [U −1] has � π (1) and � π (2) as rows. Thus [P ] = [U ][Λ][U −1] and [P 2] = [U ][Λ][U −1][U ][Λ][U −1] = [U ][Λ2][U −1] Similarly, for any n ≥ 2, [P n] = [U ][Λn][U −1] (1) Eq. 3.29 in text has a typo and should be (1) above. We can solve (1) in general (if all M eigenvalues are distinct) as easily as for M = 2. Break [Λ]n into M terms, n [Λ]n = [Λn 1 ] + · · · + [ΛM] where n [Λn i ] has λi in position (i, i) and has zeros elsewhere. Then [P n] = M � λn ν (i)� π (i) i� i=1 [P n] = � π (1) = � π (2) � P21 , P12 P12 +P21 P12 +P21 = (1, −1) �M λn� ν (i)� π (i) i=1 i � c � ν (1) = (1, � 1) 12 � ν (2) = P12P+P , 21 −P21 P12 +P21 The steady-state vector is � π=� π (1) and � ν (1)� π= � π1 π2 π1 π2 [P n] = � � � ν (2)� π (2) = π1 + π2λn 2 π1 − π1λn 2 � �c π2 −π2 −π1 π1 π2 − π2λn 2 n π2 + π1λ2 � � We see that [P n] converges to �e � π , and the rate of convergence is λ2. This solution is exact. It essentially extends to arbitrary finite M. Distinct eigenvalues for M > 2 states Recall that, for an M state Markov chain, det[P −λI] is a polynomial of degree M in λ. It thus has M roots (eigenvalues), which we assume here to be distinct. Each eigenvalue λi has a right eigenvector � ν (i) and a left eigenvector � π (i). Also � π (i)� ν (j) = 0 for each i, j �= i. By scaling � ν (i) or � π (i), we can satisfy � π (i)� ν (i) = 1. ν (1) to � ν (M) and Let [U ] be the matrix with columns � (1) (M) let [V ] have rows � π to � π . Then [V ][U ] = I, so [V ] = [U −1]. Thus the eigenvec­ tors � ν (1) to � ν (M) are linearly independent and span M space. Same with � π (1) to � π (M). Putting the right eigenvector equations together, [P ][U ] = [U ][Λ]. Postmultiplying by [U −1], this be­ comes [P ] = [U ][Λ][U −1] [P n] = [U ][Λn][U −1] Breaking [Λn] into a sum of M terms as before, [P n] = M � i=1 λn ν (i)� π (i) i� Since each row of [P ] sums to 1, �e is a right eigen­ vector of eigenvalue 1. Thm: The left eigenvector � π of eigenvalue 1 is a steady-state vector if it is normalized to � π�e = 1 . Thm: The left eigenvector � π of eigenvalue 1 is a steady-state vector if it is normalized to � π�e = 1 . Pf: There must be a left eigenvector � π for eigen­ � value 1. For every j, 1 ≤ j ≤ M, πj = k πk Pkj . Tak­ ing magnitudes, |πj | ≤ � k |πk |Pkj (2) with equality iff πj = |πj |eiφ for all j and some φ. � � Summing over j, j |πj | ≤ k |πk |. This is satisfied with equality, so (2) is satisfied with equality for each j. Thus (|π1|, |π2|, . . . , |πM| is a nonnegative vector satis­ fying the steady-state vector equation. Normalizing � to j |πj | = 1, we have a steady-state vector. Thm: Every eigenvalue λ� satisfies |λ�| ≤ 1. Pf: We have seen that if � π (�) is a left eigenvec­ tor of [P ] with eigenvalue λ�, then it is also a left eigenvector of [P n] with eigenvalue λn � . Thus � (�) n πi Pij for all j. i � (�) (�) n |λn |πi | Pij for all j. � | |πj | ≤ i (�) Let β be the largest of |πj | over j. For that maxi(�) λn � πj = mizing j, |λn �|β ≤ � n ≤ βM β Pij i n Thus |λ� | ≤ M for all n, so |λ�| ≤ 1. These two theorems are valid for all finite-state Markov chains. For the case with M distinct eigen­ values, we have [P n] = M � λn ν (i)� π (i) i� i=1 If the chain is an ergodic unichain, then one eigen­ value is 1 and the rest are strictly less than 1 in magnitude. π is deter­ Thus the rate at which [P n] approaches �e� mined by the second largest eigenvalue. If [P ] is a periodic unichain with period d, then there are d eigenvalues equally spaced around the unit circle and [P n] does not converge. M states and M independent eigenvectors Next assume that one or more eigenvalues have multiplicity greater than 1, but that if an eigenvalue has multiplicity k, then it has k linearly independent eigenvectors. We can choose the left eigenvectors of a given eigenvalue to be orthonormal to the right eigen­ vectors of that eigenvalue. After doing this and defining [U ] as the matrix with columns � ν (M), we see [U ] is invertible and ν (1), . . . , � π (1), . . . , � π (M). We that [U −1) is the matrix with rows � then again have [P n] = M � i=1 λn ν (i)� π (i) i� Example: Consider a Markov chain consisting of � ergodic sets of states. Then each ergodic set will have an eigenvalue equal to 1 with a right eigenvector equal to 1 on the states of that set and 0 elsewhere. There will also be a ‘steady-state’ vector, nonzero only on that set of states. Then [P n] will converge to a block diagonal matrix where for each ergodic set, the rows within that set are the same. The Jordan form Unfortunately, it is possible that an eigenvalue of algebraic multiplicity k ≥ 2 has fewer than k linearly independent eigenvectors. The decomposition [P ] = [U ][Λ][U −1] can be replaced in this case by a Jordan form, [P ] = [U ][J][U −1] where [J] has the form   λ1 0 0 0 0  0 λ1 0 0 0    [J] =  0 0 λ2 1 0  . 0 0 0 λ 0 2 0 0 0 0 λ2 The eigenvalues are on the main diagonal and ones are on the next diagonal up where needed for defi­ cient eigenvectors. Example:   1/2 1/2 0   [P ] =  0 1/2 1/2  . 0 0 1 The eigenvalues are 1 and 1/2, with algebraic mul­ tiplicity 2 for λ = 1/2. There is only one eigenvector (subject to a scaling constant) for the eigenvalue 1/2. [P n] approaches steady-state as n(1/2)n. Fortunately, if [P ] is stochastic, the eigenvalue 1 al­ ways has as many linearly independent eigenvectors as its algebraic multiplicity.