Markov's Matrix Magic by Ian Stewart

Reproduced with permission of the author

Let M be the transition matrix. First, calculate a set of 40 numbers, called the eigenvalues of M. A number m is an eigenvalue of M if you can write 40 numbers on the 40 vertices of the network so that when you split each into six and let it flow along the six clockwise lines emanating from that vertex, the resulting numbers are exactly m times the size of the numbers with which you started. (Phew! It's more easily expressed in symbols: Mv = mv for some v.) But there's a twist: the eigenvalues need not be real numbers between 0 and 1. They can. be complex numbers, expressible using the number i which is the square root of -1. The sequence formed by these 40 numbers is called an eigenvector. Now all you have to do is find the biggest eigenvalue among the 40 you've calculated. Then the probability distribution will be approximated as closely as you wish by the corresponding eigenvector, once "normalized" so that its entries add to 1, as genuine probabilities should. (This step just means that you divide every entry by the total.) Because of the rotational symmetry, it is actually not hard to find the eigenvalues and eigenvectors. One eigenvector shows all 40 entries equal to 1/40. What is its eigenvalue? Well, suppose you start from this distribution, split each 1/40 into six equal pieces of size 1/240 and shove them along their six clockwise lines. Each vertex receives exactly six contributions: one from each of the six preceding vertices. So it ends up as 6 x 1/240, or 1/40. This is what an eigenvector should do, and in this case the eigenvalue is 1. I won't tell you the other 39 eigenvaluos, whose expressions are beautiful (perhaps only to mathematicians). In fact, the next largest one has an absolute value of 0.964. So 1 is the largest eigenvalue, and its eigenvector does indeed represent the long-term state of the probability distribution.