3
$\begingroup$

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?

  • 0
    I made a slight TeX edit. It looked liked you had the multiplication $n(i-1)$.2011-12-08
  • 0
    @DavidMitra Thanks - it now looks as I intended it.2011-12-08
  • 0
    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.2011-12-08
  • 0
    @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.2011-12-08
  • 0
    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\}$.2011-12-08
  • 0
    @DilipSarwate: Thanks! Turns out my solution with David's suggestion is right (edit: see addition to post above - I don't know how to add linebreaks here). Can you add that as an answer?2011-12-08
  • 0
    It is perfectly OK, indeed even encouraged, to post your own solution as an answer and accept it after the waiting period is over. So why don't you do that?2011-12-08
  • 0
    @DilipSarwate: Done! Thanks for your help guys.2011-12-08
  • 0
    Just wondering if the set contains all distinct chips or not?2011-12-08
  • 0
    @EmmadKareem: Yes the chips are all distinct.2011-12-08

2 Answers 2

3

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

1

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