# Bound that random walk stays within with constant probability?

For one-dimensional random walk, it is well-known that if the walk goes for $n$ steps, with constant probability it ends within $\pm\sqrt{n}$.

What is the bound, in terms of $n$, such that if the walk goes for $n$ steps, with constant probability it always stays within that bound? It is probably no longer on the order of $\sqrt{n}$, but is it still less than the order of $n$?

My interpretation of the problem is that you want a function $f(n)$ so that a walk of $n$ steps stays within $f(n)$ of the origin with probability $c+o(1)$ for some $0\lt c \lt 1$. If so, the right form of $f$is still $c'\sqrt{n}$ since the rescaled limit as $n\to \infty$ is Brownian motion, and for any $a$, Brownian motion has a positive probability of staying inside an interval $[-a,a]$ up to time $1$, and a positive probability of leaving. The exact value can be expressed as an infinite sum, or in terms of theta functions. See Theorem 7.43 in Brownian Motion.
For a probability 1 statement, it's $\pm\sqrt{n\log\log n}$ (times a constant), see Law of the Iterated Logarithm.
• I think Bjorn's answer is wrong here. I think that $\mathbb P(\max_{0\le i\le n}|X_i|\le C\sqrt n)$ is bounded below in $n$. Commented Nov 24, 2015 at 23:28
• I agree that this answer seems to be to a different question than was asked. By the way, the LIL gives a probability $1$ statement about the limit superior, not the supremum, so I'm not sure what it says about a fixed $n$. Commented Nov 24, 2015 at 23:34