17
$\begingroup$

In Michael Lugo's blog post Variations on the drunken-bird theorem, and real-world sightings he wonders (without coming to a conclusion) what the maximum 'safe' number of dimensions to get drunk in might be.

So where's the line between "always finds his way home" and "gets lost forever"? It seems to me that this should be at 2+ε dimensions, since that's what we need to make the sum convergent, but I don't know if anyone's studied random walks on fractal spaces.

In the comments Matt Noonan recalls an unverified claim that the line is at 2.5 dimensions.

Can anybody shed any further light on these musings?

Improve this question
$\endgroup$
1
  • $\begingroup$ I recall my undergraduate markov chain lecturer also stating without proof or reference that the answer was 2.5 dimensions. $\endgroup$
    – Kevin Buzzard
    Commented Nov 4, 2009 at 9:59

4 Answers 4

Reset to default
5
$\begingroup$

Indeed, the answer is 2+ϵ in most senses. For example, consider a wedge in Z3 which is all the points (x,y,z) such that |z|<f(x) for some specific increasing function f:N->N .

These wedges are transient already for pretty slowly growing functions. If you take f(x)=xϵ which correspond, in the sense of volume growth, to 2+ϵ dimensions, then it is transient for any ϵ>0.

One can get even more refined results by taking f(x)=log(x)a, in which case the wedge is transient if and only if a>1.

You can find more information in the book of Lyons with Peres.

Improve this answer
$\endgroup$
2
$\begingroup$

In that post, my intuition was simply that the probability of a random walk in d dimensions being at the origin at time t scales like t-d/2, and ∑t > 0 t-d/2 converges if and only if d > 2. Obviously this can only be turned into a proof if d is an integer.

Improve this answer
$\endgroup$
1
$\begingroup$

There are some "fractal" meanings to a question like this.

See the delightful little Carus Monograph Random Walks and Electric Networks by Doyle and Snell. At the end of Chapter 6 they discuss a certain tree that has dimension log 6/log 2 = 2.5849... It is used to show that the 3-dimensional lattice is transient.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is far from my field, but I know that Tom Lindstrøm has been doing some work with this kind of question. See his “Brownian motion on nested fractals” AMS memoir #83 (1990) (ams.org/mathscinet-getitem?mr=988082). $\endgroup$
    – Harald Hanche-Olsen
    Commented Nov 4, 2009 at 15:04
  • $\begingroup$ Doyle and Snell is such a beautiful book. If every field had such a natural, elegant introduction, we'd all understand a lot more math. $\endgroup$
    – Tom Church
    Commented Nov 4, 2009 at 16:08
0
$\begingroup$

Have a look at

http://mathworld.wolfram.com/PolyasRandomWalkConstants.html

The answer turns out that at as soon as dim > 2 the probability of recurrence is lower than 100%.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ I suspect that in that article, p is constrained to be an integer (though it doesn't say so explicitly). $\endgroup$
    – Andrew Stacey
    Commented Nov 4, 2009 at 12:05
  • $\begingroup$ You mean in the mathworld article? p seems to denote the probability of recurrence, so it is a real number in the interval [0, 1]. Or do I misunderstand your post? $\endgroup$
    – Tim vB
    Commented Nov 4, 2009 at 12:08
  • 1
    $\begingroup$ I conjecture that Andrew meant to say "d is constrained to be an integer" $\endgroup$
    – Kevin Buzzard
    Commented Nov 4, 2009 at 12:10
  • $\begingroup$ Ouch, good point, my memory tricked me into believing that d is real - sorry, I probably have to withdraw my answer. $\endgroup$
    – Tim vB
    Commented Nov 4, 2009 at 12:36
  • 3
    $\begingroup$ Sorry, sometimes I read articles upside-down. $\endgroup$
    – Andrew Stacey
    Commented Nov 4, 2009 at 16:07

You must log in to answer this question.

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