Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Can you tell us where this question arose? It looks like homework... –  HJRW Oct 10 '12 at 9:55
3  
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.