Bregman projections and partition design for accelerating finite Markov chains
math.PR, cs.IT, math.IT, math.OC, stat.CO
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 33 pages, 4 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study Gibbs averaging of finite Markov chains with a prescribed stationary distribution π.
Abstract
We study Gibbs averaging of finite Markov chains with a prescribed stationary distribution π. Given a transition matrix P and the Gibbs kernel G induced by a state-space partition, we prove that GPG is an information projection for every admissible Bregman generator ϕ, with divergences defined using transition probabilities relative to π. A Pythagorean identity characterizes this projection and recovers the relative entropy and weighted Frobenius cases. A dual characterization identifies GPG as a kernel closest to stationarity among those with the same projection chain as P; for relative entropy, it maximizes the entropy rate. The identities also give monotonicity under partition coarsening. For every reversible ergodic baseline P, Gibbs averaging cannot increase the squared weighted Frobenius distance to stationarity at any positive integer time, and the inequality is strict unless P=GPG. The corresponding mixing time therefore cannot increase. To choose the partition, we identify the divergence of G from stationarity as the exact worst-case divergence of GPG over all π-stationary baselines P. This objective depends only on the block masses. We give an exact algorithm for concave block costs, including those arising from relative entropy and power generators ϕ(u)=u p with 1<p<2, and a greedy approximation algorithm with a provable guarantee for p>2. For power generators ϕ(u)=u p with p>1, the objective is proportional to Tsallis entropy of order 2-p: its minimization favors imbalanced block masses when 1<p<2 and balanced block masses when p>2, while all k-block partitions have the same objective value when p=2. A numerical experiment compares the resulting projected chains with a local Metropolis sampler on a multi-modal π.
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