Minimal Covariance of random variables.

Question

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!

Answer 1

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.

Answer 2

Let's say that $Cov(X_i, X_j) = c$. As all of the diagonal elements are $1/4$, the covariance matrix $C$ can be written as the sum of two matrices: $$C = (1/4 - c) I_n - c J_n$$ where $J_n$ is the all ones matrix. Notice that the all ones vector $\vec{1}$ is the eigenvector of $C$ with the smallest eigenvalue (why?), and since we know that $$\min_{\|v\| = 1} \vec{v}^T C \vec{v} = \lambda_{min}(C)$$ and that a matrix is positive semidefinite if and only if all of its eigenvalues are non-negative, we must have that $\lambda_{min}(C) = 1/4 - c - cn \geq 0$. Rearranging, we see that $c \geq (4 (1-n))^{-1}$, which confirms BGM's observations.