How many chips drawn with replacement until a duplicate is found?

Question

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?

Answer 1

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} $

Answer 2

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). $$