My question is similar to the birthday problem, but I can't seem to find a simple solution. The question (in a general form) is that, given a set of $n$ people who each choose elements from a set of $N$ elements ($p = 1/N$), what is the expected number (mean $\mu_x = E(x)$) of unique destinations that will be chosen provided an infinite number of trials.
For a specific example, imagine a skyscraper with $N$ floors and an elevator full of people on floor 0 with capacity $n$. The question, then, would be how many different stops, on average, will the elevator have to make on its trip to the $N^{th}$ floor, if it stops at every floor where $\geq1$ people need to get out.
From solutions of the birthday problem, I know that there are $n(1-\frac{1}{N})^{n-1}$ unique destinations, and $n(1-(1-\frac{1}{N})^{n-1})$ people who share a destination. From this, shouldn't the expected number of unique destinations be $n(1-\frac{1}{N})^{n-1} + n(1-(1-\frac{1}{N})^{n-1})\cdot($mean # of people who have chosen the same destination given that at least 2 people have chosen it$)$? The problem (for me at least) is determining this last term.
Thanks!
Let's use the method of indicator variables.
Let $X$ be the number of different destinations that are chosen; $X$ is a random variable whose range of values is $\{0,1,\dots,N\}.$
For each $i\in\{1,\dots,n\},$ let $X_i$ be the random variable which takes the value $1$ if at least one of the $n$ people picks the $i^{\text{th}}$ destination, $0$ if nobody picks it. Thus $X=X_1+\cdots+X_N.$
The probability that a given person, call him Joe, picks the $i^{\text{th}}$ destination is $\frac1N$; the probability that Joe does not pick the $i^{\text{th}}$ destination is $1-\frac1N$; the probability that nobody picks the $i^{\text{th}}$ destination is $(1-\frac1N)^n$; the probability that at least one person picks the $i^{\text{th}}$ destination, also known as $P(X_i=1),$ is $1-(1-\frac1N)^n.$ It follows that $$E(X_i)=0\cdot P(X_i=0)+1\cdot P(X_i=1)=P(X_i=1)=1-(1-\frac1N)^n$$ and $$E(X)=E(X_1+\cdots+X_N)=E(X_1)+\cdots+E(X_N)=N(1-(1-\frac1N)^n).$$