Minimum Covariance Between Bernoulli Variables

Question

Suppose $X_1,...,X_n \sim Ber(\frac{1}{2})$, and that $COV(X_i,X_j) = COV(X_k,X_l)$ for $k\neq l,j\neq i$.

How small can the covariance be?

My attempt:

We know that $COV(X_i,X_j) = E(X_1X_2)-E(X_1)E(X_2) = E(X_1X_2)-\frac{1}{4}\geq -\frac{1}{4}$

since $Img(X_iX_j) = \{0,1\}$. And I have an example where that number is attained, simply letting $X_2 =1$ iff $X_1 = 0$. So the minimum is $-\frac{1}{4}$. How off is this?

Answer 1

Observe first that, denoting $S = \sum_i X_i$, $$\operatorname{Var}(S)=\sum_i \operatorname{Var}(X_i)+\sum_{i\neq j}\operatorname{Cov}(X_i,X_j)=\frac{1}{4}n+n(n-1)C,$$ where $C$ is the common covariance.

• For even $n$, since the variance is nonnegative, we see that $C\ge -\frac{1}{4(n-1)}$, with equality if $S$ is a.s. constant.

• For odd $n$, note that $\mathbb{E}[S] = \frac{n}2$ is half-integer, while $S$ is integer. Therefore, $|S-\mathbb{E}[S]|\ge \frac12$, so $\operatorname{Var}(S) = \mathbb{E}[(S-\mathbb{E}[S])^2]\ge \frac14$. Consequently, $C\ge -\frac{1}{4n}$, with equality if $|S-\mathbb{E}[S]|= \frac12$ a.s.

This bound is achievable (and hence tight):

• If $n$ is even, choose a random subset $A$ of size $\frac{n}2$ from $\{1,\cdots,n\}$, and set $X_i=\mathbb{I}[i\in A]$.
• If $n$ is odd, pick $k\in\left\{\frac{n-1}{2},\frac{n+1}{2}\right\}$ with equal probability, choose a random subset $A$ of size $k$ from $\{1,\cdots,n\}$, and set $X_i=\mathbb{I}[i\in A]$.