3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ The Markov chain dynamics is independent of the past. The dynamics you describe depends on the immediate past. I could be wrong, but it would help if you detail the question by including 1. the state space of this Markov chain and 2.the transition probabilities. $\endgroup$ Mar 22, 2017 at 10:33
  • $\begingroup$ The OP has actually described the chain on the integer interval $[0,2n]$ whose transitions are combined steps (1) and (2). Then one should just write (and easily solve) the usual equation for the expected absorption (hitting) times. $\endgroup$
    – R W
    Mar 22, 2017 at 13:20
  • 1
    $\begingroup$ It is possible to write down a generating function for the expected stopping time. If $a_{ij}$ is the expected stopping time with $i$ white and $j$ black balls, then the generating function $f(x,y)=\sum_{ij} a_{ij} x^i y^j$ satisfies $-xy \frac{\partial}{\partial x} \frac{\partial}{\partial y} \left( \frac{(x-y)^2}{xy} f\right) = \left( x \frac{\partial}{\partial x}+y \frac{\partial}{\partial y} \right)^2 \frac{x}{1-x} \frac{y}{1-y}$ which has the solution $f = xy \frac{(xy-1)(\log(1-x) - \log(1-y))}{(x-y)(1-x)^2(1-y)^2}+\frac{xy}{(1-x)^2(1-y)^2}$. $\endgroup$
    – dgulotta
    Mar 22, 2017 at 13:59
  • $\begingroup$ @Joseph O'Rourke Come on - by symmetry the stopping time is the same as just for the associated chain on $[0,n]$. So, for $n=2$ we are talking about the chain on $\{0,1,2\}$ with the transition probabilities $p(2,2)=p(2,1)=1/2$ and $p(1,2)=p(1,0)=3/16,\; p(1,1)=10/16$. $\endgroup$
    – R W
    Mar 22, 2017 at 15:01
  • $\begingroup$ @RW: Sorry, I misunderstood the process. Deleted my comment. For $n=2$, the stopping time is about $9.3$. For $n=3$, about $22.2$. $\endgroup$ Mar 22, 2017 at 18:12

1 Answer 1

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ THX. Could you quickly elaborate (I'm too much of an amateur) how you got to the difference equation? The rest looks like standard math even for me :-) $\endgroup$ Mar 23, 2017 at 12:19
  • $\begingroup$ The expected times should satisfy $f(i)=\frac{i(n-i)}{n^2} f(i-1)+\frac{i^2+(n-i)^2}{n^2} f(i) + \frac{(n-i)i}{n^2} f(i+1) + 1$, and rearranging gives the difference equation. $\endgroup$
    – dgulotta
    Mar 23, 2017 at 17:37
  • $\begingroup$ Asked the question, immediately after went to the university library, saw a new book on Markov chains and found essentially the same explanation. :-) (Anyway, THX again, as your version immediately suggests how to generalize it to arbitrary probabilities and even m-dimensional walks. $\endgroup$ Mar 24, 2017 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.