random walk returning probability - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T14:27:36Z http://mathoverflow.net/feeds/question/109285 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109285/random-walk-returning-probability random walk returning probability maomao 2012-10-10T09:50:57Z 2012-10-11T12:03:31Z <p>Consider a two-dimensional random walk, but this time the probabilities are not 1/4, but some values p_1, p_2, p_3, p_4 with $\sum_{i=1}^4 p_i=1$. For example, from (0,0), it goes to (1,0) with p_1, goes to (0,1) with p_2 etc.</p> <p>The question is how to compute the probability x of going back to (0,0), starting from (0,0). In general, this probability is not 1. </p> <p>Thanks.</p> http://mathoverflow.net/questions/109285/random-walk-returning-probability/109308#109308 Answer by James Martin for random walk returning probability James Martin 2012-10-10T16:22:30Z 2012-10-10T21:39:49Z <p>Since the number of visits has geometric distribution, it's enough to find its expected value. </p> <p>Here is one approach: since you can solve the one-dimensional case, treat the two-dimensional case as two "interleaved" one-dimensional walks, one north-south, the other east-west. Let's say $p_1$ is the probability of north, $p_2$ is the probability of south. Then at each step, we do a step from the north-south walk with probability $p_1+p_2$ and a step from the east-west walk with probability $p_3+p_4$; each step of the north-south walk is north with probability $p_1/(p_1+p_2)$ and south with probability $p_2/(p_1+p_2)$.</p> <p>So then the probability of being back at the origin at time $N$ is the sum over $m$ of </p> <p>$P(X=m) P(\text{north-south walk at 0 after$m$steps})P(\text{east-west walk at 0 after$N-m$steps})$</p> <p>where $X$ is Binomial$(N, p_1+p_2)$. </p> <p>Sum over $N$ to get the total expected number of visits. </p> <p>I don't see that this will give you a closed-form answer, but it may at least make it easier to compute and/or obtain bounds. </p> http://mathoverflow.net/questions/109285/random-walk-returning-probability/109374#109374 Answer by Johan Wästlund for random walk returning probability Johan Wästlund 2012-10-11T12:03:31Z 2012-10-11T12:03:31Z <p>A special case where we can avoid one of the two sums in James Martin's answer is when the "determinant" $p_1p_3-p_2p_4$ of the four probabilities is zero. Then we can treat the random walk as a "sum" of two independent one-dimensional random walks, one taking steps $(+1/2, +1/2)$ or $(-1/2,-1/2)$, the other taking steps $(+1/2,-1/2)$ or $(-1/2,+1/2)$. The original walk is back at the origin precisely when both these 1D-walks are.</p> <p>If the transition probabilities of the two component walks are $p, (1-p)$ and $q, (1-q)$ respectively, then the expected number of visits to the origin (including the start) is $$\sum_{n=0}^\infty \binom{2n}{n}^2 p^nq^n(1-p)^n(1-q)^n.$$</p> <p>In terms of the original probabilities, $$pq(1-p)(1-q) = (p_1+p_2)(p_2+p_3)(p_3+p_4)(p_4+p_1).$$</p> <p>I'm no expert on this type of sum, but according to Maple, $$\sum_{n=0}^\infty \binom{2n}{n}^2 x^n = \frac2{\pi} EllipticK(4\sqrt{x}).$$</p> <p>The probability of never returning is the reciprocal of this (with $x=pq(1-p)(1-q)$), in other words $$\frac{\pi}{2EllipticK(4\sqrt{(p_1+p_2)(p_2+p_3)(p_3+p_4)(p_4+p_1)})}.$$</p> <p>An obvious question is whether this holds also when $p_1p_3 \neq p_2p_4$. Off the top of my head I don't see why it couldn't.</p>