Bound on the running maximum of a random walk with small drift

Ofer Busani Ofer Busani
University of Bristol
School of Mathematics
Fry Building
Woodland Rd.
Bristol BS8 1UG
UK. [email protected] https://people.maths.bris.ac.uk/ di18476/ and Timo Seppäläinen Timo Seppäläinen
University of Wisconsin-Madison
Mathematics Department
Van Vleck Hall
480 Lincoln Dr.
Madison WI 53706-1388
USA. [email protected] http://www.math.wisc.edu/ seppalai

Abstract.

We derive a lower bound for the probability that a random walk with i.i.d. increments and small negative drift $\mu$ exceeds the value $x>0$ by time $N$ . When the moment generating functions are bounded in an interval around the origin, this probability can be bounded below by $1-O(x|\mu|\log N)$ . The approach is elementary and does not use strong approximation theorems.

2000 Mathematics Subject Classification:

60K35, 60K37

O. Busani was supported by EPSRC’s EP/R021449/1 Standard Grant.

T. Seppäläinen was partially supported by National Science Foundation grant DMS-1854619 and by the Wisconsin Alumni Research Foundation.

1. Introduction

1.1. Background

This paper arose from the need of a random walk estimate for the authors’ article [2] on directed polymers. This estimate is a positive lower bound on the running maximum of a random walk with a small negative drift. Importantly, the bound had to come with sufficient control over its constants so that it would apply to an infinite sequence of random walks whose drift scales to zero as the maximum is taken over expanding time intervals. The natural approach via a Brownian motion embedding appeared to not give either the desired precision or the uniformity. Hence we resorted to a proof from scratch. For possible wider use we derive the result here under general hypotheses on the distribution of the step of the walk.

The polymer application of the result pertains to the exactly solvable log-gamma polymer on the plane. The objective of [2] is to prove that there are no bi-infinite polymer paths on the planar lattice $\mathbb{Z}^{2}$ . The technical result is that there does not exist any nontrivial Gibbs measures on bi-infinite paths that satisfy the Dobrushin-Lanford-Ruelle (DLR) equations under the Gibbsian specification defined by the quenched polymer measures. In terms of limits of finite polymer distributions, this means that as the southwest and northeast endpoints of a random polymer path are taken to opposite infinities, the middle portion of the path escapes. This is proved by showing that in the limit the probability that the path crosses the $y$ -axis along a given edge decays to zero. This probability in turn is controlled by considering stationary polymer processes from the two endpoints to an interval along the $y$ -axis. The crossing probability can be controlled in terms of a maximum of a random walk. In the case of the log-gamma polymer, the steps of this random walk are distributed as the difference of two independent log-gamma variables. The case needed for [2] is treated in Example 2.7 below.

1.2. The question considered

We seek a lower bound on the probability that the running maximum of a random walk with negative drift reaches a level $x>0$ . To set the stage, we discuss the matter through Brownian motion. Let $S^{N}_{n}=\sum_{i=1}^{n}X^{N}_{i}$ be a random walk with drift $\mathbb{E}(X^{N}_{1})=\mu_{N}=\mu N^{-1/2}<0$ , and such that the random walks $S^{N}$ converge weakly to a Brownian motion with drift $\mu<0$ . The probability of the event

\displaystyle\sup_{1\leq n\leq N}S^{N}_{n}>x

should be approximately the same as that of

(1.1)

\displaystyle\sup_{0\leq s\leq 1}(B_{s}+s\mu)>xN^{-1/2}.

This latter can be computed (see (3.7)) to be

(1.2)

\displaystyle\mathbb{P}\big{\{}\sup_{0\leq s\leq 1}(B_{s}+s\mu)>xN^{-1/2}\hskip 0.7pt\big{\}}=1-O(|\mu|xN^{-1/2}\hskip 0.7pt).

This suggests that we should aim for an estimate of the type

(1.3)

\displaystyle\mathbb{P}\Big{(}\sup_{1\leq n\leq N}S^{N}_{n}>x\Big{)}\geq 1-O(|\mu_{N}|x).

To reach this precision weak convergence is not powerful enough, for a weak approximation of random walk by Brownian motion reaches only a precision of $O(N^{-1/4})$ [12, 7]. Our estimate (2.4) below does almost capture (1.3): we have to allow an additional $\log N$ factor inside the $O(\cdot)$ and consider $x$ of order at least $(\log N)^{2}$ .

The by-now classical Komlós-Major-Tusnády (KMT) coupling [9] gives a strong approximation of random walk with Brownian motion with a discrepancy that grows logarithmically in time. This precision is sufficient for us, as we illustrate in Section 3. The problem is now the control of the constants in the approximation. Uniformity of the constants is necessary for our application in [2]. But verifying this uniformity from the original work [9] appeared to be a highly nontrivial task. In the end it was more efficient to derive the estimate (Theorem 2.2 below) from the ground up.

The difficulty of the original KMT proof has motivated several recent attempts at simplification and better understanding of the result, such as Bhattacharjee and Goldstein [1], Chatterjee [3], and Krishnapur [10]. There is another strong approximation result due to Sakhanenko [11] which, according to p. 232 of [3], “is so complex that some researchers are hesitant to use it”.

1.3. Sketch of the proof

Our proof is elementary. The most sophisticated result used is the Berry-Esseen theorem. Given a random walk of small drift $\mu<0$ , our approach can be summarized in two main steps:

(1)

Up to the time the random walk hits the level $-\varepsilon|\mu|^{-1}$ it behaves like an unbiased random walk.
(2)

By the time the random walk hits the level $-\varepsilon|\mu|^{-1}$ it will have had about $\log_{2}(\varepsilon|\mu|^{-1}x^{-1})$ independent opportunities to hit the level $x$ . By the previous step this implies that the probability on the left-hand side of (1.3) is of order $1-(1/2)^{\log_{2}(\varepsilon|\mu|^{-1}x^{-1})}=1-O(|\mu|\varepsilon^{-1}x)$ .

As we will take $\varepsilon=(\log N)^{-1}$ in the proof, we will obtain the right order in (1.3) up to a logarithmic factor (Theorem 2.2). After the statement of the theorem we illustrate it with examples. Then we demonstrate that even if we knew that the constants in the KMT approximation can be taken uniform, the result would not be essentially stronger in the regime in which we apply our result.

2. Main result

For each $N\in\mathbb{Z}_{>0}$ , let $\{X^{N}_{i}\}_{i\geq 1}$ be a sequence of non-degenerate i.i.d. random variables. Denote their moment generating function by

\displaystyle M_{N}(\theta)

\displaystyle=\mathbb{E}\big{(}e^{\theta X^{N}_{1}}\big{)}.

Write $M_{N}^{(0)}=M_{N}$ and $M_{N}^{(i+1)}=(d/d\theta)M_{N}^{(i)}$ .

Assumption 2.1.

We assume that the random variables $\{X^{N}_{i}\}_{i\geq 1}$ satisfy the following:

(i)

There exists an open interval $(-\theta_{0},\theta_{0})$ around the origin on which each moment generating function $M_{N}$ is finite. Furthermore, there exists a finite constant $C_{M}$ and $\theta_{1}>0$ such that we have the uniform bounds

(2.1)

\displaystyle|M_{N}^{(i)}(\theta)|

\displaystyle\leq C_{M}\quad\text{for all $N$, $0\leq i\leq 3$, and $\theta\in[-\theta_{1},\theta_{1}]$}

for the compact interval $[-\theta_{1},\theta_{1}]\subset(-\theta_{0},\theta_{0})$ .

(ii)

There exists a finite constant $\sigma_{*}>0$ such that

(2.2)

\displaystyle\mathbb{E}\big{[}(X^{N}_{1})^{2}\big{]}\geq\sigma_{N}^{2}={\rm\mathbb{V}ar}(X^{N}_{1})\geq{\sigma^{2}_{*}}\quad\text{for all $N$.}

(iii)

There exists a finite constant $D_{\mu}>0$ such that the expectations $\mu_{N}=\mathbb{E}\big{(}X^{N}_{1}\big{)}$ satisfy

(2.3) $\displaystyle-D_{\mu}(\log N)^{-3}\leq\mu_{N}\leq 0\quad\text{for all $N$.}$

The conditions in Assumption 2.1 are fairly natural. Note that (2.1) has to be checked only for $i=0$ at the expense of shrinking the interval $[-\theta_{1},\theta_{1}]$ and increasing $C_{M}$ . To make a positive maximum possible, condition (2.2) ensures enough diffusivity and condition (2.3) limits the strength of the negative drift. The bound (2.4) below shows that $D_{\mu}$ has to be vanishingly small in order for the result to be nontrivial.

For $m\geq 1$ let $S^{N}_{m}=\sum_{k=1}^{m}X^{N}_{k}$ be the random walk associated with the steps $\{X^{N}_{i}\}_{i\geq 1}$ . Here is the main theorem.

Theorem 2.2.

There exist finite constants $C$ and $N_{0}$ that depend on $\theta_{1},{\sigma^{2}_{*}},D_{\mu}$ and $C_{M}$ such that, for every $N\geq N_{0}$ and $x\geq(\log N)^{2}$ ,

(2.4)

\displaystyle\mathbb{P}\Big{(}\max_{1\leq m\leq N}S^{N}_{m}\leq x\Big{)}\leq C\hskip 0.7ptx(\log N)(\hskip 0.7pt|\mu_{N}|\vee N^{-1/2}\hskip 0.7pt).

Remark 2.3 (The constants in the theorem).

The constant $C$ in the upper bound (2.4) is given by

(2.5)

C=4\exp\bigl{\{}4(C_{0}+4c_{\tau}^{-1})(1+D_{\mu})+8\theta_{1}^{-1}\bigl{(}1+\log(e^{\theta_{1}}C_{M}+1)\bigr{)}+4C_{M}\bigr{\}}+3

where

(2.6)

C_{0}=2(\sigma_{*}^{-1}+9e^{\theta_{1}}\sigma_{*}^{-3}C_{M}^{\hskip 0.7pt5/2})+2e^{8C_{M}\sigma_{*}^{-4}+8\sigma_{*}^{-2}}c_{\tau}^{-1}+12\sigma_{*}^{-2}\,,

(2.7)

c_{\tau}=\log\frac{2}{1+\Phi_{{\sigma^{2}_{*}}}[-2,2]}\,,

and $\Phi_{{\sigma^{2}_{*}}}$ is the mean zero Gaussian distribution with variance ${\sigma^{2}_{*}}$ .

Throughout the proof we state explicitly the various conditions $N\geq N_{0}$ required along the way. Let us assume that $N\geq 2$ so that $\log N$ does not vanish. Then all the conditions $N\geq N_{0}$ can be combined into a single condition of the form

(2.8)

f(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1},N)\geq 1

where the function $f$ is a strictly positive continuous function on $\mathbb{R}_{>0}^{4}\times\mathbb{R}_{\geq 2}$ , nondecreasing in $\theta_{1}$ , nonincreasing in $C_{M}$ and $D_{\mu}$ , but depends on ${\sigma^{2}_{*}}$ in both directions. When $(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1})$ is restricted to a compact subset $\mathcal{K}$ of $\mathbb{R}_{>0}^{4}$ , there exists a finite index $N_{\mathcal{K}}$ such that $f(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1},N)$ is a nondecreasing function of $N\geq N_{\mathcal{K}}$ for any fixed $(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1})\in\mathcal{K}$ , and

