What is this?

A matlab script to compute the nearest reversible Markov chain.

For any Markov chain exists according to a given norm and probability vector a unique closest reversible Markov chain. For example, consider the followin Markov chain:

This Markov chain is not reversible. According to the Frobenius norm the closest reversible Markov chain according to

can be computed as

If we choose the probability vector as

then the closest reversible Markov chain according to the Frobenius norm is approximately given by

For the full theory check out the paper or the Wikipedia article

How to use it?

Go with Matlab in the folder where you have saved the file getClosestSparse.m.

Assume you have a NxN dimensonal Markov chain A and a N-dimensional probability vector m then you can compute the closest reversible NxN dimensonal Markov chain U according to the Frobenius-Norm with the command

U = getClosestSparse(A,m)

If you want that A and U have similar rare events (this implies that they have similar eigenvalues, see the above mentioned paper) then you can compute the closest reversible NxN dimensonal Markov chain U according to a special weighted norm with the command

U = getClosestSparse(A,m,1)

Note that the computation of the Markov chain U according to a special weighted norm is only usable if m has no zero entries. For the closest reversible Markov chain U according to the Frobenius-Norm zero entries are allowed.