What is the sampling-distribution of distinct values?

Question

Say we sample $k$ times from a discrete random-variable $X$, and count the number of distinct values. Call this statistic/random-variable $U$. What can we say about the distribution of $U$?

For instance, we may pick 10 000 random people from the USA, count the number of distinct first names, then repeat 100 times. We get $631,721,575,634,...647$. How are these values distributed?

By 'distinct' I mean 'happening at least once over $k$ samples'. eg for $\{3,1,3,3,4,3,4,9\}$ there are 4 distinct values (1,3,4,9), so $u=4$.

I'm not so much interested in estimators, but more in the behavior of $U$.

Experimentally, for non-small $k$, I've found $U$ to be approximately Normally-distributed when $X$ is sampled from a range of discrete distributions (Zipfian, Geometric, Poisson), even when combining samples from various distributions. What is the justification for this?

Answer 1

Suppose that $X$ takes on $n$ values index by $i$ with probability $p_i$. Let $D_t$ denote the number of distinct values at time $t$. Let $X_s=1$ if at time $s$ we introduce a new value that hasn't been seen before. Then:

$$D_t=X_1+...+X_t.$$ This is essentially the Coupon Collector Problem with generalized probabilities for each coupon. In particular the distribution of $X_i$ is related to the waiting time $W_k$ to collect $k$ distinct events: $P(D_t=s)=P(W_s\leq t,W_{s+1}>t)$. So it's not surprising that something like the normal distribution pops up here, if one assumes the correlations between $X_i$ are small, so that the CLT would apply. If the probabilities of each $X_i$ are tiny and the number of objects is extremely large, then you might expect a Poisson distribution. In particular the waiting time for the next object is geometric: your success probability is the sum of probabilities over all objects you have yet to collect.

I believe originally Baum and Billingsly originally studied the distributions of $W_k$ as a function of both $k$ and $n$ for the classical coupon collector problem (with equal probabilities) and found there are at least 4 different limits for $W_k$: degenerate, poisson, gaussian or gumbal, depending on the way $k,n$ scale with eachother. You can find a summary of these on page 3 of this reference. I strongly presume that similar results will hold for $D_t$, but the specifics for generalized probabilities are likely much more complicated to analyze. However, for a finite number of objects, the ultimate limit shapes are most likely the above distributions.