Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have about 3.5GB worth of data that I need to get statistics from, all split up into about 71MB files, with an (approximately) equal number of samples. From this data, I would like to gather mean and standard deviation. Parsing the entirety of the standard deviation is probably a bad idea, since it's 3.5GB.

However, I know that with mean, I can at least (with some accuracy, since they're approximately the same size), take the average for each file, and then take the average of each of those sub-averages.

With standard deviation, it's a little more tricky, though. I've taken some time to run tests and found out that the standard deviation of a large sample size seems to be approximately similar to the average of the standard deviations of equivalently sized smaller chunks of samples. Does this actually hold true, or was that just a coincidence within the few tests that I've run? If it does hold true, then can I calculate what my percent error is probably going to be? Finally, is there a more accurate way to test for standard deviation that doesn't require me mulling over 3.5GB of data at a time?

share|improve this question
1  
I don't see why you can't process the whole body of data. 3.5 GB is not all that large, and computing mean and standard deviation is very simple. Just make sure your arithmetic has enough precision that later samples aren't lost to rounding. –  Nate Eldredge May 4 '11 at 15:00
    
Note: If every sample were 1 byte, and you could only process 1 million per second, processing 3.5 GB would only take 1 hour - and this estimate is probably 1-3 orders of magnitude too high. –  Nate Eldredge May 4 '11 at 15:06
    
@Nate: This is true, and I still might do it for "fun," but I really just needed a "quick and dirty" way to get the results as soon as possible. Even though calculating the standard deviation would only take an hour by that time, I would have to double that, because first I would have to go through the entire thing and parse the average, unless I'm thinking about this all wrong. –  ashays May 4 '11 at 15:50
    
You can do it in one pass. See my answer. –  Nate Eldredge May 4 '11 at 19:15
add comment

3 Answers

Posting as an answer in response to comments.

Here's a way to compute the mean and standard deviation in one pass over the file. (Pseudocode.)

n = r1 = r2 = 0;
while (more_samples()) {
    s = next_sample();
    n += 1;
    r1 += s;
    r2 += s*s;
}
mean = r1 / n;
stddev = sqrt(r2/n - (mean * mean));

Essentially, you keep a running total of the sum of the samples and the sum of their squares. This lets you easily compute the standard deviation at the end.

share|improve this answer
3  
The computation for standard deviation can be unstable, most especially for sample sizes as large as the OP's since if the data's variance is small relative to the sizes of the elements, the square of the mean has the same order of magnitude as the mean of the squares, resulting in subtractive cancellation. Fortunately, there is a better way, due to Chan, Golub, and LeVeque. See their paper for details. –  J. M. May 4 '11 at 19:39
    
@J.M. after quickly scanning the paper, I was unable to locate the best one-pass algorithm. But using the table at the back, the "textbook algorithm" given by @Nate seems to be the best solution. In any case this is the one that I put into practice, and my results seem logical. –  ashays May 6 '11 at 2:15
    
@ashays: If the variance is not much tinier than the data entries, then yes, one-pass is sufficient. If the variance is much smaller relative to the data entries, you have to use the corrected two-pass scheme. –  J. M. May 6 '11 at 3:32
add comment

You seem to have about $f=50$ files. If you know the mean $\mu_i$ and variance $\sigma_i^2$ (square of the standard deviation) and number of elements $n_i$ of each file, then your overall mean should be

$$\mu = \frac{\sum_{i=1}^{f} n_i \mu_i }{\sum_{i=1}^{f} n_i}$$

and your overall variance

$$\sigma^2 = \frac{\sum_{i=1}^{f} n_i \left(\sigma_i^2 +(\mu_i-\mu)^2\right) }{\sum_{i=1}^{f} n_i}.$$

If you have forgotten to collect the number of elements of each file but are confident they are each the same then you can use

$$\mu = \frac{1}{f}\sum_{i=1}^{f} \mu_i $$

which is the mean of the means, and

$$\sigma^2 = \frac{1}{f}\sum_{i=1}^{f} \left(\sigma_i^2 +(\mu_i-\mu)^2\right) .$$

The wrong thing to do would be taking the average of the standard deviations (or even the average of the variances), since this would ignore the effect of the differences in the means and so produce a result which was too small.

share|improve this answer
add comment

You have a sampling problem. I would treat your large sample as a population, and then sample from that. First take a random sample of data, and test that the data is normally distributed and free of outliers. Then compute the sample standard deviation along with confidence intervals using a chi-square distribution.

$$\sqrt{\frac{(n-1)s^2}{\chi^2\left(df,\frac{\alpha}{2}\right)}} < \sigma < \sqrt{\frac{(n-1)s^2}{\chi^2\left(df,1-\frac{\alpha}{2}\right)}}$$

Bear in mind that there will always be a margin of error unless you compute the entire population, which seems impractical in your case.

share|improve this answer
    
Could you define your terms for me? It's been years since I've taken a statistics course. Essentially, I just need the definitions of $s^2$, $df$, and $\alpha$. Thanks! –  ashays May 4 '11 at 15:02
    
s2 = the square of the computed standard deviation. df = degrees of freedom (sample size -1), and alpha is the signficance level (typical between .05 and .10) –  Ralph Winters May 4 '11 at 15:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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