Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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