Let $\{X_i\}_{i=1}^\infty$ be a sequence of discerete i.i.d. random variables with identical distributions such that:
- $E(X_i)=0 $
- $0<V(X_i)<\infty$
- $P(|X_i|>x)\leq 2^{1-x} $
We consider the random walk $S_t$ defined at time $t$ by $S_t=\sum_{i=1}^t X_i$, and for each $n\geq 0$ we define a stopping time $\tau_n=\min \{t\in \mathbb{N} \mid |S_t|\geq n \} $.
What is the expectation $E(\tau_n)$? More specifically, does it hold that $E(\tau_n)\in \mathcal{O}(n^2)$? If $X_i$ were to be such that $P(X_i=a)=P(X_i=-a)=\frac{1}{2}$ then we can get from optional stopping theorem that $E(\tau_n)=(\frac{n}{a})^2$. But how would one go about computing the expected stopping time if the steps are possibly unbounded? Or even is the steps are bounded, but the exact distribution is not known?
Best Answer
As long as the increments are bounded, you can still use the Optional Stopping Theorem to get the order of $\tau_n$ even without referencing the precise distribution of the steps. The logic is similar to the ordinary random walk example you cited.
Let $C := \mathbb E[X_i^2]$, which we know to be finite; then $M_t := S_t^2 - Ct$ is a martingale, since \begin{align*} & \mathbb E \left[S_{t+1}^2 - C(t+1) \mid \mathscr F_{t} \right] \\ =\ & \mathbb E \left[S_t^2 + 2 S_t X_{t+1} + X_{t+1}^2 - C(t+1) \mid \mathscr F_t \right] \\ =\ & S_t^2 + 2S_t \mathbb E\left[X_{t+1} \mid \mathscr F_t \right] + \mathbb E \left[ X_{t+1}^2 \mid \mathscr F_t \right] - C(t+1) \\ =\ & S_t^2 + 0 + C - C(t+1) = S_t^2 - Ct. \end{align*}
You can argue that $\tau_n$ is geometrically dominated (hence integrable), and since the increments of $M_t$ are bounded (to be precise, the increments of $M_{t \wedge \tau_n}$ are bounded), it follows that $\mathbb E[S_{\tau_n}^2 - C \tau_n] = 0 \implies \mathbb E[\tau_n] = \mathbb E[S_n^2] / C$. From here, note that $S_{\tau_n}^2$ is at least $n^2$ and is at most $(n+k)^2$, where $k$ is the bound on the increment $X_i$.
I'm not immediately sure what to do with the case where the increments are geometrically dominated but not bounded, since the OST does not apply for free in this case. I suspect the result holds anyway, but I'd have to think more about it.
Editing to record for posterity: I didn't see this at the time when I wrote the original answer, but after some reflection (and helpful comments by the OP), this bounded-increment solution is enough to achieve the desired result even in the unbounded-increment case. If we consider a modified process $S_t'$ whose increments are $$X_t' := \begin{cases} X_t, & -2n \leq X_t \leq 2n \\ -2n-1, & X_t < -2n \\ 2n+1, & X_t > 2n\end{cases}$$ then $\tau_n$ and $\tau_n'$ have the same distribution. Since the increments of $S_n'$ are bounded, the above comments apply, and we have the needed result.