Supermartingale with bdd increment and positive variance before $\tau$ satisfies $P_k(\tau >u) \leq \frac{4k}{\sigma \sqrt{u}}$ for large $u$.

Question

Lemma 2.4 of "Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability" by Levin, Luczak, Perez, 2010 states that

Let $(W_t)_{t \in \mathbb N}$ be a non-negative supermartingale and $\tau$ be a stopping time such that $W_0=k \geq 0 $ , $W_{t+1} -W_t \leq B$ for some $B>0$, and finally $Var (W_{t+1} | \mathcal F_t ) > \sigma ^2 >0$ on the event $\{ \tau >t \} $. Then for $u > 4B^2 / (3 \sigma ^2)$, we have $$P_k(\tau >u) \leq \frac{4k}{\sigma \sqrt{u}}$$

The paper says to look at chapter 18 of "Markov chain and Mixing times" by Levin, Peres, Wilmer for a proof, but I could not find the proof in that reference.

How can I prove the above lemma?

Any help is appreciated.

Answer 1

The claimed Lemma is actually the Proposition 17.20. in section 17.5. of the book "Markov Chains and Mixing Times (2nd edition)" written by David A.Levin and Yuval Peres, whose proof is contained in the Appendix D of the same book.