# Lecture 21

## Covariance, Correlation, Variance of a sum, Variance of Binomial & Hypergeometric
----

### Definition

Covariance of any 2 random variables $X, Y$ is defined as

\begin{align}
  Cov(X, Y) &= \mathbb{E}\left( (X - \mathbb{E}(X)) (Y - \mathbb{E}(Y)) \right) \\
  &= \mathbb{E}(XY) - \mathbb{E}(X) \, \mathbb{E}(Y) & \quad \text{similar to definition of variance}
\end{align}

Covariance is a measure of how $X, Y$ might vary _in tandem_. 

If the product of $(X - \mathbb{E}(X))$ and $(Y - \mathbb{E}(Y))$ is _positive_ then that means that both values are either _positive_ ($X,Y$ tend to be greater than their respective means); or they are both _negative_ ($X,Y$ tend to be less than their means).

Correlation is defined in terms of covariance, as you will see in a bit.

### Properties

\begin{align}
  & \text{[1]} & Cov(X,X) &= Var(X) \\
  \\
  & \text{[2]} & Cov(X,Y) &= Cov(Y,X) \\
  \\
  & \text{[3]} & Cov(X, c) &= 0 & \quad \text{for some constant }c \\
  \\
  & \text{[4]} & Cov(cX, Y) &= c \, Cov(X,Y) & \quad \text{bilinearity} \\
  \\
  & \text{[5]} & Cov(X, Y+Z) &= Cov(X,Y) + Cov(X,Z) & \quad \text{bilinearity} \\
  \\
  & \text{[6]} & Cov(X+Y, Z+W) &= Cov(X,Z) + Cov(X,W) + Cov(Y,Z) + Cov(Y,W) & \quad \text{applying (5)} \\
  \\
  & \Rightarrow & Cov \left( \sum_{i=1}^{m} a_{i} \, X_{i},  \sum_{j=1}^{n} b_{j} \, Y_{j} \right) &= \sum_{i,j} a_{i} \, b_{j} \, Cov \left( X_{i}, Y_{j} \right) \\
  \\
  & \text{[7]} & Var(X_1 + X_2) &=  Cov(X_1+X_2, X_1+X_2) \\
  & & &= Cov(X_1, X_1) + Cov(X_1, X_2) + Cov(X_2, X_1) + Cov(X_2, X_2) \\
  & & &= Var(X_1) + Var(X_2) + 2 \, Cov(X_1, X_2) \\
  \\
  & \Rightarrow & Var(X_1 + X_2) &= Var(X_1) + Var(X_2) & \quad \text{if }X_1, X_2 \text{ are uncorrelated} \\
  \\
  & \Rightarrow & Var(X_1 + \dots + X_n) &= Var(X_1) + \dots + Var(X_n) + 2 \, \sum_{i \lt j} Cov(X_i, X_j) \\
\end{align} 

#### Bilinearity

If you imagine treating one variable as fixed and then start working with the other, it sort of looks like _linearity_. It also sort of looks like the distributive property, too. 

Bilinearity lets us

\begin{align}
  Cov(\lambda X, Y) &= \lambda \, Cov(X, Y) = Cov(X, \lambda Y) & \quad \text{freely move scaling factors} \\
  \\
  Cov(X, Y_1 + Y_2) &= Cov(X, Y_1) + Cov(X, Y_2) \\
  Cov(X_1 + X_2, Y) &= Cov(X_1, Y) + Cov(X_2, Y) & \quad \text{distribution in }Cov \text{ operator} \\
\end{align}

### Theorem If $X,Y$ are independent, then they are also uncorrelated, i.e., $Cov(X,Y) = 0$

The converse is not true, however: $Cov(X,Y) = 0$ does not necessarily mean that $X,Y$ are independent.

Consider $Z \sim \mathcal{N}(0,1)$, and $X \sim Z, Y \sim Z^2$.

\begin{align}
  Cov(X,Y) &= \mathbb{E}(XY) - \mathbb{E}(X)\,\mathbb{E}(Y) \\
  &= \mathbb{E}(Z^3) - \mathbb{E}(Z) \, \mathbb{E}(Z^2) \\
  &= 0 - 0 & \quad \text{odd moments of }Z \text{ are 0} \\
  &= 0
\end{align}

But given $X \sim Z$, we know *exactly* everything about $Y$. And knowing $Y$, gives us everything about $X$, _except for the sign_.

