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$.
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*}