How to prove the ‘covariance inequality’ for discrete random variables?

Question

I’m trying to prove the following ‘covariance inequality’ $$ |\operatorname{Cov}(x,y)|\le\sqrt{\operatorname{Var}(x)}\sqrt{\operatorname{Var}(y)}\,, $$ where covariance and variance are defined using discrete values, \begin{align} \operatorname{Cov}(x,y) &= \frac{1}{n-1}\sum_{i=1}^n \big[(x_i-\bar x)(y_i-\bar y)\big]\,, \\ \operatorname{Var}(x) &= \frac{\displaystyle\sum_{i=1}^n(x_i-\bar x)^2}{n-1}\,, \\ \operatorname{Var}(y) &= \dfrac{\displaystyle\sum_{i=1}^n(y_i-\bar y)^2}{n-1}\,. \end{align}

There are plenty of proofs of to be found online (such as this one). However, they all either seem to be for continuous random variables, or just refer me to the Cauchy-Schwarz inequality, which I am aware of, but not sure how to apply to this particular proof. Basically, I am wondering if there is a way to prove this inequality using those above definitions.

I’ve tried substituting these definitions into the inequality above, but after expanding these summations and getting rid of the $1/(n-1)$ on both sides, I’m left with a mess (as you can imagine) with summation terms on both sides, some in the absolute value, and some in the square root. I’m not sure if there’s some algebraic mistake I’m making, some summation property I’m missing, or if substitution is just the wrong way to go about this proof.

Answer 1

First recall that

$$ \text{Var}(x) = \frac{1}{n} \sum_{j=0}^{n-1} (x_i - \bar{x})^2.$$

See for example https://en.wikipedia.org/wiki/Variance#Discrete_random_variable.

Cauchy-Schwarz says that

$$ \left( \sum_{j=1}^n u_j v_j \right)^2 \leq \left(\sum_{j=1}^n (u_j)^2 \right) \left( \sum_{j=1}^n (v_j)^2\right).$$

See for example https://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality.

Let's see how to apply it. First we write things out.

$$ \text{Cov}(x,y)^2 = \left(\frac{1}{n} \sum_{j=0}^{n-1} (x_j - \bar{x}) (y_j - \bar{y}) \right)^2 = \frac{1}{n^2} \left(\sum_{j=0}^{n-1} (x_j - \bar{x}) (y_j - \bar{y}) \right)^2.$$

It now looks something like Cauchy-Schwarz. Let's apply it.

$$ \text{Cov}(x,y)^2 \leq \frac{1}{n^2} \left(\sum_{j=0}^{n-1} (x_j-\bar{x})^2\right) \left( \sum_{j=0}^{n-1} (y_j - \bar{y})^2\right).$$

I can actually rewrite this as

$$ \text{Cov}(x,y)^2 \leq \left(\frac{1}{n} \sum_{j=0}^{n-1} (x_j-\bar{x})^2\right) \left(\frac{1}{n} \sum_{j=0}^{n-1} (y_j - \bar{y})^2\right).$$

Note that this looks like our definition of variance. Applying that, we have

$$ \text{Cov}(x,y)^2 \leq \text{Var}(x) \text{Var}(y).$$

Now take the square root of both sides.

Answer 2

Without considering continuous or discrete, the following is a very elementary proof.

Let’s consider the r.v. $Z=Y+aX$ and let’s calculate its variance:

$$\operatorname V(Z)=\operatorname V(Y)+a^2\operatorname V(X)+2a \operatorname{Cov}(X,Y)\geq0.$$

As per the fact that variance cannot be negative, the above expression is a 2nd-degree inequality in $a$ and as per the fact that the 2nd-degree term has positive coefficient the discriminant $\Delta$ must be $\leq0$.

Thus,

$$4\operatorname{Cov}^2(X,Y)-4\operatorname V(X)\operatorname V(Y)\leq0$$

$$\iff \operatorname{Cov}^2(X,Y)\leq \operatorname V(X)\operatorname V(Y).$$