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

Given $f(x)$, a strictly positive monotonically decreasing sequence, converging to 0. How to check whether a one dimensional random walk with stepsize $f(n)$ in random direction at the $n$-th step, will travel arbitrarily far from the origin with probability 1? Clearly $\sum_n f(n)$ needs to diverge, what other conditions are necessary? What are sufficient conditions?
Given an $f(x)$, say $1/\ln(x)$, how to check if it holds?

share|cite|improve this question
(1) I never heard of a 1-dimensional desert. (2) Can you be more specific as to "random" direction? What if the distribution is i.i.d binomial but biased 99.999...% right versus left? – alancalvitti Aug 10 '12 at 2:12
Good question, then what happends. but start with uniform – hjg Aug 10 '12 at 2:14
up vote 3 down vote accepted

The variance needs to diverge, so $\sum_nf^2(n)$ must diverge as well; thus $f(n)=1/n$ won't work – see Byron Schmuland's Random Harmonic Series on that.

share|cite|improve this answer
@hjg: You asked in a now-deleted comment whether this is sufficient. I would think so, since the central limit theorem would seem to indicate that the distribution should become Gaussian in form, and for a Gaussian distribution the variance going to infinity implies probability $1$ of getting arbitrarily far from the origin, but I haven't tried to show this formally. – joriki Aug 10 '12 at 12:27
I think one can change the time of the process so as to get a process which behaves much like a simple random walk, which would prove that the process goes arbitrarily far from the origin (and much more). – D. Thomine Aug 10 '12 at 12:46
@D.Thomine: How would that work? And does it confirm the idea that the divergence of $\sum_nf^2(n)$ is necessary and sufficient? – joriki Aug 10 '12 at 12:48

I'll detail my comment under Joriki's answer. This is just an idea, my skills are a bit rusted so I won't take the time to check all the details.

Let $(S_n)$ be the random walk with steps of size $f(k)$. Let me put:

$$V(n) = \sum_{k \leq n} f(k)^2.$$

Then, $S_n$ is approximately a gaussian of variance $V(n)$. Moreover, for $m \leq n$ we get that $S_n - S_m$ is approximately a gaussian of variance $V(n) - V(m)$. If I define the generalized inverse of $V$ by:

$$N(T) = \inf \{t > 0: V(t) \geq T \},$$

and $S_T' = S_{N(T)}$, then $S_T$ is almost a random walk with i.i.d. increments (actually, it is not, but the steps are independent and have almost a variance of $1$ and much more, so the long-time behavior of $(S_T)$ should be the same as for a classical random walk, modulo small tweaks).

If $V(n)$ has a finite limit, then $S_T'$ is not defined for large $T$, which is coherent with the fact that (S_n) converges almost surely. However, if $V(n)$ has an infinite limit, then the function $N(T)$ is also defined for all time and increases to $+ \infty$. You should be able to get everything you want:

  • that the random walk $(S_n)$ almost surely takes arbitrarily large positive and negative values;
  • asymptotics for hitting times;
  • versions of the law of iterated logarithm...

In particular, the condition $\lim_{n \to +\infty} V(n) = +\infty$ would be necessarily and sufficient for the first bullet to happen.

This method is related to the fact that "every continuous martingale is a brownian motion with a change of time". I remind you that this is just an idea, to take with a grain of salt.

share|cite|improve this answer

Your Answer


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

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