So $X,Y$ are dependent, yet their covariance (and hence correlation) is 0.

## Definition

Correlation is defined in terms of covariance.

\begin{align}
  Corr(X,Y) &= \frac{Cov(X,Y)}{\sigma_{X} \, \sigma_{Y}} = \frac{Cov(X,Y)}{\sqrt{Var(X)} \, \sqrt{Var(Y)}} \\
  \\
  &= Cov \left( \frac{X-\mathbb{E}(X)}{\sigma_{X} }, \frac{Y-\mathbb{E}(Y)}{\sigma_{Y}} \right) & \quad \text{standardize first, then find covariance} \\
\end{align}

Correlation is dimensionless, and like standard deviation, is unit-less.

Correlation also ranges from -1 to 1. This is what happens when we divide by $\sqrt{Var(X)} \, \sqrt{Var(Y)}$

### Theorem $-1 \le Corr(X,Y) \le 1$

Without loss of generality, assume that $X,Y$ are already standarized (mean 0, variance 1).

\begin{align}
  Var(X + Y) &= Var(X) + Var(Y) + 2\, Corr(X,Y) \\
  &= 1 + 1 + 2 \, \rho & \quad \text{ where } \rho = Corr(X,Y) \\
  &= 2 + 2 \, \rho \\
  0 &\le 2 + 2 \, \rho & \quad \text{since }Var \ge 0 \\
  0 &\le 1 + \rho & \Rightarrow \rho \text{ has a floor of }-1 \\
  \\
  Var(X - Y) &= Var(X) + Var(-Y) - 2\, Corr(X,Y) \\
  &= 1 + 1 - 2 \, \rho & \quad \text{ where } \rho = Corr(X,Y) \\
  &= 2 - 2 \, \rho \\
  0 &\le 2 - 2 \, \rho & \quad \text{since }Var \ge 0 \\
  0 &\le 1 - \rho & \Rightarrow \rho \text{ has a ceiling of }1 \\
  \\
  &\therefore -1 \le Corr(X,Y) \le 1 &\quad \blacksquare
\end{align}

## Cov in a Multinomial

Given $(X_1, \dots , X_k) \sim Mult(n, \vec{p})$, find $Cov(X_i, X_j)$ for all $i,j$.

\begin{align}
  \text{case 1, where } i=j \text{ ...} \\
  \\
  Cov(X_i, X_j) &= Var(X_i) \\
  &= n \, p_i \, (1 - p_i) \\
  \\
  \\
  \text{case 2, where } i \ne j \text{ ...} \\
  \\
  Var(X_i + X_j) &= Var(X_i) + Var(X_j) + 2 \, Cov(X_i, X_j) & \quad \text{property [7] above} \\
  n \, (p_i + p_j) \, (1 - (p_i + p_j)) &= n \, p_i \, (1 - p_i) + n \, p_j \, (1 - p_j) + 2 \, Cov(X_i, X_j) & \quad \text{lumping property} \\
  2 \, Cov(X_i, X_j) &= n \, (p_i + p_j) \, (1 - (p_i + p_j)) - n \, p_i \, (1 - p_i) - n \, p_j \, (1 - p_j) \\
  &= n \left( (p_i + p_j) - (p_i + p_j)^2 - p_i + p_i^2 - p_j + p_j^2  \right) \\
  &= n ( -2 \, p_i \, p_j ) \\
  Cov(X_i, X_j) &= - n \, p_i \, p_j
\end{align}

Notice how case 2 where $i \ne j$ yields $Cov(X_i, X_j) = - n \, p_i \, p_j$, which is negative. This should agree with your intuition that for $(X_1, \dots , X_k) \sim Mult(n, \vec{p})$, categories $i,j$ are competing with another, and so they cannot be positively correlated nor independent of each other.

## Variance of a Binomial

Applying what we now know of covariance, we can obtain the variance of $X \sim Bin(n, p)$.

We can describe $X = X_1 + \dots + X_n$ where $X_i$ are i.i.d. $Bern(p)$.

Now consider _indicator random variables_. Let $I_A$ be the indicator of event $A$. 

