View PDF HTML (experimental)

Abstract:We study Kullback-Leibler (KL) contraction in finite Markov chains through a row-wise perspective. Evaluating the SDPI ratio at point masses yields a state-indexed retention profile $r(x)=D_{\mathrm{KL}}(P(x,\cdot)\|\pi)/\log(1/\pi(x))$ and a localization ratio $L(P)=\bar r_\pi/M\in[0,1]$ (with $M=\max_x r(x)$, $\bar r_\pi=\mathbb{E}_\pi r$) that distinguishes localized from global contraction obstructions. Our main contributions are (i) a convexity-gap identity showing that the gap between the row-averaged divergence and $D_{\mathrm{KL}}(\mu P\|\pi)$ equals the mutual information $I_\mu(X;Y)$, and a derived decomposition of the contraction ratio into entropy inflation and a mutual-information penalty; (ii) a Cheeger-type lower bound on $M$, tying the bottleneck geometry of $P$ directly to the row-retention profile; (iii) an explicit construction proving that $L(P_n)\to 0$ does not force $\eta_{\mathrm{KL}}(P_n)/M_n\to 1$, identifying cardinality of high-retention states (not their $\pi$-mass) as the decisive quantity. Alongside these, we record structural consequences, optimal Markov/reverse-Markov tail bounds for $r$, a Bhatia-Davis variance bound, two-sided spectral bounds with an explicit cubic correction, a KL/Pinsker mixing-time bound, and tensorization for product chains. We further show that $L(P)$ is structurally decoupled from the spectral gap, the Cheeger constant, and the mixing time: every vertex-transitive chain satisfies $L(P)=1$ regardless of its mixing speed, and the empirical rank correlations between $L(P)$ and these classical invariants on a diverse but limited test suite are essentially zero. The numerical experiments are exploratory and not used as evidence for a universal classification theorem.

Submission history

From: Saurav Jadhav [view email]
[v1] Thu, 25 Jun 2026 14:15:59 UTC (32 KB)