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