随机算法 (Fall 2011)/Chebyshev's Inequality

From EtoneWiki
Jump to: navigation, search

Variance

Definition (variance)
The variance of a random variable is defined as
The standard deviation of random variable is

We have seen that due to the linearity of expectations, the expectation of the sum of variable is the sum of the expectations of the variables. It is natural to ask whether this is true for variances. We find that the variance of sum has an extra term called covariance.

Definition (covariance)
The covariance of two random variables and is

We have the following theorem for the variance of sum.

Theorem
For any two random variables and ,
Generally, for any random variables ,
Proof.
The equation for two variables is directly due to the definition of variance and covariance. The equation for variables can be deduced from the equation for two variables.

We will see that when random variables are independent, the variance of sum is equal to the sum of variances. To prove this, we first establish a very useful result regarding the expectation of multiplicity.

Theorem
For any two independent random variables and ,
Proof.

With the above theorem, we can show that the covariance of two independent variables is always zero.

Theorem
For any two independent random variables and ,
Proof.

We then have the following theorem for the variance of the sum of pairwise independent random variables.

Theorem
For pairwise independent random variables ,
Remark
The theorem holds for pairwise independent random variables, a much weaker independence requirement than the mutual independence. This makes the variance-based probability tools work even for weakly random cases. We will see what it exactly means in the future lectures.

Variance of binomial distribution

For a Bernoulli trial with parameter .

The variance is

Let be a binomial random variable with parameter and , i.e. , where 's are i.i.d. Bernoulli trials with parameter . The variance is

Chebyshev's inequality

With the information of the expectation and variance of a random variable, one can derive a stronger tail bound known as Chebyshev's Inequality.

Theorem (Chebyshev's Inequality)
For any ,
Proof.
Observe that

Since is a nonnegative random variable, we can apply Markov's inequality, such that