6
$\begingroup$

I'm reading about markov chains and how to analyze and bound their hitting / mixing times. However many of the useful results seem to require that the analyzed markov chain be symmetric. For reference, I am using the text "Markov Chains and Mixing Times", as viewed here: http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf

Some of the relevant techniques are:

  • the Commute Time Identity, which relates the hitting time and commute times of nodes to effective resistance properties of the underlying network. However this assumes that the underlying network is undirected.

  • Spectral methods which relate the mixing time of a random walk to the eigenvalues of the underlying adjacency / transition matrix. However these assume that the matrix is symmetric and that all of the eigenvalues are real.

I'm having a hard time finding relevant techniques for directed / non symmetric random walks (but still aperiodic with no absorbing states). My questions are:

  1. Are there parallels of the above techniques on markov chains which do not have symmetric transition properties? In particular, do any of the spectral methods apply when the transition matrix has complex eigenvalues?
  2. Are they common / known techniques for modifying a directed markov chain into an undirected one which has similar or comparable properties, so that the above techniques can be applied?
$\endgroup$
  • 2
    $\begingroup$ I think it is in general hard to use the eigenvalues because even if the transition matrix is diagonalizable, there is no way to guarantee a basis of eigenvectors which doesn't massively distort the total variation distance. It seems to me that often people often use coupling in the irreversible case but I am not an expert. $\endgroup$ – Benjamin Steinberg Feb 7 '18 at 21:22
1
$\begingroup$

There's this paper extending the electrical network approach to non-reversible chain that you might find interesting:

Márton Balázs, & Áron Folly. (2016). An Electric Network for Nonreversible Markov Chains. The American Mathematical Monthly, 123(7), 657-682. doi:10.4169/amer.math.monthly.123.7.657

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.