\lim_{N\to\infty}\;\inf_{(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1})\hskip 0.55pt\in\hskip 0.55pt\mathcal{K}}f(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1},N)=\infty.

In particular, for each compact subset $\mathcal{K}\subset\mathbb{R}_{>0}^{4}$ there exists a finite index $N_{0,\mathcal{K}}$ such that (2.8) holds for all $N\geq N_{0,\mathcal{K}}$ and all $(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1})\in\mathcal{K}$ . Furthermore, it is evident from (2.5)-(2.7) that $C$ is a continuous function of $(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1})\in\mathbb{R}_{>0}^{4}$ . We conclude with the following local uniformity statement.

Corollary 2.4.

For each compact subset $\mathcal{K}\subset\mathbb{R}_{>0}^{4}$ there exist finite constants $C_{0,\mathcal{K}}$ and $N_{0,\mathcal{K}}$ such that the following holds: the estimate (2.4) with $C=C_{0,\mathcal{K}}$ on the right-hand side is valid whenever $N\geq N_{0,\mathcal{K}}$ , simultaneously for all walks $\{S^{N}_{m}\}_{m\geq 1}$ that satisfy Assumption 2.1 with parameters $(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1})\in\mathcal{K}$ .

We illustrate the result with some examples.

Example 2.5 (Gaussian random walk).

Let $B_{t}$ be a Brownian motion, $\mu<0$ , and define the random walk $S^{N}_{m}=B_{m}+mN^{-1/2}\mu$ . We can verify that the bound (2.4) is off by a logarithmic factor in this case, by comparison with the running maximum of the Brownian motion. For $x>0$ and large enough $N$

(2.9)		$\displaystyle\mathbb{P}\big{(}\max_{1\leq m\leq N}S^{N}_{m}\leq x\big{)}$	$\displaystyle\geq\mathbb{P}\big{(}\sup_{0\leq t\leq N}B_{t}+tN^{-1/2}\mu\leq x\big{)}$
(2.9)			$\displaystyle\geq 1-e^{-2xN^{-1/2}\|\mu\|}\geq x\|\mu_{N}\|=xN^{-1/2}\|\mu\|.$

where the middle inequality follows from (3.7) with $\mu(N)=\mu$ and $b(N)=xN^{-1/2}$ .(2.9) shows that the optimal error is at most $O(x|\mu_{N}|)$ , and that Theorem 2.2, if not optimal, is only $\log N$ away from being so.

A natural way to produce examples is to take $X^{N}_{i}$ as the difference of two independent random variables whose means come closer as $N$ grows and whose variances stay bounded and bounded away from zero.

Example 2.6 (Exponential walk).

Consider a random walk $S_{n}=\sum_{k=1}^{n}X_{k}$ with step distribution $X_{k}\overset{d}{=}Y_{\alpha}-Y_{\beta}$ where $Y_{\alpha}$ and $Y_{\beta}$ are two independent exponential random variables with rates $\alpha$ and $\beta$ , respectively. $\mu=\mathbb{E}[X_{k}]=\frac{\beta-\alpha}{\alpha\beta}$ so we assume that $\alpha>\beta$ . The distribution of the supremum of $S_{n}$ is well-known and also feasible to compute (Example (b) in Section XII.5 of Feller [6]): for $x>0$ ,

\displaystyle\mathbb{P}\bigl{(}\sup_{n\geq 0}S_{n}\leq x)=1-\frac{\beta}{\alpha}e^{-(\alpha-\beta)x}=\beta|\mu|\bigl{(}1+\beta x\bigr{)}+O(\mu^{2}x^{2})

where we assume $|\mu|x$ small and expand $e^{s}=1+s+O(s^{2})$ . We obtain a lower bound:

	$\displaystyle\mathbb{P}\bigl{(}\max_{1\leq n\leq N}S_{n}\leq x)$	$\displaystyle\geq P\bigl{(}\sup_{n\geq 0}S_{n}\leq x)=\beta\|\mu\|\bigl{(}1+\beta x\bigr{)}+O(\mu^{2}x^{2})$
		$\displaystyle\geq\beta^{2}\|\mu\|x+O(\mu^{2}x^{2}).$

Thus for $|\mu|\geq N^{-1/2}$ and small $x|\mu|$ , the upper bound (2.4) loses only a logarithmic factor.

That $\max_{1\leq n\leq N}S_{n}$ is close to the overall maximum $\sup_{n\geq 0}S_{n}$ in the case $|\mu|\geq N^{-1/2}$ is a consequence of the fact that the overall maximum is taken at a random time of order $\mu^{-2}$ . This claim is seen conveniently through ladder intervals $\{T_{i}\}_{i\geq 1}$ . These are the intervals $T_{i}=\tau_{i}-\tau_{i-1}$ between successive ladder epochs defined by $\tau_{0}=0$ and

\tau_{i}=\inf\{n>\tau_{i-1}:S_{n}>S_{\tau_{i-1}}\}.

The distribution of $T_{i}$ is given by

\mathbb{P}(T_{i}=\infty)=1-\frac{\beta}{\alpha}\quad\text{and}\quad\mathbb{P}(T_{i}=n)=C_{n-1}\frac{\alpha^{n-1}\beta^{n}}{(\alpha+\beta)^{2n-1}}\quad\text{for }n\in\mathbb{Z}_{>0},

where $\{C_{k}\}_{k\geq 0}$ are the Catalan numbers. (This calculation can be found in Lemma B.3 in the appendix of [5].) Set $T_{0}=0$ and let $N=\max\{n\geq 0:T_{n}<\infty\}$ be the number of finite ladder intervals. The maximum $\sup_{n\geq 0}S_{n}$ is taken at time $\zeta=\sum_{i=1}^{N}T_{i}$ . One calculates $\mathbb{E}[\zeta]=\frac{1}{\alpha\beta}\mu^{-2}$ and ${\rm\mathbb{V}ar}[\zeta]=c_{\alpha,\beta}\mu^{-4}$ . Thus for large enough $k$ , $\mathbb{P}(\zeta>k\mu^{-2})\leq C_{\alpha,\beta}k^{-2}$ .

Example 2.7 (Log-gamma walk).

This is the application of Theorem 2.2 used in [2].

Let $G^{\lambda}$ denote generically a parameter $\lambda$ gamma random variable, that is, $G^{\lambda}$ has density function $f(x)=\Gamma(\lambda)^{-1}x^{\lambda-1}e^{-x}$ on $\mathbb{R}_{>0}$ . For $\alpha,\beta>0$ let $S^{\alpha,\beta}_{m}=\sum_{i=1}^{m}X^{\alpha,\beta}_{i}$ denote the random walk where the distribution of the i.i.d. steps $\{X^{\alpha,\beta}_{i}\}_{i\geq 1}$ is specified by

X^{\alpha,\beta}_{1}\;\overset{d}{=}\;\log G^{\alpha}-\log G^{\beta}

with two independent gamma variables $G^{\alpha}$ and $G^{\beta}$ on the right.

Let $\psi_{0}(s)=\Gamma^{\prime}(s)/\Gamma(s)$ be the digamma function and $\psi_{1}(s)=\psi_{0}^{\prime}(s)$ the trigamma function on $\mathbb{R}_{>0}$ . Their key properties are that $\psi_{0}$ is strictly increasing with $\psi_{0}(0+)=-\infty$ and $\psi_{0}(\infty)=\infty$ , while $\psi_{1}$ is strictly decreasing and strictly convex with $\psi_{1}(0+)=\infty$ and $\psi_{1}(\infty)=0$ .

Fix a compact interval $[\rho_{\rm min},\rho_{\rm max}]\subset(0,\infty)$ . Fix a positive constant $a_{0}$ and let $\{s_{N}\}_{N\geq 1}$ be a sequence of nonnegative reals such that $0\leq s_{N}\leq a_{0}(\log N)^{-3}$ . Define a set of admissible pairs

\mathcal{S}_{N}=\{(\alpha,\beta):\alpha,\beta\in[\rho_{\rm min},\rho_{\rm max}],\;-s_{N}\leq\alpha-\beta\leq 0\}.

For $(\alpha,\beta)\in\mathcal{S}_{N}$ , the mean step satisfies

(2.10)		$\displaystyle\mu_{\alpha,\beta}$	$\displaystyle=\mathbb{E}[X^{\alpha,\beta}_{1}]=\mathbb{E}[\log G^{\alpha}]-\mathbb{E}[\log G^{\beta}]=\psi_{0}(\alpha)-\psi_{0}(\beta)$
(2.10)			$\displaystyle=\psi_{1}(\lambda)(\alpha-\beta)\;\in\;[-a_{0}\hskip 0.7pt\psi_{1}(\rho_{\rm min})(\log N)^{-3},0]$

where we used the mean value theorem with some $\lambda\in(\rho_{\rm min},\rho_{\rm max})$ . We take $D_{\mu}=a_{0}\hskip 0.7pt\psi_{1}(\rho_{\rm min})$ .

The MGF of $X^{\alpha,\beta}_{1}$ is

(2.11)

\displaystyle M_{\alpha,\beta}(\theta)

\displaystyle=\mathbb{E}\big{[}e^{\theta X^{\alpha,\beta}_{1}}\big{]}=\mathbb{E}\big{[}(G^{\alpha})^{\theta}\hskip 0.9pt\big{]}\,\mathbb{E}\big{[}(G^{\beta})^{-\theta}\hskip 0.9pt\big{]}=\frac{\Gamma(\alpha+\theta)\Gamma(\beta-\theta)}{\Gamma(\alpha)\Gamma(\beta)}

for $\theta\in(-\alpha\hskip 0.9pt,\beta)$ . For the interval in assumption (2.1) we can take $[-\theta_{1},\theta_{1}]=[-\tfrac{1}{2}\rho_{\rm min},\tfrac{1}{2}\rho_{\rm min}]$ . Now (2.1) holds with a single constant $C_{M}=C_{M}(\rho_{\rm min},\rho_{\rm max})$ for all choices of $\alpha,\beta\in[\rho_{\rm min},\rho_{\rm max}]$ .

The variance satisfies

{\rm\mathbb{V}ar}(X^{\alpha,\beta}_{1})={\rm\mathbb{V}ar}(\log G^{\alpha})+{\rm\mathbb{V}ar}(\log G^{\beta})=\psi_{1}(\alpha)+\psi_{1}(\beta)\geq 2\psi_{1}(\rho_{\rm max})={\sigma^{2}_{*}}.

The constants $(C_{M},D_{\mu},{\sigma^{2}_{*}},\theta_{1})$ have been fixed and they work simultaneously for all $(\alpha,\beta)\in\mathcal{S}_{N}$ and all $N\geq 1$ . Define $C$ through (2.5)–(2.7). Choose $N_{0}$ so that (2.8) holds for all $N\geq N_{0}$ . Now $C$ and $N_{0}$ are entirely determined by $(a_{0},\rho_{\rm min},\rho_{\rm max})$ . We state the result as a corollary of Theorem 2.2.

Corollary 2.8.

