Speaker
Description
An ergodic Markov chain, with transition probability matrix $P$ and stationary vector $\mathbf{\pi}$, is called reversible if $D_{\mathbf{\pi}} P = P^\top D_{\mathbf{\pi}}$, where $D_{\mathbf{\pi}}$ is the diagonal matrix with the components of $\mathbf{\pi}$ on its diagonal. Reversibility is a desirable property in Markov chain theory. Indeed, in many algorithms and applications, reversibility can be exploited in order to derive stability characteristics. Sets of possible applications include computational biology, statistical physics, and Markov Chain Monte Carlo methods.
Nevertheless, in several frameworks, the transition matrix $P$ of a Markov chain may be estimated from noisy measurements and data. Then, even in settings where the reversibility property should be satisfied, a numerical discrepancy may lead to a non-reversible Markov chain. This issue can be solved by computing the nearest reversible Markov chain to a given one.
In this talk, given a Markov chain, we present a method for the numerical approximation of the reversible Markov chain closest to it. The closeness between two Markov chains is measured by means of the distance, induced by the Frobenius norm, between the corresponding transition matrices.
The approach we propose is based on a Riemannian optimization procedure over the manifold of the reversible stochastic matrices, sharing the same stationary distribution $\mathbf{\pi}$ [1].
The proposed algorithm automatically detects any transient states and restricts its analysis to the remaining recurrent subchain, and in the presence of multiple ergodic classes, our approach processes each one
independently, by isolating and solving smaller, decoupled subchains.
The applicability of our approach has been tested by comparing it with the quadratic programming based method in [2]. Numerical tests show that, for large-sized transition matrices, the Riemannian-based method is often faster and more accurate than the QP competitor.
References
- F. Durastante, M. Gnazzo and B. Meini. A Riemannian Optimization Approach for Finding the Nearest Reversible Markov Chain, arXiv.2505.16762 (2025).
- A.J.N. Nielsen and M. Weber. Computing the nearest reversible Markov chain, Numerical Linear Algebra with Applications 22(3), 483 – 499 (2015).
