arXiv:2606.14225 · v3

Limits of Finite-Sample Dependence Measures under Data Processing Inequality

首次提交 2026-06-12 16:06

版本更新 2026-11-02 21:50

雷达观测 2026-11-04 23:41

摘要

We study dependence measures between two discrete random variables. The measures vanish at independence and satisfy the data processing inequality (DPI): stochastic post-processing of one variable cannot increase dependence. We ask which such measures admit an exactly unbiased estimator from a fixed finite number of i.i.d. samples, a property equivalent to being polynomial in the joint probabilities. We distinguish fixed-alphabet DPI, which preserves the alphabet size of the variable being processed, from dimension-changing DPI. Under one-sided fixed-alphabet DPI, every measure with a continuously differentiable extension to a neighborhood of the closed probability simplex vanishes whenever one processed state has zero probability. If the processed alphabet is larger than the other alphabet, the measure is identically zero. If it has $n$ states and the other alphabet has at least $n$, every nonzero polynomial measure has degree at least $2n$ and requires at least $2n$ samples for unbiased estimation. Both bounds are attained by the Gram determinant. Under one-sided dimension-changing DPI, every family with the same boundary regularity is identically zero. These results yield sharp task bounds for multi-task peer prediction. For two agents with $n$ signals each, $2n$ tasks are necessary and sufficient for nontrivial expected payments that vanish for independent reports and cannot increase under memoryless stochastic garbling. Under these requirements, unequal signal-space sizes force the larger-alphabet agent's expected payment to vanish identically for any finite number of tasks.