The variance of a sample can be defined as $$s^2 = \frac{1}{2}\frac{1}{n(n-1)}\sum_{i}\sum_{j\ne i}\left(x_i - x_j\right)^2$$

Apart from the factor of $1/2$, this can be paraphrased verbally as

The variance is the average of the squared distances between pairs of distinct data points

Mathematically, this is equivalent to the "usual" definition of variance, $s^2 = \frac{1}{n-1}\sum \left(x_i -\bar{x} \right)^2$. Conceptually, however, it seems (to me) quite different, in two respects:

  1. This definition makes no reference to the mean value $\bar{x}$; we are not measuring how far apart points are from the mean, but rather how far away points are from one another.
  2. The factor of $n-1$ in the denominator -- which is well-known to be a source of confusion for students (see, e.g., Intuitive explanation for dividing by $n-1$ when calculating standard deviation?) -- appears naturally because there are $n(n-1)$ ordered pairs of distinct data points $(x_i, x_j), i\ne j$. No need for either hand-waving justifications about "cushioning" the sample variance, or for complicated calculations of estimator bias.

Again, just to be clear, I understand why the standard definition of $s^2$ includes a denominator of $n-1$, and I understand that the double-sum definition above is mathematically equivalent to the standard definition. What I would like to know:

Are there contexts (pedagogical or otherwise) in which the alternate definition of variance (as a double-sum over pairs of data points) is more commonly referred to? Are there any textbooks, for example, that take this as the primary definition?

  • 1
    $\begingroup$ Please see stats.stackexchange.com/questions/3931 for answers to (2) and (3) and stats.stackexchange.com/questions/18058 for a visual explanation of (1). $\endgroup$
    – whuber
    Jun 11 '18 at 15:09
  • 3
    $\begingroup$ That emphasis doesn't come through very clearly, so I recommend you reformulate your question to give that issue prominence. Since the two formulas are algebraically equivalent, as definitions they are equally good. For further insight you might consider the complexities of the two algorithms: one is $O(n)$ and the other is $O(n^2).$ $\endgroup$
    – whuber
    Jun 11 '18 at 15:30
  • 1
    $\begingroup$ I have read your question through--in its various versions--some three or four times over already. I apologize, but I see no reason to keep rereading it. All along it repeatedly emphasizes the $n-1$ term and there still is nothing in the explicit list of questions that attempts to focus the reader's attention on whether or not one first removes the mean from the data. So far, everything I have seen looks like it is answered elsewhere on this site (apart from that observation about algorithmic complexity, but there's nothing much to it after all). $\endgroup$
    – whuber
    Jun 11 '18 at 15:44
  • 1
    $\begingroup$ I have edited the question to try to clarify what I am asking (and in particular to emphasize that I am not asking why the variance has a factor of $n-1$ in the denominator). I hope this helps? $\endgroup$
    – mweiss
    Jun 11 '18 at 17:33
  • 4
    $\begingroup$ The double sum definition is (of course) prominently used when discussing U statistics. It is also interesting to see the sample variance as a measure of typical (squared) distance between two randomly picked points, not unlike gini impurity for a categorical variable. $\endgroup$
    – Michael M
    Jun 11 '18 at 18:46

Using symmetry, your double sum can be written as $$ s^2 = \text{ave}_{i < j} f(x_i, x_j) $$ with $f(x, y) := \frac{1}{2} (x - y)^2$ and as such is a U-statistic of degree 2 with kernel $f$ for the estimation of the parameter $\theta = E(f(X, Y)) = \ldots = \text{Var}(X)$, $X$, $Y$ iid. It is actually one of the most prominent, non-trivial examples of a U-statistic and shines accordingly in theoretical math stats classes.

Being a U-statistic is nice because e.g.

  • a U-statistic is automatically "optimal" in the sense of being U-nbiased with minimum variance (bye-bye Rao-Blackwell theorem) and

  • there is a (more or less explicit) formula for its variance and thus its standard error.

Nevertheless, this alternative representation of the sample variance $s^2$ is rarely used in practice although, as you mentioned, it seems to highlight a different aspect of variation ("typical squared difference between two random picks" instead of "typical squared difference between random pick and mean").

The U-statistics representation of $s^2$ always reminds me of Gini impurity used in decision tree learning where that often plays the role of variance for categorical responses. For a discrete random variable $Z$ with levels $z_1, \dots, z_m$ and $\text{Pr}(Z = z_j) = p_j$, it is defined as $$ I(Z) = 1 - \sum_{j = 1}^m p_i^2 = \sum_{i}\sum_{j \ne i} p_i p_j, $$ and as such is the probability of two random picks not being equal (again something like a typical difference between two random picks).


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