1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nhtrnm Oct 6 '17 at 16:15
  • 1
    $\begingroup$ 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... $\endgroup$ – dfnu Oct 6 '17 at 21:11
  • $\begingroup$ Oh you’re right. I am totally wrong. But yeah the problem remains as to how to find big-O of that. $\endgroup$ – nhtrnm Oct 6 '17 at 23:20
1
$\begingroup$

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

$\endgroup$

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.