pipette
ENEnglish

Bregman projections and partition design for accelerating finite Markov chains

Michael C.H. Choi, Youjia Wang

Preprint

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 .

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 33 pages, 4 figures