Expected value of the number of different objects selected when choosing k objects from n objects with replacement

Question

Suppose there are n items on a menu, and k customers order a single item from the menu. Each customer's order is independent from any of the other orders and they are equally likely to order any item on the menu.

Of interest is the expected number of different items that were ordered.

The way I approached this problem was to define an indicator random variable, denoted $I_{i,j}$, which takes on a value of 1 if the j-th customer does not order the i-th item on the menu.

$I_{i,j}$ has the following probability mass function: $P(I_{i,j} = x) = \begin{cases} \frac{n-1}{n} \quad ,x=1\\ \frac{1}{n} \quad,x=0\\ \end{cases}$

From the definition of expectation:

$E(I_{i,j}) = 0*P(I_{i,j}=0) + 1*P(I_{i,j}=1) = \frac{n-1}{n}$

Define N as the random variable which takes on the value of different items ordered by the k customers. Then I believe we can relate N to the indicator variables defined above as follows:

$N = n - \sum_{i=1}^n (\prod_{j=1}^k I_{i,j})$

The expectation of N would thus be:

$E(N) = E( n - \sum_{i=1}^n (\prod_{j=1}^k I_{i,j}))$

From the linearity of expectations: $E(N) = E( n) - E(\sum_{i=1}^n (\prod_{j=1}^k I_{i,j}))$ $E(N) = n - \sum_{i=1}^n E(\prod_{j=1}^k I_{i,j}))$

Since each of order of the i-th item si independent of whether the i-th item was ordered by any other customer, the Expectation of the product should be equal to the product of the expectations:

$E(N) = n - \sum_{i=1}^n (\prod_{j=1}^k E(I_{i,j}))$

$E(N) = n - \sum_{i=1}^n \prod_{j=1}^k (\frac{n-1}{n})$

$E(N) = n - \sum_{i=1}^n (\frac{n-1}{n})^k$

$E(N) = n - n (\frac{n-1}{n})^k$

I was hoping somebody might be able to provide me a name for the distribution N takes (if one exists), which could help me verify my approach?

Answer 1

The slick approach is to use linearity of expectation. Let the random variable $X$ represent the number of distinct numbers chosen. Then $X=Z_1+Z_2+\cdots+Z_n$ where $Z_j=1$ if the number $j$ was chosen and $Z_j=0$ if the number $j$ was not chosen. Then $$E(X)=\sum_{j=1}^n E(Z_j)=\sum_{j=1}^n p_j$$ where $p_j$ is the probability that $j$ was chosen. Then $1-p_j$ is the probability that $j$ was not chosen in $k$ iterations, that is $1-p_j=((n-1)/n)^k$. We then get $$E(X)=n\left(1-\frac{(n-1)^k}{n^k}\right).$$