# Lower bound for small deviation probability of driftless random walk

Let $S_0=0$ and $S_n = \sum_{k=1}^n Z_k$ with i.i.d real valued random variables $(Z_n)$ with $E[Z_1]=0$ and $P[Z_1 \geq 1]>0$. Let furthermore $0<\alpha<1/2$. I'm interested in lower bounds for the probabilities

$$p_n:= P[\forall i=1,\ldots,n: S_i \geq i^\alpha]$$

for $n \rightarrow \infty$. One might try

$$p_n \geq \prod\limits_{i=1}^n P[S_i \geq i^\alpha|S_{i-1} \geq (i-1)^\alpha]$$

and then use, if $Z_n > C$ a.s. for a constant $C > - \infty$, and suitable moment conditions hold, something like $$P [ Si \geq i^\alpha | S_{i-1} \geq (i-1)^\alpha] \geq 1 - \frac{C}{\sqrt{i}}$$

via the Berry-Esseen theorem. However, I don't think that is optimal. I'd like to have such an inequality with $1/n$ instead of $1/\sqrt{n}$. Any suggestions?

• There is no nontrivial lower bound for $p_n$. E.g. $p_n =0$ for all $n$ when $Z_1 < 1$ a.e. – js21 Sep 28 '17 at 15:57
• I am also unable to understand where your first inequality for $p_n/p_{n-1}$ comes from. – js21 Sep 28 '17 at 16:32

You can find the asymptotics for this probability. For that let $$\tau:=\inf\{i\ge 1: S_i\le i^\alpha\}.$$ Then, if $Var(S_1)<\infty$ then the asymptotics for $$p_n=\mathbf P(\tau>n)\sim \frac{C}{\sqrt n},\quad n\to \infty,$$ see https://arxiv.org/abs/1403.5918 for random walks with i.i.d. increments, and https://arxiv.org/abs/1611.00493 for random walks whose increments are independent but not necessarily identical. In the latter case the answer is $$\mathbf P(\tau >n) \sim \frac{C}{\sqrt{Var(S_n)} },\quad n\to \infty.$$
• Hello Denis; unfortunately I wasn't able to prove the asymptotics for the i.i.d. increments. I tried to use Theorem 1 of your paper. I have a problem at writing $\tau$ in the form of $T_g$ with $g$ increasing. I have also doubts when I draw the problem graphically with the curves $g(t)=t^{\alpha}$ and $h(t)=-g(t)$. Can you give a hint or some further explanations on how to prove the asymptotics $\sim c/\sqrt{n}$? – student19 Dec 16 '17 at 18:35
• In the first paper you could you the results related to the shrinking domain, see page 5. The corresponding stopping time is denoted as $\widehat T_g$ . The result that can be applied is Theorem 7. It is not an optimal result. The second paper uses a slightly different notation, and the stopping time is denoted as $T_g$. You can use Theorem 2 together with Theorem 7 in the second paper. – Denis Denisov Dec 17 '17 at 10:18
• Thank you very much for your explanations. I'm already happy with the asymptotics for the case of i.i.d. increments and applying Theorem 7 of the first paper seems sufficient to me. I guess, there is a not so important irreducibility assumption related to this theorem, to prevent something like $P[S_1 \leq 1]=1$, which I maybe overlooked. If you can write this condition down, it would help me. – student19 Dec 18 '17 at 20:49
• Yes, you are right, there should be an irreducibility condition. We forgot to assume it in the first paper, but it is given in the second paper, see equation (6), which required $P(T_g>n)>0$ for all $n$. This condition holds in your question, as you assume that $P(Z_1\ge 1)>0$. – Denis Denisov Dec 19 '17 at 21:34