Finding the expected stopping time of random walk

Question

been stuck on this optional stopping theorem quesiton for some time. I feel like I'm heading in the right direction but I am not sure if I am right.

Problem

Consider a random walk $\left(S_{n}\right)_{n}$ with i.i.d. increments $$ X_{i}= \begin{cases}-1 & 1 / 2 \\ 0 & 1 / 4 \\ 1 & 1 / 4\end{cases} $$ Suppose $S_{0}=0$. Let $T=\inf \left\{n: S_{n}\text{ is either }100\text{ or }-10\right\}$.

• Find $E[T]$.
• Find $\mathbb{P}\left(S_{T}=100\right)$.

My attempt $$E[x_i]=(-1) \cdot \frac{1}{2}+(0) \cdot \frac{1}{4}+(1) \cdot \frac{1}{4} = -\frac{1}{4}$$

We need a martingale to use optional stopping theorem. Hence, I used: $$M_{n}=\sum^{n} x_{i}+\frac{n}{4}$$

I showed this a martingale. However I am stuck on how to move forward from here:

$$E\left[M_{T}\right]=E\left[\sum^{T} x_{i}+\frac{T}{4}\right]$$

$$E[T]=\frac{- E\left[S_{T}\right]}{4}$$

So would this mean $E[T] = -400$ or $40$ depending if $S_{n} = -100$ or $10$.

Answer 1

Let $\mathbb{E}_a T$ be this stopping time assuming our initial position was $a$. Then we have (in a manner similar to gambler's ruin) \begin{align*} \mathbb{E}_a T &= \frac{1}{2}(1 + \mathbb{E}_{a-1}T) + \frac{1}{4}(1 + \mathbb{E}_aT) + \frac{1}{4}(1 + \mathbb{E}_{a+1}T) \\ \implies \mathbb{E}_a T &= \frac{4}{3} + \frac{2}{3} \mathbb{E}_{a-1}T + \frac{1}{3} \mathbb{E}_{a+1}T \end{align*} with $\mathbb{E}_{-100} T = \mathbb{E}_{10} T = 0$. I'll leave it to you to solve this recurrence for $\mathbb{E}_0T$.

In solving $\mathbb{P}(S_T = 100)$, consider the "thinned" process $Y_j$ such that \begin{align*} Y_j = X_{i(j)}, \qquad i(j) = \min\left\{i: \sum_{n = 1}^{i} \mathbb{I}(S_n \neq S_{n-1}) \ge j\right\} \end{align*} That is, we ignore each $\{X_i = 0\}$ when forming our sum; this makes complete sense, since a "draw" in gambler's ruin doesn't contribute anything. Then we have \begin{align*} Y_j = \begin{cases} -1 & \text{w.p. } \frac{2}{3} \\ 1 & \text{w.p. } \frac{1}{3} \end{cases} \end{align*} Now solve this probability $\mathbb{P}(S_T = 100)$ like a normal gambler's ruin.