Learning Sums of Independent Integer Random Variables

Let S = X1 + · · · + Xn be a sum of n independent integer random variables Xi, where each Xi is supported on {0, 1,..., k − 1} but otherwise may have an arbitrary distribution (in particular the Xi’s need not be identically distributed). How many samples are required to learn the distribution S to high accuracy? In this paper we show that the answer is completely independent of n, and moreover we give a computationally efficient algorithm which achieves this low sample complexity. More precisely, our algorithm learns any such S to ɛ-accuracy (with respect to the total variation distance between distributions) using poly(k, 1/ɛ) samples, independent of n. Its running time is poly(k, 1/ɛ) in the standard word RAM model. Thus we give a broad generalization of the main result of [DDS12b] which gave a similar learning result for the special case k = 2 (when the distribution S is a Poisson Binomial Distribution). Prior to this work, no nontrivial results were known for learning these distributions even in the case k = 3. A key difficulty is that, in contrast to the case of k = 2, sums of independent {0, 1, 2}-valued random variables may behave very differently from (discretized) normal distributions, and in fact may be rather complicated — they are not log-concave, they can be Θ(n)-modal, there is no relationship