Nearest Reversible Markov Chains with Sparsity Constraints: An Optimization Approach
This work addresses the practical need to enforce reversibility and sparsity in Markov chains for applications in MCMC, computational chemistry, and data-driven modeling.
The authors formulate the problem of approximating a non-reversible Markov chain by a reversible one with sparsity constraints as a quadratic programming problem, and demonstrate its effectiveness through numerical experiments.
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.