7
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 9, 2010 at 12:22
  • $\begingroup$ 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}$. $\endgroup$
    – Choli
    Sep 28, 2010 at 22:24

5 Answers 5

14
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$ Apr 17, 2012 at 16:43
2
$\begingroup$

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

$\endgroup$
1
1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I agree with i) and I need to think more about ii). $\endgroup$ Jul 9, 2010 at 15:18
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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!

$\endgroup$
5
  • 1
    $\begingroup$ I don't understand: isn't your guess too much asymmetrical? $\endgroup$ Jul 9, 2010 at 12:59
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 9, 2010 at 13:13
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 9, 2010 at 13:17
  • 1
    $\begingroup$ I stand corrected! Thanks for enlightening me with such clear examples. Mea culpa! $\endgroup$ Jul 9, 2010 at 13:22
  • 1
    $\begingroup$ Glad to see you admit your error (though I had not expected otherwise). Downvote retracted. $\endgroup$ Jul 9, 2010 at 23:38

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.