Editing Standard deviation (section)

==Rapid calculation methods==
{{See also|Algorithms for calculating variance}}
The following two formulas can represent a running (repeatedly updated) standard deviation. A set of two power sums {{math|{{var|s}}{{sub|1}}}} and {{math|{{var|s}}{{sub|2}}}} are computed over a set of {{mvar|N}} values of {{mvar|x}}, denoted as {{math|{{var|x}}{{sub|1}}, ..., {{var|x}}{{sub|{{var|N}}}}}}:

<math display="block">s_j = \sum_{k=1}^N{x_k^j}.</math>

Given the results of these running summations, the values {{mvar|N}}, {{math|{{var|s}}{{sub|1}}}}, {{math|{{var|s}}{{sub|2}}}} can be used at any time to compute the ''current'' value of the running standard deviation:

<math display="block">\sigma = \frac{\sqrt{Ns_2 - s_1^2}}{N}</math>

Where {{mvar|N}}, as mentioned above, is the size of the set of values (or can also be regarded as {{math|{{var|s}}{{sub|0}}}}).

Similarly for sample standard deviation,

<math display="block">s = \sqrt{\frac{Ns_2 - s_1^2}{N(N - 1)}}.</math>

In a computer implementation, as the two {{math|{{var|s}}{{sub|{{var|j}}}}}} sums become large, we need to consider [[round-off error]], [[arithmetic overflow]], and [[arithmetic underflow]]. The method below calculates the running sums method with reduced rounding errors.<ref>{{cite journal |last=Welford |first=B. P. |title=Note on a Method for Calculating Corrected Sums of Squares and Products |journal=Technometrics |volume=4 |issue=3 |date=August 1962 |pages=419–420 |doi=10.1080/00401706.1962.10490022|citeseerx=10.1.1.302.7503 }}</ref> This is a "one pass" algorithm for calculating variance of {{mvar|n}} samples without the need to store prior data during the calculation. Applying this method to a time series will result in successive values of standard deviation corresponding to {{mvar|n}} data points as {{mvar|n}} grows larger with each new sample, rather than a constant-width sliding window calculation.

For {{math|{{var|k}} {{=}} 1, ..., {{var|n}}}}:

<math display="block">\begin{align}
  A_0 &= 0\\
  A_k &= A_{k-1} + \frac{x_k - A_{k-1}}{k}
\end{align}</math>

where {{mvar|A}} is the mean value.
<math display="block">\begin{align}
  Q_0 &= 0 \\
  Q_k &= Q_{k-1} + \frac{k-1}{k} \left(x_k - A_{k-1}\right)^2 = Q_{k-1} + \left(x_k - A_{k-1}\right)\left(x_k - A_k\right)
\end{align}</math>

Note: {{math|{{var|Q}}{{sub|1}} {{=}} 0}} since {{math|{{var|k}} &minus; 1 {{=}} 0}} or {{math|{{var|x}}{{sub|1}} {{=}} {{var|A}}{{sub|1}}}}.

Sample variance:
<math display="block">s^2_n = \frac{Q_n}{n - 1}</math>

Population variance:
<math display="block">\sigma^2_n = \frac{Q_n}{n}</math>

===Weighted calculation===
<!--N.B. the apparently superfluous trailing \0 in the <math> equations prevents conversion of simple formulas to HTML, resulting in more consistent formatting.-->
When the values <math>x_k</math> are weighted with unequal weights <math>w_k</math>, the power sums {{math|{{var|s}}{{sub|0}}, {{mvar|s}}{{sub|1}}, {{var|s}}{{sub|2}}}} are each computed as:

<math display="block">s_j = \sum_{k=1}^N w_k x_k^j.\,</math>

And the standard deviation equations remain unchanged. {{math|{{var|s}}{{sub|0}}}} is now the sum of the weights and not the number of samples {{mvar|N}}.

The incremental method with reduced rounding errors can also be applied, with some additional complexity.

A running sum of weights must be computed for each {{mvar|k}} from 1 to {{mvar|n}}:
<math display="block">\begin{align}
  W_0 &= 0 \\
  W_k &= W_{k-1} + w_k
\end{align}</math>

and places where {{math|1/{{var|k}}}} is used above must be replaced by <math>w_k/W_k</math>:
<math display="block">\begin{align}
  A_0 &= 0 \\
  A_k &= A_{k-1} + \frac{w_k}{W_k}\left(x_k - A_{k-1}\right) \\
  Q_0 &= 0 \\
  Q_k &= Q_{k-1} + \frac{w_k W_{k-1}}{W_k}\left(x_k  -A_{k-1}\right)^2 = Q_{k-1} + w_k\left(x_k-A_{k-1}\right)\left(x_k - A_k\right)
\end{align}</math>

In the final division,
<math display="block">\sigma^2_n = \frac{Q_n}{W_n}\,</math>

and
<math display="block">s^2_n = \frac{Q_n}{W_n - 1},</math>

or 
<math display="block">s^2_n = \frac{n'}{n' - 1} \sigma^2_n,</math>

where {{mvar|n}} is the total number of elements, and {{mvar|{{prime|n}}}} is the number of elements with non-zero weights.

The above formulas become equal to the simpler formulas given above if weights are taken as equal to one.