Two-dimensional random walk

Question

Suppose we have a particle in the plane at the origin $(0,0)$. It moves randomly on the integer lattice $Z^2$ to any of the adjacent vertexs with equal probability $1/4$. What's the probability of reaching a fixed point $(x,y)$ before returning to the origin?

The analogous problem in one dimension is easy. The probability is:

$ \dfrac{1}{2|x|} $

I have read some related articles working on finite graphs; but I am not be able to obtain the answer for my problem.

Thank you very much for your attention

Answer 1

Let $a$ and $b$ be fixed points in the integer lattice, and let $f(p)$ be the probability that a random walk starting at the point $p$ will arrive at $a$ before $b$. Then for every point in the plane other than $a$ and $b$, we have, $$ f(p) = \frac{f(p+i)+f(p-i)+f(p+j)+f(p-j)}{4} $$ where $i$ and $j$ are the basis unit vectors. That is, the value of $f$ at a point is equal to the average of the values of $f$ at the neighboring points.

A function on the square lattice with this property is called harmonic, and satisfies a discrete version of Laplace's equation: $$ \Delta f = 0 $$ where $\Delta$ is the discrete Laplace operator. Unfortunately, the function $f$ is not quite harmonic, since the equation above need not hold when $p=a$ or $p=b$.

In particular, the function $f$ actually satisfies the Poisson equation $$ \Delta f(p) = C_1 \delta_a(p) + C_2 \delta_b(p), $$ where $\delta_a$ is the function which is $1$ at $a$ and zero elsewhere, $\delta_b$ is the same for $b$, and $C_1$ and $C_2$ are unknown constants.

Since Poisonn's equation is linear, it suffices to solve the equations $$ \Delta f(p) = \delta_a(p)\qquad\text{and}\qquad\Delta f(p) = \delta_b(p) $$ independently, and then take an appropriate linear combination of the solutions. Solutions to equations such as these are called lattice Green's functions. For the integer lattice, the lattice Green's functions cannot be written in a closed form, but there are definite integral formulas that can be used to compute the function to arbitrary precision (see here).

Once you know the values of the lattice Green's functions, you ought to be able to solve for the constants $C_1$ and $C_2$ by using the boundary conditions $f(a) = 1$ and $f(b) = 0$.

Answer 2

See the delightful little book Random Walks and Electric Networks by Doyle and Snell.

Answer 3

Hello

Thanks for the answer. But I am a bit confused with this formula:

$\displaystyle{\sum\limits_{n=1}^\infty p_{2n}\prod\limits_{m=1}^{n}(1-r_{2m}),}$

It seems that for each $2n$ you obtain the probability of reach the point exactly in $2n$ steps and not reach the origin in $2m$ steps with $m< n$.

So, two questions:

i) If this works, it would be?:

$\displaystyle{\sum\limits_{n=1}^\infty p_{2n}\prod\limits_{m=1}^{n-1}(1-r_{2m}),}$

ii) On the other hand, it seems to take the product of $p_{2n}\prod\limits_{m=1}^{n}(1-r_{2m})$ the events of being in $(x_1,x_2)$ in $2n$ steps and not being in $(0,0)$ at $2m<2n$ step must be independent; but, are they independent?

Answer 4

http://puhep1.princeton.edu/~mcdonald/examples/EM/atkinson_ajp_67_486_99.pdf

I haven't checked its validity, but it has Mathematica code for calculating what you want. As a side notice, the asymptotics of this probability is C/log r, (where r is the distance to (x,y)).

Answer 5

This is not an answer, just an observation. The probability of returning to the origin eventually is 1 (approaches 1 as the number of steps approaches infinity). This is Pólya's famous 1921 result. The same is true for reaching any fixed point $(x,y)$: the probability of reaching it is 1. My guess is that the probability of reaching $(x,y)$ before hitting the origin (or any other fixed point) is likely still 1. But this is only a guess. As pointed out in the comments, this was a terrible guess!