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.
There are some further refinements which may give probability strictly between 0 and 1, such as a paper by Gut and Spataru.
