# Expected Value Of Number of Removals From Urn

Here's the question: "An urn contains b blue balls and r red balls. You repeatedly and independently remove balls from urn (without returning them) until the first blue ball is drawn. All balls currently in the urn have an equal probability of being selected each time a ball is removed. Define the random variable X as the number of balls that are drawn (number of red balls that are removed plus the first blue ball that is removed). Find E[X], the expected value of random variable X."

I'm having trouble finding a closed form expression for the expected value. Here's the work I've done:

• @callculus: no, the balls aren't replaced. – Yves Daoust Mar 3 '17 at 23:08
• @YvesDaoust "All balls have an equal probability of being selected each time a ball is removed." Due to this part I thought it is with replacement, especially the part "equal probability". – callculus Mar 3 '17 at 23:13
• What is meant by define $x$? – VortexYT Mar 3 '17 at 23:13
• @callculus: the term "removed" is used twice. The term "drawn" is also used twice, but only for the last ball. – Yves Daoust Mar 3 '17 at 23:16
• Balls are removed and not replaced. You stop taking out balls until you remove your first blue ball, and the random variable X takes the value for how many draws it took to get to this point. – LeBron James Mar 3 '17 at 23:17

You are on the right path in solving the problem, however, there is a nice technique for evading the calculations, which is finding the expected value using indicator functions.

First, number the red balls from $$1$$ to $$r$$ and define $$X_i$$ to be the function indicating whether ball number $$i$$ is drawn before the first blue ball or not. So $$X_i$$ is $$1$$ if the i'th ball is drawn before the first blue ball and zero otherwise.

Now, it is easy to see that $$X$$ is the sum of indicators, i.e. $$X = 1 + \sum_{i=1}^r X_i$$

so the expected value of both sides are equal, and using the expected of the sum property and the symmetry between $$\mathbb{E}[X_i]'s$$, we get:

$$\mathbb{E}[X] = 1 + \sum_{i=1}^r \mathbb{E} [X_i] = 1 + r\mathbb{E}[X_1] = 1 + r\mathbb{P}[X_1]$$

the problem now boils down to finding the probability that the first red ball is drawn before the first blue ball, which is just $$\frac{1}{b+1}$$, since out of b+1 different ways of putting 1 red ball and b blue balls next to each other, only the one which the first red ball comes first is valid. you can then arrange other red balls where ever you want.

Finally, the expected value is given by:

$$\mathbb{E}[X] = 1 + \frac{r}{b+1}$$

Hint:

The first drawing gives a blue with probability $d_1=b/(b+r)$.

Otherwise, the second drawing gives a blue with conditional probability $d_2=b/(b+r-1)$.

Otherwise, the third drawing gives a blue with conditional probability $d_3=b/(b+r-2)$.

...

Otherwise, the $r+1^{th}$ drawing gives a blue with conditional probability $d_{r+1}=b/b$.

Then

$$p_1=d_1,\\ p_2=(1-p_1)d_2=d_2-d_1d_2,\\ p_3=(1-p_2)d_3=d_3-d_2d_3+d_1d_2d_3,\\ \cdots\\ p_{r+1}=(1-p_r)d_{r+1}=d_{r+1}-d_rd_{r+1}+d_{r-1}d_rd_{r+1}+\cdots \pm d_1d_2d_3\cdots d_{r+1}.$$

Let $E[r,b]$ denote the desired answer.

Consider the problem this way:

You have $r$ red balls in a line and you are going to insert $b$ blues into that line. These will divide the red balls into $b+1$ strings of red balls. By symmetry, each of these is expected to have the same length which must then be $\frac {r}{b+1}$. It follows that your answer is $$E[r,b]=\boxed {\frac r{b+1}+1}$$

Note 1: to get intuition for the symmetry argument, first imagine that the red balls are arranged in a circle instead of a line and that there is $1$ yellow ball added in with the blues. It is now clear I think that the gaps must have the same expected length $\frac r{b+1}$ and deleting the yellow ball restores the problem to the original.

Note 2: If you still find the symmetry argument hard to intuit, the answer can be verified by looking at a recursion. The first draw is either red or blue, so we get $$E[r,b]=\frac b{r+b}\times 1+\frac r{r+b}\times \left(E[r-1,b]+1\right)$$ and it is straightforward to verify that the answer obtained above satisfies this (along with the obvious boundary condition $E[0,b]=1$ for $b>0$).

• How do you solve this problem without using the symmetry argument, but with the argument I have used in my work? – LeBron James Mar 4 '17 at 2:10
• Can you solve the problem using algebra and probabilities instead of symmetry/intuition arguments? Look at the work I've done. – LeBron James Mar 4 '17 at 2:14
• Well, I wouldn't. I don't even see a quick way to solve the recursion I wrote down (though surely there must be one). Manipulating identities between all the binomial coefficients may well be possible, but likely to be hard (and the proofs of those identities will likely involve symmetry). But the recursive argument (effectively proof by induction on $r$) is purely algebraic. – lulu Mar 4 '17 at 2:15
• Can you walk through how to do this algebraically with summations? Please look at the work I've posted. In addition, we should use these identities to help arrive at the answer: i.imgur.com/4amu4EU.png, i.imgur.com/ICLFw4N.png – LeBron James Mar 4 '17 at 2:18
• That's just the definition of the Expected Value. Of course the recursion uses the definition. – lulu Mar 4 '17 at 2:19