Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

marked as duplicate by Fabian, joriki, Brian M. Scott, Sasha, Rudy the Reindeer Oct 5 '12 at 12:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

@David: It is, and joriki’s nice answer recapitulates Byron Schmuland’s accepted answer to the earlier question. – Brian M. Scott Oct 4 '12 at 21:52
up vote 5 down vote accepted

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


share|cite|improve this answer
+1. As I said in my answer, there ought to be a slick way to do it instead of brute-force algebra. – Michael Hardy Oct 4 '12 at 21:49
. . . . . 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. – Michael Hardy Oct 4 '12 at 21:50

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


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

share|cite|improve this answer

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.