In the setting described above the bound below holds for all $N\geq N_{0}$ , $(\alpha,\beta)\in\mathcal{S}_{N}$ , and $x\geq(\log N)^{2}$ :

\displaystyle\mathbb{P}\Big{\{}\hskip 0.7pt\max_{1\leq m\leq N}S^{\alpha,\beta}_{m}\leq x\Big{\}}\leq C\hskip 0.55ptx\hskip 0.55pt(\log N)(\mu_{\alpha,\beta}\vee N^{-1/2}\hskip 0.9pt).

3. Comparison with the KMT coupling

As a counterpoint to our Theorem 2.2 we derive here an estimate for a single random walk with the Komlós-Major-Tusnády (KMT) [9] coupling with Brownian motion. We emphasize though that Theorem 3.1 below is not an alternative to our Theorem 2.2 because we do not know how the constants $C,K,\lambda$ below depend on the distribution of the walk. Hence without further work we cannot apply the resulting estimate (3.2) to an infinite family of random walks.

However, this section does illustrate that in a certain regime of vanishing drift the estimates (2.4) and (3.2) are essentially equivalent, as explained below in Remark 3.2. So even if one were to conclude that the constants $C,K,\lambda$ below can be taken uniform, the result remains the same.

Let $\overline{S}_{n}=\sum_{k=1}^{n}\overline{X}_{k}$ be a mean-zero random walk with i.i.d. steps $\{\overline{X}_{k}\}$ and unit variance $E[\,\overline{X}^{\hskip 0.7pt2}\,]=1$ . The KMT coupling (Theorem 1 in [9]) constructs this walk together with a standard Brownian motion $B_{\raisebox{0.5pt}{\scaleobj{0.6}{\bullet}}}$ on a probability space such that the following bound holds:

(3.1)

P\bigl{(}\;\max_{1\leq k\leq N}|\overline{S}_{k}-B_{k}|\geq C\log N+z\hskip 0.7pt\bigr{)}\leq Ke^{-\lambda z}\qquad\text{for all }N\in\mathbb{Z}_{>0}\ \text{ and }\ z>0,

where $C,K,\lambda$ are finite positive constants determined by the distribution of $\overline{X}_{k}$ .

We apply this to the running maximum of a random walk with a negative drift.

Theorem 3.1.

Let $S_{n}=\sum_{i=1}^{n}X_{i}$ be a random walk with i.i.d. steps $\{X_{i}\}$ that satisfy $E[e^{tX}]<\infty$ for $t\in(-\delta,\delta)$ for some $\delta>0$ . Assume the drift is negative: $\mu=EX_{1}<0$ , and the variance $\sigma^{2}=E[\hskip 0.9pt(X_{1}-\mu)^{2}\hskip 0.9pt]>0$ . Then there exists a constant $C_{1}$ determined by the distribution of the normalized variable $\overline{X}_{1}=\sigma^{-1}(X_{1}-\mu)$ such that, for all real $x>0$ and integers $N>e^{4}$ ,

(3.2)		$\displaystyle P\bigl{\{}\hskip 0.9pt\max_{0\leq k\leq N}S_{k}<x\bigr{\}}$	$\displaystyle\leq C_{1}\Bigl{(}\hskip 0.7ptN^{1-(\log N)/2}+\frac{\sigma x+\sigma^{2}\log N}{N^{3/2}\mu^{2}}\hskip 0.9pte^{(\sigma^{-1}x+\log N)\sigma^{-1}\mu}\hskip 0.7pt\Bigr{)}$
(3.2)			$\displaystyle\qquad+1-e^{2(\sigma^{-1}x+C_{1}\log N)\sigma^{-1}\mu}.$

Remark 3.2.

To compare this estimate with Theorem 2.2, imagine that we can let $\mu$ vary as a function of $N$ while preserving the constant $C_{1}$ in (3.2). Consider the regime where $\sigma^{2}$ is constant, $x>\log N$ and $|\mu|$ vanishes fast enough so that $x|\mu|$ stays bounded. Then the first parenthetical expression on the right of (3.2) is dominated by a constant multiple of $xN^{-3/2}\mu^{-2}$ . To the last part apply $1-e^{s}\leq|s|$ for $s<0$ . The bound (3.2) becomes

(3.3)

P\bigl{\{}\hskip 0.9pt\max_{0\leq k\leq N}S_{k}<x\bigr{\}}\leq C_{2}\hskip 0.9ptx\bigl{(}N^{-3/2}\mu^{-2}+|\mu|\bigr{)}.

The bound (2.4) is worse than the one above by at most a $\log N$ factor, and not at all if $\mu$ vanishes fast enough. In particular, for the application in [2], the KMT bound cannot give anything substantially better than Theorem 2.2.

Proof of Theorem 3.1.

Apply (3.1) to the mean-zero unit-variance normalized walk $\overline{S}_{N}=\sigma^{-1}(S_{N}-N\mu)$ . To simplify some steps below we can assume that $C\geq 1\vee\lambda^{-1}$ . Let $x>0$ and $z=\lambda^{-1}\log N$ .

		$\displaystyle P\bigl{\{}\hskip 0.9pt\max_{0\leq k\leq N}S_{k}<x\bigr{\}}=P\bigl{\{}\hskip 0.9pt\max_{0\leq k\leq N}\bigl{(}\overline{S}_{k}+k\sigma^{-1}\mu\bigr{)}<\sigma^{-1}x\bigr{\}}$
(3.4)			$\displaystyle\leq Ke^{-\lambda z}+P\bigl{\{}\hskip 0.9pt\max_{0\leq k\leq N}\bigl{(}B_{k}+k\sigma^{-1}\mu\bigr{)}<\sigma^{-1}x+C\log N+z\bigr{\}}.$

Let $M_{k}=\sup_{0\leq s\leq 1}(B_{k+s}-B_{k})$ . Since $\mu<0$ ,

\displaystyle\sup_{0\leq t\leq N}\bigl{(}B_{t}+t\sigma^{-1}\mu\bigr{)}

\displaystyle\leq\max_{0\leq k\leq N}\bigl{(}B_{k}+k\sigma^{-1}\mu\bigr{)}+\max_{0\leq k\leq N-1}M_{k}.

With this we continue from above.

(3.5)		$\displaystyle\text{line \eqref{kmt600}}\;\leq\;Ke^{-\lambda z}\;+$	$\displaystyle P\bigl{\{}\hskip 0.9pt\sup_{0\leq t\leq N}\bigl{(}B_{t}+t\sigma^{-1}\mu\bigr{)}<\sigma^{-1}x+2C\log N+z\bigr{\}}$
(3.5)			$\displaystyle\qquad+P\bigl{\{}\hskip 0.9pt\max_{0\leq k\leq n-1}M_{k}>C\log N\bigr{\}}.$

We bound the two probabilities above separately. Recall that $C\geq 1$ . For the running maximum of standard Brownian motion, by (2.8.4) on page 96 of [8],

(3.6)		$\displaystyle P\bigl{\{}\hskip 0.9pt\max_{0\leq k\leq N-1}M_{k}>\log N\bigr{\}}$	$\displaystyle\leq N\hskip 0.55ptP\bigl{\{}\hskip 0.7pt\sup_{0\leq s\leq 1}B_{s}>\log N\bigr{\}}=N\sqrt{2/\pi}\int_{\log N}^{\infty}e^{-y^{2}/2}\,dy$
(3.6)			$\displaystyle\leq\frac{N\sqrt{2/\pi}}{\log N}\int_{\log N}^{\infty}y\hskip 0.7pte^{-y^{2}/2}\,dy=\frac{\sqrt{2/\pi}}{\log N}N^{1-(\log N)/2}.$

For the running maximum of Brownian motion with drift, use first Brownian scaling, and then the density of the hitting time $T_{b(N)}$ of the point $b(N)=N^{-1/2}(\sigma^{-1}x+2C\log N+z)$ with drift $\mu(N)=\sigma^{-1}N^{1/2}\mu<0$ from (3.5.12) on page 197 of [8].

(3.7)			$\displaystyle P\bigl{\{}\hskip 0.9pt\sup_{0\leq t\leq N}\bigl{(}B_{t}+t\sigma^{-1}\mu\bigr{)}<\sigma^{-1}x+2C\log N+z\bigr{\}}$
			$\displaystyle=P\bigl{\{}\hskip 0.9pt\sup_{0\leq t\leq 1}\bigl{(}B_{t}+t\sigma^{-1}N^{1/2}\mu\bigr{)}<N^{-1/2}(\sigma^{-1}x+2C\log N+z)\bigr{\}}$
			$\displaystyle=P\bigl{\{}\hskip 0.9pt\sup_{0\leq t\leq 1}\bigl{(}B_{t}+t\mu(N)\bigr{)}<b(N)\bigr{\}}=P^{(\mu(N))}\{T_{b(N)}>1\}$
			$\displaystyle={b(N)}\int_{1}^{\infty}\frac{1}{\sqrt{2\pi s^{3}}}e^{-(b(N)-\mu(N)s)^{2}/2s}\,ds+P^{(\mu(N))}\{T_{b(N)}=\infty\}$
			$\displaystyle={b(N)}e^{b(N)\mu(N)}\int_{1}^{\infty}\frac{1}{\sqrt{2\pi s^{3}}}e^{-\tfrac{1}{2}b(N)^{2}s^{-1}-\tfrac{1}{2}\mu(N)^{2}s}\,ds+1-e^{2b(N)\mu(N)}$
			$\displaystyle\leq 2\hskip 0.55pte^{b(N)\mu(N)}\hskip 0.9pt\frac{b(N)}{\mu(N)^{2}}+1-e^{2b(N)\mu(N)}$
			$\displaystyle\leq 2\hskip 0.55pte^{(\sigma^{-1}x+\log N)\sigma^{-1}\mu}\hskip 0.9pt\frac{\sigma x+3C\sigma^{2}\log N}{N^{3/2}\mu^{2}}+1-e^{2(\sigma^{-1}x+3C\log N)\sigma^{-1}\mu}.$

The second last inequality dropped the denominator $2\pi s^{3}\geq 1$ and the term $-\tfrac{1}{2}b(N)^{2}s^{-1}$ from the exponent, and then integrated. The last inequality substituted in $z=\lambda^{-1}\log N\leq C\log N$ to bound

N^{-1/2}(\sigma^{-1}x+\log N)\leq b(N)\leq N^{-1/2}(\sigma^{-1}x+3C\log N).

The conclusion (3.2) follows from substituting into (3.5) the bounds from above. ∎

4. Auxiliary facts

Before starting the proof proper, we record some simple facts. First, assumptions (2.1) and (2.2) gives these bounds:

(4.1)			$\displaystyle 0<{\sigma^{2}_{*}}\leq\mu_{2,N}\equiv\mathbb{E}\big{[}(X^{N}_{1})^{2}\big{]}=M_{N}^{(2)}(0)\leq C_{M},$
			$\displaystyle\|\mu_{3,N}\|\equiv\|\mathbb{E}\big{[}(X^{N}_{1})^{3}\big{]}\|=\|M_{N}^{(3)}(0)\|\leq C_{M},$
			$\displaystyle\mathbb{P}(X^{N}_{1}>t)\leq C_{M}e^{-\theta_{1}t}.$

Lemma 4.1.

