3

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?

lebesgue
  • 301
  • 1
    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? – JMoravitz Sep 07 '17 at 04:20
  • 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. – haydn_c Sep 07 '17 at 04:33
  • This is related to Banach's matchbox problem. – bof Sep 07 '17 at 07:49

2 Answers2

2

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$. (WHY? let $N$ be the number of tosses needed to get at least n+1 heads or tails. What is the probability $\mathbb{P}(N = k+1)$?) 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}} $$

Ryan
  • 689
  • Could you please elaborate more on how you prove the equation using the probabilistic (coin flip) approach? Thanks! – lebesgue Nov 26 '19 at 21:06
  • you mean this equation $\sum_{k=n}^{2n} {k\choose n} \frac{1}{2^{k}}=1$ ? – Ryan Dec 04 '19 at 14:35
  • Yes, what is the logic of you proof? – lebesgue Dec 06 '19 at 15:51
  • I think the $E[X]$ is 1 larger than it's supposed to be. See https://en.wikipedia.org/wiki/Banach%27s_matchbox_problem#:~:text=Banach's%20match%20problem%20is%20a,problem%20or%20provided%20an%20answer. My monte carlo answer matches with the wikipedia version – roulette01 Aug 18 '20 at 22:47
  • @lebesgue I edit my answer with some explanation (I was asked the same question very recently) – Ryan Aug 05 '21 at 20:20
0

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)=2\left(\dfrac{1}{2}\right)^n$$

$$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)$.

alpastor
  • 1,460