<p>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.</p>

CC BY-SA 3.0
2011-09-02T19:09:57.537Z
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.
Josephine Moeller
CC BY-SA 3.0
2011-09-02T19:44:19.983Z
And bounded! It should be even _easier_ to return to the origin than in the plane.
Derrick Stolee
CC BY-SA 3.0
2011-09-02T22:47:22.533Z
Oops, you're right. I'll edit it to another shape.
xpda
CC BY-SA 3.0
2011-09-02T18:41:24.543Z
2011-09-02T22:54:49.737Z
2011-09-02T22:54:49.737Z
xpda
<p><a href="http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html">Probability on Trees and Networks</a> by Peres and Lyons mentions this in Chapter 2 (page 50):</p>

<blockquote>
  <p>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</p>
  
  <p>$$ W_f := \{ (x, y, z) : |z| \leq f(|x|) \} $$</p>
  
  <p>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, </p>
  
  <p>$$\sum_{n \geq 1}\frac{1}{n(f(n)+1)} = \infty$$</p>
  
  <p>is sufficient for recurrence.</p>
</blockquote>

CC BY-SA 3.0
2011-09-04T15:53:02.397Z
this is an excellent reference, and has a general technique for determining when such walks diverge. Nice !
Suresh Venkat
CC BY-SA 3.0
2011-09-04T15:28:57.413Z
2011-09-04T17:17:32.633Z
2011-09-04T17:17:32.633Z
Marcin Kotowski
<p><a href="http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomwalks.html" rel="nofollow noreferrer">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</a>. </p>

<p>My question is:</p>

<blockquote>
  <p>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 ?</p>
</blockquote>

<p>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. </p>

<p>Are there other shapes that interpolate between the two-D and the three-D case ? </p>

<p><strong>Update</strong> (pulled in from comments): <a href="https://mathoverflow.net/questions/45098/when-do-3d-random-walks-return-to-their-origin">a related question was asked on MO</a> - 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. </p>

CC BY-SA 3.0
2011-09-02T16:43:10.240Z
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$.
v s
CC BY-SA 3.0
2011-09-02T16:44:44.170Z
A search for random percolation walks gave me:
http://www.maths.bath.ac.uk/~ak257/englander-kersting/Ben.pdf
v s
CC BY-SA 3.0
2011-09-02T16:57:10.843Z
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?
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-02T16:59:08.327Z
That's definitely one way of defining the problem. Another, more informal way, would be to define nontrivial lattices that are more than 2D in some form for which certain return does happen.
Suresh Venkat
CC BY-SA 3.0
2011-09-02T17:46:39.060Z
Note: a related question was asked on MO: http://mathoverflow.net/questions/45098/when-do-3d-random-walks-return-to-their-origin - 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.
Suresh Venkat
CC BY-SA 3.0
2011-09-02T18:22:23.187Z
Can you edit the question to expand your comment about the comparison with the question on MathOverflow?  I thought about the same thing, and it deserves more attention than just a comment.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-02T19:08:36.463Z
It's funny what comes up over dinner...
Josephine Moeller
CC BY-SA 3.0
2011-09-02T19:23:09.250Z
[Random Walks on Fractal Curves](http://arxiv.org/abs/1103.5249).
Aaron Sterling
CC BY-SA 3.0
2011-09-03T07:28:28.570Z
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.
James King
<pr.probability><random-walks><markov-chains>
Drunken birds vs drunken ants: random walks between two and three dimensions
Suresh Venkat
# Drunken birds vs drunken ants: random walks between two and three dimensions

(Asked by: username_0 on 2011-09-02)

[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](http://www.math.cornell.edu/~mec/Winter2009/Thompson/randomwalks.html).

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](https://mathoverflow.net/questions/45098/when-do-3d-random-walks-return-to-their-origin) - 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.

**Tags:** pr.probability, random-walks, markov-chains
> **Comments:**
> **username_1**: 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$.  
> **username_1**: A search for random percolation walks gave me: http://www.maths.bath.ac.uk/~ak257/englander-kersting/Ben.pdf  
> **username_2**: 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?  
> **username_0**: That's definitely one way of defining the problem. Another, more informal way, would be to define nontrivial lattices that are more than 2D in some form for which certain return does happen.  
> **username_0**: Note: a related question was asked on MO: http://mathoverflow.net/questions/45098/when-do-3d-random-walks-return-to-their-origin - 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.  
> **username_3**: Can you edit the question to expand your comment about the comparison with the question on MathOverflow?  I thought about the same thing, and it deserves more attention than just a comment.  
> **username_4**: It's funny what comes up over dinner...  
> **username_5**: [Random Walks on Fractal Curves](http://arxiv.org/abs/1103.5249).  
> **username_6**: 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.  

---

## 2 answers

### Answer by username_9 on 2011-09-04. Score: 17 | Accepted answer

[Probability on Trees and Networks](http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html) 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.

> **Comments:**
> **username_0**: this is an excellent reference, and has a general technique for determining when such walks diverge. Nice !  

---

### Answer by username_7 on 2011-09-02. Score: 1

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.

> **Comments:**
> **username_4**: 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.  
> **username_8**: And bounded! It should be even _easier_ to return to the origin than in the plane.  
> **username_7**: Oops, you're right. I'll edit it to another shape.  

---

