# Random walk always stays below a level $a$

Suppose we have a random walk $$S_n$$ with i.i.d. steps $$X_i$$. We assume that $$\mathbb{E}[X_i] = -\mu, \text{Var}[X_i] = 1,$$ where $$\mu$$ is close (or going) to zero. We also assume that the moment generating function and its derivatives $$M_{X_i}, M_{X_i}', M_{X_i}'', M_{X_i}'''$$ are all bounded in $$(-\epsilon, \epsilon)$$ by a constant $$C$$, where $$\epsilon, C$$ are independent of $$\mu$$ (which is going to zero).

Fix a constant $$a\geq 1$$, are there any estimates in the literature for the probability of the random walk always stays below $$a$$, i.e. $$\mathbb{P}\big\{{\max_{n\geq 0} S_n \leq a}\big\}?$$ (I believe the upper bound should be $$Ca\mu$$.)

For the special case where we replace $$a$$ by $$0$$, then $$\mathbb{P}\big\{{\max_{n\geq 0} S_n \leq 0}\big\} \leq C\mu$$ which essentially follows from Sparre-Andersen theorem together with Berry-Esseen bound.

• For the record: the only universal lower bound is clearly zero, as shown by the random walk with $X_i = a + 1$ with probability $1-\varepsilon$ and $X_i = -((1-\varepsilon)(a+1) + \mu)/\varepsilon$ with probability $\varepsilon$. Sep 16, 2021 at 19:52
• On a second thought, there is no non-trivial universal upper bound, too: just consider the trivial random walk with $X_i = -\mu$. Sep 16, 2021 at 19:55
• @MateuszKwaśnicki thank you for the remark, I added the assumption that $\text{Var}(X_i) >\delta$.
– Xiao
Sep 16, 2021 at 20:01
• This can save the lower bound, but the upper bound still seems impossible: if $X_i = -1/\mu$ with probability $\mu^2$ and $X_i = 0$ otherwise, then $X_i$ has mean $-\mu$ and variance $1-\mu^2 \approx 1$, and still $S_n = 0$ almost surely. Sep 16, 2021 at 20:32
• @MateuszKwaśnicki Thanks again! In my case, the $X_i$ is an explicit (continuous) distribution supported on $(-\infty, \infty)$, but I will think about a condition so that this can be stated with generality.
– Xiao
Sep 16, 2021 at 20:47

Let $$p(a):=P\big(\max_{n\ge0} S_n\le a\big).$$ Assume that $$c_3:=E|X_1-EX_1|^3<\infty$$.

By the improvement by Sakhanenko of Lemma 8 by S. Nagaev (the improvement consisting in removing an extra factor $$c_3$$) and trivial time-rescaling, $$p(a)-p(0)\le C\mu(a+c_3)$$ for $$\mu\ge0$$ and $$a\ge0$$; everywhere here, $$C$$ denotes various universal positive real constants. Also, you know that $$p(0)\le C\mu$$. So, for all $$a\ge c_3$$ $$p(a)\le C\mu a.\tag{1}$$

Concerning a lower bound on $$p(a)$$, Corollary 1 to Theorem 16 of $$\S$$23 of the book by Borovkov implies $$p(a)\ge1-e^{-Qa} \tag{2}$$ for $$a\ge0$$, where $$Q:=\sup\{t\colon M(t)\le1\}$$, $$M(t):=Ee^{tX}$$, and $$X:=X_1$$.

If e.g. $$|X|\le b$$ almost surely for some real $$b>0$$, then for all $$t\in[0,Q]$$ we have $$M''(t)=EX^2e^{tX}\le b^2 M(t)\le b^2$$, by the convexity of $$M$$. So, $$1=M(Q)\le M(0)+M'(0)Q+b^2Q^2/2=1-\mu Q+b^2Q^2/2$$, whence $$Q\ge c\mu$$, where $$c:=\frac2{b^2}$$. If now $$Qa$$ is large, then (2) implies $$p(a)\approx1$$, so that the lower bound in (2) is as good as it can be. If, finally, $$Qa$$ is not large, then the lower bound in (2) is $$\asymp Qa\ge c\mu a$$, which matches (1).

• Thank you so much for the answer! I am interested in when $\mu\to 0$. So the constants can not implicitly depend on the step distribution $F$; they can certainly depend on $c_3$ since I can control this quantity while sending $\mu$ to zero. With a quick look over the paper, it seems that it doesn't use things like KMT coupling where the constants implicitly depend on $F$ that we have no control over. I will look more carefully at the papers, in case you can already spot a place where the constants might implicitly depend on $F$, I would really appreciate if you could point it out : )
– Xiao
Sep 17, 2021 at 3:58
• @Xiao : As is stated in the answer, the constants $C$ are universal, and the dependence on the distribution of $X_1$ is only as follows: to get (1), we need to require that $a\ge c_3$ -- or, more generally, that $a\ge c_3/C$ for some universal positive real constant $C$. Sep 17, 2021 at 4:03