Additive averaging kernels speed up finite Markov chains via partition optimization
michaelchchoi · x · 2026-09-22
Paper 4 of the JJSD Monte Carlo special issue thread (open access): Lim & Choi study additive mixtures of Markov kernels Aα = αP + (1−α)G, where P is a baseline sampler and G a Gibbs kernel induced by a partition of the state space — interpretable as a projection of a lifted Markov chain. For the Frobenius objective they derive explicit trace formulae and a Cheeger-type functional characterizing optimal two-block partitions, yielding a submodular optimization problem solvable via majorisation–minimisation, plus geometric decay rates governed by the absolute spectral gap of P. For KL divergence they show convexity-based bounds reduce partition selection to the Gibbs component. Curie–Weiss experiments show suitable partition and α choices significantly accelerate convergence.
More from Research
- Burkov: a 7B model trained only on 2,000 core words could master any describable task — burkov · 2026-09-22
- Shenzhen University and HKUST propose ECA: evidence checks before agent actions — jiqizhixin · 2026-09-22
- WorldCrafter: Video World Model with Implicit 3D-Aware Memory Opensourced — _akhaliq · 2026-09-22
- SaaS sales conversations dataset with 100K+ English dialogues trends on Hugging Face — DeepMostInnovations · 2026-09-22
- onPanda: token-level correction tool cuts alignment data annotation time by 52% — stepfun-ai · 2026-09-22
- Randomized step sizes make Metropolis–Hastings robust to tuning, study finds — michaelchchoi · 2026-09-22