Near-Optimal Bounds for Testing Histogram Distributions

We investigate the problem of testing whether a discrete probability distribution over an ordered domain is a histogram on a specified number of bins. One of the most common tools for the succinct approximation of data, k-histograms over [n], are probability distributions that are piecewise constant over a set of k intervals. The histogram testing problem is the following: Given samples from an unknown distribution p on [n], we want to distinguish between the cases that p is a k-histogram versus varepsilon-far from any k-histogram, in total variation distance. Our main result is a sample near-optimal and computationally efficient algorithm for this testing problem, and a nearly-matching (within logarithmic factors) sample complexity lower bound. Specifically, we show that the histogram testing problem has sample complexity widetilde Theta (√nk / varepsilon + k / varepsilon2 + √n / varepsilon2).