MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 $\{X_n\}_{n\geq 0}$ be a random walk. Let us assume that $\mathbb{E}X_1 =0$ and $\mathbb{E}X_1^2=1$. Let also $\mathbb{E}\exp(c|X_1|)<+\infty$ for some $c>0$ and $X_1$ has a law with unbounded support. I conjecture that for any $A>0$

$\mathbb{P}(\forall_{i\in \{1,2,\ldots,n\} } X_i \geq A \sqrt{i} ) \sim n^{-C},$

where $C>0$ is some constant depending on $A$.

I can prove this claim for some special classes of RWs (e.g. with Gaussian steps). Does anyone knows general results of this kind?

Further, faster functions, e.g.

$\mathbb{P}(\forall_{i\in \{1,2,\ldots,n\} } X_i \geq \sqrt{i} \log \log i ) \sim ?,$

Solution: Using the suggestions of Ofer Zeitouni (see below) I was able to make a proof of the above statement. The sketch is contained in

share|cite|improve this question
You should be a little bit careful about how you state it and what normalization you use. We can always have $P_n \ge\frac {1}{2en}$ no matter what the function is (just take the symmetric steps with $P(Y=\pm x_n)=\frac{1}{2n(n+1)}$ with $x_n$ going up very fast). So, in general I would expect just power upper and lower bounds, not an asymptotic. However, you may not need such weird step distributions, so tell us some precise setup you'll be happy with and someone will take it from there. – fedja Aug 15 '13 at 14:15
Another interesting regime to consider is $X_i\ge A\sqrt{\sum_{j\le i}Y_j^2}$, which makes more sense because it is scale invariant and asymptotically coincides with yours if $EY^2=1$ and, say, all moments exist (to control the speed of convergence in the Law of Large Numbers). – fedja Aug 15 '13 at 14:22
Thanks for your comments. I've added some assumption which might be to strong but should do the job. – Piotr Miłoś Aug 15 '13 at 18:32
Your problem seems very similar to Theorem 1 on page 218 of Petrov's "Sums of Independent Random Variables" (1975). – Brendan McKay Aug 17 '13 at 14:57
Thanks. But I do not see how this is relevant. It gives information about one dimensional marginals of the random walk. In my question I ask about properties of the paths. – Piotr Miłoś Aug 27 '13 at 16:23
up vote 1 down vote accepted

Here is a suggestion, I have not checked all details:

You could mimic the Gaussian computation by doing an exponential change of measure that makes the mean of the $i$th summand to be $1/\sqrt{i}$. The change of measure then will read roughly as $$\Lambda_n=e^{\sum_{i=1}^n (c/\sqrt{i}) X_i-c'\sum_{i=1}^n (1/i)},$$ where $X_i$ are now zero mean variables that are independent, but not exactly of the same law, and the $c,c'$ can be computed (I think they are 1 and 1/2 in the situation you described, but I did not check carefully). Letting $S_t=\sum_{i=1}^t X_i$, you need to compute $$E(1_{S_t>0, t=1,...,n} \Lambda_n)\,.$$ The second term in $\Lambda_n$ will contribute $n^{-c'}$, and the first term is negligible, while $\Gamma:=E(1_{S_t>0, t=1,...n})\sim 1/\sqrt{n}$. This would yield your claim with $C=c'+1/2$.

There are plenty of details to check (including that the first term in $\Lambda_n$ is negligible, which should be easy by integration by parts, and that $\Gamma$ behaves as if the summands were i.i.d, not merely well behaved independent).

The same idea works for the second function you ask about, you will then get $n^{-C (\log \log n)^2}$. The computation begins to break down in the large deviations regime, i.e. when replace $\sqrt{i}$ by $i$.

share|cite|improve this answer
Thanks for the suggestions. They are useful indeed. I was not able to prove the assertions using only the change of measure you suggested. The problem is that the lower-bound and upper-bound do not match. However, one can make "two step" proof. In the first step use change of measure to get some "gap" and in the second step use the KMT coupling to compare with Gaussian case (which can be proven easier). I am putting a file with the draft of the solution in the main question above. – Piotr Miłoś Aug 16 '13 at 16:07

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.