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.
$\begingroup$
$\endgroup$
6
asked Mar 22, 2017 at 10:02
-
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$– Liviu NicolaescuCommented 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 WCommented 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$– dgulottaCommented 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 WCommented 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$– Joseph O'RourkeCommented Mar 22, 2017 at 18:12
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
3
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$.
-
$\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$ Commented Mar 23, 2017 at 12:19
-
1$\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$– dgulottaCommented 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$ Commented Mar 24, 2017 at 13:01