Let $\{Y_{i}\}$ be i.i.d. random variables with common marginal distribution $\nu$ . Assume that, for two constants $0<c_{1},C_{1}<\infty$ ,

(4.2)

\displaystyle\mathbb{E}(e^{tY_{1}})\leq C_{1}\quad\text{ for }\quad t\in[0,c_{1}].

Then

\displaystyle\mu_{\rm max}=\mu_{\rm max}(\nu,n)\equiv\mathbb{E}\bigl{[}\max\{0,Y_{1},...,Y_{n}\}]\leq c_{1}^{-1}\log(C_{1}n+1).

Proof.

For $0<t\leq c_{1}$ ,

\displaystyle e^{t\mu_{\rm max}}\leq\mathbb{E}\big{(}e^{t(0\vee\max_{1\leq i\leq n}Y_{i})}\big{)}\leq 1+\mathbb{E}\Big{(}\sum_{i=1}^{n}e^{tY_{i}}\Big{)}=1+n\mathbb{E}\big{(}e^{tY_{1}}\big{)}\leq C_{1}n+1,

and the claim follows by taking $t=c_{1}$ . ∎

Since $M_{N}^{\prime\prime}>0$ there is a unique minimizer

(4.3)

\displaystyle\theta^{N}_{0}=\arg\min\{M_{N}(\theta)\}.

Lemma 4.2.

Let $N_{0}$ be such that $C_{M}|\mu_{N}|\leq\tfrac{1}{3}{\sigma^{2}_{*}}$ for $N\geq N_{0}$ and set $c_{M}=2\sigma_{*}^{-2}$ . Then for $N\geq N_{0}$ ,

\displaystyle 0\leq\theta^{N}_{0}\leq c_{M}|\mu_{N}|.

Proof.

If $M^{\prime}_{N}(0)=\mu_{N}=0$ then the minimum is taken at $\theta^{N}_{0}=0$ .

So suppose $M^{\prime}_{N}(0)=\mu_{N}<0$ . Expansion for $\theta\in(0,\theta_{1})$ gives, with some $\theta^{\prime}\in(0,\theta)$ ,

\displaystyle M^{\prime}_{N}(\theta)

\displaystyle=\mu_{N}+\mu_{2,N}\theta+\tfrac{1}{2}M^{(3)}_{N}(\theta^{\prime})\hskip 0.7pt\theta^{2}\geq\mu_{N}+\mu_{2,N}\theta-\tfrac{1}{2}C_{M}\theta^{2}.

Since $M^{\prime}$ is strictly increasing and $c_{M}=2/{\sigma^{2}_{*}}\geq 2\mu_{2,N}^{-1}$ , by the choice of $N_{0}$ we have for $N\geq N_{0}$

\displaystyle M^{\prime}_{N}(-c_{M}\mu_{N})\geq M^{\prime}_{N}\Big{(}-\frac{2\mu_{N}}{\mu_{2,N}}\Big{)}\geq-\mu_{N}-2C_{M}\hskip 0.9pt\frac{\mu_{N}^{2}}{\mu_{2,N}^{2}}\geq-\mu_{N}\bigl{(}1-\tfrac{2}{3}{\sigma^{2}_{*}}/\mu_{2,N}^{2}\bigr{)}>0.

It follows that there exists a unique $\theta^{N}_{0}\in(0,c_{M}|\mu_{N}|)$ such that $M^{\prime}_{N}(\theta^{N}_{0})=0.$ ∎

Define a tilted measure $Q(d\omega)=f^{\theta_{0}^{N}}_{N,n}(\omega)\mathbb{P}(d\omega)$ in terms of the Radon-Nikodym derivative

\displaystyle f^{\theta_{0}^{N}}_{N,n}(\omega)=\frac{e^{\theta^{N}_{0}S^{N}_{n}}}{\mathbb{E}\big{(}e^{\theta^{N}_{0}S^{N}_{n}}\big{)}}.

Denote the expectation under $Q$ by $\mathbb{E}^{Q}$ . Increase $N_{0}$ further so that $N\geq N_{0}$ implies $\theta^{N}_{0}\in[-\theta_{1}/2,\theta_{1}/2]$ and $-\mu_{N}\leq 2$ . Then for $0\leq i\leq 3$ and $\theta\in(-\theta_{1}/2,\theta_{1}/2)$ , the MGF under $Q$ satisfies

(4.4)		$\displaystyle M^{(i)}_{Q,N}(\theta)$	$\displaystyle=\mathbb{E}^{Q}\big{(}(X^{N}_{1})^{i}e^{\theta X^{1}_{N}}\big{)}=M_{N}(\theta^{N}_{0})^{-1}\mathbb{E}\big{(}(X^{N}_{1})^{i}e^{(\theta+\theta^{N}_{0})X^{1}_{N}}\big{)}$
(4.4)			$\displaystyle=M_{N}(\theta^{N}_{0})^{-1}M^{(i)}_{N}(\theta^{N}_{0}+\theta)\leq e^{-\mu_{N}\theta_{0}^{N}}C_{M}\leq e^{\theta_{1}}C_{M},$

where the first inequality used Jensen’s inequality and (2.1). From this we get moment bounds under $Q$ : for $0\leq i\leq 3$ ,

(4.5)

\displaystyle\mathbb{E}^{Q}\big{(}(X^{N}_{1})^{i}\big{)}

\displaystyle=M^{(i)}_{Q,N}(0)\leq e^{\theta_{1}}C_{M}.

For $|\theta|\leq\theta_{1}$ , there exists $\theta^{\prime}\in(-\theta_{1},\theta_{1})$

\displaystyle M_{N}^{(2)}(\theta)=\mu_{2,N}+M_{N}^{(3)}(\theta^{\prime})\theta

Increase $N_{0}$ further if necessary so that $\theta^{N}_{0}\leq\frac{{\sigma^{2}_{*}}}{2C_{M}}$ for $N\geq N_{0}$ and we can write

\displaystyle M_{N}^{(2)}(\theta_{0}^{N})\geq{\sigma^{2}_{*}}-C_{M}\theta_{0}^{N}\geq\frac{{\sigma^{2}_{*}}}{2}.

Then from $\mathbb{E}^{Q}(X^{N}_{1})=0$ and the third equation in (4.4),

(4.6)

\displaystyle{\rm\mathbb{V}ar}^{Q}(X^{N}_{1})=\mathbb{E}^{Q}\big{(}(X^{N}_{1})^{2}\big{)}

\displaystyle=M^{(2)}_{Q,N}(0)=M_{N}(\theta^{N}_{0})^{-1}M^{(2)}_{N}(\theta^{N}_{0})\geq C_{M}^{-1}\frac{{\sigma^{2}_{*}}}{2}.

5. Proof of the main theorem

To lighten the notation we omit the label $N$ from $\mu=\mu_{N}$ and $\theta_{0}=\theta^{N}_{0}$ , and from some other notation that obviously depend on $N$ . For $y>0$ let

\displaystyle\tau_{y}=\inf\{m\geq 1:|S^{N}_{m}|\geq y\}

denote the first hitting time of the cylinder of width $2y$ . Let $\Phi_{\sigma^{2}}$ denote the centered Gaussian distribution with variance $\sigma^{2}$ .

Lemma 5.1.

For real $k\geq 0$ and $y\geq y_{0}$ we have $\mathbb{P}(\tau_{y}>ky^{2})\leq 2e^{-c_{\tau}k},$ where

(5.1)

y_{0}=1\,\vee\,\frac{6C_{M}\sigma_{*}^{-3}}{1-\Phi_{{\sigma^{2}_{*}}}[-2,2]}\qquad\text{and}\qquad c_{\tau}=\log\frac{2}{1+\Phi_{{\sigma^{2}_{*}}}[-2,2]}\,\in\,(0,\log 2).

Proof.

Let $\widebar{S}^{N}_{m}=S^{N}_{m}-m\mu$ be the centered walk. Consider an integer $k\geq 1$ and a real $y\geq 1$ . Look at the process along time increments of size $\lfloor{y}\rfloor^{2}$ :

	$\displaystyle\mathbb{P}(\tau_{y}>ky^{2})$	$\displaystyle\leq\mathbb{P}(\tau_{y}>k\lfloor{y}\rfloor^{2})\leq\mathbb{P}(\,\|S^{N}_{m\lfloor{y}\rfloor^{2}}\|\leq y\text{ for }m=1,\dotsc,k\,)$
		$\displaystyle\leq\mathbb{P}(\,\|S^{N}_{m\lfloor{y}\rfloor^{2}}-S^{N}_{(m-1)\lfloor{y}\rfloor^{2}}\|\leq 2y\text{ for }m=1,\dotsc,k\,)$
		$\displaystyle=\bigl{(}\mathbb{P}\{\,S^{N}_{\lfloor{y}\rfloor^{2}}\in[-2y,2y]\}\bigl{)}^{k}=\bigl{(}\mathbb{P}\bigl{\{}\,\lfloor{y}\rfloor^{-1}\overline{S}^{N}_{\!\lfloor{y}\rfloor^{2}}\in[-2-\mu\lfloor{y}\rfloor\hskip 0.7pt,2-\mu\lfloor{y}\rfloor]\bigr{\}}\bigl{)}^{k}$
		$\displaystyle\leq\Bigl{(}\Phi_{\sigma_{N}^{2}}[-2-\mu\lfloor{y}\rfloor,2-\mu\lfloor{y}\rfloor]+3\frac{\mu_{3,N}}{\sigma^{3}}\lfloor{y}\rfloor^{-1}\Bigr{)}^{k}\leq\bigl{(}\Phi_{\sigma_{N}^{2}}[-2,2]+6C_{M}\sigma_{*}^{-3}y^{-1}\bigl{)}^{k}.$

The penultimate inequality is the Berry-Esseen Theorem. We use the version from [4, Section 3.4.4] where the constant is 3. The last inequality is a simple property of a centered Gaussian. Now for $y\geq y_{0}$ and $c_{\tau}$ as above,

	$\displaystyle\sup_{{\sigma^{2}_{}}\leq\sigma^{2}\leq C_{M}}\Phi_{\sigma^{2}}[-2,2]+3C_{M}\sigma_{}^{-3}y^{-1}$	$\displaystyle\leq\Phi_{{\sigma^{2}_{}}}[-2,2]+3C_{M}\sigma_{}^{-3}y_{0}^{-1}$
		$\displaystyle\leq\tfrac{1}{2}(1+\Phi_{{\sigma^{2}_{*}}}[-2,2])=e^{-c_{\tau}}.$

We have proved $\mathbb{P}(\tau_{y}>ky^{2})\leq e^{-c_{\tau}k}$ for $k\in\mathbb{Z}_{\geq 0}$ . Extend this to real $k\in\mathbb{R}_{\geq 0}$ :

\displaystyle\mathbb{P}(\tau_{y}>ky^{2})

\displaystyle\leq\mathbb{P}(\tau_{y}>\lfloor{k}\rfloor y^{2})\leq e^{-c_{\tau}\lfloor{k}\rfloor}\leq e^{-c_{\tau}(k-1)}=2(1+\Phi_{{\sigma^{2}_{*}}}[-2,2])^{-1}e^{-c_{\tau}k}<2e^{-c_{\tau}k}.\qed

Let $H_{N}=\mu^{-2}\wedge N$ . By (2.3)

