On additive averaging kernels for finite Markov chains

Abstract

Abstract We study additive mixtures of Markov kernels of the form $$A_\alpha = \alpha P + (1-\alpha )G$$ A α = α P + ( 1 - α ) G , where $$\alpha \in [0,1]$$ α ∈ [ 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_\alpha $$ 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_\alpha $$ 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 $$\alpha $$ α can significantly accelerate convergence in total variation distance. We observe a consistent trade-off between local exploration and global averaging, with intermediate values of $$\alpha $$ α achieving the best performance across regimes.