## Probability of a Random Walk crossing an increasing function of the standard deviation

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 2 Answers

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

-

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 2012 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 2012 at 21:30

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 32, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9518276453018188, "perplexity_flag": "head"}