(5.2)

\displaystyle D_{\mu}^{-2}(\log N)^{6}\leq H_{N}\leq N.

Define the truncated version of $\tau_{y}$

\displaystyle\hat{\tau}_{y}=\tau_{y}\wedge H_{N}.

The following result shows that although the random walk $S^{N}_{m}$ has negative drift, up to times of order $H_{N}$ it behaves similarly to an unbiased random walk in the following sense: if $y>0$ is not too small, but small compared to $H_{N}^{1/2}$ , the probability that the random walk reaches level $y$ before level $-y$ is close to $1/2$ . Our choice of $H_{N}$ can be justified by decomposing the random walk into

\displaystyle S^{N}_{n}=\sum_{i=1}^{n}\big{(}X_{i}^{N}-\mu\big{)}+n\mu.

For $\varepsilon>0$ small and $|\mu|\geq N^{-1/2}$ (so that $H_{N}=\mu^{-2}$ ),

(5.3)

\displaystyle(\varepsilon H_{N})^{-1/2}S^{N}_{\varepsilon H_{N}}=(\varepsilon H_{N})^{-1/2}\sum_{i=1}^{\varepsilon H_{N}}\big{(}X_{i}^{N}-\mu\big{)}+\varepsilon^{1/2}.

\displaystyle(\varepsilon H_{N})^{-1/2}\sum_{i=1}^{\varepsilon H_{N}}\big{(}X_{i}^{N}-\mu\big{)}\overset{d}{\approx}N(0,\sigma),

we see that the left hand side of (5.3) is dominated by the first term on the right hand side. That is, up to time $\varepsilon H_{N}$ the random walk $S^{N}$ behaves approximately like an unbiased random walk.

Lemma 5.2.

Let $y_{0}$ be as in (5.1). There exist finite constants $N_{0}$ and $C_{0}$ such that, for $N\geq N_{0}$ and $y_{0}\leq y\leq(\log N)^{-1}H_{N}^{1/2}$ ,

\displaystyle\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)\geq\tfrac{1}{2}\Bigl{[}1-C_{0}H_{N}^{-\frac{1}{2}}\big{(}y+(\log H_{N})^{2}\big{)}-\frac{2}{\theta_{1}y}\log(e^{\theta_{1}}C_{M}H_{N}+1)\Bigr{]}.

$C_{0}$ depends on $\theta_{1},{\sigma^{2}_{*}}$ and $C_{M}$ while $N_{0}$ depends on $\theta_{1},{\sigma^{2}_{*}}$ , $D_{\mu}$ and $C_{M}$ .

Proof.

The constant $C_{0}$ comes as follows in terms of the constants previously introduced above and new constants $C_{2},C_{3},C_{4}$ introduced below in the course of the proof:

(5.4)		$\displaystyle C_{0}=C_{2}+C_{4}$	$\displaystyle=2(\sigma_{}^{-1}+9e^{\theta_{1}}\sigma_{}^{-3}C_{M}^{5/2})+2C_{3}c_{\tau}^{-1}+6c_{M}$
(5.4)			$\displaystyle=2(\sigma_{}^{-1}+9e^{\theta_{1}}\sigma_{}^{-3}C_{M}^{\hskip 0.7pt5/2})+2e^{2C_{M}c_{M}^{2}+4c_{M}}c_{\tau}^{-1}+6c_{M}.$

Under the measure $Q$ , $S_{n}$ is a mean-zero random walk and hence a martingale. Furthermore, ${\hat{\tau}_{y}}$ is a bounded stopping time. From this,

\displaystyle 0=\int S_{\hat{\tau}_{y}}dQ=\int_{S_{\hat{\tau}_{y}}\geq y}S_{\hat{\tau}_{y}}dQ+\int_{S_{\hat{\tau}_{y}}\leq-y}S_{\hat{\tau}_{y}}dQ+\int_{S_{\hat{\tau}_{y}}\in(-y,y)}S_{\hat{\tau}_{y}}dQ.

On the event $S_{\hat{\tau}_{y}}\geq y$ , we have $\hat{\tau}_{y}=\tau_{y}$ and $S_{\hat{\tau}_{y}-1}<y\leq S_{\hat{\tau}_{y}}=S_{\hat{\tau}_{y}-1}+X^{N}_{\hat{\tau}_{y}}\leq y+X^{N}_{\hat{\tau}_{y}}$ and so

	$\displaystyle\int_{S_{\hat{\tau}_{y}}\geq y}S_{\hat{\tau}_{y}}\,dQ$	$\displaystyle\leq\int_{S_{\hat{\tau}_{y}}\geq y}\big{(}y+X^{N}_{\hat{\tau}_{y}}\big{)}\,dQ\leq\int_{S_{\hat{\tau}_{y}}\geq y}\big{(}y+0\vee\max_{1\leq i\leq H_{N}}X^{N}_{i}\big{)}\,dQ$
		$\displaystyle\leq y\hskip 0.9ptQ(S_{\hat{\tau}_{y}}\geq y)+\mu_{\rm max}(Q,H_{N})\;\leq\;y\hskip 0.9ptQ(S_{\hat{\tau}_{y}}\geq y)+2\theta_{1}^{-1}\log(e^{\theta_{1}}C_{M}H_{N}+1),$

where we applied Lemma 4.1 under the distribution $Q$ with $C_{1}=e^{\theta_{1}}C_{M},c_{1}=\tfrac{1}{2}\theta_{1}$ from (4.4). Combine the displays above to obtain

	$\displaystyle Q(S_{\hat{\tau}_{y}}\geq y)$	$\displaystyle\geq-\,y^{-1}\!\!\!\int\limits_{S_{\hat{\tau}_{y}}\leq-y}S_{\hat{\tau}_{y}}dQ\;-\;y^{-1}\!\!\!\!\!\!\int\limits_{S_{\hat{\tau}_{y}}\in(-y,y)}S_{\hat{\tau}_{y}}dQ\;-\;2\theta_{1}^{-1}y^{-1}\log(e^{\theta_{1}}C_{M}H_{N}+1)$
		$\displaystyle\geq Q(S_{\hat{\tau}_{y}}\leq-y)-Q(S_{\hat{\tau}_{y}}\in(-y,y))-2\theta_{1}^{-1}y^{-1}\log(e^{\theta_{1}}C_{M}H_{N}+1).$

Use

\displaystyle Q(S_{\hat{\tau}_{y}}\leq-y)=1-Q(S_{\hat{\tau}_{y}}\geq y)-Q(S_{\hat{\tau}_{y}}\in(-y,y))

to rewrite the above as

(5.5)

\hskip 0.9ptQ(S_{\hat{\tau}_{y}}\geq y)\geq\tfrac{1}{2}[1-2\hskip 0.9ptQ(S_{\hat{\tau}_{y}}\in(-y,y))-2\theta_{1}^{-1}y^{-1}\log(e^{\theta_{1}}C_{M}H_{N}+1)].

It remains to bound the probability on the right. $S_{\hat{\tau}_{y}}\in(-y,y)$ forces $\hat{\tau}_{y}=H_{N}$ and thereby another application of the Berry-Esseen theorem, while using (4.5), (4.6) and $y\geq y_{0}\geq 1$ , gives

	$\displaystyle Q\bigl{\{}S_{\hat{\tau}_{y}}\in(-y,y)\bigr{\}}$	$\displaystyle=Q\bigl{\{}H_{N}^{-1/2}S_{H_{N}}\in(-H_{N}^{-1/2}y,H_{N}^{-1/2}y)\bigr{\}}$
		$\displaystyle\leq\Phi_{{\sigma^{2}_{}}}(-H_{N}^{-1/2}y,H_{N}^{-1/2}y)+3\frac{e^{\theta_{1}}C_{M}}{2^{-3/2}C_{M}^{-3/2}\sigma_{}^{3}}H_{N}^{-\frac{1}{2}}$
		$\displaystyle\leq 2(2\pi{\sigma^{2}_{}})^{-1/2}yH_{N}^{-1/2}+9\frac{e^{\theta_{1}}C_{M}}{C_{M}^{-3/2}\sigma_{}^{3}}H_{N}^{-\frac{1}{2}}\leq(\sigma_{}^{-1}+9e^{\theta_{1}}\sigma_{}^{-3}C_{M}^{5/2})\hskip 0.55pty\hskip 0.55ptH_{N}^{-\frac{1}{2}}$
		$\displaystyle\equiv\tfrac{1}{2}C_{2}\hskip 0.55pty\hskip 0.55ptH_{N}^{-\frac{1}{2}}.$

Rewrite (5.5) as

(5.6)

\displaystyle Q(S_{\hat{\tau}_{y}}\geq y)\geq\tfrac{1}{2}[1-C_{2}\hskip 0.55pty\hskip 0.55ptH_{N}^{-\frac{1}{2}}-2y^{-1}\theta_{1}^{-1}\log(e^{\theta_{1}}C_{M}H_{N}+1)].

It remains to switch from $Q$ back to the original distribution $\mathbb{P}$ . Recall the Radon-Nikodym derivative $f^{\theta}_{n}={M(\theta)^{-n}}{e^{\theta S_{n}}}$ . Introduce a temporary quantity $G_{0}>1$ to be chosen precisely below. Decompose according to the value of $\hat{\tau}_{y}$ and use Cauchy-Schwarz:

	$\displaystyle Q(S_{\hat{\tau}_{y}}\geq y)$	$\displaystyle=\mathbb{E}\big{[}f^{\theta_{0}}_{{\hat{\tau}_{y}}}(\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt{\hat{\tau}_{y}}\leq G_{0}}+\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt{\hat{\tau}_{y}}>G_{0}})\big{]}$
(5.7)			$\displaystyle\leq\mathbb{E}\big{[}f^{\theta_{0}}_{{\hat{\tau}_{y}}}\hskip 0.7pt\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt{\hat{\tau}_{y}}\leq G_{0}}\big{]}+\Big{(}\mathbb{E}\big{[}(f^{\theta_{0}}_{{\hat{\tau}_{y}}})^{2}\big{]}\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{P}\{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt{\hat{\tau}_{y}}>G_{0}\}\Big{)}^{\frac{1}{2}}.$

Let us first bound the second term on line (5.7). Note that $f^{\theta}_{n}$ is a $\mathbb{P}$ -martingale and ${\hat{\tau}_{y}}$ is a stopping time bounded by $H_{N}$ . Hence $(f^{\theta}_{n})^{2}$ is a submartingale and we have

	$\displaystyle\Big{(}\mathbb{E}[(f^{\theta_{0}}_{\hat{\tau}_{y}})^{2}\hskip 0.7pt]\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{P}\{S_{\hat{\tau}_{y}}\geq y,{\hat{\tau}_{y}}>G_{0}\}\Big{)}^{\frac{1}{2}}$
	$\displaystyle\leq\Big{(}\mathbb{E}[(f^{\theta_{0}}_{H_{N}})^{2}\hskip 0.7pt]\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{P}\{S_{\hat{\tau}_{y}}\geq y,{\hat{\tau}_{y}}>G_{0}\}\Big{)}^{\frac{1}{2}}=\bigg{(}\frac{M(2\theta_{0})}{M(\theta_{0})^{2}}\bigg{)}^{H_{N}/2}\Big{(}\mathbb{P}\{S_{\hat{\tau}_{y}}\geq y,{\hat{\tau}_{y}}>G_{0}\}\Big{)}^{\frac{1}{2}}.$

