# Expected number of trials to see x unique values out of N total values

I'm new to these forums so please forgive me if my question is poorly worded/phrased. Suppose I have a list of N unique integers that I'm drawing from, one at a time, with replacement. Let x be the number of non-repeated integers I've drawn thus far (or, put another way, the number of trials thus far whose outcome was distinct from every trial before it). Finally, let n be the amount of non-repeated integers I'm seeking, n being (obviously) between [0, N]. How many trials will it take, on average, before x=n?

For example, take a deck of cards. If I'm drawing with replacement how many trials will it take until I've seen 26 different cards.

-

Welcome! Your problem is very succinctly stated and it is in fact a variation of the very famous coupon collector's problem (which is your problem for $x=n$). The wikipedia page I linked to outlines a solution, but let me repeat it here for completeness.

Let $T_i$ be the number of tries to obtain the $i$th object after the first $i-1$ have been obtained already. Then the expected number of tries to see $x$ objects is $$\operatorname{E}[T]=\operatorname E[T_1]+\cdots + \operatorname E[T_x]$$ Let us focus now on each $\operatorname E[T_i]$. Suppose you have a total of $n$ objects, all equally likely to be drawn and that you have already seen $i-1$ of them. The chances of you drawing a previously unseen object is the complement of the probability of drawing an object you've already seen. Therefore $$\Pr(\text{draw}\ i\text{th item})=1-\frac{i-1}{n}=\frac{n-i+1}{n}$$ The expected number of draws is then the reciprocal of this probability $$\operatorname E[T_i] = \frac{n}{n-i+1}$$ Your sum is then $$\operatorname{E}[T]=\sum_{i=1}^x\frac{n}{n-i+1}=n\left(H_n - H_{n-x}\right)$$ where $H_i$ is the $i$th Harmonic number (with $H_0 = 0$).

To answer your example, for a regular $52$ card deck, it would be expected to take $$\operatorname{E}[T_{26}] = 52\left(H_{52} - H_{26}\right) \approx 35.5$$ So around thirty-five and a half draws to see half the cards of a deck.

-

Following on this, the answer is $$\sum_{k=0}^{x-1}\frac{N}{N-k}=N\sum_{k=N-x+1}^{N}\frac1k.$$

-

Let's think this through: The first card drawn can't be a repeat of any previous card since there aren't any previous cards. So what is the probability that the second card repeats the first one? What is the probablilty that the third card repeats either the first or second card? Continue calculating this until you see a pattern and can derive a formula for the probability that the $n$th card repeats any of the first $n-1$ cards.

There are a few other details to deal with; this is just where my mind starts in trying to search for a solution.

-