# Expected Unique Values From Limited Deck

I have been thinking on this one for a while, and I'm not quite sure the best way to approach it. I feel I'm missing something obvious, but I'm just a novice in probability, and getting a bit of a push along the way would help.

Suppose we have a deck of cards with 3 sets of the values 1 through 15 (45 cards total). If we draw 9 cards from the deck without replacement, what is the expected number of unique values drawn?

For the sake of brevity, let us call the number of unique values n. I have been attempting to solve this problem by way of calculating P(X=n) for each n between 3 and 9. There are trivial cases, for instance where the number of unique values is 9 or 3, but other values quickly gives way to a lot of combinatorics for the repeated values, and I feel that this is more work than is truly required to find E[n].

Is there something that I am missing that simplifies this calculation, such as a property of normal distributions I have overlooked, or perhaps a fast method to do this iterated expectation? Or is this lengthy method the only valid approach?

Hints: The linearity of expectation implies that $E[X+Y]=E[X]+E[Y]$

Define the indicator random variables $X_i = \begin{cases} 1&\text{if}~i~\text{was among the numbers drawn}\\0&\text{otherwise}\end{cases}$

Let $X=\sum\limits_{i=1}^{15} X_i$

What does $X$ represent then in regards to your problem?

$E[X]=E\left[\sum\limits_{i=1}^{15}X_i\right] = \sum\limits_{i=1}^{15}E[X_i]=\dots$

• Would $X$ be the number of unique values drawn in this instance? But that still leaves the probability that $X_i$ is drawn (the two values are not equally likely), correct? Is that the only missing piece then? – TheCinnaman Apr 3 '17 at 4:43
• @TheCinnaman Yes, $X$ is indeed the random variable counting the number of unique values seen. As for calculating $E[X_1],E[X_2],\dots,E[X_{15}]$, each of these fifteen values are going to be equal by symmetry, so we turn our attention to calculating $E[X_1]$ specifically. Note, it is easier in this case to calculate the probability $Pr(X_1=0)$ first and use this to calculate $Pr(X_1=1)$ since they must add to one. So... what is the probability that there are no 1's in the draw? – JMoravitz Apr 3 '17 at 4:48
• Dude/tte, you are the wo/man. So, if that is case, then we just have to get the probability that we DON'T pick the 3 cards with the value $i$. So we have $P(X_i =0) = \frac{42}{45}\times \frac{41}{44} \ldots$, or more simply $P(X_i=0)=\frac{\frac{42!}{(42-9)!}}{\frac{45!}{(45-9)!}}$. Then, we just take the inverse, and that is $E[X_i]$, just multiply by 15 and you are done. Of course, in the general case, we actually perform the sum, but these expectations are identical. If I am correct, that gives $E[X] = \frac{3525}{473}$ or about $7.45243$. – TheCinnaman Apr 3 '17 at 4:56
• Quite. You'll find several examples of questions where calculating expected value directly (like you appeared like you were about to do here) is incredibly tedious, but by breaking it apart as the sum of multiple random variables allows you to simplify things tremendously. Breaking apart as the sum of binary random variables also can be especially powerful when using things like the probabilistic method. When something is overly tedious, it often helps to look for a more convenient way to do things. – JMoravitz Apr 3 '17 at 5:02
• That is exactly why I came here. Your help was invaluable in cracking this nut. Now that you show me that, it's such a simple problem. – TheCinnaman Apr 3 '17 at 5:03