4
$\begingroup$

In an urn, there are $m$ red balls and $n$ green balls.

Every minute, you draw one from the urn. What is the expected number of balls (regardless of its color) left in the jar after you have drawn all red or green balls?

After some experimentation, I found the expected value is $\frac{m(m+1)+n(n+1)}{(n+1)(m+1)}$ for $m$ and $n \ge 0.$

I cannot find any intuitive way to arrive to this formula.

p.s. I tried conditional expectation, p.g.f, m.g.f.

p.s.2 once I found that formula, I could prove it easily using induction. But I am very interested to know if there is any other way to arrive to that formula (maybe just from a pure probability perspective?).

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ You formula cannot possibly be correct, because the expectation will be the same when the ball colors are switched, which swaps $m$ and $n:$ therefore the formula must be invariant when $m$ and $n$ are switched. $\endgroup$
    – whuber ♦
    Apr 20, 2021 at 14:23
  • $\begingroup$ @whuber thanks for pointing out, It's a typo, I just updated with the correct formula $\endgroup$
    – Louis Law
    Apr 20, 2021 at 14:31
  • 1
    $\begingroup$ Is this a question from a course or textbook? If so, please add the self-study tag & read its wiki. $\endgroup$
    – Stephan Kolassa
    Apr 20, 2021 at 14:41
  • $\begingroup$ @StephanKolassa thanks, this is not from schoolwork. $\endgroup$
    – Louis Law
    Apr 20, 2021 at 14:50
  • $\begingroup$ The new formula gives the wrong values when $m=0$ or $n=0,$ so it's still not correct. $\endgroup$
    – whuber ♦
    Apr 20, 2021 at 14:51

1 Answer 1

Reset to default
3
$\begingroup$

This problem is interesting because an intuitive approach leads to a quick solution.

Consider a simplified version. Randomly draw every ball from the urn, one at a time, and lay them down in sequence as you do so. The sequence ends with a string of all green or all red balls. You will eventually get to keep this "monochromatic suffix" as a reward, but for now let's suppose you care only about keeping the red balls. What is your expected reward?

Look at the sequence you laid down. It consists of $m$ red balls among which $n$ green balls are interspersed. These green balls divide the red balls into $n+1$ groups (of which many may be empty). Intuitively, we would figure each group -- including the last -- must therefore contain $m/(n+1)$ red balls on average.

This can be demonstrated with a basic combinatorial argument, but that isn't necessary. Computer science teaches us it can be much easier to check the solution to a problem than to produce it in the first place. Therefore, let's immediately check this guess to see whether it needs any correcting.

The check is done by mathematical induction on the number of balls in the urn, $N=m+n.$ The formula is correct when the urn is empty; that is, when $N=m+n=0$ it gives the right answer $0/(0+1)=0.$ Suppose now the formula happens to be true for $N \ge0.$ The formula clearly is correct when $m=0$ or $n=0,$ because in either case you will keep all the red balls in the urn and the formula counts them. So, suppose both $m$ and $n$ are nonzero. We only need to show the formula holds for all the other possible values with $m+n=N;$ that is, $m=1,2,\ldots,N-1$ and $n=N-m.$

The expected reward $f(m,n),$ by definition, is the expected reward after drawing a red ball times the chance of drawing a red ball, plus the expected reward after drawing a green ball times the chance of drawing a green ball:

$$f(m,n) = f(m-1,n)\left(\frac{m}{m+n}\right) + f(m,n-1)\left(\frac{n}{m+n}\right) .$$

Since both $(m-1)+n$ and $m+(n-1)$ are less than $N,$ and we have assumed the formula holds in such cases, we may plug it into the forgoing equation to produce

$$f(m,n) =\frac{m-1}{n+1} \left(\frac{m}{m+n}\right) + \frac{m}{(n-1)+1}\left(\frac{n}{m+n}\right) = \frac{m}{n+1},$$

QED.

The analysis for the green balls is identical: just swap the colors, which swaps $m$ and $n.$ Thus, the total reward for both red and green balls is

$$f(m,n) + f(n,m) = \frac{m}{n+1} + \frac{n}{m+1}.$$

Improve this answer
$\endgroup$
3
  • $\begingroup$ the intuition mentioned is quite interesting, thanks for the answer $\endgroup$
    – Louis Law
    Apr 24, 2021 at 2:50
  • $\begingroup$ But what are the assumptions behind this intuition. If we change the problem a bit, let's say the urn is now transparent, every time we draw, we pick one colour at random, so there is 50% chance draw red/green. In this case, the answer should be different and how this intuition apply? $\endgroup$
    – Louis Law
    Apr 24, 2021 at 4:50
  • $\begingroup$ The basis for the intuition is that under the original rules, you are sampling without replacement,. whence every sequence is equally probable. When you change the rules you will need to reconsider those probabilities. $\endgroup$
    – whuber ♦
    Apr 24, 2021 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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