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?


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]$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.