To bound the $M$ -factor on the right, expand $M$ and use (2.1), (4.1) and $\mu<0$ . In the numerator, for some $\eta\in(0,2\theta_{0})$ ,

M(2\theta_{0})=1+\mu 2\theta_{0}+2\mu_{2}\theta_{0}^{2}+\tfrac{8}{6}M^{(3)}(\eta)\theta_{0}^{3}\leq 1+2\mu_{2}\theta_{0}^{2}+\tfrac{4}{3}C_{M}\theta_{0}^{3}

and similarly in the denominator:

(5.8)			$\displaystyle\Big{[}M(2\theta_{0})M(\theta_{0})^{-2}\Big{]}^{H_{N}/2}\leq\Big{(}1+2\mu_{2}\theta_{0}^{2}+\tfrac{4}{3}C_{M}\theta_{0}^{3}\Big{)}^{H_{N}/2}\Big{(}1+\mu\theta_{0}+\tfrac{1}{2}\mu_{2}\theta_{0}^{2}-\tfrac{1}{6}C_{M}\theta_{0}^{3}\Big{)}^{-H_{N}}$
			$\displaystyle\leq\Big{(}1+2C_{M}c_{M}^{2}\mu^{2}+\tfrac{4}{3}C_{M}c_{M}^{3}\|\mu\|^{3}\Big{)}^{\tfrac{1}{2}\mu^{-2}}\Big{(}1-c_{M}\mu^{2}-C_{M}c_{M}^{3}\|\mu\|^{3}\Big{)}^{-\mu^{-2}}$
			$\displaystyle\leq e^{2C_{M}c_{M}^{2}+4c_{M}}\equiv C_{3}.$

Above we used $H_{N}\leq\mu^{-2}$ and increased $N_{0}$ once more so that $N\geq N_{0}$ guarantees $\tfrac{2}{3}c_{M}|\mu|\leq 1$ , $c_{M}\mu^{2}+C_{M}c_{M}^{3}|\mu|^{3}\leq\tfrac{1}{2}$ and $C_{M}c_{M}^{3}|\mu|\leq 1$ . Then we applied the bounds

	$\displaystyle\Big{(}1+2C_{M}c_{M}^{2}\mu^{2}+\tfrac{4}{3}C_{M}c_{M}^{3}\|\mu\|^{3}\Big{)}^{\tfrac{1}{2}\mu^{-2}}$	$\displaystyle\leq e^{C_{M}c_{M}^{2}(1+\frac{2}{3}c_{M}\|\mu\|)}\leq e^{2C_{M}c_{M}^{2}},$
	$\displaystyle\Big{(}1-c_{M}\mu^{2}-C_{M}c_{M}^{3}\|\mu\|^{3}\Big{)}^{-\mu^{-2}}$	$\displaystyle\leq\Big{(}1+2c_{M}\mu^{2}\bigl{(}1+C_{M}c_{M}^{3}\|\mu\|\bigr{)}\Big{)}^{\mu^{-2}}\leq e^{2c_{M}(1+C_{M}c_{M}^{3}\|\mu\|)}\leq e^{4c_{M}},$

where the second line also used $(1-a)^{-1}\leq 1+2a$ for $a\in[0,\tfrac{1}{2}]$ . Put (5.8) back up, set $G_{0}=yH_{N}^{1/2}$ , and apply Lemma 5.1 (for which we use the assumption $y\geq y_{0}$ ):

(5.9)

\displaystyle\Big{(}\mathbb{E}[(f^{\theta_{0}}_{\hat{\tau}_{y}})^{2}\hskip 0.7pt]\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{P}\{S_{\hat{\tau}_{y}}\geq y,{\hat{\tau}_{y}}>G_{0}\}\Big{)}^{\frac{1}{2}}\leq C_{3}\bigl{(}\mathbb{P}\{{\hat{\tau}_{y}}>G_{0}\}\bigr{)}^{\frac{1}{2}}\leq 2C_{3}e^{-c_{\tau}H_{N}^{1/2}y^{-1}}.

Next we bound the first term on line (5.7). Use $M(\theta_{0})\leq 1$ . Let $\mathcal{M}_{n}=\max_{1\leq i\leq n}X^{N}_{i}$ .

(5.10)			$\displaystyle\mathbb{E}\big{[}f^{\theta_{0}}_{{\hat{\tau}_{y}}}\hskip 0.7pt\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt{\hat{\tau}_{y}}\leq G_{0}}\big{]}=\mathbb{E}\Big{[}\frac{e^{\theta_{0}S_{\hat{\tau}_{y}}}}{M(\theta_{0})^{\hat{\tau}_{y}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt{\hat{\tau}_{y}}\leq G_{0}}\Big{]}$
			$\displaystyle\leq\mathbb{E}\Big{[}\frac{e^{\theta_{0}S_{\hat{\tau}_{y}}}}{M(\theta_{0})^{G_{0}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt\mathcal{M}_{H_{N}}\leq(\log H_{N})^{2}}\Big{]}+\mathbb{E}\Big{[}\frac{e^{\theta_{0}S_{\hat{\tau}_{y}}}}{M(\theta_{0})^{\hat{\tau}_{y}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt\mathcal{M}_{H_{N}}>(\log H_{N})^{2}}\Big{]}$
			$\displaystyle\leq\mathbb{E}\Big{[}\frac{e^{\theta_{0}(y+\mathcal{M}_{H_{N}})}}{M(\theta_{0})^{G_{0}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt\mathcal{M}_{H_{N}}\leq(\log H_{N})^{2}}\Big{]}+\mathbb{E}\Big{[}\frac{e^{\theta_{0}S_{\hat{\tau}_{y}}}}{M(\theta_{0})^{\hat{\tau}_{y}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt\mathcal{M}_{H_{N}}>(\log H_{N})^{2}}\Big{]}$

Let us first bound the second term. Using Cauchy-Schwarz, the bound

\displaystyle\mathbb{P}(\mathcal{M}_{H_{N}}>t)\leq H_{N}C_{M}e^{-\theta_{1}t},

the bound (5.8), and the tail bound in (4.1), it follows that

	$\displaystyle\mathbb{E}\Big{[}\frac{e^{\theta_{0}S_{\hat{\tau}_{y}}}}{M(\theta_{0})^{\hat{\tau}_{y}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt\mathcal{M}_{H_{N}}>(\log H_{N})^{2}}\Big{]}$	$\displaystyle\leq\Big{(}\mathbb{E}[(f^{\theta_{0}}_{H_{N}})^{2}\hskip 0.7pt]\Big{)}^{\frac{1}{2}}\Big{(}\mathbb{P}\{\mathcal{M}_{H_{N}}>(\log H_{N})^{2}\}\Big{)}^{\frac{1}{2}}$
		$\displaystyle\leq C_{3}H_{N}^{1/2}C^{1/2}_{M}e^{-\frac{1}{2}\theta_{1}(\log H_{N})^{2}}.$

The first term on the last line of (5.10) is bounded as follows, with $G_{0}=yH_{N}^{1/2}$ .

	$\displaystyle\mathbb{E}\Big{[}\frac{e^{\theta_{0}(y+\mathcal{M}_{H_{N}})}}{M(\theta_{0})^{G_{0}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt\mathcal{M}_{H_{N}}\leq(\log H_{N})^{2}}\Big{]}\leq\mathbb{E}\Big{[}\frac{e^{\theta_{0}(y+(\log H_{N})^{2})}}{M(\theta_{0})^{G_{0}}}\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y}\Big{]}$
	$\displaystyle\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y){e^{c_{M}H_{N}^{-1/2}[y+(\log H_{N})^{2}]}}M(\theta_{0})^{-\hskip 0.7ptyH_{N}^{1/2}}\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y){e^{c_{M}H_{N}^{-1/2}[y+(\log H_{N})^{2}]}}e^{c_{M}yH_{N}^{-1/2}}$
	$\displaystyle=\mathbb{P}(S_{\hat{\tau}_{y}}\geq y){e^{c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}]}}$
	$\displaystyle\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)\big{[}1+2c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}]\big{]}\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)+2c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}].$

We used above Jensen’s inequality in the form $M(\theta_{0})^{-yH_{N}^{1/2}}\leq e^{-\theta_{0}\mu yH_{N}^{1/2}}$ , the definition of $H_{N}$ in the form $|\mu|H_{N}^{1/2}\leq 1$ , and then $\theta_{0}\leq c_{M}|\mu|\leq c_{M}H^{-1/2}$ . Furthermore, by (5.2) and our assumption $y\leq(\log N)^{-1}H_{N}^{1/2}$ we have

c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}]\leq c_{M}(2+D_{\mu})(\log N)^{-1}\leq\log 2

where we choose $N_{0}$ large enough so that the last inequality holds for $N\geq N_{0}$ . Then we applied the inequality $e^{x}\leq 1+2x$ for $x\in[0,\log 2]$ .

Going back to (5.10), for $N\geq N_{0}$ ,

	$\displaystyle E\big{[}f^{\theta_{0}}_{{\hat{\tau}_{y}}}\hskip 0.7pt\mathbf{1}_{S_{\hat{\tau}_{y}}\geq y,\hskip 0.9pt{\hat{\tau}_{y}}\leq G_{0}}\big{]}$	$\displaystyle\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)+2c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}]+C_{3}H_{N}^{1/2}C^{1/2}_{M}e^{-\frac{1}{2}\theta_{1}(\log H_{N})^{2}}$
		$\displaystyle\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)+3c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}].$

The second inequality is guaranteed for example by choosing $N_{0}$ large enough so that $N\geq N_{0}$ implies

D_{\mu}^{-2}(\log N)^{6}\geq\hskip 0.9pte^{\theta_{1}^{-1}}\qquad\text{and}\qquad c_{M}C_{3}^{-1}C_{M}^{-1/2}\bigl{(}\log[D_{\mu}^{-2}(\log N)^{6}\hskip 0.7pt]\bigr{)}^{2}\geq e^{\frac{1}{2}\theta_{1}^{-1}}.

This works due to the lower bound (5.2) on $H_{N}$ and because the function $f(x)=xe^{-\frac{1}{2}\theta_{1}(\log x)^{2}}$ achieves its maximum $e^{\frac{1}{2}\theta_{1}^{-1}}$ at $x=e^{\theta_{1}^{-1}}$ after which it decreases.

Combine the above with (5.9) on line (5.7) to get this upper bound:

(5.11)	$\displaystyle Q(S_{\hat{\tau}_{y}}\geq y)$	$\displaystyle\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)+2C_{3}e^{-c_{\tau}H_{N}^{1/2}y^{-1}}+3c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}]$
		$\displaystyle\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)+2C_{3}c_{\tau}^{-1}H_{N}^{-1/2}y+3c_{M}H_{N}^{-1/2}[2y+(\log H_{N})^{2}]$
		$\displaystyle\leq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)+C_{4}\hskip 0.55ptH_{N}^{-1/2}[y+(\log H_{N})^{2}]$

