random walk returning probability - MathOverflow

random walk returning probability

2012-10-10T09:50:57Z

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.

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.

Thanks.

Answer by James Martin for random walk returning probability

2012-10-10T16:22:30Z

Since the number of visits has geometric distribution, it's enough to find its expected value.

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

So then the probability of being back at the origin at time $N$ is the sum over $m$ of

$P(X=m) P(\text{north-south walk at 0 after $m$ steps})P(\text{east-west walk at 0 after $N-m$ steps})$

where $X$ is Binomial$(N, p_1+p_2)$.

Sum over $N$ to get the total expected number of visits.

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.

Answer by Johan Wästlund for random walk returning probability

2012-10-11T12:03:31Z

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.

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

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

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

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

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.