# Expected value of balls left, drawing colored balls with 0.5 probability

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

Every minute, you toss a coin and decide which color to draw, then remove one ball of that color from the urn. (e.g. remove one green ball if it is a tail)

What is the expected number of balls left in the jar after you have drawn all red or green balls?

Note that 0 <= m+n <= 10^5 And the solution should be implemented in a way that it return results within 5 second using 1 CPU and 1GB ram.

p.s. this is an interview question I found online (from some interview question banks), tried to attack this problem using binomial / negative-binomial distribution but no luck so far

• Have you got any details about the coin? Is it fair? Commented Jul 28, 2021 at 4:43
• Yes, it's a fair coin @Spätzle Commented Jul 28, 2021 at 4:46
• How does it differ from your previous question? stats.stackexchange.com/questions/520599/… Commented Jul 28, 2021 at 5:01
• @Spätzle, in this question, any ball is removed with 0.5 probability every round because of the fair coin Commented Jul 28, 2021 at 5:04
• There's a connection to the negative binomial but it's not itself negative binomial. It's conceptually straightforward to write a loop that "pushes" probabilities from the starting state towards the stopping states if you just need a numeric calculation. Commented Jul 28, 2021 at 5:51

So you've got $$m$$ red balls and $$n$$ green balls. As the coin is fair, $$P(Green)=P(Red)=0.5$$.

Assume we've had $$k$$ draws, the probability of drawing $$g$$ greens and $$k-g$$ reds is $$P(k,g)={k \choose g}0.5^{k}$$, and the number of balls left in the urn is $$m+n-k$$. The expected value of balls left in the urn (given one color is completely out) is then:

$$\sum_{k=n}^{n+m-1}{(m+n-k){k \choose n}0.5^k}+\sum_{k=m}^{n+m-1}{(m+n-k){k \choose m}0.5^k}$$

So if you're going to solve this numerically, write two loops and you're good.

But wait a second, what if $$k$$ is too large for a factorial computation? or we fear it might be too slow? This is where the normal approximation becomes handy. As $$p=0.5$$ it is proper for any $$k \geq 10$$, according to the $$3\sigma$$ rule of thumb. The derivation of the expected number of balls left is very simple.

So, overall, your function should condition of the size of the input: if $$m,n<10$$ you should sum using the formula above; otherwise, solve using the normal.

• These sums have closed formulas ;-).
– whuber
Commented Jul 28, 2021 at 12:11
• yes @whuber I suppose so but I did not find them quickly enough and in any way the normal approximation should do it. I believe this should be a variant of $\sum_{k}{k{n \choose k}}=n2^{n-1}$ but I didn't get the proper maneuver when writing. Commented Jul 28, 2021 at 14:47
• The problem is that when $n+m$ is large, such as $10^5$ (as in the question), the terms in the sums will overflow and underflow, so some kind of simplification is needed.
– whuber
Commented Jul 29, 2021 at 13:50
• That's why I've referred to the normal approximation Commented Jul 29, 2021 at 16:37
• Thanks for the answer, the normal approximation is a great idea and indeed it should be good enough and works in practice @whuber do you think it is possible to have a closed formulas for those sums? I spent days trying to crack it but still no luck, hope you could shed some lights on it Commented Aug 2, 2021 at 1:46