# random walk returning probability

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.

-
Can you tell us where this question arose? It looks like homework... – HJRW Oct 10 '12 at 9:55
The problem is from computer science, and we want to compute certain probability of infinite-state Markov chains. The goal is to decide whether the probability is >= some threshold. To this end, we want to find some characterisation of the probability. For 1-D case, this can be done by polynomial equations, but I do not know how to do for the 2-D case. Hence is the question. – maomao Oct 10 '12 at 10:08
Do you need an exact answer or just an approximation? I looked for an exact answer but wasn't able to find one. After enough steps, the random walk distribution will be approximately a Gaussian, so you could get an approximation by calculating the probability of return exactly for, say, 100 steps, then estimating the probability of large-time returns with the central limit theorem. (And unless p_1 and p_3 are very close and p_2 and p_4 are very close, this last term is very small.) – Robert Young Oct 11 '12 at 14:41
You can write the probability as an integral via Fourier analysis. One could just numerically approximate this integral. – Will Sawin Oct 12 '12 at 2:02

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.

-

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.

-