# Two bins with n balls each, find O(expectation of balls left) after one of the bins is empty.

Given two bins with $n$ balls each, on each step with equal probability, you take a ball from one of the bins. When balls in one of the bins finish, what is $O$(expectation of balls in the other bin)?

Edit: I had this question in a quantitative researcher interview and the answer is $\sqrt n$. I also simulated it as a part of the interview and it is indeed square root of $n$.

• Oh yeah, so I have written down explicit expectation formula and got something like $\sum_{x=0}^n 2x (\frac 1 2)^{2n-x} {2n-x \choose n}$ but couldn't find big-O of that. – nhtrnm Oct 6 '17 at 16:15
• I came up with what appears to me as a slightly different value for the probability of having $x$ balls left in one of the bins when the last ball is extracted from the other bin. For me it is $P(x) = 2\left(\frac{1}{2}\right)^{2n-x}\binom{2n-x-1}{n-1}$, for $x=1,2,\dots,n$. ($x=0$ is not a possibile value since, if I got it right, the process ends when the last ball is extracted by either one bin. Correct?) Sorry if the comment is useless or even wrong. I was curious and tried out myself. That is all for now... – dfnu Oct 6 '17 at 21:11
• Oh you’re right. I am totally wrong. But yeah the problem remains as to how to find big-O of that. – nhtrnm Oct 6 '17 at 23:20

Suppose two bins contain $n$ balls each. Repetedly choose one bin at random and extract one ball from it. Let $X$ be the number of balls that remain in one bin when the other is emptied. Show that that $\mbox{E}[X] = O(\sqrt n)$ for $n\rightarrow \infty$.
Let us first consider the probability of $X=k$, for $k=1,2,\dots,n$. If exactly $k$ balls are left - say - in the first bin when the second is emptied, that means that $n + n -k = 2n-k$ extractions have occured, the last one being from the second bin. The previous $2n-k-1$ exctrations can form any sequence containing exactly $n-1$ balls from the second bin. Noting that each sequence has probability $\left(\frac{1}{2}\right)^{2n-k}$ and that the same reasoning must be repeated also for sequences terminating by emptying the first bin, we obtain the following result. $$P(X = k) = 2 \left(\frac{1}{2}\right)^{2n-k}\binom{2n-k-1}{n-1}.$$ Thus the requested exptected value is \begin{eqnarray*} \mbox{E}[X] &=& \sum_{k=1}^{n}2 k \left(\frac{1}{2}\right)^{2n-k}\binom{2n-k-1}{n-1}=\\ &=& \sum_{k=0}^{n-1}2 (k+1) \left(\frac{1}{2}\right)^{2n-k-1}\binom{2n-k}{n-1}=\\ &=&\frac{2^{2-2n}}{(n-1)!}\cdot\sum_{k=0}^{n-1} (k+1)2^k\frac{(2n-k)!}{(n-k+1)!}. \end{eqnarray*} We can use now Stirling's asymptotic expression of the factorial terms to get \begin{eqnarray*} \mbox{E}[X] &\sim & \frac{2^{2-2n}\mbox{e}^{-n}}{\sqrt{2\pi (n-1)} (n-1)^n}\cdot \sum_{k=0}^{n-1} (k+1)2^k\sqrt{\frac{2n-k}{n-k+1}}\left(\frac{2n-k}{n-k+1}\right)^{n} \sim\\ &\sim & \frac{2^{2-2n}\mbox{e}^{-n}}{\sqrt{\pi(n-1)} (n-1)^n}\cdot \sum_{k=0}^{n-1} (k+1)2^k\left(\frac{2n-k}{n-k+1}\right)^{n}=\\ &=&\frac{2^{2-2n}\mbox{e}^{-n}}{\sqrt{\pi(n-1)} (n-1)^n}\cdot \sum_{k=0}^{n-1} (k+1)2^k\left(1+\frac{n-1}{n-k+1}\right)^{n}\leq\\ &\leq &\frac{2^{2-2n}\mbox{e}^{-n}}{\sqrt{\pi(n-1)} (n-1)^n}\cdot \sum_{k=0}^{n-1} (k+1)2^k\left(1+\frac{n-1}{2}\right)^{n} \sim\\ &\sim &\frac{2^{2-2n}\mbox{e}^{-n}}{\sqrt{\pi(n-1)} (n-1)^n}\cdot \sum_{k=0}^{n-1} (k+1)2^k\left(\frac{n-1}{2}\right)^{n}=\\ &=&\frac{2^{2-3n}\mbox{e}^{-n}}{\sqrt{\pi(n-1)}}\cdot \sum_{k=0}^{n-1} (k+1)2^k \end{eqnarray*} We use now the results $$\sum_{k=0}^{n-1} 2^k = 2^n-1$$ and $$\sum_{k=0}^{n-1} k2^k = (n-2)2^n+2$$ to obtain \begin{eqnarray*} \mbox{E}[X] &=&O\left( \frac{2^{2-3n}\mbox{e}^{-n}}{\sqrt{\pi(n-1)}}\cdot[2^n(n-1)+1]\right)=\\ &=&O\left(\frac{2^{2-2n}(n-1)\mbox{e}^{-n}}{\sqrt{\pi(n-1)}}\right)=\\ &=& O\left(\sqrt n\right). \end{eqnarray*}