# How many chips drawn without replacement until a duplicate is found?

Note - this problem is not homework. I'm studying for an exam and this problem is in our text (A First Course in Probability by Sheldon Ross) with no listed solution.

The problem is:

A jar contains n chips. Suppose a boy successively draws a chip from the jar, each time replacing the one drawn before drawing another. The process continues until the boy draws a chip that he has previously drawn. Let X denote the number of draws, and compute its probability mass.

So we want the probability that it will take i draws to draw a duplicate, for some fixed $0<=i<=n$. I'm using an unofficial solutions manual which claims the following solution:

$P\{X=i\} = \frac{i(i-1)}{2n}$

But that doesn't make sense to me because what if $n=6$, $i=4$? Surely $P\{X=4\}$ isn't 1?

My solution is as follows:

First we choose $i-1$ unique chips with probability $\frac{\binom{n}{i-1}}{n^{(i-1)}}$ and then we choose a duplicate chip with probability $\frac{i-1}{n}$ to get a final probability of $P\{X=i\} = \frac{\binom{n}{i-1}}{n^{(i-1)}} * \frac{i-1}{n}$.

If my solution is incorrect (I am suspicious because of the different solution from the manual), what is the flaw in my reasoning?

-
I made a slight TeX edit. It looked liked you had the multiplication $n(i-1)$. –  David Mitra Dec 8 '11 at 12:22
@DavidMitra Thanks - it now looks as I intended it. –  Cam Dec 8 '11 at 12:28
Note that in your probability for choosing $i-1$ unique chips, the numerator is counting unordered outcomes and the denominator is counting ordered outcomes. But, you can easily correct this... The answer in the solution manual is clearly incorrect, as you observed. –  David Mitra Dec 8 '11 at 12:30
@DavidMitra: I think that can be corrected by replacing $\binom{n}{i-1}$ with $\frac{n!}{(n-i+1)!}$ so the numerator counts ordered outcomes. –  Cam Dec 8 '11 at 12:35
Hint: Try computing $P\{X > i\}$ where obviously $P\{X > 1\} = 1$. The event $\{X > i\}$ occurs if the first $i$ chips drawn are all different. There are $n$ possible first chips, $(n-1)$ possible second chips, $\ldots$, $(n-i+1)$ $i$-th chips and so $$P\{X > i\} = \frac{n(n-1)\cdots(n-i+1)}{n^i}.$$ Now find $P\{X = i\}$ as $P\{X > i-1\} - P\{X > i\}$. –  Dilip Sarwate Dec 8 '11 at 12:52

Using David's suggestion to have the numerator count ordered results, my solution becomes $\frac{\frac{n!}{(n-i+1)!}}{n^{i-1}} \dot{} \frac {i-1}{n}$ . The correctness of this can be seen by the method proposed by Dilip which is probably better than the handwaving in my original post:

$P\{X>i\} - P\{X>i-1\} = \frac{n(n-1)\dot{}\dot{}\dot{}(n-i+2)}{n^{i-1}} - \frac{n(n-1)\dot{}\dot{}\dot{}(n-i+1)}{n^{i}}$

$= \frac{n\dot{}n(n-1)\dot{}\dot{}\dot{}(n-i+2)}{n^{i}} - \frac{n(n-1)\dot{}\dot{}\dot{}(n-i+1)}{n^{i}}$

$= \frac{n\dot{}\dot{}\dot{}(n-i+2) \dot{} (n-(n-i+1))}{n^{i}}$

$= \frac{\frac{n!}{(n-i+1)!}}{n^{i-1}} \dot{} \frac {i-1}{n}$

-
The probability that the $i$-th chip drawn is the first duplicate can also be calculated by multiplying the (conditional) probabilities of successive events together. The first chip is unique with probability $1$; the next is unique with probability $1-1/n$; then $1-2/n$ and so on; finally, the $i$-th chip is a duplicate with probability $(i-1)/n$. The result is $$P\{X=i\} = \left(\frac{i-1}{n}\right)\prod_{j=0}^{i-1}\left(1 - \frac{j}{n}\right).$$