= Square-root tail bound for martingale absorption
{title2=$\mathbb P(T>n)\leq2\tau/(\sigma\sqrt n)$}
Under the conditional-<variance> and overshoot assumptions of the <absorption-time bound from conditional variance and overshoot>, $\mathbb P(T>n)\leq2\tau/(\sigma\sqrt n)$. Bound the probability by $\mathbb P(T_R<\infty)+\mathbb E(T\wedge T_R)/n$ and optimize $1/R+\tau^2R/(\sigma^2n)$. If the resulting bound is below one, its minimizing threshold is greater than one; otherwise the probability bound is trivial.
Back to article page
