A Riemannian Optimization Approach for Finding the Nearest Reversible Markov Chain
This work addresses a specific algorithmic challenge in probability theory and computational statistics, offering an incremental improvement for researchers and practitioners needing reversible Markov chain approximations.
The paper tackles the problem of finding the nearest reversible Markov chain to a given one with the same stationary distribution, using a novel Riemannian optimization approach that achieves this by minimizing the Frobenius norm between transition matrices. The method is shown to be effective in synthetic experiments and in constructing reversible chains from data, outperforming an existing quadratic programming method.
We address the algorithmic problem of determining the reversible Markov chain $\tilde X$ that is closest to a given Markov chain $X$, with an identical stationary distribution. More specifically, $\tilde X$ is the reversible Markov chain with the closest transition matrix, in the Frobenius norm, to the transition matrix of $X$. To compute the transition matrix of $\tilde X$, we propose a novel approach based on Riemannian optimization. Our method introduces a modified multinomial manifold endowed with a prescribed stationary vector, while also satisfying the detailed balance conditions, all within the framework of the Fisher metric. We evaluate the performance of the proposed approach in comparison with an existing quadratic programming method and demonstrate its effectiveness through a series of synthetic experiments, as well as in the construction of a reversible Markov chain from transition count data obtained via direct estimation from a stochastic differential equation.