Limits of Finite-Sample Dependence Measures under Data Processing Inequality
Abstract
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.
Related
- Scale-invariant bounds on thin sets for measures satisfying a first-order PDE and the anisotropic Michael-Simon inequality
- Efficient estimation of measures of functional dependence
- Grünbaum's inequality for Gaussian and convex probability measures
- Endpoint Lorentz Inequality for Riesz Potentials with Respect to General Measures
- Dirac measures can be quantum limits on the Sierpinski gasket
BibTeX
@misc{kong2026limits,
title = {{Limits of Finite-Sample Dependence Measures under Data Processing Inequality}},
author = {Yuqing Kong},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2606.14225},
eprint = {2606.14225},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.14225},
}
RIS
TY - UNPB
TI - Limits of Finite-Sample Dependence Measures under Data Processing Inequality
AU - Yuqing Kong
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2606.14225
UR - https://arxiv.org/abs/2606.14225
AB - 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.
ER -