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

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.

The order of magnitude of the sum of the first displayed series is indeed $$\asymp n^2$$ when the random walk is symmetric.
Let $$$$M_k:=\max_{0\le j\le k}X_j.$$$$ Then, by the reflection principle (see e.g. page 4) and the Berry--Esseen inequality, for any real $$z>0$$ $$$$P(M_k\ge n)\le2P(X_k\ge n)\le2G(n/\sqrt k)+c/\sqrt k \le3G(z)$$$$ if $$n/\sqrt k\ge z$$ and $$c/\sqrt k\le G(z)$$, that is, if
$$$$c^2/G(z)^2=:a\le k\le n^2/z^2, \tag{1}$$$$ 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 $$$$P(\tau_n whence $$P(\tau_n\ge k)\ge1/2$$. So, $$$$\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.$$$$ You already noted that $$\sum_{k=0}^\infty P(\tau_n\ge k)^2\le n^2$$. So, $$$$s:=\sum_{k=0}^\infty P(\tau_n\ge k)^2\asymp n^2,$$$$ 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|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, $$$$s\le\sum_{0\le k\le1+2n/\mu}1^2 +\sum_{k\ge2n/\mu}(C/k)^2\asymp n.$$$$ On the other hand, $$$$s\ge\sum_{0\le k\le n}1^2>n.$$$$ So indeed, if the walk is not symmetric, then $$$$s\asymp n.$$$$