Finite-Sample Unbiasedly Estimable Information Monotones

Abstract

Which measures of statistical dependence can be estimated unbiasedly from a fixed number of samples while satisfying the data processing inequality (DPI)? For finite alphabets, finite-sample unbiased estimability is equivalent to polynomial dependence on the distribution, and the minimum polynomial degree equals the exact sample complexity. Let \(U\inΔ_{n,m}\) be the joint-distribution matrix, with stochastic post-processing applied to the \(n\)-state row variable. Our main classification concerns fixed-alphabet left-sided DPI. We first prove a result beyond polynomiality: for every \(n,m\ge2\), any functional that satisfies left-sided DPI, vanishes under independence, and extends to a \(C^1\) function on a neighborhood of the probability simplex must vanish whenever \(U\) has a zero row. If DPI is strengthened to allow changes in the processed alphabet size, every such cross-dimensional family is identically zero. For fixed-alphabet DPI, this gives a sharp trichotomy. If \(n>m\), every such \(C^1\)-extendable functional is identically zero. If \(n=m\), every nonzero admissible polynomial is divisible on the simplex by \((\det U)^2\), giving the sharp degree bound \(2n\). If \(n<m\), every admissible polynomial lies, modulo the simplex relation, in the square of the ideal generated by the \(n\times n\) maximal minors of \(U\); the sharp degree bound is again \(2n\), attained by \(\det(UU^\top)\). These results also show that a \(C^1\)-extendable functional satisfying left-sided DPI can vanish exactly at independence only when the processed variable is binary. We further prove coNP-hardness of DPI recognition for polynomial functionals and derive corresponding impossibility and exact task-complexity results for multi-task peer prediction.