\begin{align}
  I_A &\in \{0, 1\} \\
  \\
  \Rightarrow I_A^2 &= I_A \\
  I_A^3 &= I_A \\
  & \text{...} \\
  \\
  \Rightarrow I_A \, I_B &= I_{A \cap B} & \quad \text{for another event } B \\
  \\
  Var(X_i) &=  \mathbb{E}X_i^2 - ( \mathbb{E}X_i)^2 \\
  &= p_i - p_i^2 \\
  &= p_i \, (1 - p_i) \\
  &= p \, q & \quad \text{variance of Bernoulli} \\
  \\
  \Rightarrow Var(X) &= Var(X_i + \dots + X_n) \\
  &= Var(X_i) + \dots + Var(X_n) + 2 \, \left( \sum_{i \ne j} Cov(X_i, X_j) \right) \\
  &= n \, p \, q + 2 \, (0) & \quad Cov(X_i,X_j) = 0 \text{ since } X_i \text{ are i.i.d.} \\
  &= n \, p \, q
\end{align}

## Variance of Hypergeometric

Given $X \sim HGeom(w, b, n)$ where 

\begin{align}
  X &= X_1 + \dots + X_n \\
  \\
  X_j &= 
  \begin{cases}
    1, &\text{ if }j^{th} \text{ ball is White}  \\
    0, &\text{ otherwise } \\
  \end{cases} \\
\end{align}

Recall that the balls are sampled _without replacement_, so the draws are not independent.

However, for any draw, it is not the case that any particular ball would prefer to be drawn for that particular iteration. So there is some symmetry we can leverage!

\begin{align}
  Var(X) &= n \, Var(X_1) + 2 \, \binom{n}{2} Cov(X_1, X_2) & \quad \text{symmetry!} \\
  \\
  \text{now } Cov(X_1, X_2) &= \mathbb{E}(X_1 X_2) - \mathbb{E}(X_1) \, \mathbb{E}(X_2) \\
  &= \frac{w}{w+b} \, \frac{w-1}{w+b-1} - \left( \frac{w}{w+b} \right)^2 & \quad \text{recall } I_A \, I_B = I_{A \cap B} \text{; and symmetry} \\
\end{align}

Prof. Blitzstein runs out of time, but the rest is just algebra. _To be concluded in the next lecture._

----

# Appendix: Variance, Covariance and Linear Algebra

Let's relate what we know about variance, covariance and correlation with the concept of the [dot product](https://www.mathsisfun.com/algebra/vectors-dot-product.html) in linear algebra:

\begin{align}
  Cov(X, Y) &= X \cdot Y \\
            &= x_1 \, y_1 + \dots + x_n \, y_n \\
  \\
  Var(X) &= Cov(X, X) \\
         &= X \cdot X \\
         &= x_1 \, x_1 + \dots + x_n \, x_n \\
         &= |X|^2 \\
  \\
  \Rightarrow |X| &=  \sigma_{X} \\
                  &= \sqrt{Var(X)} \\
                  &= \sqrt{x_1 \, x_1 + \dots + x_n \, x_n} & \quad \text{the size of }\vec{X} \text{ is its std. deviation} \\
\end{align}

Now let's take this a bit further...

\begin{align}
  X \cdot Y &= |X| \, |Y| \, cos \theta \\
  \\
  \Rightarrow cos \theta &= \frac{X \cdot Y}{|X| \, |Y|} \\
                         &= \frac{Cov(X, Y)}{\sigma_{X} \, \sigma_{Y}} \\
                         &= \rho & \quad \text{... otherwise known as }Corr(X,Y) \\
\end{align}

Since $\rho_{X,Y} = cos_{X,Y} \theta$, we can see that the correlation of $X,Y$ is also the factor that projects vector $X$ onto $Y$, or vice versa. Now you can see why we can use cosine similarity as a metric to measure how close 2 vectors $X,Y$ are, since it is $Corr(X,Y)$.

f34ee65f8b8bf44eb9a58f679ec0c300a3ed557e
ipynb
Jupyter Notebook
Lecture_21.ipynb
dirtScrapper/Stats-110-master
a123692d039193a048ff92f5a7389e97e479eb7e
BSD-3-Clause
Lecture_21.ipynb
dirtScrapper/Stats-110-master
a123692d039193a048ff92f5a7389e97e479eb7e
BSD-3-Clause
Lecture_21.ipynb
dirtScrapper/Stats-110-master
a123692d039193a048ff92f5a7389e97e479eb7e
BSD-3-Clause
Qwen/Qwen-72B
1. YES
2. YES