1
$\begingroup$

The context for this is that I was trying to solve the problem 3.11.13 (c) from the Grimmett & Stirzaker textbook :

(b) An urn contains b blue and r red balls. Balls are removed at random until the first blue ball is drawn. Show that the expected number drawn is (b + r + 1)/(b + 1).

(c) The balls are replaced and then removed at random until all the remaining balls are of the same colour. Find the expected number remaining in the urn.

Let's write this expectation : $E[T]$

So I translated the problem into something more amenable. I consider that we draw all $r+b$ balls successively and line them up from left to right. I noticed that given that the remaining color is blue, the probability of having a certain number $k$ of blue balls left in the urn is the same as the probability (say $\mathbb{P}(T=k|B)$ ) for the $r+b-k$-th ball to be red and all balls to the right to be blue. The order doesn't matter in drawing without replacement situations so it is as if the first ball we drew was red and the next $k$ balls after that were blue, therefore we have :

$\mathbb{P}(T=k |B) = \frac{r+b}{b} \frac{r}{r+b} \frac{b}{r+b-1} \dots \frac{b-(k-1)}{r+b-1-(k-1)}$.

So by the obvious notation we get : $E[T] = \frac{b}{r+b}E[T|B] + \frac{r}{r+b}E[T|R]$

Long story short we obtain :

$\frac{b}{r+b} E[T|B] = \sum_{i=1}^b k \frac{r}{r+b} \frac{b}{r+b-1} \dots \frac{b-(k-1)}{r+b-1-(k-1)} = \sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}}$

I took a peek at the answer I'm supposed to get, so I know that $\frac{b}{r+b} E[T|B]$ is supposed to be equal to $\frac{b}{r+ 1}$, but I don't know how to simplify it.

tl;dr,

I'm trying to prove that :

$\sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}} = \frac{b}{r + 1}$

Anyone can help?

EDIT:

The hockey-stick identity was the way to go (had no idea it was a thing).

We rearrange $\sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}}$ to get : $\sum_{k=1}^b \frac{b! (r+b-k)!}{(b-k)! (r+b)!} = \frac{1}{\binom{b+r}{r}}\sum_{k=1}^b \binom{r+b-k}{r} = \frac{1}{\binom{b+r}{r}}\sum_{k=r}^{r+b-1} \binom{k}{r}$

Which yields $\frac{b}{r+1}$ using the hockey-stick identity!

$\endgroup$
2
  • $\begingroup$ Here's how to ask a good question. Follow these guidelines to get help in this forum. It's particularly important that you share your own work and thoughts on the problem to show that you have made a serious effort by yourself before asking for help, and you're not just trying to get others to solve it for you. $\endgroup$
    – jjagmath
    Jan 26 at 9:03
  • $\begingroup$ Here you go I've added some context to my question to prove that I'm not trying to use people's kindness to get a good grade on my homework. $\endgroup$ Jan 26 at 9:50

1 Answer 1

1
$\begingroup$

There shouldn't be an $r$ in the sum, i.e. the result should be

$$\sum_{k=1}^b \frac{\binom{b}{k}}{\binom{r+b}{k}} = \frac{b}{r+1}$$

Hint: write the binomial coefficients with factorials, shuffle it around (maybe you need to introduce something new to form a new binomial coefficient) and use the hockey-stick identity.

$\endgroup$
1
  • $\begingroup$ Thank you for your help, I had never heard of the hockey-stick identity, it's easy now! $\endgroup$ Jan 28 at 10:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .