# Order of magnitude of the hitting time of a random walk

Consider the random walk on $\mathbb R$ with $X_0 = a >0$ and $$X_{n+1} = X_n + U_n,$$ where $U_0, U_1, U_2,\ldots$ is an i.i.d. sequence of uniform random numbers in $[-1,1]$.

How does the hitting time to $(-\infty,0]$; i.e. $$\tau_a:=\min\{n : X_n\leq 0\}$$ behave for large $a$?

In need to prove $\tau_a$ is of order $a^2$; i.e. for any $\epsilon>0$ there are constants $C$ and $C'$ such that for large enough $a$ we have

$$\mathbb P[Ca^2<\tau_a<C'a^2]>1-\epsilon.$$

• The hitting time has a heavy tail. If it goes the wrong way in the first $a^2$ time steps, then you can expect to wait $a^2$ steps more. So your $r_a$ should be the same size as your $m_a$. That is to say, it only really makes sense to look for bounds of the form $\mathbb P(\tau_a > m_a) < \epsilon$. – Anthony Quas Dec 18 '15 at 0:59
• @AnthonyQuas Shouldn't the bound be of the form $\mathbb{P}(\tau_a \le m_a)<\epsilon$? The series bounding the other tail is divergent. – S.B. Dec 18 '15 at 4:17
• @AnthonyQuas Can't understand your point. Since $\tau_a<\infty$ a.s., $\tau_a$ has some unknown distribution on the natural numbers. The numbers $m_a$ and $r_a$ exist anyway. – Ali Khezeli Dec 18 '15 at 5:09

We assume that $U$ is centered, square integrable and we denote by $\sigma^2>0$ its variance. Given $a\geq 0$, I denote by $\tau_a$ the hitting time of $[a,+\infty)$ by $X$ starting from $X_0=0$ (this formulation is of course equivalent but more natural when using the following method). Fix $\varepsilon>0$ and let us prove that there exists $C,C'$ such that, for all $a$ large enough, \begin{align*} \mathbb{P}(C a^2< \tau_a \leq C' a^2+1)\geq 1-\varepsilon. \end{align*} We will use Donsker invariance principle, although there is no need to carefully check the law of hitting times for the Brownian motion, nore to quantify the speed of convergence to the Brownian motion.

Let $B$ be a standard one dimensional Brownian motion and choose $C>0$ and $C'>C$ such that \begin{align*} \mathbb{P}(C < T_{1/\sigma}\leq C')\geq 1-\varepsilon/3, \end{align*} where $T_{1/\sigma}$ is the hitting time of $1/\sigma$ by the Brownian motion $B$.

