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.

  • $\begingroup$ 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$. $\endgroup$ Sep 16, 2021 at 19:52
  • $\begingroup$ On a second thought, there is no non-trivial universal upper bound, too: just consider the trivial random walk with $X_i = -\mu$. $\endgroup$ Sep 16, 2021 at 19:55
  • $\begingroup$ @MateuszKwaśnicki thank you for the remark, I added the assumption that $\text{Var}(X_i) >\delta$. $\endgroup$
    – Xiao
    Sep 16, 2021 at 20:01
  • $\begingroup$ 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. $\endgroup$ Sep 16, 2021 at 20:32
  • $\begingroup$ @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. $\endgroup$
    – Xiao
    Sep 16, 2021 at 20:47

1 Answer 1


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

  • $\begingroup$ 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 : ) $\endgroup$
    – Xiao
    Sep 17, 2021 at 3:58
  • 1
    $\begingroup$ @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$. $\endgroup$ Sep 17, 2021 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.