Lagmental Vicfred

Markov's Inequality Uses Only Nonnegativity by Vicfred

tags: mathematics, concentration inequalities, tail bounds, martingales

A nonnegative random variable cannot exceed a threshold often unless its mean is large. The example is deliberately concrete; it is a test of the statement, not a substitute for it.

Notation

Tail bounds convert information about the moment-generating function \(M_X(\lambda)=\mathbf E[e^{\lambda X}]\) into estimates for \(\mathbf P(X\ge t)\). Stronger assumptions produce exponentially sharper bounds.

$$ X\ge0,\qquad a>0 $$

I keep the defining relation \(\mathsf D\) above the derived relation \(\mathsf C\). This exposes whether cancellation used \(x\ne0\) and whether the conclusion is canonical.

$$ \mathbf P(X\ge a)\le\frac{\mathbf E[X]}a $$

Stress the formula

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ \mathbf E[X]\ge\mathbf E[X\mathbf1_{\{X\ge a\}}]\ge a\,\mathbf P(X\ge a) $$

Interpretation

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad X\ge0,\qquad a>0,\\[5pt] \mathsf{C}\;&:\quad \mathbf P(X\ge a)\le\frac{\mathbf E[X]}a. \end{aligned} $$

Limit of the argument

The parameter must be optimized only over values where the moment-generating function exists. Independence and boundedness hypotheses are not interchangeable.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \mathbf P(X\ge a)\le\frac{\mathbf E[X]}a \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Thu 02 July 2009. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.