For a reversible finite-state Markov chain, the second largest eigenvalue determines how fast the Markov chain converges to its stationary distribution.

A few questions (e.g, 1, 2) refer to Chapter 12 (examples starting on page 165) of the book Markov Chains and Mixing Times by Levin, Peres, and Wilmer, where the eigenvalues of some symmetric random walks are found.

Are there similar results available for asymmetric random walks? I am struggling to derive what the eigenvalues are in that case.

  • $\begingroup$ In the asymmetric case, the eigenvalues can have nonzero imaginary parts, which I suppose makes the notion of "spectral gap" need improvement. $\endgroup$ – Rodrigo de Azevedo Mar 9 at 11:09
  • $\begingroup$ If the random walk is reversible (which puts some constraints on the transition probabilities), then the eigenvalues are real. $\endgroup$ – arni Mar 9 at 11:17
  • 1
    $\begingroup$ I remember reading this paper, where they focus mostly on the symmetric case, though they consider the non-symmetric case (in section 6), too. $\endgroup$ – Rodrigo de Azevedo Mar 9 at 11:36
  • 1
    $\begingroup$ Thanks. This is a good paper. $\endgroup$ – arni Mar 9 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.