# Drunk person walking in 1D desert

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?

-
(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

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.

-
@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.

-