On the Structure, Covering, and Learning of Poisson Multinomial Distributions

An (n, k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set B-k = {e(1), . . . , e(k)} of standard basis vectors in R-k. We prove a structural characterization of these distributions, showing that, for all epsilon > 0, any (n, k)-Poisson multinomial random vector is epsilon-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent (poly(k/epsilon), k)-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of [2], by simultaneously applying to all approximation requirements epsilon. In particular, it overcomes factors depending on log n and, importantly, the minimum eigenvalue of the PMD's covariance matrix. We use our structural characterization to obtain an epsilon-cover, in total variation distance, of the set of all (n, k)-PMDs, significantly improving the cover size of [3], [4], and obtaining the same qualitative dependence of the cover size on n and epsilon as the k = 2 cover of [5], [6]. We further exploit this structure to show that (n, k)-PMDs can be learned to within e in total variation distance from (O) over tilde (k)(1/epsilon(2)) samples, which is near-optimal in terms of dependence on e and independent of n. In particular, our result generalizes the single-dimensional result of [7] for Poisson binomials to arbitrary dimension. Finally, as a corollary of our results on PMDs, we give a (O) over tilde k(1/epsilon(2)) sample algorithm for learning (n, k)-sums of independent integer random variables (SIIRVs), which is near-optimal for constant k.