Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A random walk in the plane with step size $f(n)$ is cool if there is some constant $C$ such that it returns within a distance $C$ of the origin infinitely many times with probability $1$.

At the $n$-th step it moves $f(n)$ in one of the directions $x,y,-x,-y$ with equal probability.

$f(n)=1$ is cool. Is there a cool $f(n)$ such that $\lim\limits_{n\rightarrow\infty} f(n)=\infty$?

If $f(n)$ eventually dominates $n!$, then $f(n)$ is uncool; is there a sharpest upper bound on the growth rate for $f(n)$ to be cool?

share|cite|improve this question
Are you dealing with 1-dimensional random walks [you say "returns to the interval (-C,+C)"] or 2-dimensional random walks [you say "one of the directions x,y,-x,-y"]? – Henry Feb 23 '12 at 21:15
Here's a rough heuristic that might hold. If $f(n)$ grows slowly, and there isn't any weird modular behavior (e.g. all even steps after a certain time), then at time $n$ the variance of each coordinate is about $\frac{1}{2} \sum_{i=1}^n f(i)^2$. Making a bunch of unsubstantiated independence/smoothness assumptions, you might then expect to hit near $0$ with probability proportional to $\frac{1}{\sum_{i=1}^n f(i)^2}$ (if each coordinate spreads out over a range of size $m$, both numbers might be small with probability about $1/m^2$). (continued next comment) – Kevin Costello Feb 24 '12 at 4:51
If you take $f(n)$ growing sufficiently slowly, then the expected number of returns near $0$ is infinite, and (again making a bunch of unsubtantiated independence assumptions), you could hope that $f(n)$ is cool. – Kevin Costello Feb 24 '12 at 4:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.