Nearest Reversible Markov Chains with Sparsity Constraints: An Optimization Approach

Reversibility is a key property of Markov chains, central to algorithms such as Metropolis--Hastings and other MCMC methods. Yet many applications yield non-reversible chains, motivating the problem of approximating them by reversible ones with minimal modification. We formulate this task as a matrix nearness problem and focus on the practically relevant case of sparse transition matrices. The resulting optimization problem is a quadratic programming problem, and numerical experiments illustrate the effectiveness of the approach. This framework provides a principled way to enforce reversibility and sparsity patterns in Markov chains with applications in MCMC, computational chemistry, and data-driven modeling.

This repository contains the accompanying code of the paper

@misc{CipDurGnaMei2026,
  title={Nearest Reversible Markov Chains with Sparsity Constraints: An Optimization Approach},
  author={Stefano, Cipolla and Fabio, Durastante and Miryam, Gnazzo and Beatrice, Meini},
  year={2026}
}

Collaborators

• Stefano Cipolla 📧,
• Miryam Gnazzo 📧,
• Fabio Durastante 📧 💻,
• Beatrice Meini 📧.

Conda environment for MSMbuilder

A Conda environment with MSMbuilder can be crated from the spec-file.txt file by doing

conda create --name msmbuilder --file spec-file.txt python=3.6

and then be activated by doing

conda activate msmbuilder

After that the code under the folder msm_datase can be run inside the active Conda environment.

Comparison with Riemannian Solver

One of the example runs a comparison with the Riemannian-based optimization for the computation of the nearest reversible Markov chain, see the following paper for the details

@misc{durastante2025riemannianoptimizationapproachfinding,
      title={A Riemannian Optimization Approach for Finding the Nearest Reversible Markov Chain}, 
      author={Fabio Durastante and Miryam Gnazzo and Beatrice Meini},
      year={2025},
      eprint={2505.16762},
      archivePrefix={arXiv},
      primaryClass={math.NA},
      url={https://arxiv.org/abs/2505.16762}, 
}

and the associated repository for the code. This code needs the Manopt toolbox to be runned.

Gurobi

The proposed solver can use the Matlab interface to Gurobi to solve the relevant quadratic programming. If you are an academic, you can request a free license to evaluate the performances. Otherwise, the code can be run by employing Matlab's quadprog.