# On additive averaging kernels for finite Markov chains

arXiv: https://arxiv.org/abs/2604.12334 · HTML: https://mlsanity.com/paper/2604.12334/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Apr 2026.

## Built on by (most cited first, 1 of 1)

- [Spectral partitioning for k-block averaging kernels of finite Markov chains](https://mlsanity.com/paper/2608.21466/) (2026)

## Abstract (arXiv)

We study additive mixtures of Markov kernels of the form Aα = α P + (1-α)G, where α ∈ [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.