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



Random walk over a function
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$.


