1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

As for the second example - my understanding is that any of the three conditions in Wikipedia's article is sufficient, but the actual necessary thing is for the martingale to be uniformly integrable, which is more complicated. You are right that none of Wikipedia's conditions apply. If you look in the probability theory reference book that is cited there, you can see more details, but the probability theory got too heavy for me.

However, there is also a proof of the same result that uses fewer martingales and more graph theory. You can find it, for example, in Frieze and Karoński's Introduction to Random Graphs. The idea here is that we can:

  • 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).
  • Prove the same result about the size of the largest component, with the extra knowledge that it's a tree, which lets us get away with just the second moment method and lots of algebra (Lemma 2.12).
| cite | improve this answer | |
$\endgroup$

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.