For all @math , we show that the set of Poisson Binomial distributions on @math variables admits a proper @math -cover in total variation distance of size @math , which can also be computed in polynomial time. We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games.
These results provide structural information about PBDs that can be well approximated by simpler distributions, but fall short of our goal of approximating a PBD to within arbitrary accuracy . Indeed, the approximations obtained in the probability literature (such as the Poisson, Normal and Binomial approximations) typically depend on the first few moments of the PBD being approximated, while higher moments are crucial for arbitrary approximation @cite_22 . At the same time, algorithmic applications often require that the approximating distribution is of the same kind as the distribution that is being approximated. E.g., in the anonymous game application mentioned earlier, the parameters of the given PBD correspond to mixed strategies of players at Nash equilibrium, and the parameters of the approximating PBD correspond to mixed strategies at approximate Nash equilibrium. Approximating the given PBD via a Poisson or a Normal distribution would not have any meaning in the context of a game.
@cite_22
2094799272
The Poisson binomial distribution is approximated by a binomial distribution and also by finite signed measures resulting from the corresponding Krawtchouk expansion. Bounds and asymptotic relations for the total variation distance and the point metric are given.