# How is the optional stopping theorem applied here?

I am reading the book Random Graph Dynamics by Rick Durett and on page 42 they apply the optional stopping theorem, which I have never heard of before, and I can not figure out how it can be applied in the scenario. I read the Wikipedia page and they give an example where the stopping theorem can not be applied as it would give a contradiction, but I do not understand why it can not be applied. Clearly, I do not understand the conditions of the theorem.

So one of the conditions on Wikipedia states that the stopping time $$\tau$$ has finite expectation and the conditional expectations of the absolute value of the martingale increments are almost surely bounded. But they then give the example of the martingale of a random walk on the integers starting at $$0$$ with stopping time upon reaching some fixed integer $$m>0$$. Clearly $$E(X_\tau)=m\neq0=E(X_0)$$. However, to my knowledge, $$\tau$$ has finite expectation and the absolute value of the martingale increments are definitely bounded by $$1$$, so how do you avoid this contradiction?

The application in the book I am reading is on the following martingale. Let $$S_0=1$$ and $$S_{t+1}-S_t\sim-1+\mbox{Binomial}(n,p)$$ independent with $$np=\lambda<1$$. Let $$\tau$$ be the stopping time defined as the smallest integer such that $$S_\tau=0$$. Then $$E(S_t)=1+t(\lambda-1)$$, so $$0=E(S_\tau)=1+E(\tau)(\lambda-1)$$, so $$E(\tau)=1/(1-\lambda)<\infty$$. Let $$X_t:=S_{t+1}-S_t$$ such that $$E\left(e^{\theta S_{t+1}}\right)=E\left(e^{\theta S_t}\right)E\left(e^{\theta X_t}\right).$$ We find $$M_t:=e^{\theta S_t}/E\left(e^{\theta X_t}\right)^t$$ to be a martingale. The book claims that we can use the optional stopping theorem to conclude that $$E(M_\tau)=E(M_0)$$, but I do not see which condition applies. The stopping time can be arbitrarily large and the value $$M_t$$ can become arbitrarily large. There is also no constant $$c$$ such that $$E(|M_{t+1}-M_t|:F)\leq c$$ almost surely for every event $$F\in\mathcal{F}_t$$. What am I missing?

In your first example, the one from Wikipedia: for a random walk on the integers with $$\tau = \inf\{t : X_t = m\}$$, even though $$\tau$$ is finite with probability $$1$$, $$\mathbb E[\tau] = \infty$$. This is why conditions (a) and (b) don't apply. Condition (c) doesn't apply because for any $$c>0$$, $$\Pr[X_{t \wedge \tau} < -c]$$ is positive if $$t$$ is large enough.
• Prove that in $$\mathbb G_{n,p}$$ with $$np = \lambda <1$$, very few vertices are in components with cycles (Lemmas 2.10 and 2.11 in Frieze and Karoński).