MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(S_n)_{n=0}^{\infty}$ be a random walk with $S_n = \sum_{i=1}^n X_i$, and let the $X_i$ be distributed according to some (bounded) distribution function $F$ with mean $0$ and variance $1$, so that $S_n$ has mean $0$ and variance $\sigma_n^2 = n$. Let $g(n)$ be a (slowly) increasing function of $n$, and let $h(n) = g(n) \sigma_n = g(n) \sqrt{n}$. I am interested in

$$\mathcal{P}_h(n) := P(\exists \ n_0 \leq n: S_{n_0} > h(n_0)),$$

or equivalently,

$$\mathcal{P}_h(n) := P(\exists \ n_0 \leq n: \frac{S_{n_0}}{\sigma_{n_0}} > g(n_0)),$$

and in particular, proving that $\mathcal{P}_h(n)$ is small for certain fixed $F$ and $g$ and large $n$. In other words, we start a random walk, and instead of asking for the probability that at some point it ends up in, say, the rightmost $5\%$ region of all values at that time (which would correspond to $g(n)$ being constant), the region gets smaller over time. So as $n$ increases, the a priori probability $P(S_n > h(n))$ decreases.

At this point I am interested in any ideas for solving this problem. If you have any ideas on how to prove that $\mathcal{P}_h(n)$ is small, I would really like to hear your thoughts. Also if the case of a standard random walk is easier, a solution to that problem may give insight to this problem as well.

Right now I have a proof for $P_h(n) < \epsilon$ based on using a piecewise constant function $\ell$ as a lower bound for $h$, i.e. $\ell(n) \leq h(n)$ for all $n$, and showing that $\mathcal{P}_{\ell}(n) < \epsilon$. But this does not seem like a sharp bound in general, and I am curious if there are better proof methods for this problem.

share|cite|improve this question

Check out the Law of iterated Logarithm. Is this enough for your purpose?

share|cite|improve this answer
Thanks, that looks very interesting. But I'm also interested in an "efficient" way to turn the $\mathcal{P}_h(n)$ above into something nicer. Of course we could use the upper bound $P(\exists \ n_0 \leq n: S_{n_0} > h(n_0)) \leq \sum_{i=1}^n P(S_i > h(i))$ but that does not seem very sharp. – TMM Apr 30 '12 at 20:42
I suggest taking a look at how the LIL is derived, then trying to apply similar methods for your problem. In general, you want to measure the correlation between the events $S_i > h(i)$, and it is often useful to bunch all of these events for $i=2^j,..,2^{j+1}$ together. the correlation between different $j$'s here will then decay exponentially. – Ori Gurel-Gurevich Apr 30 '12 at 21:30

I think you need to look for Large Deviation Theory for help; in particular you could check out Dembo and Zetouni's book. I think a version of equation (1.2.14) might be a good place to start.

share|cite|improve this answer

Your Answer


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

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