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](https://mathoverflow.net/questions/319439/fourier-transform-of-a-simple-random-walk) question, so the objective is essentially to see if something interesting about a random walk can be derived via these Fourier methods.



Distribution of first time a 1D random walk hits n or -n
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](https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=2ahUKEwj6ycu949ngAhUl_IMKHZqWCK8QFjAAegQIChAC&url=http%3A%2F%2Fcgm.cs.mcgill.ca%2F~breed%2FMATH671%2Flecture2corrected.pdf&usg=AOvVaw2AWnEgYglDpWEJX383zQ14)) and the [Berry--Esseen inequality](https://en.wikipedia.org/wiki/Berry%E2%80%93Esseen_theorem), 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}


