title: Finding stationary distribution of a markov process given a transition probability matrix
body: <p>There has been two threads related to this issue on Stack Overflow: </p>
  
  <ul>
  <li><a href="https://stackoverflow.com/q/38103503/4891738">How can I obtain stationary distribution of a Markov Chain given a transition probability matrix</a> describes what a transition probability matrix is, and demonstrate how a stationary distribution is reached by taking powers of this matrix;</li>
  <li><a href="https://stackoverflow.com/q/38143932/4891738">How to find when a matrix converges with a loop</a> uses an R loop to determine when the matrix power converges.</li>
  </ul>
  
  <p>The above is straightforward, but very expensive. If we have a transition matrix of order <code>n</code>, then at each iteration we compute a matrix-matrix multiplication at costs <code>O(n ^ 3)</code>.</p>
  
  <p>Is there a more efficient way to do this? One thing that occurs to me is to use Eigen decomposition. A Markov matrix is known to:</p>
  
  <ul>
  <li>be diagonalizable in complex domain: <code>A = E * D * E^{-1}</code>;</li>
  <li>have a real Eigen value of 1, and other (complex) Eigen values with length smaller than 1.</li>
  </ul>
  
  <p>The stationary distribution is the Eigen vector associated with the Eigen value of 1, i.e., the first Eigen vector.</p>
  
  <p>Well, the theory is nice, but I can't get it work. Taking the matrix <code>P</code> in the first linked question:</p>
  
  <pre><code>P &lt;- structure(c(0, 0.1, 0, 0, 0, 0, 0, 0.1, 0.2, 0, 0, 0, 0, 0, 0.2, 
  0.3, 0, 0, 0.5, 0.4, 0.3, 0.5, 0.4, 0, 0, 0, 0, 0, 0.6, 0.4, 
  0.5, 0.4, 0.3, 0.2, 0, 0.6), .Dim = c(6L, 6L))
  </code></pre>
  
  <p>If I do:</p>
  
  <pre><code>Re(eigen(P)$vectors[, 1])
  # [1] 0.4082483 0.4082483 0.4082483 0.4082483 0.4082483 0.4082483
  </code></pre>
  
  <p>What's going on? According to previous questions, the stationary distribution is:</p>
  
  <pre><code># [1] 0.002590673 0.025906737 0.116580322 0.310880848 0.272020713 0.272020708
  </code></pre>