3.2 Elements of Probability

We start with estimates on deviations of random variables. Let X be a random variable with expectation E( X) and second central moment var( X) = E(( X ? E( X)) ²). Let X take only nonnegative values.

Theorem 3.27

(Markov s inequality) For any nonnegative random variable, X,

Proof This is a proof for discrete random variables; generalization to the continuous case is straightforward. Since X takes only nonnegative values,

Note that we can substitute any positive function f for X,

If, moreover, f is a nondecreasing function, we get

Theorem 3.28

(Chebyshev s inequality) For any random variable X,

Proof We choose f ( X) = X ², and have

Let X now be a sum of n independent random variables X _j, j = 0 , 1 , , n ? 1. We denote by ? the expectation of X, and have

Theorem 3.29

(Chernoff bound)

Proof We pick f( X) = e ^?X, and compute

Now

and we are done.

In the above we essentially used the multiplicative property of the function e ^?x, namely that

The exponential function of the purely imaginary argument,

also possesses this property.

Let X be a random variable having probability density function (p.d.f.), f ( x). The characteristic function ? of