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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.