Order of magnitude of the hitting time of a random walk

Question

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

Answer 1

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*}

Answer 2

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

Answer 3

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*}

Answer 4

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