2
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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$
    – Mateusz Kwaśnicki
    Commented 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$
    – Mateusz Kwaśnicki
    Commented 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
    Commented 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$
    – Mateusz Kwaśnicki
    Commented 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
    Commented Sep 16, 2021 at 20:47

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented 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$
    – Iosif Pinelis
    Commented Sep 17, 2021 at 4:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .