27
$\begingroup$

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 (source)

(3D random-walk image credit to http://logo.twentygototen.org/.)

$\endgroup$
2
  • 6
    $\begingroup$ 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. $\endgroup$ Commented Nov 6, 2010 at 22:06
  • $\begingroup$ @David: Thanks! That makes sense: $\sigma \sqrt{T}$ in 2D. $\endgroup$ Commented Nov 6, 2010 at 22:25

7 Answers 7

34
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you Louigi! I was wondering about fattening the plane slightly into 3D, so your beautifully clear explanation is much appreciated! $\endgroup$ Commented Nov 7, 2010 at 17:31
7
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ @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? $\endgroup$ Commented Nov 6, 2010 at 22:51
  • 1
    $\begingroup$ Yes - that's what I meant - ANY 3D step distribution is transient. $\endgroup$
    – R W
    Commented Nov 6, 2010 at 23:37
  • 3
    $\begingroup$ @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! $\endgroup$
    – user6096
    Commented Nov 6, 2010 at 23:38
  • 1
    $\begingroup$ @Joseph: P.S. On page 164 $\endgroup$
    – user6096
    Commented Nov 6, 2010 at 23:40
  • 1
    $\begingroup$ This is not so surprising (at least the finite variance case) if one remembers that the large scale behavior is will be essentially the same as that of a simple random walk (if the expectation is zero) and like a biased random walk (if the expectation is not zero). Basically, all you can do is just apply a linear transformation. The infinite variance case should be even easier, but I don't see an easy explanation immediately. $\endgroup$ Commented Nov 7, 2010 at 7:31
4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$ Commented Nov 6, 2010 at 23:00
  • $\begingroup$ @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... $\endgroup$ Commented Nov 6, 2010 at 23:36
  • $\begingroup$ 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? $\endgroup$ Commented Nov 6, 2010 at 23:46
  • $\begingroup$ @sleepless: This is a useless nonspecific response, but aside from my personal geometry research, I am wondering how bees and other random 3D-walkers return home...? E.g, following Lévy flight: en.wikipedia.org/wiki/L%C3%A9vy_flight . $\endgroup$ Commented Nov 7, 2010 at 0:01
  • 2
    $\begingroup$ 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 $\endgroup$ Commented Nov 7, 2010 at 0:17
2
$\begingroup$

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

$\endgroup$
1
  • 10
    $\begingroup$ @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. :-) $\endgroup$ Commented Nov 6, 2010 at 21:39
2
$\begingroup$

The answer to your question appears to be contained in a 1928 Theorem of Polya, on simple random works on a lattice $\mathbb Z^d$. As a soft-reference, see page 15 of this short paper, using only very basic mathematics (Stirling's formula, etc.). The crux of the solution is to show that in $3$ dimensions, the average number of returns to the origin is finite, and so a.e you eventually get lost for good!

$\endgroup$
1
$\begingroup$

The original question was whether there are conditions on the step-direction distribution, such that the walk is recurrent in d=3 or higher.

Yes, there are such conditions, although rigorous arguments hold only for Cayley trees (V. Sood & P. Grassberger, PRL 99, 098701 (2007)).

Take any large graph (N nodes, N>>1), and pick randomly a "target" node T. Then start a biased random walk from some node i close to T, where the bias is such that a step is taken with higher probability, if it decreases the (graph) distance to the node, and lower probability if it increases it. For Cayley trees and for sparse random graphs with bounded degrees (such as large Erdos-Renyi graphs) there exist a critical bias strength b_c, such that the target T is reached in a time \propto the distance d(i,T) for b>b_c, but only at a time O(N) for b<b_c.

Heuristic arguments suggest that the same is true also for regular lattices of any dimension >2.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .