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

-
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

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