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

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

share|improve this question
2  
The correct terminology would be "random walk on a 2D lattice"; for the "2D random walk" see for example carma.newcastle.edu.au/jon/walks.pdf. –  Wadim Zudilin Jul 9 '10 at 12:22
    
In one dimension, I don't think that the probability is $\frac{1}{2|x|}$ . For example, for $x=3$ the probability is $\frac{3}{16}$. –  Choli Sep 28 '10 at 22:24
add comment

5 Answers

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

share|improve this answer
    
I suspect this answer is related to the paper which originally answered this question, "Random paths in two and three dimensions" by McCrea and Whipple: ams.org/mathscinet-getitem?mr=2733 –  David White Apr 17 '12 at 16:43
add comment

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

share|improve this answer
1  
The pairing in that book confirms my suspicion that the question is isomorphic to that of this paper: arxiv.org/PS_cache/cond-mat/pdf/9909/9909120v4.pdf , although for the life of me I can't write the isomorphism down.... –  Tom Boardman Jul 9 '10 at 15:17
add comment

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?

share|improve this answer
    
I agree with i) and I need to think more about ii). –  Andrey Rekalo Jul 9 '10 at 15:18
add comment

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

share|improve this answer
add comment

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!

share|improve this answer
1  
I don't understand: isn't your guess too much asymmetrical? –  Pietro Majer Jul 9 '10 at 12:59
1  
The guess is wrong. If you are at (1,0) then the probability of hitting (20,20) before (0,0) is certainly less than 1/4, since you go to (0,0) in one step with probability 1/4. –  Gerald Edgar Jul 9 '10 at 13:13
1  
That is an exceedingly bad guess. For example, the walk (0,0)→(1,0)→(0,0) has probability 1/16; hence the asked for probability is certainly less than 15/16. More abstractly, by countable additivity your guess implies that a random walk will almost surely visit every point in the plane before returning to the origin, which is absurd. –  Harald Hanche-Olsen Jul 9 '10 at 13:17
1  
I stand corrected! Thanks for enlightening me with such clear examples. Mea culpa! –  Joseph O'Rourke Jul 9 '10 at 13:22
1  
Glad to see you admit your error (though I had not expected otherwise). Downvote retracted. –  Harald Hanche-Olsen Jul 9 '10 at 23:38
add comment

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.