where $C_{4}=2C_{3}c_{\tau}^{-1}+6c_{M}$ . The second inequality above came from $xe^{-x}\leq e^{-1}$ for $x\geq 0$ . Put (5.11) and (5.6) together to obtain the claim of the lemma. ∎

By adjusting a constant we can replace $\hat{\tau}_{y}$ with $\tau_{y}$ in the previous estimate.

Corollary 5.3.

Under the assumptions of Lemma 5.2, with $C_{10}=C_{0}+2c_{\tau}^{-1}$ ,

(5.12)

\displaystyle\mathbb{P}(S_{\tau_{y}}\geq y)\geq\tfrac{1}{2}\Bigl{[}1-C_{10}H_{N}^{-\frac{1}{2}}\big{(}y+(\log H_{N})^{2}\big{)}-\frac{2}{\theta_{1}y}\log(e^{\theta_{1}}C_{M}H_{N}+1)\Bigr{]}

Proof.

The assumption $y_{0}\leq y\leq H_{N}^{1/2}$ implies that Lemma 5.1 applies to give

(5.13)

\mathbb{P}(\tau_{y}>H_{N})\leq e^{-c_{\tau}H_{N}y^{-2}}\leq e^{-c_{\tau}H_{N}^{1/2}y^{-1}}\leq c_{\tau}^{-1}H_{N}^{-1/2}y.

The claim then comes from Lemma 5.2 and $\mathbb{P}(S_{\tau_{y}}\geq y)\geq\mathbb{P}(S_{\hat{\tau}_{y}}\geq y)-\mathbb{P}(\tau_{y}>H_{N}).$ ∎

For $w>0$ truncate:

\displaystyle\widehat{X}^{N,w}_{i}=X^{N}_{i}\mathbf{1}_{\{X^{N}_{i}\geq-w\}}-w\mathbf{1}_{\{X^{N}_{i}<-w\}}\qquad\text{and}\qquad\widehat{S}^{N,w}_{n}=\sum_{i=1}^{n}\widehat{X}^{N,w}_{i}.

Define

\displaystyle t_{y}=\inf\{m\geq 1:|\widehat{S}^{N,w}_{m}|\geq y\}.

We transfer bound (5.12) to the truncated walk $\widehat{S}$ . The reason is that the proof of the forthcoming Lemma 5.5 is easier for the truncated RW.

Corollary 5.4.

Under the assumptions of Lemma 5.2, with $C_{11}=C_{0}+4c_{\tau}^{-1}$ ,

\displaystyle\mathbb{P}(\widehat{S}^{N,w}_{t_{y}}\geq y)\geq\tfrac{1}{2}\Bigl{[}1-C_{11}H_{N}^{-\frac{1}{2}}\big{(}y+(\log H_{N})^{2}\big{)}-\frac{2}{\theta_{1}y}\log(e^{\theta_{1}}C_{M}H_{N}+1)-H_{N}C_{M}e^{-\theta_{1}w}\Bigr{]}.

Proof.

Note that

(5.14)			$\displaystyle\mathbb{P}\big{(}\widehat{S}^{N,w}_{m}\neq S^{N}_{m}\ \text{ for some $1\leq m\leq H_{N}$}\big{)}=\mathbb{P}\big{(}\widehat{X}^{N,w}_{i}\neq X^{N}_{i}\quad\text{for some $1\leq i\leq H_{N}$}\big{)}$
		$\displaystyle=\mathbb{P}\big{(}\inf_{1\leq i\leq H_{N}}X^{N}_{i}<-w\big{)}\leq H_{N}C_{M}e^{-\theta_{1}w}.$

Moreover,

	$\displaystyle\mathbb{P}(\widehat{S}^{N,w}_{t_{y}}\geq y)$	$\displaystyle\geq\mathbb{P}(S^{N}_{\tau_{y}}\geq y,\,\tau_{y}\leq H_{N},\,\widehat{S}^{N,w}_{m}=S^{N}_{m}\quad\text{for all $1\leq m\leq H_{N}$})$
		$\displaystyle\geq\mathbb{P}(S^{N}_{\tau_{y}}\geq y)-\mathbb{P}(\tau_{y}>H_{N})-\mathbb{P}(\widehat{S}^{N,w}_{m}\neq S^{N}_{m}\quad\text{for some $1\leq m\leq H_{N}$})$
(5.15)			$\displaystyle\geq\mathbb{P}(S^{N}_{\tau_{y}}\geq y)-c_{\tau}^{-1}H_{N}^{-1/2}y-H_{N}C_{M}e^{-\theta_{1}w},$

where we used (5.14) and (5.13). Combine the above with (5.12) to obtain the result. ∎

We turn to the main argument of the proof of Theorem 2.2, that is, to show that the probability of the random walk $\widehat{S}_{m}$ to hit the level $x$ before hitting the level $-\varepsilon H^{1/2}$ is close to $x|\mu|$ . This gives rise to the error term in (2.4). We sketch the reasoning.

Let us try to hit the level $x>0$ starting from the origin. By Corollary 5.4 there is a probability $\approx 1/2$ to hit $x$ before hitting $-x$ . Suppose we failed and hit $-x$ first. We have another chance to hit $x$ by going $2x$ upward from the level $-x$ . By Corollary 5.4 the probability of going $2x$ up to the level $x$ before going $2x$ down to the level $-4x$ is $\approx 1/2$ . We continue this way until we either hit the level $x$ or the level $-\varepsilon H_{N}^{1/2}$ . How many trials to hit $x$ do we have before we hit $-\varepsilon H_{N}^{1/2}$ ? Approximately $K=\log_{2}(x^{-1}\varepsilon H_{N}^{1/2})$ . The trials are independent and so the probability of hitting the level $-\varepsilon H_{N}^{1/2}$ before hitting the level $x$ is $\approx 2^{-K}=Cx|\mu|$ , which is what we seek.

We introduce the notation to make the sketch precise. See Figure 5.1 for an illustration.

Define $K=\lfloor{\log_{2}({x}^{-1}(\log N)^{-1}H_{N}^{1/2})}\rfloor-2$ . For $i\geq 0$ set $L_{i}=2^{i+2}-3$ . Inductively these satisfy $L_{0}=1$ and $L_{i}=2L_{i-1}+3$ . Furthermore,

\displaystyle xL_{K}\leq(\log N)^{-1}H_{N}^{1/2}.

Define the stopping times

	$\displaystyle T_{0}$	$\displaystyle=\inf\{n:\|\widehat{S}^{N,x}_{n}\|\geq xL_{0}\}$
	$\displaystyle\text{and }\quad T_{i}$	$\displaystyle=\inf\{n\geq T_{i-1}:\widehat{S}^{N,x}_{n}\leq-xL_{i}\text{ or }\widehat{S}^{N,x}_{n}\geq x\}.$

Note that $T_{i}=T_{i-1}$ is possible.

Lemma 5.5.

There exist finite constants $C_{12}$ and $N_{0}$ such that for $N\geq N_{0}$ and $x\geq(\log N)^{2}$ ,

\displaystyle\mathbb{P}\bigl{(}\,\max_{1\leq m\leq T_{K}}\widehat{S}^{N,x}_{m}<x\bigr{)}\leq C_{12}\hskip 0.9ptx\hskip 0.9pt(\log N)H_{N}^{-1/2},

where

\displaystyle C_{12}=4\exp\bigl{\{}4(C_{0}+4c_{\tau}^{-1})(1+D_{\mu})+8\theta_{1}^{-1}\bigl{(}1+\log(e^{\theta_{1}}C_{M}+1)\bigr{)}+4C_{M}\bigr{\}}

and $C_{0}$ in the expression above is from (5.4).

Proof.

Since $C_{0}\geq 2$ , we have $C_{12}\geq 4e^{8}\geq 2^{10}$ . Then we can assume that $x\leq 2^{-10}(\log N)^{-1}H_{N}^{1/2}$ , for otherwise the bound on the probability is $>1$ . This guarantees that $K\geq 8$ . It also implies that unless $|\mu|\leq 2^{-10}(\log N)^{-3}$ , the result is trivial.

Since $\widehat{X}^{N,x}_{i}\geq-x$ ,

(5.16)

\{\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i}\}=\{-x(L_{i}+1)<\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i}\}

and

\displaystyle\big{\{}\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i},\widehat{S}^{N,x}_{T_{i+1}}\leq-xL_{i+1}\big{\}}\subseteq\{T_{i}<T_{i+1}\}.

Note that

(5.17)

\displaystyle E\equiv\Big{\{}\max_{1\leq m\leq T_{K}}\widehat{S}^{N,x}_{m}<x\Big{\}}\subseteq\bigcap_{1\leq i\leq K}\{\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i}\}.

Due to (5.16)

(5.18)			$\displaystyle\mathbb{P}\big{(}\widehat{S}^{N,x}_{T_{0}}\leq-xL_{0},...,\widehat{S}^{N,x}_{T_{i-1}}\leq-xL_{i-1},\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i}\big{)}$
			$\displaystyle=\mathbb{P}\big{(}\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i}\|\widehat{S}^{N,x}_{T_{0}}\leq-xL_{0},...,\widehat{S}^{N,x}_{T_{i-1}}\leq-xL_{i-1}\big{)}$
			$\displaystyle\qquad\qquad\cdot\;\mathbb{P}\big{(}\widehat{S}^{N,x}_{T_{0}}\leq-xL_{0},...,\widehat{S}^{N,x}_{T_{i-1}}\leq-xL_{i-1}\big{)}$
			$\displaystyle\leq\mathbb{P}\big{(}\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i}\|\widehat{S}^{N,x}_{T_{0}}\leq-xL_{0},...,\widehat{S}^{N,x}_{T_{i-1}}=-x(L_{i-1}+1)\big{)}$
			$\displaystyle\qquad\qquad\cdot\;\mathbb{P}\big{(}\widehat{S}^{N,x}_{T_{0}}\leq-xL_{0},...,\widehat{S}^{N,x}_{T_{i-1}}\leq-xL_{i-1}\big{)}$
			$\displaystyle=\mathbb{P}\big{(}\widehat{S}^{N,x}_{t_{x(L_{i-1}+2)}}\leq-x(L_{i-1}+2)\big{)}\mathbb{P}\big{(}\widehat{S}^{N,x}_{T_{0}}\leq-xL_{0},...,\widehat{S}^{N,x}_{T_{i-1}}\leq-xL_{i-1}\big{)}.$

The last equality used the definition of the stopping time $t_{y}$ , the definition of $L_{i}$ , and the Markov property. For $1\leq i\leq K$ define the events

\displaystyle A^{N}_{i}=\{\widehat{S}^{N,x}_{t_{x(L_{i-1}+2)}}\leq-x(L_{i-1}+2)\}.

Applying (5.18) to (5.17) repeatedly,

\displaystyle\mathbb{P}(E)\leq\mathbb{P}\Big{(}\bigcap_{1\leq i\leq K}\{\widehat{S}^{N,x}_{T_{i}}\leq-xL_{i}\}\Big{)}\leq\prod_{1\leq i\leq K}\mathbb{P}(A^{N}_{i}).

