7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Can you tell us where this question arose? It looks like homework... $\endgroup$
    – HJRW
    Oct 10, 2012 at 9:55
  • 3
    $\begingroup$ 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. $\endgroup$
    – maomao
    Oct 10, 2012 at 10:08
  • $\begingroup$ 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.) $\endgroup$ Oct 11, 2012 at 14:41
  • $\begingroup$ You can write the probability as an integral via Fourier analysis. One could just numerically approximate this integral. $\endgroup$
    – Will Sawin
    Oct 12, 2012 at 2:02

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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