I'm trying to prove the following 'covariance inequality'
$$
|\text{Cov}(x,y)|\le\sqrt{\text{Var}(x)}\sqrt{\text{Var}(y)}\,,
$$
where covariance and variance are defined using discrete values,
$$
\text{Cov}(x,y) = \frac{1}{n-1}\sum_{i=1}^n \big[(x_i-\bar{x})(y_i-\bar{y})\big]\,,
$$
$$
\text{Var}(x) = \frac{\sum_{i=1}^n(x_i-\bar{x})}{n-1}\,,
$$
$$
\text{Var}(y) = \frac{\sum_{i=1}^n(y_i-\bar{y})}{n-1}\,.
$$
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 ridding 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.
Best Answer
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.