Timeline for Drunkards Uphill Walk
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 18:38 | comment | added | aorq | It seems to me that this is a special case of mathoverflow.net/questions/41939/a-balls-and-colours-problem/… except that with probability $1/n^2$ you don't do anything. | |
| Mar 23, 2017 at 12:05 | vote | accept | Hauke Reddmann | ||
| Mar 22, 2017 at 18:12 | comment | added | Joseph O'Rourke | @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$. | |
| Mar 22, 2017 at 18:06 | answer | added | dgulotta | timeline score: 4 | |
| Mar 22, 2017 at 15:01 | comment | added | R W | @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$. | |
| Mar 22, 2017 at 13:59 | comment | added | dgulotta | 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}$. | |
| Mar 22, 2017 at 13:20 | comment | added | R W | 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. | |
| Mar 22, 2017 at 10:33 | comment | added | Liviu Nicolaescu | 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. | |
| Mar 22, 2017 at 10:02 | history | asked | Hauke Reddmann | CC BY-SA 3.0 |