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?
Drunk person walking in 1D desert
-
0Good question, then what happends. but start with uni$f$orm – 2012-08-10
2 Answers
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.
-
0@D.Thomine: How would that work? And does it confirm the idea that the divergence of $\sum_nf^2(n)$ is necessary and sufficient? – 2012-08-10
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.