How to Compute Standard Deviation in One Pass

Unbiased Estimator of Sample Standard Deviation

The formula for the sample standard deviation is

where

N is the number of data points in your sample. The first formula is known as the unbiased estimator of sample standard deviation. This is a technical detail but the (N-1) in the denominator makes the estimator unbiased. When N is large N vs. (N-1) does not matter but when N is small you should use (N-1).

Computing std in 1 pass

If someone asks you to write a simple program to compute the standard deviation and if you decide to use the formula shown above then you have to compute the average first then compute the standard deviation which means you have to make 2 passes over the data points.

You should know that there is an algebraic identity you can take advantage of to compute the standard deviation in 1 pass.

using this algebraic identity we can write the std as

.

Example Program in C#

The C# code below implements the last formula for the sample standard deviation

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace example_std_stderr
{
  class Program
  {
    static void Main(string[] args)
    {
      // we need a data set
      // let’s populate an array with data points
      // it does not matter what the distribution looks like
      // replace this section with your own data retrieval code
      int N = 100;
      ArrayList al = new ArrayList();
      for(int i=0; i<N; i++)
      {
        double val = Math.Exp(-(double)i/N);
        al.Add(val);
      }
      double[] arr = (double[])al.ToArray(typeof(double));

      // compute the sampling standard deviation in 1 pass
      double sum1 = 0;
      double sum2 = 0;
      for(int i=0; i < arr.Length; i++)
      {
         sum1 += arr[i] * arr[i];
         sum2 += arr[i];
      }

      double mean_val = sum2 / arr.Length;
      double sample_variance =
      (sum1 – arr.Length * mean_val * mean_val) / (arr.Length -1);

      double sample_std_deviation = Math.Sqrt(sample_variance);    
    }
  }
}
Advertisements

About Suresh Emre

I have worked as a physicist at the Fermi National Accelerator Laboratory and the Superconducting Super Collider Laboratory. I am a volunteer for the Renaissance Universal movement. My main goal is to inspire the reader to engage in Self-discovery and expansion of consciousness.
This entry was posted in tutorial and tagged . Bookmark the permalink.