There are two urns with n red balls and n blue balls respectively.

You will first randomly choose a urn and then draw one ball from it. Repeat the process till one of the urns is empty for the first time. What is the expected amount of remaining balls, that is, how many balls are left in the non-empty urn on average?

  • 1
    $\begingroup$ Answer the following leading questions: How many sequences of $n-1$ r's and $k$ b's exist? How many sequences of pulling balls end after exactly $n+k$ turns? How many balls are left in the non-empty urn if it ended after $n+k$ turns? What is the definition of expected value? $\endgroup$ – JMoravitz Sep 7 '17 at 4:20
  • $\begingroup$ You can firstly compute the expected ball left conditioned on the time $T$ which is the first time one urn becomes empty, and then use the law of total expectation. $\endgroup$ – haydn_c Sep 7 '17 at 4:33
  • $\begingroup$ This is related to Banach's matchbox problem. $\endgroup$ – bof Sep 7 '17 at 7:49

There is a close form for the expectation. As mentioned above, $Y=2n-X$ has probability mass function $$ \mathbb{P}(Y=k)= {k-1\choose n-1} \frac{1}{2^k}, \; k\in\{n,n+1,\cdots,2n-1\} $$ We can directly compute $$ \mathbb{E}(Y) = \sum_{k=n}^{2n-1} k {k-1\choose n-1} \frac{1}{2^{k-1}} \\ = 2n \sum_{k=n}^{2n-1} {k\choose n} \frac{1}{2^{k}} $$ Now we notice that $\sum_{k=n}^{2n} {k\choose n} \frac{1}{2^{k}}=1$. This is because ${k\choose n} \frac{1}{2^{k}}$ is precisely the probability of seeing $n$ heads or tails by flipping a fair coin $k$ times. Therefore, we have $$ \mathbb{E}(Y)=2n\left(1-{2n\choose n} \frac{1}{2^{2n}}\right) \quad \text{and} \quad \mathbb{E}(X) = 2n {2n\choose n} \frac{1}{2^{2n}} $$ Using Stirling approximation, we finally see that $$ \mathbb{E}(X) = 2n {2n\choose n} \frac{1}{2^{2n}} \sim 2\sqrt{\frac{n}{\pi}} $$

  • $\begingroup$ Could you please elaborate more on how you prove the equation using the probabilistic (coin flip) approach? Thanks! $\endgroup$ – lebesgue Nov 26 '19 at 21:06
  • $\begingroup$ you mean this equation $\sum_{k=n}^{2n} {k\choose n} \frac{1}{2^{k}}=1$ ? $\endgroup$ – Ryan Dec 4 '19 at 14:35
  • $\begingroup$ Yes, what is the logic of you proof? $\endgroup$ – lebesgue Dec 6 '19 at 15:51

Let $X$=The number of trials until one of the urns is empty. We want to find the distribution of X. We know that $X$ must be at least $n$ and at most $2n-1$.


$$P(X=n+1)=2\left[ {n \choose n-1}\left(\frac{1}{2}\right)^{n-1}\left(\frac{1}{2}\right)\cdot \left(\frac{1}{2}\right)\right] = 2 \left[{n \choose n-1}\left(\frac{1}{2}\right)^{n+1} \right]$$

Continuing this we find that

$$P(X=x) = 2\left[ {x-1 \choose n-1}\left(\frac{1}{2}\right)^x \right], \;x \in \{n,n+1,...,2n-1\}$$

We need to find the expected value of $X$ because the answer to the problem (what is the expected number of ball in the remaining urn) is $2n - E(X)$. I wasn't able to find a closed form for $E(X)$. If we let $Y=X-n$ then we get that

$$ P(Y=y)=2{n+y-1 \choose n-1}\left(\frac{1}{2} \right)^{n+y} = 2{n+y-1 \choose y}\left(\frac{1}{2} \right)^{n+y}, \; y \in \{0,1,...,n-1\} $$

I thought it would be easier to find $E(Y)$ because $Y$ ranges from $0$ to $n-1$ versus $X$ which ranges from $n$ to $2n-1$ but I still wasn't able to come up with a closed form. If you could, then $E(X) = E(Y)+n$ and the answer to the original problem would be $2n- E(X) = n - E(Y)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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