Combinatorial reasoning in an expected value problem

Question

I saw this problem:

There is an urn with $a$ red and $a$ blue balls. We are drawing from it without replacement until we have drawn all the blue balls (we know there are $a$ of them). What is the expected value of the number of balls remaining in the urn?

This can be solved by taking $a+ (a-1) {a \choose 1} + (a-2) {a+1 \choose 2}+\dotsb+1 {2a-2 \choose a-1 } $ and applying the identity $\sum_{i=0}^{k} {n+i \choose i}= {n+k+1 \choose k} $ multiple times. It gives $\frac {2a \choose a+1} {2a \choose a}$ which simplifies to $\frac {a}{a+1}$.

Is there a reasoning that produces this result directly?

Answer 1

I also have a heuristic, non-combinatorial approach.

This problem can be recast as a boxes and balls problems.

Imagine that you lay out all $a$ blue balls in a row. You have $a$ red balls in your hand. Imagine that there are "boxes" between the blue balls and two "boxes" at the ends of the row. Let $I_j$ indicate whether or not the ball $j$th red ball was thrown into the last box. We can pretend that this last box is the urn that contains the number of red balls $X$ remaining after we've drawn the last blue one. Notice that the probability that a particular red ball is thrown into the last bin is $\frac{1}{a+1}$. Then $$E[X] = E\left[\sum_{j = 1}^a I_j\right] = a P(I_j = 1) = \frac{a}{a+1}.$$

Answer 2

EDIT: The below answer may not be as "combinatorial" as you desire, but I think conditioning on the first draw and using recursion might give some insight into the problem.

Let $p(a,b)$ be the number of expected balls remaining when playing the same game, but initially there are $a$ blue balls and $b$ red balls. Clearly $p(1,1)=\frac{1}{2}$. By conditioning on the first draw, $p(a,1)=\frac{1}{2}p(a-1,1)+\frac{1}{a+1}p(a,0)=\frac{a}{a+1}p(a-1,1)$, and by induction $$ p(a,1)=\frac{1}{a+1} $$ Similarly, $$p(1,b)=\frac{1}{b+1}p(0,b)+\frac{b}{b+1}p(1,b-1)$$ and by induction again we can see $$ p(1,b)=\frac{b}{2}. $$ This suggests the general answer may be $p(a,b)=\frac{b}{a+1}$.

Now using double induction on $a, b$ gives $$ p(a,b)=\frac{a}{a+b}p(a-1,b)+\frac{b}{a+b}p(a,b-1)=\frac{b}{(a+1)}, $$ from which you may set $a=b$ to get your answer