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$.
 A: Here is my try. I am not totally sure all the approximation steps are fine, so please have a look, if you like, and let me know.
First I reformulate the problem just to be sure I got that right and I also write down the steps we already discussed about in the comments.
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*}
