Expectation Deviation Upper Bound
Why
We bound the probability that a random variance deviates from its mean using its variance.
Result
Suppose $f: \Omega \to \R $ is measurable on
the probability space $(\Omega , \mathcal{F} , P)$.
Then
\[ P[\abs{f - \E (f)} \geq t] \leq \frac{\var f}{t^2} \quad \text{ for all } t > 0 \]
The symbols $\abs{f - \E (f)} \geq t$ denote
the set $\Set*{x \in X}{ \abs{f(x) - \E (f)}
\geq t}$.
This set is the same as the set
\[ \Set*{x \in X}{({f(x) - \E (f)})^2 \geq t^2}. \]
By using the tail measure upper bound,\[ P(\Set*{x \in X}{({f(x) - \E (f)})^2 \geq t^2}) \leq \frac{\E (f - \E (f))^2}{t^2}. \]
We recognize the numerator of the right hand side as the variance of $f$.The above is also called Chebychev’s Inequality (or the Chebyshev inequality).