Distribution of first time a 1D random walk hits n or -n

Question

Let $(\omega_1, \omega_2, \ldots)$ be iid in $\{-1, 1\}$ and $X_k = \sum_{i=1}^k \omega_i$ be a simple one-dimensional random walk.

Let $\tau_n = \min \{i\in\mathbb{N}: |X_i|=n\}$ be the first time the random walk is $n$ steps from the origin. What I am interested in is the distribution of this hitting time -- in particular, I want to know how the following quantity grows with $n$:

$$\sum_{k=0}^\infty (\mathbb{P}(\tau_n \geq k))^2$$

It is easy to see that it is bounded above by $n^2$, by rewriting it as $$\mathbb{E}\left[\sum_{k=0}^{\tau_n} \mathbb{P}(\tau_n \geq k)\right] \leq \mathbb{E}[\tau_n]$$

However, this is only barely not good enough for me -- what I really need to know is that this is $o(n^2)$, not just $O(n^2)$. (Or, I suppose, knowing that it isn't $o(n^2)$, though that would be a bit boring.)

Another related, and I assume easier, question is this: How many moments does $\tau_n$ have, and what are they?

This question is motivated by this question, so the objective is essentially to see if something interesting about a random walk can be derived via these Fourier methods.

Answer 1

The order of magnitude of the sum of the first displayed series is indeed $\asymp n^2$ when the random walk is symmetric.
Let \begin{equation} M_k:=\max_{0\le j\le k}X_j. \end{equation} Then, by the reflection principle (see e.g. page 4) and the Berry--Esseen inequality, for any real $z>0$ \begin{equation} P(M_k\ge n)\le2P(X_k\ge n)\le2G(n/\sqrt k)+c/\sqrt k \le3G(z) \end{equation} if $n/\sqrt k\ge z$ and $c/\sqrt k\le G(z)$, that is, if
\begin{equation} c^2/G(z)^2=:a\le k\le n^2/z^2, \tag{1} \end{equation} where $G:=1-\Phi$, $\Phi$ is the standard normal cumulative distribution function, and $c>0$ is a universal real constant (one may take $c=1$). Letting now $z$ be such that $G(z)=1/12$, for $k$ as in (1) we have \begin{equation} P(\tau_n<k)\le2P(M_k\ge n)\le6G(z)=1/2, \end{equation} whence $P(\tau_n\ge k)\ge1/2$. So, \begin{equation} \sum_{k=0}^\infty P(\tau_n\ge k)^2 \ge \sum_{a\le k\le n^2/z^2} (1/2)^2 \asymp n^2. \end{equation} You already noted that $\sum_{k=0}^\infty P(\tau_n\ge k)^2\le n^2$. So, \begin{equation} s:=\sum_{k=0}^\infty P(\tau_n\ge k)^2\asymp n^2, \end{equation} as claimed.

---

If the walk is not symmetric, then the sum $s$ of the above series is $\asymp n$. Indeed, without loss of generality $p:=P(\omega_1=1)>1/2$. Then $\mu:=E\omega_1=p-q>0$ and $\sigma^2:=Var\,\omega_1<1$, where $q:=1-p$. So, for $k\ge2n/\mu$ \begin{align} P(\tau_n\ge k+1)&\le P(|X_k|<n) \\ &\le P(X_k-k\mu<n-k\mu) \\ &\le P(X_k-k\mu<-k\mu/2) \\ &\le P(|X_k-k\mu|>k\mu/2)\le C/k, \end{align} where $C:=4\sigma^2/\mu^2<4/\mu^2$; the last displayed inequality is an instance of the Chebyshev inequality. So, \begin{equation} s\le\sum_{0\le k\le1+2n/\mu}1^2 +\sum_{k\ge2n/\mu}(C/k)^2\asymp n. \end{equation} On the other hand, \begin{equation} s\ge\sum_{0\le k\le n}1^2>n. \end{equation} So indeed, if the walk is not symmetric, then \begin{equation} s\asymp n. \end{equation}