Let $x\geq(\log N)^{2}$ . Recall that by (5.2), $(\log H_{N})^{2}H_{N}^{-1/2}\leq D_{\mu}(\log N)^{-1}$ and $H_{N}\leq N$ . Apply Corollary 5.4 with $w=x$ and $y_{i}=x(L_{i-1}+2)\in[x,(\log N)^{-1}H_{N}^{1/2}]$ for $i=1,\dotsc,K$ and $N\geq N_{0}$ to get this estimate:

	$\displaystyle\mathbb{P}(A^{N}_{i})$	$\displaystyle\leq\tfrac{1}{2}\Bigl{[}1+C_{11}H_{N}^{-\frac{1}{2}}\big{(}y_{i}+(\log H_{N})^{2}\big{)}+\frac{2}{\theta_{1}y_{i}}\log(e^{\theta_{1}}C_{M}H_{N}+1)+H_{N}C_{M}e^{-\theta_{1}x}\Bigr{]}$
		$\displaystyle\leq\tfrac{1}{2}\Bigl{[}1+C_{11}(1+D_{\mu})(\log N)^{-1}+\frac{2\log(e^{\theta_{1}}C_{M}N+1)}{\theta_{1}(\log N)^{2}}+C_{M}N^{1-\theta_{1}(\log N)^{2}}\Bigr{]}$
		$\displaystyle\leq\tfrac{1}{2}\bigl{[}1+C_{A}(\log N)^{-1}],$

where we set

\displaystyle C_{A}=C_{11}(1+D_{\mu})+2\theta_{1}^{-1}\bigl{(}1+\log(e^{\theta_{1}}C_{M}+1)\bigr{)}+C_{M}

and if necessary we increase $N_{0}$ further so that $N^{1-\theta_{1}(\log N)^{2}}\leq(\log N)^{-1}$ for $N\geq N_{0}$ .

Continue with the above estimate,

	$\displaystyle\mathbb{P}(E)$	$\displaystyle\leq\prod_{i=1}^{K}\mathbb{P}(A_{i}^{N})\leq\Big{(}\tfrac{1}{2}\bigl{[}1+C_{A}(\log N)^{-1}]\Big{)}^{K}$
		$\displaystyle=\Big{(}\tfrac{1}{2}[1+C_{A}(\log N)^{-1}]\Big{)}^{\lfloor{\log_{2}({x}^{-1}(\log N)^{-1}H_{N}^{1/2})}\rfloor-2}$
		$\displaystyle\leq 4x(\log N)H_{N}^{-1/2}\hskip 0.55pt[1+C_{A}(\log N)^{-1}]^{\log_{2}\!N}$
		$\displaystyle\leq 4e^{4C_{\!A}}x(\log N)H_{N}^{-1/2}=4e^{4C_{\!A}}x(\log N)(\|\mu\|\vee N^{-1/2}),$

where we used $\log_{2}\!N=\frac{\log N}{\log 2}\leq 4\log N$ . ∎

We are ready to prove Theorem 2.2. By Lemma 5.5, by the time $\widehat{S}$ hits the level $(\log N)^{-1}H_{N}^{1/2}$ , with high probability it has hit level $x$ as well. It remains to verify the two points below.

(i)

$\widehat{S}$ is close to $S$ on the time interval $[1,N]$ . This follows from a union bound and the exponential tail of $X^{N}_{1}$ .
(ii)

With high probability by time $N$ we hit the boundary of the cylinder of width $(\log N)^{-1}H_{N}^{1/2}$ . This follows from Lemma 5.1.

Figure 5.1. By the time the random walk

\widehat{S}^{N}

exits the cylinder of radius

(\log N)^{-1}H_{N}^{1/2}

it has had about

K

independent opportunities to hit the level

x

, each with probability close to

1/2

Proof of Theorem 2.2.

Consider $x\geq(\log N)^{2}$ . Observe that

\displaystyle\Big{\{}\max_{1\leq m\leq N}|\widehat{S}^{N,x}_{m}|\geq(\log N)^{-1}H_{N}^{1/2},\max_{1\leq m\leq T_{K}}\widehat{S}^{N,x}_{m}>x\Big{\}}\subseteq\Big{\{}\max_{1\leq m\leq N}\widehat{S}^{N,x}_{m}\geq x\Big{\}}.

Indeed, on the event $\max_{1\leq m\leq N}|\widehat{S}^{N,x}_{m}|\geq(\log N)^{-1}H_{N}^{1/2}{\geq xL_{K}}$ we have $T_{K}\leq N$ .

Next,

(5.19)		$\displaystyle\mathbb{P}\big{(}\widehat{S}^{N,x}_{m}\neq S^{N}_{m}\quad\text{for some $1\leq m\leq N$}\big{)}$	$\displaystyle=\mathbb{P}\big{(}X^{N}_{i}<-x\quad\text{for some $1\leq i\leq N$}\big{)}$
		$\displaystyle\leq C_{M}Ne^{-\theta_{1}x}\leq C_{M}Ne^{-\theta_{1}(\log N)^{2}}.$

By Lemma 5.1, (5.19) and Lemma 5.5,

	$\displaystyle\mathbb{P}\bigl{(}\,\max_{1\leq m\leq N}\widehat{S}^{N,x}_{m}\geq x\bigr{)}\geq 1-\mathbb{P}\bigl{(}\,\max_{1\leq m\leq N}\|\widehat{S}^{N,x}_{m}\|<(\log N)^{-1}H_{N}^{1/2}\bigr{)}-\mathbb{P}\bigl{(}\,\max_{1\leq m\leq T_{K}}\widehat{S}^{N,x}_{m}\leq x\bigr{)}$
	$\displaystyle\geq 1-\Big{[}\mathbb{P}\bigl{(}\,\max_{1\leq m\leq N}\|S^{N}_{m}\|<(\log N)^{-1}H_{N}^{1/2}\bigr{)}+\mathbb{P}\big{(}\widehat{S}^{N,x}_{m}\neq S^{N}_{m}\quad\text{for some $1\leq m\leq N$}\big{)}\Big{]}$
	$\displaystyle\qquad\qquad-\mathbb{P}\bigl{(}\,\max_{1\leq m\leq T_{K}}\widehat{S}^{N,x}_{m}\leq x\bigr{)}$
	$\displaystyle=1-\Big{[}\mathbb{P}\bigl{(}\tau_{(\log N)^{-1}H_{N}^{1/2}}>N\bigr{)}+\mathbb{P}\big{(}\widehat{S}^{N,x}_{m}\neq S^{N}_{m}\quad\text{for some $1\leq m\leq N$}\big{)}\Big{]}$
	$\displaystyle\qquad\qquad-\mathbb{P}\bigl{(}\,\max_{1\leq m\leq T_{K}}\widehat{S}^{N,x}_{m}<x\bigr{)}$
	$\displaystyle\geq 1-\big{[}2e^{-c_{\tau}N(\log N)^{2}H_{N}^{-1}}+C_{M}Ne^{-\theta_{1}(\log N)^{2}}\big{]}-C_{12}\hskip 0.55ptx\hskip 0.55pt(\log N)H_{N}^{-1/2}$
	$\displaystyle\geq 1-2e^{-c_{\tau}(\log N)^{2}}-C_{M}Ne^{-\theta_{1}(\log N)^{2}}-C_{12}\hskip 0.55ptx\hskip 0.55pt(\log N)H_{N}^{-1/2}$
	$\displaystyle\geq 1-(C_{12}+2)x(\log N)H_{N}^{-1/2}.$

To get the inequalities above for $N\geq N_{0}$ we increase $N_{0}$ if necessary so that $N\geq N_{0}$ guarantees $(\log N)^{-1}H_{N}^{1/2}\geq y_{0}$ to apply Lemma 5.1, and furthermore so that $2e^{-c_{\tau}(\log N)^{2}}\vee C_{M}Ne^{-\theta_{1}(\log N)^{2}}\leq(\log N)^{3}N^{-1/2}$ to get the last inequality.

Now the final inequality:

	$\displaystyle\mathbb{P}\bigl{(}\max_{1\leq m\leq N}S^{N}_{m}\geq x\bigr{)}$	$\displaystyle\geq\mathbb{P}\bigl{(}\max_{1\leq m\leq N}\widehat{S}^{N,x}_{m}\geq x\bigr{)}-\mathbb{P}\bigl{(}\widehat{S}^{N,x}_{m}\neq S^{N}_{m}\quad\text{for some $1\leq m\leq N$}\bigr{)}$
		$\displaystyle\geq 1-(C_{12}+2)x(\log N)H_{N}^{-1/2}-C_{M}Ne^{-\theta_{1}(\log N)^{2}}$
		$\displaystyle\geq 1-(C_{12}+3)x(\log N)(\|\mu\|\vee N^{-1/2}).$

Theorem 2.2 has been proved. ∎

References

[1] Chinmoy Bhattacharjee and Larry Goldstein. On strong embeddings by Stein’s method. Electron. J. Probab., 21:Paper No. 15, 30, 2016.
[2] Ofer Busani and Timo Seppäläinen. Non-existence of bi-infinite polymer Gibbs measures in the inverse-gamma polymer model. 2020. arXiv:2010.11279.
[3] Sourav Chatterjee. A new approach to strong embeddings. Probab. Theory Related Fields, 152(1-2):231–264, 2012.
[4] Rick Durrett. Probability: theory and examples. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, fourth edition, 2010.
[5] Wai-Tong (Louis) Fan and Timo Seppäläinen. Joint distribution of Busemann functions in the exactly solvable corner growth model. 2018. arXiv:1808.09069.
[6] William Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971.
[7] David F. Fraser. The rate of convergence of a random walk to Brownian motion. Ann. Probability, 1:699–701, 1973.
[8] Ioannis Karatzas and Steven E. Shreve. Brownian motion and stochastic calculus, volume 113 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1991.
[9] J. Komlós, P. Major, and G. Tusnády. An approximation of partial sums of independent RV’s, and the sample DF. II. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 34(1):33–58, 1976.
[10] Manjunath Krishnapur. One idea and two proofs of the KMT theorems. 2020. arXiv:2008.03287.
[11] A. I. Sakhanenko. Rate of convergence in the invariance principle for variables with exponential moments that are not identically distributed. In Limit theorems for sums of random variables, volume 3 of Trudy Inst. Mat., pages 4–49. “Nauka” Sibirsk. Otdel., Novosibirsk, 1984.
[12] Stanley Sawyer. Rates of convergence for some functionals in probability. Ann. Math. Statist., 43:273–284, 1972.

	$\displaystyle\Big{(}1+2C_{M}c_{M}^{2}\mu^{2}+\tfrac{4}{3}C_{M}c_{M}^{3}\|\mu\|^{3}\Big{)}^{\tfrac{1}{2}\mu^{-2}}$	$\displaystyle\leq e^{C_{M}c_{M}^{2}(1+\frac{2}{3}c_{M}\|\mu\|)}\leq e^{2C_{M}c_{M}^{2}},$
	$\displaystyle\Big{(}1-c_{M}\mu^{2}-C_{M}c_{M}^{3}\|\mu\|^{3}\Big{)}^{-\mu^{-2}}$	$\displaystyle\leq\Big{(}1+2c_{M}\mu^{2}\bigl{(}1+C_{M}c_{M}^{3}\|\mu\|\bigr{)}\Big{)}^{\mu^{-2}}\leq e^{2c_{M}(1+C_{M}c_{M}^{3}\|\mu\|)}\leq e^{4c_{M}},$