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

The probability of a random walk returning to its origin is 1 in two dimensions (2D) but only 34% in three dimensions: This is Pólya's theorem. I have learned that in 2D the condition of returning to the origin holds even for step-size distributions with finite variance, and as Byron Schmuland kindly explained in this Math.SE posting, even for distributions with infinite variance, recurrence depends upon the details of the step-length tail distribution. But this is all in 2D.

My question is:

Are there conditions on the step-size and step-direction distributions in three dimensions (3D) that ensure that the walk will return to the origin with probability 1?

Of course I exclude here a step-direction distribution that squashes 3D → 2D. But perhaps partial dimensional compression suffices?
Logo3D
(3D random-walk image credit to http://logo.twentygototen.org/.)

share|improve this question
4  
As Alekk remarked, dimensions 3 and up are transient. The easiest intuitive argument I know is that the expected distance of a 1-dimensional walk is \sqrt{T}. In the 2D case, by time T a random walk usually fills some > A (for some A) fraction of an 2\sqrt{T} by 2\sqrt{T} square, and therefor returns. The same argument shows that the fraction of the bigger dimensional cube you cover is rapidly going to 0, so you can't return. –  David Lehavi Nov 6 '10 at 22:06
    
@David: Thanks! That makes sense: $\sigma \sqrt{T}$ in 2D. –  Joseph O'Rourke Nov 6 '10 at 22:25

5 Answers 5

up vote 11 down vote accepted

For a fairly robust intuitive argument, think of a random walk in $\mathbb{R}^d$ as the "product" of $d$ one-dimensional walks in $\mathbb{R}^1$. For a (finite variance) random walk in $\mathbb{R}^1$, the probability the random walk is within $O(1)$ of the origin after $n$ steps scales like $n^{-1/2}$. If the $d$-dimensional random walk were to literally just be the independent product of $d$ one-dimensional walks, this would mean that in $\mathbb{R}^d$ the probability the random walk is near the origin after $n$ steps would be about $n^{-d/2}$, and indeed, this answer is correct. Roughly speaking, then, the reason random walk changes behavior between $d=2$ and $d=3$ is that this is when $\sum_n n^{-d/2}$ switches from divergent to convergent.

This intuition suggests that if your walk is "truly" at least $(2+\epsilon)$-dimensional for some $\epsilon > 0$, then it should be transient (if you're willing to accept this intuition of $n^{-d/2}$ behavior for fractional $d$). Terry Lyons has derived a necessary and sufficient condition for the transience of a reversible Markov chain which I think formalizes and extends this intuition. He in particular uses it to prove a necessary and sufficient condition for the transience of simple random walk on "wedges" in $\mathbb{Z}^d$. Specializing his result even further, he mentions that, letting $\Omega$ be the subgraph of $\mathbb{Z}^3$ with $$ \Omega=\{(x,y,z) \in \mathbb{Z}^3, y \leq x, x \leq (\log(z+1))^{\alpha}\} $$ then the simple random walk on $\Omega$ is transient whenever $\alpha > 1$. (The same would be true for any finite variance random walk constrained to lie in $\Omega$, though I'm not sure Terry Lyons' theorem will prove this in full generality.) The graph $\Omega$ is just a very slight "fattening" of part of $\mathbb{Z}^2$, and the walk is already transient. In a sense, random walks in $\mathbb{Z}^2$ only "just" fail to be transient, and if you go above $\mathbb{Z}^2$ in any way you will immediately be transient.

share|improve this answer
    
Thank you Louigi! I was wondering about fattening the plane slightly into 3D, so your beautifully clear explanation is much appreciated! –  Joseph O'Rourke Nov 7 '10 at 17:31

It is always transient in dimensions 3 and higher - see Theorem T1 in Section 8 of Spitzer's classical book "Principles of random walk" (2nd ed.).

share|improve this answer
    
@RW: I have just purchased this book online; thanks for the reference! But surely(?) there remain conditions on the 3D step distributions that lead to recurrence? Or are you saying that any 3D step distribution is transient? –  Joseph O'Rourke Nov 6 '10 at 22:51
    
Yes - that's what I meant - ANY 3D step distribution is transient. –  R W Nov 6 '10 at 23:37
1  
@Joseph: If you have access to Google books, look for Kallenberg's Foundations of Modern Probability (2nd edition) and look for Theorem 9.8. It is an amazing result! –  Byron Schmuland Nov 6 '10 at 23:38
    
@Joseph: P.S. On page 164 –  Byron Schmuland Nov 6 '10 at 23:40
    
@Byron: Thanks, amazing "stuff" indeed! What a rich topic! Wow. :-) –  Joseph O'Rourke Nov 7 '10 at 0:36

No, any true 3d random walk is transient. (true in the sense that this is not a 2d random walk in disguise)

share|improve this answer
5  
@Alekk: I do not doubt you, but could you please provide some support? Just having a Y/N answer does not extend my education beyond one bit. :-) –  Joseph O'Rourke Nov 6 '10 at 21:39

Are you talking about fixed biases?

