As Mike pointed out, $\tau$ is a geometric random variable. To see this, let $n \geq 0$ then
$$\begin{align}P(\tau = n) &= P(X_0 \notin S, X_1 \notin S, \ldots, X_{n-1} \notin S, X_n \in S) \\ &= P(X_0 \notin S)P(X_1 \notin S) \times \cdots \times P(X_{n-1} \notin S) \, P(X_n \in S) \\ &= (1-P(X_0 \in S))^{n-1} \, P(X_0 \in S)\end{align}$$
which proves that $\tau$ is a geometric random variable with parameter $p = P(X_0 \in S)$.
Linking your related previous question here for posterity.
(1) You are correct that $Y_n$ is a nonnegative martingale. However, the optional stopping theorem does not guarantee that $\mathbb E[Y_{\tau}] = 1$ for any stopping time with $\tau < \infty$ almost surely.
For the Optional Stopping Theorem to apply in this way, you need one of three things:
- A bounded stopping time $\tau$ (meaning that there exists some $M$ such that $\tau < M$ with probability 1)
- An integrable stopping time $\tau$ (that is, $\mathbb E[\tau] < \infty$), and a process $X_t$ with bounded increments (meaning that there exists some $M$ such that $X_{t+1} - X_t < M$ with probability 1)
- An almost surely finite stopping time $\tau$ , and a bounded process $X_t$ (meaning that there is a constant $M$ such that $-M < X_t < M$ with probability 1).
Notice that among these conditions, the heavier a restriction you place on $\tau$, the more you can relax the conditions on $X_t$, and vice versa. Going from condition 1 to 3, you can see that the conditions on $\tau$ relax, while the conditions on $X_t$ tighten.
You asked whether having $\tau < \infty$ with probability 1 was sufficient, but it is not; you need in addition to have a bounded process to guarantee the optional stopping theorem (unless you impose a stronger condition on the stopping time).
(2) With $T = \inf \{n : Y_n \leq 1/18\}$, it is true (though not trivial) that $T < \infty$ almost surely. (Short sketch of proof: consider $\log(Y_n)$, which is a random walk on $\mathbb R$ that takes larger steps downward than upward. In the long run, this will almost surely become less than any value $K$, including $K = \log(1/18)$. Or, an alternate proof: the Martingale Convergence Theorem, which implies that every nonnegative martingale converges almost surely.)
Consequently, it is true, almost by definition, that $\mathbb E[Y_T] \leq 1/18.$ This does not contradict the Optional Stopping Theorem, because the Optional Stopping Theorem does not apply to this stopping time / process.
Note that of the 3 conditions, we can immediately rule out conditions 2 and 3 as possibilities for applying the OST. The process $X_t$ is unbounded above, and even its increments are unbounded -- consider what might happen if the first $n$ steps are all taken in the positive direction. Hence, the only condition that might apply is condition 1. However, even that does not apply here; for any $M$, there is a positive probability that the first $M$ steps will all be to the right and that $T < M$ will be false.
Hence, none of the conditions for the Optional Stopping Theorem apply in this case. There is no contradiction.
Now, if you had considered the stopping time $T_2 := \{n : Y_t \leq 1/18 \text{ or } Y_t \geq 5\}$ (or any other positive number for an upper bound), then both condition sets 2 and 3 would apply in that case, and we would have $\mathbb E[Y_{T_2}] = 1$ for that example.
Best Answer
Hints: