Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/digital-systems-linear-algebra-introduction-to-formal-proof/1/f/solution

The remaining eigenvalues are
They have absolute value less than one. The three distinct eigenvalues give a basis of eigenvectors, which may be chosen as , and , with and . Write an arbitrary initial probability vector as . Summing its entries shows , because the entries of sum to one and those of sum to zero. Therefore
This proves convergence for every initial probability vector, rather than merely identifying a possible limit. In particular,
For the given initial probability vector, and ; substituting also recovers the previous answers. The slowest decaying eigenvector component has factor .

New to topics? Read the docs here!