Let $(\varphi_k)_{k\in\mathbb{N}}$ (resp. $(\psi_k)_{k\in\mathbb{N}}$) be an increasing (resp. bounded decreasing) sequence of continuous functions converging pointwisely to $\mathbf{1}_{\cdot < 1/\sigma}$. We define the continous function $f_k$ and $g_k$ on $C([0,\infty[)$ (with the topology defined p. 60 of Karatzas-Shreve) by \begin{align*} f_k(\omega)=\varphi_k(\max_{t\in[0,C]} \omega_t) \text{ and }g_k(\omega)=\psi_k(\max_{t\in[0,C']} \omega_t). \end{align*} We thus have, almost surely, \begin{align*} \mathbf{1}_{C < T_{1/\sigma}\leq C'}=\lim_{k\rightarrow\infty} f_k(B)-g_k(B). \end{align*} Hence, by the dominated convergence theorem, we can choose $k_0$ such that \begin{align*} \mathbb{E}(f_{k_0}(B)-g_{k_0}(B))\geq 1-2\varepsilon/3. \end{align*}

For any $n\in\mathbb{N}$, let us define the affine process starting from $0$ and such that \begin{align*} X_t^{(n)}=\frac{1}{\sigma \sqrt{n}}Y_{nt},\text{ with } Y_t=\sum_{n=1}^{\lfloor t\rfloor}U_n+(t-\lfloor t\rfloor)U_{\lfloor t\rfloor+1}. \end{align*} Denoting by $T^{(n)}_{1/\sigma}$ the first hitting time of $1/\sigma$ by $X^{(n)}$, it is clear that $a^2 T^{(a^2)}_{1/\sigma}\leq \tau_a < a^2 T^{(a^2)}_{1/\sigma}+1$. Hence \begin{align*} \mathbb{P}(C a^2< \tau_a \leq C' a^2+1)&\geq \mathbb{P}(C a^2< a^2 T^{(a^2)}_{1/\sigma}\leq C' a^2)\\ &= \mathbb{P}(C < T^{(a^2)}_{1/\sigma}\leq C')\\ &\geq \mathbb{E}(f_{k_0}(X^{a^2})-g_{k_0}(X^{a^2})) \end{align*} We know that the law of $(X_t^{(n)})_{t\geq 0}$ converges weakly to the Brownian motion on $C([0,\infty))$ when $n\rightarrow\infty$ (see for instance Theorem~4.20 p.71 in Karatzas-Shreve), hence \begin{align*} \mathbb{E}(f_{k_0}(X^{a^2})-g_{k_0}(X^{a^2}))\xrightarrow[a\rightarrow\infty]{} \mathbb{E}(f_{k_0}(B)-g_{k_0}(B))\geq 1-2\varepsilon/3. \end{align*} As a consequence, there exists $a_0$ such that, for all $a\geq a_0$, \begin{align*} \mathbb{P}(C a^2< \tau_a \leq C' a^2+1)\geq 1-\varepsilon. \end{align*}

After rescaling (the variance is $1/3$ instead of $1$), the random walk approaches Brownian motion. The first hitting time of $c$ for Brownian motion follows a Lévy distribution ($\textrm{Levy}(0,c^2)$). The cumulative distribution function is known explicitly as are the asymptotics. Note that $c = \sqrt{3} a$.

The probability that the hitting time is greater than $t$ is the same as the probability that a Brownian motion has not reached $0$ from $c/\sqrt{t}$ at time $1$, which is $2\Phi(c/\sqrt{t})-1$ by reflection. When $c/\sqrt{t}$ is small, this is approximately $2\phi(0)(c/\sqrt{t}) = \sqrt{\frac{2 c^2}{\pi t}}$. So, to reduce the chance of not hitting $0$ by time $t$ to some small $\varepsilon$, you need $t$ to be greater than about $2 c^2/(\pi \varepsilon^2)$ or $6a^2/(\pi \varepsilon^2)$.

• Same works for a lower bound on the hitting time. But we need an approximation of the error between the random walk and a Brownian motion. Correct? – Ali Khezeli Dec 18 '15 at 13:43
• Yes, this heuristic alone isn't rigorous. There are other arguments that it suggests, though. I'll try to post some of those later. – Douglas Zare Dec 22 '15 at 19:57
• The approximation you are looking for can be done using a version of an "almost sure invariance principle". ASIP basically says that you can enlarge your probability space and define there the random walk and a Brownian motion in a way that $S_{[nt]}-W_t$ is controlled almost surely. For the example you are mentioning, you can apply the Komlos-Major-Tsunady approximation. I think though that a direct proof without Brownian motion is easier. – user78465 Feb 22 '16 at 20:39

Here is another solution, hopefully easier to follow that the one I provided earlier (but unfortunately not shorter). It is less general, since it uses the fact that the random variables $U_i$ are symmetric and uniformly bounded by $1$. I hope it helps!

We denote by $\tau_a$ the hitting time of $a$ by $X$ starting from $0$. This formulation is of course equivalent to yours but is more natural with the following method, which mimics the proof of the reflection principle for Brownian motions.

First step (proof of a kind of reflection principle for random walks): we prove that, for all $n\geq 0$, $a\geq 0$, \begin{align*} \mathbb{P}(\tau_a\leq n)=\mathbb{P}(X_n > a)+\mathbb{P}(X_n\geq 2X_{\tau_a}-a). \end{align*} Indeed, for all $b\leq a$, \begin{align*} \mathbb{P}(\tau_a\leq n,\ X_n\leq b)&=\mathbb{P}(\tau_a\leq n,\ X_n-X_{\tau_a}\leq b-X_{\tau_a}). \end{align*} But, conditionally to $\tau_a\leq n$ and by the strong Markov property, $X_n-X_{\tau_a}$ is independent of both $\tau_a$ and $X_{\tau_a}$ and it has the same law as $X_{\tau_a}-X_n$ by symmetry of the $U_i$, hence \begin{align*} \mathbb{P}(\tau_a\leq n,\ X_n\leq b)&=\mathbb{P}(\tau_a\leq n,\ X_{\tau_a}-X_n\leq b-X_{\tau_a})\\ &=\mathbb{P}(\tau_a\leq n,\ X_{\tau_a}-X_n\leq b-X_{\tau_a})\\ &=\mathbb{P}(\tau_a\leq n,\ X_n\geq 2X_{\tau_a}- b)=\mathbb{P}(X_n\geq 2X_{\tau_a}- b), \end{align*} since $2X_{\tau_a}-b\geq 2 a-b\geq a$. Now \begin{align*} \mathbb{P}(\tau_a\leq n)&=\mathbb{P}(\tau_a\leq n,\ X_n>a)+\mathbb{P}(\tau_a\leq n,\ X_n\leq a)\\ &=\mathbb{P}(X_n>a)+\mathbb{P}(X_n\geq 2X_{\tau_a}-a). \end{align*}

Second step (conclusion using the CLT): Let $Y$ be a centred normalized Gaussian variable. We deduce from the first step and from the fact that $X_{\tau_a}\in[a,a+1]$ almost surely that \begin{align*} 2\mathbb{P}(X_n\geq a+2)\leq \mathbb{P}(\tau_a\leq n)\leq 2\mathbb{P}(X_n\geq a) \end{align*} and hence that \begin{align*} \mathbb{P}(|X_n|\geq a+2)\leq \mathbb{P}(\tau_a\leq n)\leq \mathbb{P}(|X_n|\geq a). \end{align*} Hence, for all $C'>0$, \begin{align*} \mathbb{P}(\tau_a\leq C' a^2)&\geq \mathbb{P}\left(\frac{|X_{C'a^2}|}{a\sqrt{C'}}\geq \frac{a+2}{a\sqrt{C'}}\right)\\ &\xrightarrow[a\rightarrow\infty]{} \mathbb{P}\left(|Y|\geq \frac{1}{\sqrt{C'}}\right) \end{align*} and \begin{align*} \mathbb{P}(\tau_a> C a^2)&\geq 1-\mathbb{P}\left(\frac{|X_{Ca^2}|}{a\sqrt{C}}\geq \frac{1}{\sqrt{C}}\right)\\ &\xrightarrow[a\rightarrow\infty]{} 1-\mathbb{P}\left(|Y|\geq \frac{1}{\sqrt{C}}\right). \end{align*} Choosing $C>0$ small enough and $C'>0$ big enough, we conclude that, for all $a$ large enough, \begin{align*} \mathbb{P}(C a^2<\tau_a\leq C' a^2)&\geq 1-\varepsilon. \end{align*}

Lemma 4.18 of the book Brownian Motion and Stochastic Calculus implies a lower bound on $\tau_a$ for arbitrary random walks with mean zero and a given variance. It results that there is a $\delta>0$ such that $\mathbb P[\tau_a <\delta a^2]<\epsilon$.