1
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Have you got any details about the coin? Is it fair? $\endgroup$
    – Spätzle
    Commented Jul 28, 2021 at 4:43
  • $\begingroup$ Yes, it's a fair coin @Spätzle $\endgroup$
    – Louis Law
    Commented Jul 28, 2021 at 4:46
  • $\begingroup$ How does it differ from your previous question? stats.stackexchange.com/questions/520599/… $\endgroup$
    – Spätzle
    Commented Jul 28, 2021 at 5:01
  • $\begingroup$ @Spätzle, in this question, any ball is removed with 0.5 probability every round because of the fair coin $\endgroup$
    – Louis Law
    Commented Jul 28, 2021 at 5:04
  • $\begingroup$ 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. $\endgroup$
    – Glen_b
    Commented Jul 28, 2021 at 5:51

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ These sums have closed formulas ;-). $\endgroup$
    – whuber ♦
    Commented Jul 28, 2021 at 12:11
  • $\begingroup$ 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. $\endgroup$
    – Spätzle
    Commented Jul 28, 2021 at 14:47
  • $\begingroup$ 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. $\endgroup$
    – whuber ♦
    Commented Jul 29, 2021 at 13:50
  • $\begingroup$ That's why I've referred to the normal approximation $\endgroup$
    – Spätzle
    Commented Jul 29, 2021 at 16:37
  • 1
    $\begingroup$ 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 $\endgroup$
    – Louis Law
    Commented Aug 2, 2021 at 1:46

Your Answer

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

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