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

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.