If the bias is not a fixed value like the matrices in $n$-dimensions I described above, you could have the probabilities be a function of their location in the $\mathbb{Z}^n$ lattice or a function of the current positions distance from the origin. In that case, you end-up simulating physical scenarios, such as the motion of a charged particle in an electric field, or gravitational attraction. If you used an inverse-square (to the distance) law, simulating gravity, you'd end up with a lunar-crrash-lander or a satellite-orbiting type of simulation. Are you talking about fixed biases?

(original answer below, valid for a fixed unbiased, or for a fixed-value biased random walker, where the bias is not a function of the random walker's position)


Joseph, the envelope (furthest reachable limit) of an unbiased random walk on an $n$-dimensional lattice at time step $t$ is the region containing the origin and $|d_1| + |d_2| + ... + |d_n| \le t$. So for $n=1$, that region is the line segment $-t \le x \le +t$ equivalent to $|x| \le t$.

For $n=2$, the envelope region is the diamond-shaped area $|x| + |y| \le t$, or the region bounded by the four lines $x+y=1, x+y = -1, x-y=1, x-y=-1$ or equivalently, the four lines $y=x+1, y=x-1, y= (-x)+1, y= (-x)-1$.

For $n=3$, the envelope region is the octohedral shape on the $\mathbb{Z}^3$-lattice contained within $|x|+|y|+|z| \le t$.

The probability density region of the unbiased random walk in $n$-dimensions approaches the $n$-dimensional gaussian.

So for $n=1$, the region of the envelope grows linearly as $t$, and for $n=2$, the region of the envelope grows proportionately to $t^2$, etc., growing proportionately to $t^n$ for $n$ dimensions. Once $n \gt 2$, the rate of the growth of the envelope rapidly overtakes the rate of the average distance traveled, and it becomes very unlikely that the unbiased random walker will return to the origin. That's how I've understood it to be. A reference off the top of my head would be Margulis and Toffoli's Cellular Automata Machine book from 1984 or 1985, as it gives a good description of cellular automata models of diffusion in $1$ and $2$-dimensions, and I believe in $3$-dimensions also, thought I am not certain. I believe that's where I remember reading about the "envelope"; and I remember running my own programmed simulations to draw the envelope and probability distributions for 1-d and 2-d.


In 1-dimensions, the probability distribution at time step $t$ are the convolutions of $[0.5, 0.0, 0.5]$ with itself, and the envelope is the region of this resultant convolution where the probabilities are non-zero. It's also equivalent to the Binomial expansion, or every other row of pascal's triangle divided by the sum of the elements of that row:

                    1

                 1  2  1              divided by four

              1  4  6  4  1           divided by 16

           1  6 15 20 15  6  1        divided by 64

And the $2$-dimensional version is the $2-d$ convolution of the 2-d matrix $M_2$

0    1    0

1    0    1

0    1    0

with itself $t$ numbers of times (center the matrix at the origin as an image matrix, divide it by 4, and do a 2-dimensional convolution with $M_2$ for each time step to see the probability distribution evolving).

Similarly, in $3$-d, the $M_3$ matrix is the three-dimensional matrix {$M_a \div 6; M_b \div 6; M_c \div$ 6} consisting of the three $2$-d matrices $M_a, M_b, M_c$ which I'll type out

$M_a$=

0   0   0

0   1   0

0   0   0

$M_c=M_a$

$M_b=$

0   1   0

1   0   1

0   1   0

And the 3-d probability distribution at time step $t$ is the $t$-th convolution of $M_3 \div 6$ with itself.

If you try a few steps of the $3-d$ convolution, you'll see that the probability density at the center quickly goes to zero. Once the number of dimensions is greater than $2$, the unbiased random walker is more likely to move further away in other dimensions where it's closer to the origin, rather than get closer to the origin in the dimensions where it's already further away.

share|improve this answer
    
??? Maybe you are not finished with your comment... –  Joseph O'Rourke Nov 6 '10 at 22:47
1  
Joseph, oops, I hit the "submit" button rather than the "preview LaTeX" button. I've fixed it now. –  sleepless in beantown Nov 6 '10 at 22:56
    
And I believe that as long as the conditions/biasing on the 3-d or any $ \gt 2$-d walk are not trivial (effectively reducing the random walk to a 1-d or 2-d walk), then the random walk will be transient and the likelihood for return approaches $0$ as $t$ increases. –  sleepless in beantown Nov 6 '10 at 23:00
    
@sleepless: I appreciate the detailed analysis!! "The unbiased random walker" is exactly whom I am avoiding. Your assessment corroborates with others nonqualitatively: 2D returns; ~3D does not. But I feel there must be a more nuanced intermediate characterization... –  Joseph O'Rourke Nov 6 '10 at 23:36
1  
Joseph! Bees are amazingly non-random: they communicate with dance! They use their vision and polarized light sensing to visualize the sky as a compass (direction relative to position of the sun)! They have memory and the ability to remember directions to the nectar source, so they likely have the memory or capability of calculating the reverse trip home! Now ants walking around without pheremone tracks are random; the pheremone tracks that ants lay make their motions much less random. There's a Science/Nature paper that talks about tracking honeybees with radar+RFID. :) Bflight\neqRwalk –  sleepless in beantown Nov 7 '10 at 0:17

Read Barber, M. N. and Ninham, B. W. Random and Restricted Walks: Theory and Applications. New York: Gordon and Breach, 1970.

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.