Bregman projections and partition design for accelerating finite Markov chains
En palabras de los autores
We study Gibbs averaging of finite Markov chains with a prescribed stationary distribution . Given a transition matrix and the Gibbs kernel induced by a state-space partition, we prove that 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 as a kernel closest to stationarity among those with the same projection chain as ; for relative entropy, it maximizes the entropy rate. The identities also give monotonicity under partition coarsening. For every reversible ergodic baseline , Gibbs averaging cannot increase the squared weighted Frobenius distance to stationarity at any positive integer time, and the inequality is strict unless . The corresponding mixing time therefore cannot increase. To choose the partition, we identify the divergence of from stationarity as the exact worst-case divergence of over all -stationary baselines . 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 with , and a greedy approximation algorithm with a provable guarantee for . For power generators with , the objective is proportional to Tsallis entropy of order : its minimization favors imbalanced block masses when and balanced block masses when , while all -block partitions have the same objective value when . A numerical experiment compares the resulting projected chains with a local Metropolis sampler on a multi-modal .
Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 33 pages, 4 figures