30
$\begingroup$

It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly less than 1 of returning to the origin.

My question is:

Is there something in between ? For example, suppose my space was actually a bounded region of the plane extruded out to infinity in the z-direction. (what's often called 2.5 dimensional). Do the two-dimensional results apply, or the three dimensional ?

This came up in discussions, and one heuristic argument saying that it behaves two dimensionally is that since the finite region of the plane will be covered eventually, the only nontrivial part of the walk is the 1 dimensional ray along the z direction, and so return to the origin will happen.

Are there other shapes that interpolate between the two-D and the three-D case ?

Update (pulled in from comments): a related question was asked on MO - a short summary is that if the walk is even (2+ϵ) dimensional, then uncertain return follows loosely from a diverging series. However, the above question is slightly different IMO since I'm asking about other kinds of shapes that might admit certain return.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Do not know much about the topic but percolation came up my thought! How about random walk on percolations? Seems likely to be a candidate for fractional dimensional results for any $n > 1$. $\endgroup$
    – v s
    Sep 2, 2011 at 16:43
  • 1
    $\begingroup$ in what sense do you mean in-between? There does not seem to be much in-between 1 and strictly below 1; so do you want the in-between to be with respect to the dimension of the space? In other words, does any answer have to be a walk on something with a natural measure of dimension? $\endgroup$
    – Artem Kaznatcheev ♦
    Sep 2, 2011 at 16:57
  • 6
    $\begingroup$ Note: a related question was asked on MO: mathoverflow.net/questions/45098/… - a short summary is that if the walk is even $(2+\epsilon)$ dimensional, then uncertain return follows loosely from a diverging series. However, the above question is slightly different since I'm asking about other kinds of shapes that might admit certain return. $\endgroup$
    – Suresh Venkat
    Sep 2, 2011 at 17:46
  • 2
    $\begingroup$ Random Walks on Fractal Curves. $\endgroup$
    – Aaron Sterling
    Sep 2, 2011 at 19:23
  • 3
    $\begingroup$ For a bounded region of the plane extruded out to infinity along the $z$-axis, we're essentially dealing with a thickened line rather than a fattened plane; as such, I would expect the behaviour to be closer to the one-dimensional case than the two-dimensional case. $\endgroup$
    – James King
    Sep 3, 2011 at 7:28

2 Answers 2

Reset to default
17
$\begingroup$

Probability on Trees and Networks by Peres and Lyons mentions this in Chapter 2 (page 50):

One way to make sense of this is to ask about the type of spaces intermediate between $\mathbb{Z}^2$ and $\mathbb{Z}^3$. For example, consider the wedge

$$ W_f := \{ (x, y, z) : |z| \leq f(|x|) \} $$

where $f : \mathbb{N} \rightarrow \mathbb{N}$ is an increasing function. The number of edges that leave $W_f \cap \{(x, y, z) : |x| \text{ or } |y| \leq n\}$ is of the order $n(f(n)+1)$, so that according to the Nash-Williams Criterion,

$$\sum_{n \geq 1}\frac{1}{n(f(n)+1)} = \infty$$

is sufficient for recurrence.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ this is an excellent reference, and has a general technique for determining when such walks diverge. Nice ! $\endgroup$
    – Suresh Venkat
    Sep 4, 2011 at 15:53
1
$\begingroup$

A 3-D random walk in a 3x3x3 space (like a rubik's cube) has a probability of less than one of returning to the origin, if the walk starts at the outside; but that of a 2x2x2 space is one, as is 3x3x3 space with the origin at the center. So it seems that there are some intermediate shapes, but maybe not very many.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ But a toroid is 2-dimensional. I don't find it surprising that it would return to its starting point. Seems like a special case of 2D. $\endgroup$
    – Josephine Moeller
    Sep 2, 2011 at 19:09
  • 1
    $\begingroup$ And bounded! It should be even easier to return to the origin than in the plane. $\endgroup$
    – Derrick Stolee
    Sep 2, 2011 at 19:44
  • $\begingroup$ Oops, you're right. I'll edit it to another shape. $\endgroup$
    – xpda
    Sep 2, 2011 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.