Abstract 

Consider the following estimation problem: there are n entities, each with an unknown parameter  and we observe n independent random variables, Binomial.How accurately can one recover the “histogram” (i.e. cumulative density function) of the While the empirical estimates would recover the histogram to earth mover distance (equivalently, distance between the CDFs), we show that, provided n is sufficiently large, we can achieve error which is information theoretically optimal. We also extend our results to the multi-dimensional parameter case, capturing settings where each member of the population has multiple associated parameters. Beyond the theoretical results, we demonstrate that the recovery algorithm performs well in practice on a variety of datasets, providing illuminating insights into several domains, including politics, sports analytics, and variation in the gender ratio of offspring.