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

arXiv: https://arxiv.org/abs/1504.08363 · HTML: https://mlsanity.com/paper/1504.08363/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2015.

## Built on by (most cited first, 1 of 1)

- [Learning and Covering Sums of Independent Random Variables with Unbounded Support](https://mlsanity.com/paper/2210.13313/) (2022)

## Abstract (arXiv)

An (n,k)-Poisson Multinomial Distribution (PMD) is the distribution of the sum of n independent random vectors supported on the set cal Bk=e1,ldots,ek of standard basis vectors in ℝk. We prove a structural characterization of these distributions, showing that, for all varepsilon >0, any (n, k)-Poisson multinomial random vector is varepsilon-close, in total variation distance, to the sum of a discretized multidimensional Gaussian and an independent (poly(k/varepsilon), k)-Poisson multinomial random vector. Our structural characterization extends the multi-dimensional CLT of Valiant and Valiant, by simultaneously applying to all approximation requirements varepsilon. In particular, it overcomes factors depending on log n and, importantly, the minimum eigenvalue of the PMD's covariance matrix from the distance to a multidimensional Gaussian random variable. We use our structural characterization to obtain an varepsilon-cover, in total variation distance, of the set of all (n, k)-PMDs, significantly improving the cover size of Daskalakis and Papadimitriou, and obtaining the same qualitative dependence of the cover size on n and varepsilon as the k=2 cover of Daskalakis and Papadimitriou. We further exploit this structure to show that (n,k)-PMDs can be learned to within varepsilon in total variation distance from tildeOk(1/varepsilon2) samples, which is near-optimal in terms of dependence on varepsilon and independent of n. In particular, our result generalizes the single-dimensional result of Daskalakis, Diakonikolas, and Servedio for Poisson Binomials to arbitrary dimension.