Covariance Exercises

Covariance

The variance is the spread around the mean. To measure it, we use $\mathbb{E}[(X-\mathbb{E}[X]{)}^2]$ - the distance of each point to the mean. This then gives $\mathrm{Var}[X]=\mathbb{E}[X^2]-\mathbb{E}[X{]}^2$.
Why squared? otherwise the positive/negative distances cancel each other out (it’s mean squared distance).

Now Covariance is the exact same thing but one $(X-\mathbb{E}[X])$ replaced by $(Y-\mathbb{E}[Y])$. Giving $\text{Cov}(X,Y)=\mathbb{E}[(X-\mathbb{E}[X])(Y-\mathbb{E}[Y])]$.
This measures how much variables move together (but only linearly - doesn’t pick up on $Y=X^2$).

A few things hold:

• for $X,Y$ independent $\text{Cov}[X,Y]=0$ (only holds in forward direction).
• $\mathrm{Var}[X+Y]=\mathrm{Var}[X]+\mathrm{Var}[Y]+2\text{Cov}[X,Y]$.
  • they add cleanly only when covariance vanishes.
• $\text{Cov}[aX+bY,Z]=a\text{Cov}(X,Z)+b\text{Cov}(Y,Z)$ (bilinear and symmetric).
  • this is the thing we need for our indicator-variable arguments.

Indicator Variables

For $X=\sum X_i$ of indicator variables, computing $\mathrm{Var}[X]$ gets easier, since indicators have a few special properties:

• $\mathbb{E}[X_i]=\mathrm{Pr}[X_i]$
• $X_i^2=X_i$
• $X_i\cdot X_j=\mathrm{Pr}[X_i\cap X_j]$.
  • since only the case where both are $1$ survives.

Then $\mathrm{Var}[X_i]=\mathbb{E}[X_i^2]-\mathbb{E}[X_i{]}^2=p-p^2=p(1-p)$.

• Variance of a Bernouilli variable

We also notice $\text{Cov}[X_i,X_j]=\mathrm{Pr}[X_i\cap X_j]-\mathrm{Pr}[X_i]\mathrm{Pr}[X_j]$.

• this vanishes iff $X_i,X_j$ independent

Summing up

$\mathrm{Var}[X]=\mathrm{Var}[(X_1+X_2+\cdots +X_n)(X_1+X_2+\cdots +X_n)]$ which comes out neatly to the following sum.

Variance of sum of indicators

$$\mathrm{Var}[X]=\sum _i\mathrm{Var}[X_i]+\sum _{i\ne j}\text{Cov}[X_i,X_j]$$

where $\text{Cov}[X_i,X_j]=\mathrm{Pr}[X_i{X}_j]-\mathrm{Pr}[X_i]\mathrm{Pr}[X_j]$.

Note: the second sum has $n(n-1)$ terms.
Note: we can cancel out the $i,j$ where $X_i,X_j$ are independent.

Symmetric terms

We can also simplify into ${\sum }_{i\ne j}\text{Cov}[X_i,X_j]=2{\sum }_{i<j}\text{Cov}[X_i,X_j]$ since covariance is symmetric.

A shortcut

In practice, we usually compute the second moment $\mathbb{E}[X^2]$.

$$\begin{array}{rl}{X}^2& ={\left(\sum _i{X}_i\right)}^2=\sum _i{X}_i^2+\sum _{i\ne j}{X}_i{X}_j\\ & =\sum _i{X}_i+\sum _{i\ne j}\mathrm{Pr}[X_i\cap X_j]\end{array}$$

Now this gives $\mathbb{E}[X^2]=\mathbb{E}[X]+{\sum }_{i\ne j}\mathrm{Pr}[X_i\cap X_j]$.
So $\mathrm{Var}[X]=\mathbb{E}[X]+\sum \cdots -\mathbb{E}[X{]}^2$. This means we only have to compute $\mathbb{E}[X]$ and a sum of the pairwise joint probabilities.