Bounds for average covariance across many RVs?

Question

Suppose we have two standard normal RVs that are not independent. We can construct them so that the covariance can range from -1 to 1. (At the extremes, $X_1 = -X_2$ and $X_1=X_2$).

Now consider the general case of $n$ standard normal RVs that are not independent. We consider the average covariance of pairs of these rvs, that is $E[\mathrm{Cov}(X_i, X_j)]$. I have the notion that as $n$ increases, the bounds of $E[\mathrm{Cov}(X_i, X_j)]$ narrow--is that correct?

For example, suppose we have three RVs, and $X_1 = X_2$, with $X_3$ being completely independent of both. Then the average covariance is $1/3$. Is that the most extreme possible with three RVs? If not, what is the most extreme possible value and how does it scale with $n$?

Answer 1

From an answer of mine over on stats.SE.....

Consider the variance of the sum of $n$ unit variance random variables $X_i$. We have that $$\begin{align*} \operatorname{var}\left(\sum_{i=1}^n X_i\right) &= \sum_{i=1}^n \operatorname{var}(X_i) + \sum_{i=1}^n\sum_{j\neq i}^n \operatorname{cov}(X_i,X_j)\\ &= n + \sum_{i=1}^n\sum_{j\neq i}^n \rho_{X_i,X_j}\\ &= n + n(n-1)\bar{\rho} \tag{1} \end{align*}$$ where $\bar{\rho}$ is the average value of the $\binom{n}{2}$correlation coefficients. But since $\operatorname{var}\left(\sum_i X_i\right) \geq 0$, we readily get from $(1)$ that $$\bar{\rho} \geq -\frac{1}{n-1}.$$

As another answer to the same question shows, the maximum value of $\bar{\rho}$ is $1$.

Answer 2

As an intermediate step, you can ask, for which $r$ is the $n\times n$ matrix all of whose diagonal entries are all equal to $1$ and whose off-diagonal entries are equal to $r$, positive semidefinite? Answer:

$$-\frac 1{n-1}\le r \le 1.$$

More generally, if $M$ has $1$'s on the diagonal, and is positive definite, then $\sum_{\sigma\in\mathcal S_n} \sigma M\sigma'/n!$ is as well, where the summation extends over all permutation matrices.