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.

asymptoticto that function of $n$? – Gerry Myerson Jul 31 '11 at 9:21