Comb Test: Histogram Uniformity Testing Based on Discrete Total Variation

Abstract

Histogram uniformity testing is a common statistical task usually performed using Pearson's chi-square test. This paper proposes a complementary test based on the discrete total variation of the bin counts, which is trivial to compute and, unlike chi-square, exploits bin ordering. Its exact null distribution follows from dynamic programming, and a gamma approximation, verified up to $N=5\cdot 10^4$, extends it to large samples. Matching alternatives in ${\ell }_1$ distance locates the test: it gains over chi-square only in the period-2 comb direction and is least sensitive to smooth, single-jump, and depleted-block departures, for which chi-square is preferable. Experiments on converter nonlinearity, rounding bias, and real images confirm the analysis. Code and data are available at https://github.com/DiscreteTotalVariation/CombTest.

5 pages, 5 figures