← 研踪 PaperTrailarXiv:2610.39239 · v1
Bregman projections and partition design for accelerating finite Markov chains
首次提交 2026-10-29 10:56
版本更新 2026-10-29 10:56
雷达观测 2026-10-30 11:25
摘要
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 $π$.
作者备注：33 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-29 10:56 · 最新观测版本
Bregman projections and partition design for accelerating finite Markov chains
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 $π$.
查看此版本解读 →查看此版本原文 ↗