6
$\begingroup$

Suppose we have an urn containing $m \in \mathbb{N}$ objects and we sample with replacement $n \in \mathbb{N}$ times with equal chance of sampling any object in any draw. Let $1 \leqslant K \leqslant \min(n,m)$ be the number of different objects we sample. We can represent this problem as follows:

$$\mathbf{N} \sim \text{Multinomial}(n, (\tfrac{1}{m}, \cdots, \tfrac{1}{m})) \quad \quad \quad \quad K \equiv \sum_{i=1}^m \mathbb{I}(N_i >0).$$

Find the probability mass function for $K$ (in its simplest form).

$\endgroup$
0

2 Answers 2

6
+50
$\begingroup$

The probability that $K = k$ is given by $$ p(k) = \frac{\binom{m}{k} f(n,k)}{m^n} $$ where $f(n,k)$ is the number of sequences consisting of only the integers $i = 1, \ldots, k$ of length $n$ in which each $i$ occurs at least once. To see this, note that we want the probability that exactly $k$ unique entries appear in a sequence of $n$ draws from a discrete uniform on $1, \ldots, m$. We can get this in two steps by (1) selecting which $k$ entries of the $m$ will appear and (2) choosing a sequence in which each appears at least once. The total number of sequences of length $n$ is $m^n$ which gives the denominator.

If one considers the Stirling numbers of the second kind to be "closed form" then $f(n,k)$ can be simplified as $$ f(n,k) = S(n,k) k! $$ Recall that $S(n,k)$ counts the number of ways to partition $n$ objects into $k$ non-empty equivalence classes. So, we simply partition each of our $n$ draws into $k$ classes, such that the entries in each equivalence class will be associated to the same $i \in \{1,\ldots,k\}$. Next, we need to actually associated each $i$ to the equivalence classes, and there are $k!$ ways to do this. Simplifying, we get $$ p(k) = \frac{m! S(n,k)}{(m-k)! m^n} $$ for the final answer. This should be as simple as the answer can possibly get, because Stirling numbers cannot be simplified.

Some R code to verify that this is correct, Stirling code taken from here:

Stirling2 <- function(n,m)
{
    ## Purpose:  Stirling Numbers of the 2-nd kind
    ##      S^{(m)}_n = number of ways of partitioning a set of
    ##                      $n$ elements into $m$ non-empty subsets
    ## Author: Martin Maechler, Date:  May 28 1992, 23:42
    ## ----------------------------------------------------------------
    ## Abramowitz/Stegun: 24,1,4 (p. 824-5 ; Table 24.4, p.835)
    ## Closed Form : p.824 "C."
    ## ----------------------------------------------------------------

    if (0 > m || m > n) stop("'m' must be in 0..n !")
    k <- 0:m
    sig <- rep(c(1,-1)*(-1)^m, length= m+1)# 1 for m=0; -1 1 (m=1)
    ## The following gives rounding errors for (25,5) :
    ## r <- sum( sig * k^n /(gamma(k+1)*gamma(m+1-k)) )
    ga <- gamma(k+1)
    round(sum( sig * k^n /(ga * rev(ga))))
}

set.seed(123)
n <- 7
m <- 5

f <- function(k) {
  choose(m,k) * Stirling2(n,k) * factorial(k) / m^n
}

foo <- t(replicate(100000, sample(1:m, n, replace = TRUE)))
foo2 <- apply(foo, 1, function(x) length(unique(x)))

f_hat <- mean(foo2 == 3)
f_hat + c(-1,0,1) * 1.96 * sqrt(f_hat * (1 - f_hat) / 100000)
## [1] 0.2276407 0.2302500 0.2328593
f(3)
## [1] 0.231168
sum(Vectorize(f)(1:m))
## [1] 1
$\endgroup$
2
  • 1
    $\begingroup$ This is a great answer (+1). I assume from your reasoning that you are proceeding for the case where $n \leqslant m$. Can you verify that this sums to one over the allowable range? $\endgroup$
    – Ben
    Aug 7, 2018 at 9:48
  • $\begingroup$ @Ben $n > m$ is allowed. I checked that it sums numerically (my example code is in this case). The easiest proof that this sums to 1 is probably the proof that it is the pmf of $K$, but it is possible also to do by computing $f(n,k)$ by inclusion-exclusion I think. $\endgroup$
    – guy
    Aug 7, 2018 at 13:27
2
$\begingroup$

Having now done some more study on this problem I have found that this is actually a distribution that has received quite a lot of attention in the mathematical literature. The general problem is called the "classical occupancy problem" and the resulting distribution of the number of occupied groups is called the "occupancy distribution". This distribution has been studied in detail (see e.g., Johnson and Kotz 1977; Kolchin et al 1978). The mass function is:

$$p_K(k) = \frac{(m)_k \cdot S(n,k)}{m^n} \quad \quad \quad \text{for all } 1 \leqslant K \leqslant \min (m,n),$$

where the values $(m)_k = m (m-1) \cdots (m-k+1)$ are the falling factorials. This distribution is included in some books on discrete distributions, but it is more obscure than the standard discrete distributions, and as a result, it is not well-known. Nevertheless, the distribution has been studied in great detail and its moments and generating functions are known.


Moments: The form of the distribution leads to a simple formula for the expected falling factorials:

$$\mathbb{E}((K)_r) = (m)_r \Big( \frac{m-r}{m} \Big)^n.$$

Since $(K)_r$ is a polynomial of degree $r$ in $K$, this leads to corresponding results for the raw and central moments. These get very messy for the higher-order moments, but the formulae for the mean and variance are fairly simple:

$$\begin{equation} \begin{aligned} \mathbb{E}(K) &= m \Bigg[ 1 - \Big( \frac{m-1}{m} \Big)^n \Bigg], \\[6pt] \mathbb{V}(K) &= m \Bigg[ (m-1) \Big( \frac{m-2}{m} \Big)^n + \Big( \frac{m-1}{m} \Big)^n - \Big( \frac{m-1}{m} \Big)^{2n} \Bigg]. \\[6pt] \end{aligned} \end{equation}$$


Asymptotic results: There are various well-known limiting results that look at the asymptotic form of the distribution as $m \rightarrow \infty$ and $n \rightarrow \infty$. Results depend on the "domain of convergence", but for a broad limiting domain the distribution of the number of empty cells converges to either a normal distribution or a Poisson distribution (see Kolchin et al 1978, Ch 4). For finite parameter values the Poisson approximation suffers from the fact that it constrains the variance, so it it a poor approximation except for very large $n$. Nevertheless, for very large $n$ we have:

$$n-K \sim \text{Pois}(m \cdot e^{-n/m}).$$

The normal approximation is generally a preferable approximation, since it allows freedom of the mean and variance. For large $n$ and $m$ we have the approximation:

$$K \sim \text{N}(\mu = \mathbb{E}(K), \sigma^2 = \mathbb{V}(K)).$$


References

  • Johnson, N.L. and Kotz, S. (1977) Urn Models and their Applications. John Wiley and Sons: New York.

  • Kolchin, V.F., Sevast'yanov, B.A. and Christyakov, V.P. (1978) Random Allocations. John Wiley and Sons: New York.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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