On additive averaging kernels for finite Markov chains
math.PR, cs.IT, math.CO, math.IT, math.OC, stat.CO
Submitted: 2026-04-14
Updated: 2026-07-16
Comments: 32 pages, 5 figures
DOI: 10.1007/s42081-026-00373-x
Code: https://github.com/ryan-2357/-additive
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study additive mixtures of Markov kernels of the form A α= αP + (1-α)G, where α in [0,1], P is a baseline sampler and G is a Gibbs kernel induced by a partition of the state space.
Terminology
Abstract
We study additive mixtures of Markov kernels of the form A α= αP + (1-α)G, where α in [0,1], P is a baseline sampler and G is a Gibbs kernel induced by a partition of the state space. We first motivate the study of A α, which can be interpreted as the projection of a lifted Markov chain. We then consider the minimisation of distance to stationarity under two objectives: the squared Frobenius norm and the Kullback-Leibler (KL) divergence. For the Frobenius objective, we derive explicit trace formulae and identify a Cheeger-type functional that characterises optimal two-block partitions. This yields a structured combinatorial optimisation problem admitting a difference-of-submodular decomposition, enabling efficient approximation via majorisation-minimisation. We also obtain geometric decay rates governed by the absolute spectral gap of P. For the KL divergence, we establish convexity-based bounds showing that the divergence of A α is controlled by those of both P and G, thereby reducing partition selection to the Gibbs component. Numerical experiments on the Curie-Weiss model demonstrate that suitable choice of both the partition and the parameter α can significantly accelerate convergence in total variation distance. We observe a consistent trade-off between local exploration and global averaging, with intermediate values of α achieving the best performance across regimes.
Sources
- Group-averaged Markov chains: mixing improvement
- Group-averaged Markov chains II: tuning of group action in finite state space
- Geometry and factorization of multivariate Markov chains with applications to MCMC acceleration and approximate inference
- Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves
- A zero-one law for swap-invariant events in uniform spanning forests
- Bernoulli flow for Erd s-R'enyi graphs