2
$\begingroup$

Possible Duplicate:
Pulling cards from a deck without replacement to reach a goal: average draws needed?

I mark $n$ out of $X$ balls with a small, red dot and randomly disperse the $X$ balls in a bag. $n \ge 3$ and $X \ge n$.

I then keep drawing balls out of the bag without replacement until I get 3 balls dotted with red. How many balls am I expected to draw? With replacement, this scenario would be geometrically distributed because the chance of drawing a ball with a red dot is always $\frac{n}{X}$. How do I factor in the lacking of replacement?

  • 0
    @David: It is, and joriki’s nice answer recapitulates Byron Schmuland’s accepted answer to the earlier question.2012-10-04

3 Answers 3

5

You draw three dotted balls. There are $X-n$ undotted balls, and by linearity of expectation the expected number of undotted balls you draw is $(X-n)p$, where $p$ is the probability of drawing a particular undotted ball before you draw three dotted balls. The rank of the undotted ball relative to the $n$ dotted balls is uniformly random, so the chance that it's one of the first $3$ is $3/(n+1)$. Thus the expected number of draws is

$3+3(X-n)/(n+1)=3(1+(X-n)/(n+1))=3(X+1)/(n+1)\;.$

  • 0
    . . . . . however, I do think there are some observations in my answer that will repay some readers even after reading this answer, especially in the first paragraph.2012-10-04
1

The number of ways (order is important) to get 3 balls with a red dot in exactly $k>2$ draws is

$\binom{X-n}{k-3}\cdot\binom{n}{3}\cdot3\cdot(k-1)!$

The number of outcomes (order is important) of $k$ draws is

$\binom{X}{k}\cdot k!$

The probability $P(k)$ to have exactly k draws is

$P(k)=\frac{\binom{X-n}{k-3}\cdot\binom{n}{3}\cdot3\cdot(k-1)!}{\binom{X}{k}\cdot(k)!}$ $P(k)=\frac{\binom{X-n}{k-3}\cdot\binom{n}{3}\cdot3}{\binom{X}{k}\cdot k}$ $P(k)=\frac{ (X-n)! \cdot n! \cdot k! \cdot (X-k)!}{2 \cdot(k-3)! \cdot (X-n-k+3)! \cdot (n-3)! \cdot X! \cdot k }$ $P(k)=\frac{ (X-n)! \cdot n \cdot(n-1) \cdot(n-2) \cdot (k-1) \cdot (k-2) \cdot (X-k)!}{2 \cdot (X-n-k+3)! \cdot X! }$

The expected number of balls $E(k)$ you have to draw is

$E(k)=\sum_{k=3}^{X-n+3}P(k) \cdot k$

1

Each time you draw a ball, the probability that it's red is $n/X$. (The conditional probability that the second one is read, given that the color of the first one, depends on the color of the first one. But the probability that the second ball is red, given the composition of the population and no information about the color of the first one, is still $n/X$. Lack of replacement doesn't change that number, but it does alter the conditional probabilities.)

Here's a probability mass function: \begin{align} f(w) & = \Pr(\text{first red is on $w$th trial}) \\[10pt] & = \Pr(\text{exactly 2 red in first $w-1$ trials})\cdot\Pr(\text{red on $w$th trial} \mid \text{exactly 2 red in first $w-1$ trials}) \\[10pt] & = \frac{\text{number of ways to choose 2 red out of $n$ and $w-3$ others out of $X-n$}}{\text{number of ways to choose $w-1$ out of $X$}} \cdot \frac{n-2}{X-w+1} \\[10pt] & = \frac{\dbinom{n}{2}\dbinom{X-n}{w-3}}{\dbinom{X}{w-1}} \cdot \frac{n-2}{X-w+1}. \end{align}

Now one could say the expected number of trials is $\displaystyle\sum_{w=3}^X w f(w)$, and then seek a closed form.

I am not altogether happy with this answer for two reasons: (1) I haven't given the closed form; and (2) I think there ought to be a slick way that doesn't require finding $f(w)$. Often it's easier to find the expected value of a random variable than the whole probability mass function.

More later, perhaps . . . . . .