2
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – TMM
    Apr 30, 2012 at 20:42
  • $\begingroup$ 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. $\endgroup$ Apr 30, 2012 at 21:30
2
$\begingroup$

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.

$\endgroup$

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.