An urn is filled with n black and n white balls. Do the following Markov process: 1. Draw ball, memorize color, throw it back. 2. Draw another ball (might be the same!), color it with memorized color, throw it back. 3. Rinse and repeat until only one color remains, when the process stops. 4. Count number of steps. What is the expectation value?  

Somewhat contrary to intuition, there is no runaway effect: The probability for a step in each direction is always equal, $(2n-k)k/(2n)^2$ for k black balls. Only the hill is getting steeper and steeper for the poor drunkard when you are near the end - the probability to stay put skyrockets.  

I did the math (or Wiki did it for me - <https://en.wikipedia.org/wiki/Absorbing_Markov_chain>). I get values $2, 28/3, 111/5 (n=1,2,3)$ (a few more n suggest an $O(n^4)$ growth) but can't guess a closed form (even the denominator is a double factorial from hell). Surely this problem (and some obvious generalizations) is already known? In which case a link suffices.



Drunkards Uphill Walk
Let $f(i)$ be the expected stopping time with $i$ white balls and $n-i$
black balls. Then $f$ satisfies the difference equation
$$f(i-1)-2f(i)+f(i+1)=-\frac{n^2}{i(n-i)}$$
The general solution to this equation is
$$\begin{split} f(i) & = \sum\_{j=1}^{i-1} -(i-j) \frac{n^2}{j(n-j)} + Ai+B \\
& = \sum\_{j=1}^{i-1} n \left(\frac{n-i}{n-j}-\frac{i}{j} \right) + Ai + B \\
& = n\left( (n-i)(H\_{n-1}-H\_{n-i}) - i H\_{i-1} \right) + Ai+B
\end{split}$$
where $H\_i$ is the harmonic sum $\sum\_{j=1}^i \frac{1}{j}$ and $A$
and $B$ are constants. (The last line doesn't make sense for $i=0$, but it works for all other $i$.)
The solution with $f(0)=f(n)=0$ is $A=n^2 H\_{n-1}$, $B=0$. So
$$ f(i)= n\left( n H\_{n-1}-(n-i) H\_{n-i} - i H\_{i-1} \right).$$
In the middle case $n=2k, i=k$, this is about $4k^2 \ln 2$.


