most recent 30 from http://mathoverflow.net 2013-05-26T00:22:48Z http://mathoverflow.net/feeds/question/95586 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95586/probability-of-a-random-walk-crossing-an-increasing-function-of-the-standard-devi TMM 2012-04-30T16:06:49Z 2012-04-30T19:45:08Z

<p>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</p> <p>$$\mathcal{P}_h(n) := P(\exists \ n_0 \leq n: S_{n_0} > h(n_0)),$$</p> <p>or equivalently,</p> <p>$$\mathcal{P}_h(n) := P(\exists \ n_0 \leq n: \frac{S_{n_0}}{\sigma_{n_0}} > g(n_0)),$$</p> <p>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.</p> <p>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.</p> <p>Right now I have a proof for $P_h(n) &lt; \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) &lt; \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.</p>

http://mathoverflow.net/questions/95586/probability-of-a-random-walk-crossing-an-increasing-function-of-the-standard-devi/95602#95602 tipanverella 2012-04-30T18:55:08Z 2012-04-30T18:55:08Z

<p>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.</p>

http://mathoverflow.net/questions/95586/probability-of-a-random-walk-crossing-an-increasing-function-of-the-standard-devi/95608#95608 Ori Gurel-Gurevich 2012-04-30T19:45:08Z 2012-04-30T19:45:08Z

<p>Check out the <a href="http://en.wikipedia.org/wiki/Law_of_the_iterated_logarithm" rel="nofollow">Law of iterated Logarithm</a>. Is this enough for your purpose?</p>