3
$\begingroup$

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

$\endgroup$
0

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ Commented Nov 24, 2015 at 23:28
  • $\begingroup$ 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$. $\endgroup$ Commented Nov 24, 2015 at 23:34
  • $\begingroup$ Yes I'm not really sure what the OP intended, maybe pi66 will clarify. $\endgroup$ Commented Nov 24, 2015 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.