Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
5  
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
2  
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

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.