# Expected Steps for $k$ Balls in Bin A

I've been stuck on this expected value question for some time now, for some reason:

Suppose we have two bins. Bin A has $$k$$ balls and Bin B has $$n-k$$ balls. For each step, we randomly pick a ball from one of the bins (so each ball has a $$1/n$$ chance of being selected each time) and move it to the other bin. What is the expected number of steps required until there are $$k$$ balls in Bin A again?

As for my work, I let $$E_i$$ be the expected number of steps required until there are $$k$$ balls in Bin A, if we started out with $$i$$ balls in Bin A. Then I found that $$E_i=\frac inE_{i-1}+\frac{n-i}nE_{i+1}+1$$ for $$i$$ for $$1\le i\le n-1$$. For $$0$$ and $$n$$, I found that \begin{align*}E_0&=E_1+1\\E_n&=E_{n-1}+1.\end{align*} When I tried to solve this system of equations, I got some really ugly constants that I couldn't figure out how to simplify. In particular, I found that \begin{align*}E_1&=E_2+\frac{n+1}{n-1}\\E_2&=E_3+\frac{n^2+n+2}{(n-1)(n-2)}\\E_3&=E_4+\frac{n^3+5n+6}{(n-1)(n-2)(n-3)}.\end{align*} I feel like this might not be the right approach, so feel free to suggest something completely different. Thanks!

Edit: I've edited my initial conditions, but I still can't get it to work out.

• Your initial conditions are wrong. $E_0=1+E_1$, for instance. The ball must be chosen from the full bin. – saulspatz Jul 22 at 16:18
• @saulspatz Apparently, I copied in the incorrect initial conditions, but I was actually using the correct ones. Still not sure how to do this :( – boink Jul 22 at 16:59
• You need to work $k$ into the picture. For $i=k\pm1$, one of the terms $E_{i-1}$ or $E_{i+1}$ in your recurrence should be replaced by $1$. – Steve Kass Jul 22 at 17:11
• @SteveKass Okay, that makes sense to me. I'm sorry, but I don't quite see how that solves the problem, since all that happens is I have split this problem into two (smaller) problems, where the endpoints are $0$ and $k-1$ (or $k+1$ and $n$), rather than $0$ and $n$. If someone could explain this, that'd be brilliant! Thanks :) – boink Jul 22 at 17:41
• I posted what I think are the right recurrence relations as an answer, as it's too long for a comment. – Steve Kass Jul 22 at 19:18

Your recursion is only right is we define $$E_i$$ such that $$E_k=0$$ (hence, not the expected time to get $$k$$ balls again, but to simply get $$k$$ balls). Then the recursion is indeed

$$E_i=\frac inE_{i-1}+\frac{n-i}nE_{i+1}+1 \hskip{1cm} i\ne k, \; 0\le i\le n \tag 1$$ with $$E_i=0$$ if $$i=k$$ or $$i<0$$ or $$i>n$$.

Once we have $$E_i$$, the required expected time is $$F_k=\frac knE_{k-1}+\frac{n-k}nE_{k+1}+1$$.

The linear system $$(1)$$ has $$n$$ variables and $$n$$ equations, it can be solved numerically (for example, writing the system in matricial form). But I'm not sure about a symbolic solution.

Alternatively, and perhaps a little more elegant, this can modelled as a Markov chain with $$n+1$$ states, and the expected time between visits can be obtained from its limiting distribution. Again, this is easy... numerically.

Update: this is an Ehrenfest model. The following is adapted/copied from here.

Let $$C_{i, j}$$ be the expected time to get from $$i$$ balls to $$j$$ balls in the first bin, with $$C_{i,i}=0$$

Then, for $$0

$$C_{i,n}=\frac{i}{n} C_{i-1,n}+\frac{n-i}{n} C_{i+1,n}+1 \tag 2$$

(like eq. $$(1)$$ , a little more general). Or

$$n(C_{i,n}-C_{i+1,n} - 1 ) =i( C_{i-1,n}-C_{i+1,n} )\tag 3$$

But we also know, by linearity of expectation

$$C_{i,n}=C_{i,i+1} +C_{i+1,i+2} + \cdots + C_{n-1,n} \tag4$$

Putting both eqs together:

$$n (C_{i,i+1} -1)=i(C_{i-1,i} +C_{i,i+1}) \implies A_i(n-i)=i A_{i-1} +n\tag{5}$$ where $$A_i=C_{i,i+1}$$. With the initial condition $$A_0=1$$ this is solved by

$$A_i=\frac{\sum_{t=0}^{i}\binom{n}{t}}{\binom{n-1}{i}} \tag6$$

By simmetry of the bins, $$B_i \triangleq C_{i,i-1} = C_{n-i,n-i+1}=A_{n-i}\tag 7$$

Finally our desired expected time is

$$F_k = 1 + \frac{k}{n}A_{k-1} + \frac{n-k}{n}B_{k+1}=1 + \frac{k}{n}A_{k-1} + \frac{n-k}{n}A_{n-k-1}\tag8$$

...which, operating, gives $$F_k=\frac{2^n}{\binom{n}{k}} \tag9$$

This result is surprisingly (embarrasingly) simple, so perhaps I messed up something or either there should be a much simpler derivation... (Granted, this derivation solves a more general problem: it gives the expected time from any values of the start and end ocuppancy values)

Update 2: I wrote the result above and I saw this: if we regard this as a Markov Chain, but with the $$2^n$$ states corresponding to which (labeled) balls are in bin $$A$$, then the chain is reversible (the matrix is doubly stochastic) and hence the states are equiprobable in the equilibrium distribution, with $$p=1/2^{n}$$ each. Then the $$n+1$$ macro states composed of those states having $$k$$ balls have total probability $$\binom{n}{k}/2^n$$, and the mean recurrence time is $$2^n/\binom{n}{k}$$

[Not a full answer, but too long for a comment.]

The correct recursion for this problem is a little different than yours, which doesn’t account for actually reaching the goal of $$k$$ balls in the bin.

Let $$E(i)$$ be the expected number of steps needed to reach $$k$$ balls in bin A for the first time in the future, if there are currently $$i$$ balls in bin A and $$n-i$$ balls in bin B.

For $$i$$ equal to $$0$$ or $$n$$:

$$\begin{equation} E(0) = \begin{cases} 1+E(1) & \mbox{ if } k\neq1 \\ 1 & \mbox{ if } k=1 \end{cases} \end{equation}$$

$$\begin{equation} E(n) = \begin{cases} 1+E(n-1) & \mbox{ if } k\neq n-1 \\ 1 & \mbox{ if } k=n-1 \end{cases} \end{equation}$$

For $$0< i < n$$,

$$\begin{equation} E(i) = \begin{cases} \frac in E(i-1)+\frac{n-i}nE(i+1)+1 & \mbox{ if } k\notin\{i-1,i+1\} \\ \frac in +\frac{n-i}n(1+E(i+1)) & \mbox{ if } k=i-1 \\ \frac{n-i}n +\frac in(1+E(i-1)) & \mbox{ if } k=i+1 \end{cases} \end{equation}$$