Lagmental Vicfred

Chebyshev's Inequality Applies Markov to Squared Deviation by Vicfred

tags: mathematics, concentration inequalities, tail bounds, martingales

Finite variance bounds deviations from the mean by an inverse square. I want the notation, the mechanism, and the failure mode visible at the same time.

Start locally

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.

$$ \mu=\mathbf E[X],\qquad\sigma^2=\operatorname{Var}(X) $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ \mathbf P(|X-\mu|\ge t)\le\frac{\sigma^2}{t^2} $$

Compute before generalising

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ \mathbf P(|X-\mu|\ge t)=\mathbf P((X-\mu)^2\ge t^2)\le\frac{\mathbf E[(X-\mu)^2]}{t^2} $$

The global view

The aligned summary deliberately puts the datum and conclusion on different rows. Mathematically, this is the distinction between specifying an object and proving a property of it.

$$ \begin{aligned} \mathsf{D}\;&:\quad \mu=\mathbf E[X],\qquad\sigma^2=\operatorname{Var}(X),\\[5pt] \mathsf{C}\;&:\quad \mathbf P(|X-\mu|\ge t)\le\frac{\sigma^2}{t^2}. \end{aligned} $$

Edge conditions

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-\mu|\ge t)\le\frac{\sigma^2}{t^2} \end{gathered}} $$

With the dependency made explicit, the same pattern can be recognised safely in nearby problems. A changed hypothesis should now be easy to spot.

This article was posted on Mon 06 June 2016. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.