Approximating and Testing k-Histogram Distributions in Sub-linear Time

摘要

A discrete distribution p, over [n], is a k-histogram if its probability distribution function can be represented as a piece-wise constant function with k pieces. Such a function is represented by a list of k intervals and k corresponding values. We consider the following problem: given a collection of samples from a distribution p, find a k-histogram that (approximately) minimizes the σ2 distance to the distribution p. We give time and sample efficient algorithms for this problem. We further provide algorithms that, distinguish distributions that have the property of being a k-histogram from distributions that are e-far from any A-histogram in the σ1 distance and σ2 distance respectively.