# How far will a random walk on the integers go?

Let $S_n$ be the distance walked at time $n$ in a simple symmetric random walk on $\mathbb{Z}$ (with steps $=\pm1$).

It is well known that $\lim_{n\to\infty}(E(|S_n|)/\sqrt{n})=\sqrt{2 /\pi}$.

Can we describe the set $F$ of monotonic "growth" functions with probability 1 of being crossed by $|S_n|$ for $n>1$?

Clearly $f(x)=\sqrt{x}$ is in $F$ and I think I could prove that $g(x)=2f(x/2)$ is in $F$ whenever $f$ is. I have no idea beyond that.

-
Have you heard about the Law of iterated logarithm? en.wikipedia.org/wiki/Law_of_the_iterated_logarithm I think that this may help you. – Leonid Petrov Jul 31 '11 at 8:36
How is $f(x) = \sqrt{x}$ clearly if $F\hspace{.03 in}$? Among other things, $f$ can only be hit by $|S_n|$ at perfect squares. – Ricky Demer Jul 31 '11 at 9:18
Does it makes sense for a limit on $n$ to be a function of $n$? Perhaps you mean the expected value is asymptotic to that function of $n$? – Gerry Myerson Jul 31 '11 at 9:21
Gerry Myerson: yes, I edited accordingly. @Ricky Demer: I replaced "hit" with "crossed" - I hope that clarifies that I'm not looking for equality of two functions, but for $f$'s such that $\limsup |S_n|/f(n) \ge 1$ with probability 1 – Yaakov Baruch Jul 31 '11 at 11:23
@Leonid: I think your comment is the answer to the question (or at least the INTENDED question). – Yaakov Baruch Jul 31 '11 at 11:37