1

Sheldon Ross theoretical exercice

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

Is my reasoning here correct?

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

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

...

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

CrispyBacon
  • 151

2 Answers2

1

Hint: start with small $n$, e.g. $n=2$ or $n=3$.

When $n=2$, we've got:

$\mathbb{P}[X=1]=0$ (can't have a repeat chip when there are no prior chips)

$\mathbb{P}[X=2]=\frac{1}{2}$ (The chance of redrawing the chip taken on turn 1 is $\frac{1}{2}$--there's only one other chip.

$\mathbb{P}[X=3]=\frac{1}{2}$ (If $X!=2$, then in the first two turns we took two distinct chips (which happens w.p. $\frac{1}{2}$); there are no "unturned" chips left, so we no select a repeat with probability 1.

MichaelChirico
  • 4,131
  • Maybe I'm just confusing myself now, but is the answer for $n=2$ actually $(0,\frac{1}{3},\frac{2}{3})$? There are 6 possible outcomes for the game--if we label the chips 1, 2, then the game can be any of $(1,1), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2)$; exactly 2 of these last 1 turn while 4 last 2 turns. Hmm... – MichaelChirico Jul 03 '15 at 21:30
0

The probability that someone can draw $X$ coins from the bag without drawing a coin which has already been drawn is given by the recurrence relation

$$\mathbb{P}(1)=\frac{1}{n};$$ $$\mathbb{P}(X)=\frac{n-X+1}{n}\mathbb{P}(X-1).$$

The reasoning here is that, on the $X^{\text{th}}$ draw, there will be $n-X$ coins which we will not have drawn yet out of $n$ coins.

Hence, by induction, we find that

$$\mathbb{P}(X)=\frac{(n-1)!}{(n^X)(n-X)!}.$$

Archaick
  • 2,273