0
$\begingroup$

This is probably a naive question...

Why do we use something like standard deviation to measure variability, as opposed to something based on the difference between all pairs in a sample?

In other words, why do we use difference from the mean, and not just difference between all pairs of samples? Is there any advantage?

I'm doing something multivariate, which motivates my question.

$\endgroup$
0
$\begingroup$

Because the number of pairs to consider grows quadratic-ally in the number of examples. Suppose we have 1,000,000 examples. For a mean, we just have to sum and divide by 1,000,000. For the median we need to sort and take the middle element. That takes roughly $n \log{n} \approx 20,000,000$ operations. However when we want to do something with every pair, we need to consider all 499,999,500,000 pairs. An enormous amount and a lot slower than a median or mean.

$\endgroup$
1
  • $\begingroup$ Great point. For the problem I'm solving though, that's not an issue. Since I'm using multivariate dispersion, I have to calculate pairwise distances anyways. Is there any advantage other than that? $\endgroup$
    – Hallo
    Nov 25 '16 at 16:13

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.