نمایش مبدأ برای الگوریتم محاسبه واریانس

== الگوریتم Naïve ==
فرمول محاسبه واریانس [[جامعه آماری]] با اندازه ''N'' به این صورت است:

:<math>\sigma^2 = \displaystyle\frac {\sum_{i=1}^N x_i^2 - (\sum_{i=1}^N x_i)^2/N}{N}. \!</math>

فرمول محاسبه تخمین [[estimator bias|unbiased]] از واریانس [[جامعه آماری]] از یک [[نمونه (آمار)|نمونه]] محدود از n مشاهده به این صورت می‌باشد:

:<math>s^2 = \displaystyle\frac {\sum_{i=1}^n x_i^2 - (\sum_{i=1}^n x_i)^2/n}{n-1}. \!</math>

بنابراین الگوریتم naive برای محاسبه واریانس تخمینی به صورت زیر می‌باشد:

<syntaxhighlight lang="python">
def naive_variance(data):
    n = 0
    Sum = 0
    Sum_sqr = 0
    
    for x in data:
        n = n + 1
        Sum = Sum + x
        Sum_sqr = Sum_sqr + x*x
     
    variance = (Sum_sqr - (Sum*Sum)/n)/(n - 1)
    return variance
</syntaxhighlight>

این الگوریتم به راحتی می‌تواند برای محاسبه واریانس یک جامعه محدود به کار رود: فقط کافیست که در خط آخر به جای تقسیم بر ''N''، بر ''n''&nbsp;−&nbsp;1 تقسیم گردد.
چون <code>Sum_sqr</code> و <code>(Sum*Sum)/n</code> می‌توانند مقدار بسیار نزدیکی داشته باشند، تقریب زدن می‌تواند منجر شود که دقت نتیجه بسیار کمتر از دقت ذاتی موجود در محاسبات [[ممیز شناور]] شود. بنابراین این الگوریتم نباید در عمل مورد استفاده قرار گیرد.<ref name="Einarsson2005">{{cite book|author=Bo Einarsson|title=Accuracy and Reliability in Scientific Computing|url=http://books.google.com/books?id=8hrDV5EbrEsC|accessdate=17 February 2013|date=1 August 2005|publisher=SIAM|isbn=978-0-89871-584-2|page=47}}</ref><ref name="Chan1983">{{cite journal|url=http://www.cs.yale.edu/publications/techreports/tr222.pdf|author=T.F.Chan, G.H. Golub and R.J. LeVeque|title="Algorithms for computing the sample variance: Analysis and recommendations", The American Statistician, 37|pages=242–247|year=1983}}</ref> این موضوع بخصوص در مواردی که [[انحراف معیار]] نسبت به میانگین بسیار کوچک است، تشدید می‌شود. اگرچه، این الگوریتم می‌تواند با استفاده از روش میانگین مفروض بهبود یابد.

== الگوریتم دومرحله‌ای ==
یک روش جایگزین، استفاده از فرمول دیگری برای محاسبه واریانس می‌باشد، به این صورت که ابتدا [[میانگین و کوواریانس نمونه|میانگین نمونه]] را محاسبه می‌کند:

:<math>\bar x = \displaystyle \frac {\sum_{j=1}^n x_j}{n}</math>,
و سپس مجموع مربعات فاصله از میانگین را بدست می‌آورد:
:<math>\mathrm{variance} = s^2 = \displaystyle\frac {\sum_{i=1}^n (x_i - \bar x)^2}{n-1} \!</math>,
S برابر با مقدار انحراف معیار است، که با استفاده از [[شبه کد]] زیر به دست می‌آید:

<syntaxhighlight lang="python">
def two_pass_variance(data):
    n    = 0
    sum1 = 0
    sum2 = 0
    
    for x in data:
        n    = n + 1
        sum1 = sum1 + x
    
    mean = sum1/n

    for x in data:
        sum2 = sum2 + (x - mean)*(x - mean)
    
    variance = sum2/(n - 1)
    return variance
</syntaxhighlight>

این الگوریتم همواره از لحاظ عددی، سازگار است، مگر برای nهای بزرگ.<ref name="Einarsson2005"/><ref>{{cite book|first=Nicholas | last=Higham |title=Accuracy and Stability of Numerical Algorithms (2 ed) (Problem 1.10)| publisher=SIAM|year=2002}}</ref>   اگرچه می‌تواند برای نمونه‌هایی که در شرایط زیر صدق می‌کنند، دارای خطا باشد:
1.	اکثر داده‌های آن، بسیار نزدیک به میانگین(و نه برابر با آن) باشند.
2.	فقط تعداد اندکی از داده‌ها، با فاصلهٔ بسیار زیاد از میانگین باشند.{{Citation needed|date=November 2011}}.<!-- The first algorithm has less subtractions, that are a common form of losing precision in algorithms implemented in finite precision computers.-->
نتایج هر دو الگوریتم می‌تواند بی اندازه، به ترتیب [[داده ها]] وابسته باشد و می‌تواند نتایج ضعیفی برای مجموعه داده‌های بسیار بزرگ (بخاطر تکرر خطای گرد کردن) داشته باشد. تکنیکهایی همچون مجموعِ جبران شده می‌تواند تا درجه‌ای برای از بین بردن این خطا مورد استفاده قرار گیرند.

=== مغایرت جبران شده ===
نسخهٔ مجموعِ جبران شده از الگوریتم فوق بدین صورت است:<ref name=":0"/><!--Where did this algorithm come from?  It is not the normal form for a Kahan summation.-->

<syntaxhighlight lang="python">
def compensated_variance(data):
    n = 0
    sum1 = 0
    for x in data:
        n = n + 1
        sum1 = sum1 + x
    mean = sum1/n
     
    sum2 = 0
    sum3 = 0
    for x in data:
        sum2 = sum2 + (x - mean)**2
        sum3 = sum3 + (x - mean)
    variance = (sum2 - sum3**2/n)/(n - 1)
    return variance
</syntaxhighlight>

== الگوریتم برخط ==
محاسبهٔ واریانس در یک مرحله، اغلب می‌تواند بسیار مفید باشد، به عنوان مثال، وقتی داده‌ها در حال جمع‌آوری هستند و فضای کافی برای ذخیره همه داده‌ها نداریم، یا موقعی که هزینه دسترسی به حافظه، بر هزینه محاسبات تأثیر زیادی دارد. برای چنین [[الگوریتم برخط]]<nowiki/>ی، رابطه رخداد مجدد بین کمیتهایی مورد استفاده در محاسبات، مورد نیاز می‌باشد تا محاسبات ما به صورت به روشی سازگار انجام شود.
فرمول‌های زیر برای به روزرسانی [[میانگین]] و واریانس(تخمینی) داده‌ها، در زمان افزودن عنصر جدید <math>x_{\mathrm{new}}</math> استفاده می‌شود. در اینجا، ''{{overline|x}}<sub>n</sub>'' نشان دهنده میانگین ''n'' نمونهٔ اول (''x''<sub>1</sub>, ..., ''x<sub>n</sub>'') و ''s''<sup>2</sup><sub>''n''</sub> واریانس نمونه و ''σ''<sup>2</sup><sub>''N''</sub> واریانس جامعهٔ آماری آنهاست.

:<math>\bar x_n = \frac{(n-1) \, \bar x_{n-1} + x_n}{n} = \bar x_{n-1} + \frac{x_n - \bar x_{n-1}}{n} \!</math>

:<math>s^2_n = \frac{(n-2)}{(n-1)} \, s^2_{n-1} + \frac{(x_n - \bar x_{n-1})^2}{n}, \quad n>1 </math>

:<math>\sigma^2_N = \frac{(N-1) \, \sigma^2_{N-1} + (x_N - \bar x_{N-1})(x_N - \bar x_{N})}{N}.</math>

همچنین می‌توان نشان داد که کمیت مناسبتر برای به روزرسانی مجموع مربعات فاصله از میانگین کنونی (<math>\textstyle\sum_{i=1}^n (x_i - \bar x_n)^2</math>)، با عنوان <math>M_{2,n}</math> دراینجا نشان داده شده‌است:

:<math>M_{2,n}\! = M_{2,n-1} + (x_n - \bar x_{n-1})(x_n - \bar x_n)</math>
:<math>s^2_n = \frac{M_{2,n}}{n-1}</math>
:<math>\sigma^2_N = \frac{M_{2,N}}{N}</math>

یک الگوریتم عددی سازگار به صورت زیر داده شده‌است، که البته میانگین را نیز محاسبه می نماید. این الگوریتم، منتسب به Knuth<ref>[[دانلد کنوت]] (1998). ''[[هنر برنامه‌نویسی رایانه]]'', volume 2: ''Seminumerical Algorithms'', 3rd edn., p. 232. Boston: Addison-Wesley.</ref> است که او نیز از [[الگوریتم|الگوریتمی]] از Welford<ref>B. P. Welford (1962).[http://www.jstor.org/stable/1266577 "Note on a method for calculating corrected sums of squares and products"]. ''[[Technometrics]]'' 4(3):419–420.</ref> استفاده کرده و به صورت کامل تحلیل نموده‌است.<ref>Chan, Tony F.; Golub, Gene H.; LeVeque, Randall J. (1983). Algorithms for Computing the Sample Variance: Analysis and Recommendations. The American Statistician 37, 242-247. http://www.jstor.org/stable/2683386</ref><ref>Ling, Robert F. (1974). Comparison of Several Algorithms for Computing Sample Means and Variances. Journal of the American Statistical Association, Vol. 69, No. 348, 859-866. {{doi|10.2307/2286154}}</ref> همچنین معمول است که متغیرهای زیر به جای همدیگر استفاده شوند:
<math>M_k = \bar x_k</math> and <math>S_k = M_{2,k}</math><ref>http://www.johndcook.com/standard_deviation.html</ref>

<syntaxhighlight lang="python">
def online_variance(data):
    n = 0
    mean = 0
    M2 = 0
     
    for x in data:
        n = n + 1
        delta = x - mean
        mean = mean + delta/n
        M2 = M2 + delta*(x - mean)

    variance = M2/(n - 1)
    return variance
</syntaxhighlight>

این الگوریتم بخاطر کاهش میزان [[گرد کردن]]، می‌تواند کاهشِ دقتِ کمتری داشته باشد، اما احتمالاً نمی‌تواند خیلی بهینه باشد، چرا که عمل تقسیم درون حلقه انجام می‌شود. برای الگوریتم عظیمتر دومرحله‌ای برای محاسبه واریانس، بهتر است ابتدا تخمینی از میانگین را محاسبه کنیم و سپس در ادامه از این الگوریتم استفاده نماییم.
[[الگوریتم موازی]] که در ادامه خواهد آمد، نشان می‌دهد که چگونه چندین مجموعه آماری را که به صورت برخط محاسبه می‌شوند، ادغام نمود.

== الگوریتم افزایشی وزن دار ==
این الگوریتم می‌تواند برای کنترل نمونه‌های دارای وزن تعمیم یابد، بدین صورت که می‌توان شمارنده ''n'' را برای مجموع وزنهایی مشاهده شده تاکنون استفاده کرد. West (1979) <ref>D. H. D. West (1979). ''[[Communications of the ACM]]'', 22, 9, 532-535: ''Updating Mean and Variance Estimates: An Improved Method''</ref> این الگوریتم افزایشی را پیشنهاد می‌دهد:

<syntaxhighlight lang="python">
def weighted_incremental_variance(dataWeightPairs):
    sumweight = 0
    mean = 0
    M2 = 0

    for x, weight in dataWeightPairs:  # Alternatively "for x, weight in zip(data, weights):"
        temp = weight + sumweight
        delta = x - mean
        R = delta * weight / temp
        mean = mean + R
        M2 = M2 + sumweight * delta * R  # Alternatively, "M2 = M2 + weight * delta * (x−mean)"
        sumweight = temp

    variance_n = M2/sumweight
    variance = variance_n * len(dataWeightPairs)/(len(dataWeightPairs) - 1)
</syntaxhighlight>

== الگوریتم موازی ==
Chan et al.<ref name=":0">{{Citation
 |last1            = Chan
 |first1           = Tony F.
 |author1-link     = Tony F. Chan
 |last2            = Golub
 |first2           = Gene H.
 |author2-link     = Gene H. Golub
 |last3            = LeVeque
 |first3           = Randall J.
 |contribution     = Updating Formulae and a Pairwise Algorithm for Computing Sample Variances.
 |title            = Technical Report STAN-CS-79-773
 |publisher        = Department of Computer Science, Stanford University
 |year             = 1979
 |contribution-url = ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/79/773/CS-TR-79-773.pdf
}}{{پیوند مرده|date=ژانویه 2021 |bot=InternetArchiveBot }}.</ref> می‌گوید که سومین الگوریتم برخط فوق، نمونه‌ای خاص از الگوریتم است که برای هر تقسیم‌بندی از نمونه <math>X</math> به مجموعه‌های <math>X_A</math>, <math>X_B</math> درست عمل می‌کند:

:<math>\delta\! = \bar x_B - \bar x_A</math>
:<math>\bar x_X = \bar x_A + \delta\cdot\frac{n_B}{n_X}</math>
:<math>M_{2,X} = M_{2,A} + M_{2,B} + \delta^2\cdot\frac{n_A n_B}{n_X}</math>.
این موضوع می‌تواند زمانی مفید باشد که برای مثال، چندین واحد پرداش برای قسمت‌های مختلف از ورودی در نظر گرفته شده باشد.
شیوه Chan روشی برای تخمین میانگین، زمانی که <math>n_A \approx n_B</math> و هر دو بسیار بزرگ باشند، از لحاظ عددی نامطمئن است، چراکه خطای عددی موجود در <math>\bar x_B - \bar x_A</math> متناسب با زمانی نیست که <math>n_B = 1</math>. در چنین مواردی، <math>\bar x_X = \frac{n_A \bar x_A + n_B \bar x_B}{n_A + n_B}</math> ترجیح داده می‌شود.

== مثال ==
فرض کنید که عملیات ممیز شناور از استاندارد محاسباتی  [[IEEE 754#Double-precision 64 bit|IEEE 754 double-precision]] استفاده می‌کند. نمونهٔ {4، 7، 13، 16} را از یک جامعه آماری نامحدود فرض کنید. براساس این نمونه، میانگین تخمینی جامعه برابر با 10 است و واریانس تخمینی بدون پیشقدرِ جامعه برابر با 30 است. هر دو الگوریتم اول و دوم این مقادیر را به درستی محاسبه می‌کند. سپس نمونه { 10<sup>8</sup>&nbsp;+&nbsp;4, 10<sup>8</sup>&nbsp;+&nbsp;7, 10<sup>8</sup>&nbsp;+&nbsp;13, 10<sup>8</sup>&nbsp;+&nbsp;16 } را در نظر بگیرید، که مقدار واریانسی برابر با نمونهٔ قبلی به ما می‌دهد. الگوریتم دوم این واریانس تخمینی را به درستی محاسبه می‌کند، اما الگوریتم اول مقدار 29.33333333 را به جای 30 برمی‌گرداند. اگرچه این کمبود دقت قابل تحمل است و به عنوان نقص کوچکی در الگوریتم اول مشاهده می‌شود، اما به سادگی داده‌هایی یافت که نقص اساسی در الگوریتم naive را آشکار میسازد: نمونهٔ { 10<sup>9</sup>&nbsp;+&nbsp;4, 10<sup>9</sup>&nbsp;+&nbsp;7, 10<sup>9</sup>&nbsp;+&nbsp;13, 10<sup>9</sup>&nbsp;+&nbsp;16 } را در نظر بگیرید. دوباره واریانس تخمینی برابر با 30 می‌باشد که توسط الگوریتم دوم به سادگی قابل محاسبه است، اما این دفعه الگوریتم naive مقدار −170.66666666666666 را به عنوان جواب برمی‌گرداند. این یک مشکل اساسی در الگوریتم اول می‌باشد و بخاطر تقریب زدن فاجعه آمیزی رخ داده است که در مرحله آخر الگوریتم، هنگام [[تفریق]] دو عدد مشابه صورت گرفته‌است.

== آمارهای رده بالاتر ==
Terriberry<ref>{{Citation
 | last=Terriberry
 | first=Timothy B.
 | year=2007
 | title=Computing Higher-Order Moments Online
 | url=http://people.xiph.org/~tterribe/notes/homs.html
 | accessdate=19 دسامبر 2013
 | archiveurl=https://web.archive.org/web/20140423031833/http://people.xiph.org/~tterribe/notes/homs.html
 | archivedate=23 آوریل 2014
 | dead-url=yes
 }}</ref> فرمول Chan را برای محاسبه سومین و چهارمین [[گشتاور]] مرکزی تعمیم می‌دهد. برای مثال برای تخمین [[چولگی]] و [[کشیدگی]] مورد نیاز است:

:<math>M_{3,X} = M_{3,A} + M_{3,B} + \delta^3\frac{n_A n_B (n_A - n_B)}{n_X^2} + 3\delta\frac{n_AM_{2,B} - n_BM_{2,A}}{n_X}</math>
:<math>\begin{align}
M_{4,X} = M_{4,A} + M_{4,B} & + \delta^4\frac{n_A n_B \left(n_A^2 - n_A n_B + n_B^2\right)}{n_X^3} \\
                    & + 6\delta^2\frac{n_A^2 M_{2,B} + n_B^2 M_{2,A}}{n_X^2} + 4\delta\frac{n_AM_{3,B} - n_BM_{3,A}}{n_X} \\
\end{align}</math>

اینجا <math>M_k</math>  برابر با توان‌های فاصله با میانه <math>\Sigma(x - \overline{x})^k</math> است که نتیجه می‌دهد:

:چولگی: <math>g_1 = \frac{\sqrt{n} M_3}{M_2^{3/2}},</math>
:کشیدگی: <math>g_2 = \frac{n M_4}{M_2^2}-3.</math>

برای نسخه افزایشی (مثلاً <math>B = \{x\}</math>)، به صورت زیر ساده می‌شود:

:<math>\delta\! = x - m</math>
:<math>m' = m + \frac{\delta}{n}</math>
:<math>M_2' = M_2 + \delta^2 \frac{ n-1}{n}</math>
:<math>M_3' = M_3 + \delta^3 \frac{ (n - 1) (n - 2)}{n^2} - \frac{3\delta M_2}{n}</math>
:<math>M_4' = M_4 + \frac{\delta^4 (n - 1) (n^2 - 3n + 3)}{n^3} + \frac{6\delta^2 M_2}{n^2} - \frac{4\delta M_3}{n}</math>

با نگهداشتن مقدار <math>\delta / n</math>، فقط یک عمل تقسیم مورد نیاز است و آمار رده بالاتر می‌تواند بنابراین برای هزینه افزایشی محاسبه شود.
مثال الگوریتم برخط برای کشیدگی به صورت زیر پیاده‌سازی شده‌است:

<syntaxhighlight lang="python">
def online_kurtosis(data):
    n = 0
    mean = 0
    M2 = 0
    M3 = 0
    M4 = 0

    for x in data:
        n1 = n
        n = n + 1
        delta = x - mean
        delta_n = delta / n
        delta_n2 = delta_n * delta_n
        term1 = delta * delta_n * n1
        mean = mean + delta_n
        M4 = M4 + term1 * delta_n2 * (n*n - 3*n + 3) + 6 * delta_n2 * M2 - 4 * delta_n * M3
        M3 = M3 + term1 * delta_n * (n - 2) - 3 * delta_n * M2
        M2 = M2 + term1

    kurtosis = (n*M4) / (M2*M2) - 3
    return kurtosis
</syntaxhighlight>

Pébay <ref>{{Citation
 | last=Pébay
 | first=Philippe
 | year=2008
 | contribution=Formulas for Robust, One-Pass Parallel Computation of Covariances and Arbitrary-Order Statistical Moments
 | title=Technical Report SAND2008-6212
 | publisher=Sandia National Laboratories
 | contribution-url=http://infoserve.sandia.gov/sand_doc/2008/086212.pdf
 | accessdate=۱۹ دسامبر ۲۰۱۳
 | archive-date=۹ اكتبر ۲۰۲۲
 | archive-url=https://ghostarchive.org/archive/20221009/http://infoserve.sandia.gov/sand_doc/2008/086212.pdf
 | url-status=dead
 }}</ref> سپس این نتایج را برای گشتاورهای مرکزیِ رده-اختیاری، برای موارد افزایشی و دوبه دو تعمیم داد. می‌توان فرمول‌های مشابهی را برای [[کوواریانس]] یافت.
Choi و Sweetman<ref name="Choi2010">{{Citation
 |last1       = Choi
 |first1      = Muenkeun
 |last2       = Sweetman
 |first2      = Bert
 |year        = 2010
 |title       = Efficient Calculation of Statistical Moments for Structural Health Monitoring
 |url         = http://www.rms-group.org/RMS_Papers/TAMUG_Papers/MK/Efficient_Moments_2010.pdf
 |accessdate  = ۱۹ دسامبر ۲۰۱۳
 |archiveurl  = https://web.archive.org/web/20160303181457/http://www.rms-group.org/RMS_Papers/TAMUG_Papers/MK/Efficient_Moments_2010.pdf
 |archivedate = ۳ مارس ۲۰۱۶
 |dead-url    = yes
}}</ref> دو روش جایگزین برای محاسبه چولگی و کشیدگی پیشنهاد می‌دهند، که هر کدام می‌تواند مقدار قابل ملاحظه‌ای در حافظه مورد نیاز و زمان CPU در کاربردهای معینی، صرفه جویی کند. روش اول، برای محاسبه گشتاورهای آماری، با جداسازی داده‌ها، گشتاورها را از رابطه هندسیِ هیستوگرامِ به دست آمده محاسبه می‌کند، که به صورت بهینه‌ای تبدیل به یک الگوریتم یک مرحله‌ای برای گشتاورهای بالاتر می‌شود. یکی از مزایای کار این است که محاسبات گشتاورهای آماری می‌تواند با دقت اختیاری محاسبه شود، پس می‌توان این دقت را با دقت فرمت [[انبار داده]] ویا [[سخت افزار]] [[اندازه‌گیری]] اصلی، منطبق کرد. هیستوگرام نسبی از یک [[متغیر تصادفی]] می‌تواند یک در این راه قراردادی ساخته شود: محدوده مقادیر بالقوه به بازه‌هایی تقسیم می‌شود و تعداد رخدادها در هر بازه شمارش و به گونه‌ای کشیده می‌شود که مساحت هر مستطیل برابر با سهم رخدادهای آن بازه شود:

: <math> H(x_k)=\frac{h(x_k)}{A}</math>

که <math>h(x_k)</math>  و <math>H(x_k)</math> نشاندهندهٔ میزان فرکانس و فرکانس نسبی در بازهٔ <math>x_k</math> است و <math>A= \sum_{k=1}^{K} h(x_k)
\,\Delta x_k</math>  مجموع تمام نواحی هیستوگرام است. بعد از نرمال سازی، <math>n</math> گشتاور خام و گشتاورهای مرکزیِ <math>x(t)</math> می‌تواند از هیستوگرام نسبی محاسبه شود:

: <math>
 m_n^{(h)} = \sum_{k=1}^{K}  x_k^n \, H(x_k) \Delta x_k
            = \frac{1}{A} \sum_{k=1}^{K}  x_k^n \, h(x_k) \Delta x_k
</math>

: <math>
 \theta_n^{(h)}= \sum_{k=1}^{K} \Big(x_k-m_1^{(h)}\Big)^n \, H(x_k)\Delta x_k
               = \frac{1}{A} \sum_{k=1}^{K} \Big(x_k-m_1^{(h)}\Big)^n \, h(x_k) \Delta x_k
</math>

که توان <math>^{(h)}</math> نشان دهنده گشتاورهایی است که از هیستوگرام محاسبه شده‌است. برای بازهٔ با ضخامت ثابت <math>\Delta
x_k=\Delta x</math>  این دو عبارت می‌تواند با استفاده از <math>I= A/\Delta x</math> ساده شود:

: <math>
 m_n^{(h)}= \frac{1}{I} {\sum_{k=1}^{K} x_k^n \, h(x_k)}
</math>

: <math>
 \theta_n^{(h)}= \frac{1}{I}{\sum_{k=1}^{K} \Big(x_k-m_1^{(h)}\Big)^n \, h(x_k)}
</math>

دومین روش Choi و Sweetman<ref name="Choi2010"/> یک متدولوژی تحلیلی برای ترکیب گشتاورهای آماری از بخش‌های مجزا از یک بازهٔ زمانی است که گشتاورهای کلی بدست آمده، همان گشتاورهای بازهٔ زمانی کامل است. این متدولوژی می‌تواند برای محاسبه موازی گشتاورهای آماری با کمک ترکیب گشتاورهای پس آیند(بعدی) ویا ترکیب گشتاورهای آماری محاسبه شده در زمان‌های پشت سرهم، استفاده شود.
اگر تعداد <math>Q</math> مجموعه از گشتاورهای آماری به این صورت نمایش داده شوند: <math>(\gamma_{0,q},\mu_{q},\sigma^2_{q},\alpha_{3,q},\alpha_{4,q})
\quad </math>  که در آن <math>q=1,2,...,Q </math> است، سپس هر <math>\gamma_n</math> می‌تواند براساس <math>n</math> گشتاور اولیه معادل نمایش داده شود:

: <math>
 \gamma_{n,q}= m_{n,q} \gamma_{0,q} \qquad \quad \textrm{for} \quad n=1,2,3,4  \quad \text{ and } \quad q = 1,2, \dots ,Q
</math>

که <math>\gamma_{0,q}</math>  به صورت کلی در طول <math>q^{th}</math> بازهٔ زمانی بدست آمده‌است یا تعداد نقاطی که <math>\Delta t</math>  ثابت است.
مزیت نمایش گشتاورهای آماری براساس  <math>\gamma</math> این است که <math>Q</math> مجموعه می‌توانند با عمل جمع ترکیب شوند و محدودیتی در مقدار <math>Q</math> نیست.

: <math>
 \gamma_{n,c}= \sum_{q=1}^{Q}\gamma_{n,q} \quad \quad \textrm{for} \quad n=0,1,2,3,4
</math>

در اینجا اندیس <math>_c</math> ترکیب بازه‌های زمانی یا <math>\gamma</math>ی ترکیب شده را نشان می‌دهد. این مقادیر ترکیب شده از <math>\gamma</math> می‌تواند سپس به صورت معکوس به گشتاورهای خام که تمام بازهٔ ترکیبی را نشان می‌دهند، تبدیل شوند:

: <math>
 m_{n,c}=\frac{\gamma_{n,c}}{\gamma_{0,c}} \quad \textrm{for} \quad n=1,2,3,4
</math>

روابط مشاهده شده بین گشتاورهای خام (<math>m_n</math>) و گشتاورهای مرکزی (<math> \theta_n = E[(x-\mu)^n])</math>)، سپس برای محاسبه گشتاورهای مرکزیِ ترکیبِ بازه زمانی مورد استفاده قرار می‌گیرد. در پایان، گشتاورهای آماری بازهٔ ترکیبی از گشتاورهای مرکزی محاسبه می‌شوند:

: <math>
 \mu_c=m_{1,c}
 \ \ \ \ \ \sigma^2_c=\theta_{2,c}
 \ \ \ \ \ \alpha_{3,c}=\frac{\theta_{3,c}}{\sigma_c^3}
 \ \ \ \ \ \alpha_{4,c}={\frac{\theta_{4,c}}{\sigma_c^4}}-3
</math>

== کوواریانس ==
الگوریتم‌های کاملاً مشابهی هم می‌تواند برای محاسبه [[کوواریانس]] به کار برده شود. الگوریتم naive بدین صورت در می‌آید:

:<math>\operatorname{Cov}(X,Y) = \displaystyle\frac {\sum_{i=1}^n x_i y_i - (\sum_{i=1}^n x_i)(\sum_{i=1}^n y_i)/n}{n}. \!</math>

برای الگوریتم فوق می‌توان شبه کد زیر را استفاده کرد:
<syntaxhighlight lang="python">
def naive_covariance(data1, data2):
    n = len(data1)
    sum12 = 0
    sum1 = sum(data1)
    sum2 = sum(data2)

    for i in range(n):
        sum12 += data1[i]*data2[i]

    covariance = (sum12 - sum1*sum2 / n) / n
    return covariance
</syntaxhighlight>

یک الگوریتم دو مرحله‌ای مطمئن تر از لحاظ عددی، ابتدا میانه‌های میانگین را محاسبه می‌کند و سپس کوواریانس را به دست می‌آورد:
:<math>\bar x = \displaystyle \sum_{i=1}^n x_i/n</math>
:<math>\bar y = \displaystyle \sum_{i=1}^n y_i/n</math>
:<math>\operatorname{Cov}(X,Y) = \displaystyle\frac {\sum_{i=1}^n (x_i - \bar x)(y_i - \bar y)}{n}. \!</math>

الگوریتم دومرحله‌ای می‌تواند به صورت زیر نوشته شود:
<syntaxhighlight lang="python">
def two_pass_covariance(data1, data2):
    n = len(data1)

    mean1 = sum(data1) / n
    mean2 = sum(data2) / n	

    covariance = 0

    for i in range(n):
        a = data1[i] - mean1		
        b = data2[i] - mean2
        covariance += a*b / n

    return covariance
</syntaxhighlight>

یک نسخهٔ جبرانی با دقت بالاتر، الگوریتم naive را بر روی باقی‌مانده‌ها انجام می‌دهد. مجموع نهایی <math>\textstyle\sum y_i</math> و  <math>\textstyle\sum x_i</math> ''باید'' صفر شود، اما مرحله دوم هرگونه خطای کوچکی را جبران کند.
یک الگوریتم تک مرحله‌ای مطمئنی، مشابه با مورد بالا، وجود دارد، که گشتاورهای مشترک <math>\textstyle C_n = \sum_{i=1}^n (x_i - \bar x_n)(y_i - \bar y_n)</math> را محاسبه می‌کند:
:<math>\bar x_n = \bar x_{n-1} + \frac{x_n - \bar x_{n-1}}{n} \!</math>
:<math>\bar y_n = \bar y_{n-1} + \frac{y_n - \bar y_{n-1}}{n} \!</math>
:<math>C_n = C_{n-1} + (x_n - \bar x_n)(y_n - \bar y_{n-1}) = C_{n-1} + (y_n - \bar y_n)(x_n - \bar x_{n-1})</math>
عدم تقارن آشکار در تساوی آخر بخاطر این است که <math>\textstyle (x_n - \bar x_n) = \frac{n-1}{n}(x_n - \bar x_{n-1})</math>، پس هر دو عبارت به روزرسانی برابرند با: <math>\textstyle \frac{n-1}{n}(x_n - \bar x_{n-1})(y_n - \bar y_{n-1})</math> .  با محاسبهٔ میانگین‌ها می‌توان به دقت بالاتری دست یافت، سپس بااستفاده از الگوریتم تک مرحله‌ای مطمئن بر روی بقیه استفاده کرد.
بنابراین ما می‌توانیم کوواریانس را به این صورت به دست آوریم:
:<math>\begin{align}
\operatorname{Cov}_N(X,Y) = \frac{C_N}{N} &= \frac{\operatorname{Cov}_{N-1}(X,Y)\cdot(N-1) + (x_n - \bar x_n)(y_n - \bar y_{n-1})}{N}\\
   &= \frac{\operatorname{Cov}_{N-1}(X,Y)\cdot(N-1) + (y_n - \bar y_n)(x_n - \bar x_{n-1})}{N}\\
   &= \frac{\operatorname{Cov}_{N-1}(X,Y)\cdot(N-1) + \frac{N-1}{N}(x_n - \bar x_{n-1})(y_n - \bar y_{n-1})}{N}.
\end{align}</math>

به همین ترتیب، فرمولی برای ترکیب کوواریانس دو مجموعه برای موازی‌سازی محاسبات وجود دارد:
:<math>C_X = C_A + C_B + (\bar x_A - \bar x_B)(\bar y_A - \bar y_B)\cdot\frac{n_A n_B}{n_X}</math>.

== منابع ==
{{پانویس|۲|چپ‌چین=بله}}

== پیوند به بیرون ==
* {{MathWorld|title=Sample Variance Computation|urlname=SampleVarianceComputation}}

[[رده:الگوریتم‌های آماری]]
[[رده:انحراف و پراکندگی آماری]]