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 http://goo.gl/UXfGgD.

  • 2
    $\begingroup$ 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. $\endgroup$
    – fedja
    Aug 15, 2013 at 14:15
  • $\begingroup$ 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). $\endgroup$
    – fedja
    Aug 15, 2013 at 14:22
  • $\begingroup$ Thanks for your comments. I've added some assumption which might be to strong but should do the job. $\endgroup$ Aug 15, 2013 at 18:32
  • $\begingroup$ Your problem seems very similar to Theorem 1 on page 218 of Petrov's "Sums of Independent Random Variables" (1975). $\endgroup$ Aug 17, 2013 at 14:57
  • $\begingroup$ 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. $\endgroup$ Aug 27, 2013 at 16:23

1 Answer 1


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$.

  • $\begingroup$ 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. $\endgroup$ Aug 16, 2013 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.