# Minimal Covariance of random variables.

Now I was wondering if you have some bernulli random variables $X_1, X_2, X_3,\dots X_n$.

That distribute on some $1/2$ probability (Ber($1/2$)), and all of their Cov are equal, meaning that $\text{Cov}(X_i,X_j) = \text{Cov}(X_k, X_l)$ for every $i \neq j$, and every $k \neq l$.

I'm asked to find how small can the $\text{Cov}(X_i,X_j)$ be for $i \neq j$, give an example for when the minimum is received.

So I started by saying that $\text{Cov}(X_i,X_j) = \mathbb E [X_iX_j] - \mathbb E[X_i]\cdot \mathbb E[X_j] = \mathbb E[X_iX_j] - 0.25$

Basically I need now to minimize $\mathbb E [X_iX_j]$ but I'm having a hard time understanding what is exactly multiplying bernulli random variables.

Thanks for any help!

• The covariance matrix of them has a diagonal of $1/4$ (the variance $p(1-p)$ of a given marginal) and identical off-diagonal elements (the covariance). You may try to check under what condition it is positive semi-definite, and minimize the covariances under this constraint. – BGM Dec 25 '16 at 20:06
• I'm sorry but I didn't fully understand what you mean. – MathAbuser Dec 26 '16 at 17:46
• the question has been answered here: math.stackexchange.com/questions/2077861/… – Cettt Jan 2 '17 at 7:46

This question need other expert in linear algebra to solve it. Here I just provide some examples in case of small $n$. Let $c$ be the common covariance to be minimized.

When $n = 2$, the covariance matrix of $\begin{bmatrix} X_1 \\ X_2\end{bmatrix}$ is $\begin{bmatrix} \displaystyle \frac {1} {4} & c \\ c & \displaystyle \frac {1} {4}\end{bmatrix}$.

The requirement of a matrix to be a valid covariance matrix is that it is positive semi-definite. Here I am lazy/ignorant and just use the Sylvestor's Criterion to check for positive definiteness. That means we just check for the leading principal minor being positive.

Obviously the first leading prinicipal minor $\displaystyle \frac {1} {4}$ is positive.

For the above case $n = 2$, the determinant is $\displaystyle \frac {1} {16}(1 - 4c)(1 + 4c)$, so it is positive when $\displaystyle c \in \left(-\frac {1} {4}, \frac {1} {4}\right)$

You may check that the infimum $\displaystyle -\frac {1} {4}$ is attainable when $X_2 = 1 - X_1$, i.e. they are perfectly negatively correlated.

When $n = 3$, the determinant is $\displaystyle \frac {1} {64}(1 - 4c)^2(1 + 8c)$, so it is positive when $\displaystyle c > -\frac {1} {8}$. Combining with the previous constraint, we have $\displaystyle c \in \left(-\frac {1} {8}, \frac {1} {4}\right)$

When $n = 4$, the determinant is $\displaystyle \frac {1} {256}(1 - 4c)^3(1 + 12c)$, so it is positive when $\displaystyle c \in \left(-\frac {1} {12}, \frac {1} {4}\right)$.

So with these results, it is tempting to guess the determinant for general $n$ is
$$\frac {1} {4^n}(1 - 4c)^{n-1}(1 + 4(n-1)c)$$ and the infimum of $c$ is $\displaystyle -\frac {1} {4(n-1)}$. You may try to prove it via, say elementary row/column reduction and factorize it, or by induction.

P.S. For $n = 3$ case the infimum seems not attainable. Need further checking.

• I'm not sure I can use this type of solution. What if I've been given a hint that says: Look at the random variable X = $\Sigma$ Xi – MathAbuser Dec 28 '16 at 18:23