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 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<i<n$
$$ 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}$