Sample complexity of the distinct elements problem

Yihong Wu, Pengkun Yang

We consider the distinct elements problem, where the goal is to estimate the number of distinct colors in an urn containing $k$ balls based on $n$ samples drawn with replacements…