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$?



Bound that random walk stays within with constant probability?
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.*](http://www.stat.berkeley.edu/~peres/bmbook.pdf)


