Take the 2-minute tour ×

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|improve this question

2 Answers 2

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

share|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|improve this answer

Your Answer


