Skip to main content

5  Algorithms for Means, Variances, and Covariances

Many algorithms for computing means, variances, and covariances are imprecise and may produce final results containing large errors. The need to use efficient algorithms for these simple tasks is evident, and they will be described in this chapter.

5.1 Introduction

Fortunately, Python uses accurate algorithms for computing the mean, variance, and covariance. We will seek to clarify how the use of inefficient algorithms can lead to inconsistent and imprecise results. Our objective in this chapter is to present efficient algorithms for estimating these parameters when the conventional formulas may fail if used directly in the algorithms.

These efficient algorithms are particularly useful when the data have large magnitude or are very close to zero. In this particular case, some spreadsheet programs, such as Excel in its older versions, could fail (McCullough and Wilson 1999). Knowledge of algorithms that lead to greater numerical precision can prevent the researcher from making the same mistakes found in some software.

5.2 Univariate Algorithms

The basic idea of using algorithms for the mean, for the sum of powers of deviations from the mean, or for the sum of products of deviations is to apply the existing formulas recursively. If we wish, for example, to obtain the mean of \(n\) observations, we can initially compute the mean of the first observation, which is the observation itself. In a second stage, we propose an expression to update the mean of the first observation, incorporating the second one, and so on. The same updating procedure is applied to variances or covariances when we have more than one variable.

For a sample of size \(n\) given by \(X_1\), \(X_2\), \(\cdots\), \(X_n\), the conventional sample mean and variance are obtained, respectively, by:

\[ \bar{X}_. = \dfrac{\displaystyle \sum_{i=1}^n X_i}{n}, \tag{5.1}\] and \[ S^2 = \dfrac{1}{n-1}\left[\sum_{i=1}^n X_i^2 - \dfrac{\left(\displaystyle \sum_{i=1}^n X_i\right)^2}{n}\right]. \tag{5.2}\]

Some existing algorithms have sought to improve the textbook algorithms, which are the formulas in equations (5.1 and 5.2), by making adaptations that pass through the sample twice. These algorithms can be efficient from the standpoint of precision, but they are not fast, precisely because they pass through the data twice. West (1979) proposed using an algorithm that makes a single pass, updating the mean and variance at each new observation. We can easily show that for a sample of size \(n\), the mean equals \(X_1\) if \(n=1\), \((X_1+X_2)/2\) if \(n=2\), and so on. At the \((k-1)\)-th step we can specify the estimator of the mean as: \[\begin{align*} \bar{X}_{k-1} = & \frac{\displaystyle \sum_{i=1}^{k-1} X_i}{k-1}. \end{align*}\]

At the \(k\)-th step we will have observed \(X_k\), and the updated mean is:

\[ \bar{X}_{k} = \frac{\displaystyle \sum_{i=1}^{k} X_i}{k}. \tag{5.3}\]

The question we ask is: “can we express the mean at the \(k\)-th step as a function of the mean at the \((k-1)\)-th step?” The answer to this question is yes, and the result provides the desired algorithm. From equation (5.3) we obtain: \[\begin{align*} \bar{X}_{k} = & \frac{\displaystyle \sum_{i=1}^{k-1} X_i + X_k}{k}\\ = & \frac{\displaystyle (k-1)\sum_{i=1}^{k-1} X_i}{(k-1)k}+\dfrac{X_k}{k}\\ = & \frac{\displaystyle (k-1)\bar{X}_{k-1}}{k}+\dfrac{X_k}{k}\\ = & \bar{X}_{k-1} -\frac{\bar{X}_{k-1}}{k}+\dfrac{X_k}{k} \end{align*}\] resulting in the final recursive equation \[ \bar{X}_{k} = \bar{X}_{k-1} +\dfrac{X_k-\bar{X}_{k-1}}{k}, \tag{5.4}\] for \(2\le k\le n\), where \(\bar{X}_1=X_1\).

Likewise, if we define the corrected sum of squares of the first \(k\) sample observations \(1<k\le n\) as: \[\begin{align*} W2_k = & \sum_{i=1}^k X_i^2 - \dfrac{\left(\displaystyle \sum_{i=1}^k X_i\right)^2}{k} \end{align*}\] we will see that the corresponding variance is given by \(S^2_k\) \(=\) \(W2_k/(k-1)\). If we expand this expression by isolating the \(k\)-th term and simplify the resulting expression, we obtain:

\[ \begin{aligned} W2_k = \sum_{i=1}^{k-1} X_i^2 +X_{k}^2- \dfrac{\left(\displaystyle\sum_{i=1}^{k-1} X_i +X_k\right)^2}{k}\\ = W2_{k-1} + k\left(X_k-\bar{X}_{k}\right)^2/(k-1) \end{aligned} \tag{5.5}\]

The expression we developed (5.5) is equivalent to the one presented by West (1979). This can be easily demonstrated by substituting \(\bar{X}_k\), obtained in equation (5.4), into equation (5.5), from which we obtain:

\[ W2_k = W2_{k-1} + (k-1)\left(X_k-\bar{X}_{k-1}\right)^2/k \tag{5.6}\] for \(2\le k\le n\), where \(W2_{1}=0\). The variance is obtained by \(S^2 = W2_n/(n-1)\).

To demonstrate expression (5.6) directly, we have: \[\begin{align*} W2_k = & \sum_{i=1}^{k-1} X_i^2 +X_{k}^2- \dfrac{\left(\displaystyle\sum_{i=1}^{k-1} X_i +X_k\right)^2}{k}\\ = & \sum_{i=1}^{k-1} X_i^2 +X_k^2 - \dfrac{\left(\displaystyle\sum_{i=1}^{k-1} X_i\right)^2 + 2X_k\displaystyle\sum_{i=1}^{k-1} X_i+X_k^2}{k}\\ = & \sum_{i=1}^{k-1} X_i^2 +X_k^2 - \dfrac{(k-1)\left(\displaystyle\sum_{i=1}^{k-1} X_i\right)^2 + 2(k-1)X_k\displaystyle\sum_{i=1}^{k-1} X_i+ (k-1) X_k^2}{k(k-1)}\\ = & \sum_{i=1}^{k-1} X_i^2 -\dfrac{\left(\displaystyle\sum_{i=1}^{k-1} X_i\right)^2}{k-1} + X_k^2 + \dfrac{\left(\displaystyle\sum_{i=1}^{k-1} X_i\right)^2}{k(k-1)} -\dfrac{2(k-1) X_k \displaystyle\sum_{i=1}^{k-1} X_i}{k(k-1)} -\dfrac{X_k^2}{k}\\ = & W2_{k-1} + \dfrac{\left(\displaystyle\sum_{i=1}^{k-1} X_i\right)^2}{k(k-1)} -\dfrac{2(k-1) X_k \displaystyle\sum_{i=1}^{k-1} X_i}{k(k-1)} +\dfrac{(k-1) X_k^2}{k}\\ = & W2_{k-1} + \dfrac{(k-1)\bar{X}_{k-1}^2}{k} -\dfrac{2(k-1) X_k \bar{X}_{k-1}}{k} +\dfrac{(k-1) X_k^2}{k}, \end{align*}\] resulting in \[\begin{align*} W2_k = W2_{k-1} + (k-1)\left(X_k-\bar{X}_{k-1}\right)^2/k. \end{align*}\]

We can generalize this expression to compute the covariance \(S_{(x,y)}\) between a variable \(X\) and another variable \(Y\). The expression for the sum of products is given by:

\[ W2_{k,(x,y)} = W2_{k-1,(x,y)} + (k-1)\left(X_k-\bar{X}_{k-1}\right)\left(Y_k-\bar{Y}_{k-1}\right)/k \tag{5.7}\] for \(2\le k\le n\), where \(W2_{1,(x,y)}=0\). The covariance estimator is obtained by \(S_{(x,y)} = W2_{n,(x,y)}/(n-1)\).

By analyzing all these expressions, we can observe that to compute the corrected sum of squares and sum of products, we need to compute the means of the variables at the \(k\)-th step or at the previous step. The advantage is that in a single pass through the data, we obtain all the estimates. We can further extend these results to obtain sums of the third and fourth powers of deviations from the mean. The expressions we derived for this are:

\[ W3_k = W3_{k-1}+\dfrac{(k^2-3k+2)(X_k-\bar{X}_{k-1})^3}{k^2}-\dfrac{3(X_k-\bar{X}_{k-1})W2_{k-1}}{k} \tag{5.8}\] and \[ \begin{aligned} W4_k =& W4_{k-1}+\dfrac{(k^3-4k^2+6k-3)(X_k-\bar{X}_{k-1})^4}{k^3}+\\ & + \dfrac{6(X_k-\bar{X}_{k-1})^2W2_{k-1}}{k^2} -\dfrac{4(X_k-\bar{X}_{k-1})W3_{k-1}}{k} \end{aligned} \tag{5.9}\] for \(2\le k\le n\), where \(W3_{1}=0\) and \(W4_{1}=0\).

Thus, we can implement the function medsq() that returns the mean, the sum of the square, cube, and fourth power of deviations from the mean, and the variance from a data vector \(\mathbf{x}\) of dimension \(n\).

5.3 Algorithms for Mean Vectors and Covariance Matrices

In this section, we present the multivariate extension for obtaining the mean vector and the matrices of sums of squares and products and of covariances. For this reason, we did not implement a specific function to obtain the covariance between two variables \(X\) and \(Y\). Let a random sample in \(\mathbb{R}^p\) be given by \(\mathbf{X}_1\), \(\mathbf{X}_2\), \(\cdots\), \(\mathbf{X}_j\), \(\cdots\), \(\mathbf{X}_n\), where these vectors will be arranged in a matrix \(\mathbf{X}\) of dimensions \((n \times p)\). To extend the results of the previous section, we will use the same expressions, taking due care to adapt them to handle matrix and vector operations. Thus, to estimate the population mean vector, instead of using the classical textbook estimator given by \[\begin{align*} \mathbf{\bar{X}}= & \dfrac{\displaystyle\sum_{i=1}^n \mathbf{X}_i}{n}, \end{align*}\] we will use the recursive expression given by \[ \mathbf{\bar{X}}_{k} = \mathbf{\bar{X}}_{k-1} +\dfrac{\mathbf{X}_k-\mathbf{\bar{X}}_{k-1}}{k}, \tag{5.10}\] for \(2\le k\le n\), where \(\mathbf{\bar{X}}_1=\mathbf{X}_1\).

Likewise, the adaptation of expression (5.6) to \(p\) dimensions is direct, and the result obtained is:

\[ \mathbf{W}_{k} = \mathbf{W}_{k-1} + (k-1)\left(\mathbf{X}_k-\mathbf{\bar{X}}_{k-1}\right)\left(\mathbf{X}_k-\mathbf{\bar{X}}_{k-1}\right)^\top/k \tag{5.11}\] for \(2\le k\le n\), where \(\mathbf{W}_{1}=\mathbf{0}\), a matrix of zeros of dimensions \((p \times p)\). The covariance matrix estimator is obtained by \(\mathbf{S} = \mathbf{W}_{n}/(n-1)\).

We implemented the function medcov(), presented next, to obtain the mean vector, the matrix of sums of squares and products, and the covariance matrix. The argument of this function must be a matrix of multivariate data with \(n\) rows (observations) and \(p\) columns (variables). The resulting program and an example are presented below. We chose an example in which we generate a data matrix from a multivariate normal.

Fortunately, because Python (numpy) uses double precision and employs high-quality algorithms for these tasks, we do not need to worry about implementing functions such as those presented in this chapter. But if we were to use a compiler for the Pascal, Fortran, or C and C\(^{++}\) languages, we should make use of these algorithms, since only in this way will we achieve high precision, especially when dealing with data of large magnitude or very close to zero.

5.4 Case Studies

We will consider two cases of instabilities in numerical computation with classical solutions, known as Log-Sum-Exp and Kahan Summation. The Log-Sum-Exp (LSE) trick is used mainly to avoid overflow and underflow (passively) when computing exponentials, while Kahan summation is used to reduce the accumulated rounding error when adding floating-point numbers.

The LSE trick solves the instability caused by “excessive dynamic range”. When dealing with exponential functions, the difference in magnitude between inputs can be enormous, causing intermediate results to exceed the representable range of floating-point numbers.

Kahan summation, in turn, solves the instability caused by “error accumulation”. Floating-point operations have rounding errors, and single computation errors may be negligible, but when accumulated over thousands of operations, these small errors amplify, causing the final result to lose all meaning. Algorithms such as Kahan’s show that, through careful algorithm design, it is possible to control the error bound so that it does not grow without limit with the data size.

5.4.1 Log-Sum-Exp (LSE)

Its main function is to safely compute \(\log \left( \sum_{i=1}^{n} e^{x_i}\right)\). If computed directly, when \(x_i\) is very large, \(e^{x_i}\) will cause overflow, and when \(x_i\) is very small (negative), \(e^{x_i}\) will cause underflow, resulting in zero.

The central principle is based on exploiting the mathematical identity \[\log \left( \sum_{i=1}^{n} e^{x_i} \right)=m + \log \left( \sum_{i=1}^{n} e^{x_i-m}\right),\] where \(m\) \(=\) \(\max(x_i)\). This amounts to a type of normalization of the values, subtracting the maximum value from all exponents, ensuring that the largest input value to the exponential function is \(0\), thereby completely avoiding overflow. LSE ensures that no term suffers overflow, and any underflow that occurs affects only terms whose contribution is numerically negligible.

This method is extremely common in probabilistic models and machine learning algorithms, especially when working with probabilities in logarithmic space. For example, in the Softmax function for classification in neural networks, in neural network loss functions, in Bayesian inference computations, and in the Viterbi algorithm (speech recognition, bioinformatics, natural language processing, digital communications, and GPS).

The stable solution, considering that \(m\) \(=\) \(x_{\max}\) \(=\) \(\max(x_1, \dots, x_n)\), is obtained by \[ \begin{aligned} y =& \log \left( \sum_{i=1}^{n} e^{x_i} \right)= \log \left( \sum_{i=1}^{n} e^{x_i- m + m} \right)\\ =& \log \left(e^m \right)+ \log \left( \sum_{i=1}^{n} e^{x_i- m} \right)\\ =& m +\log \left( \sum_{i=1}^{n} e^{x_i- m} \right). \end{aligned}\]

5.4.2 Kahan Summation (Compensated Summation)

The goal is to reduce the accumulated rounding error when adding a large number of floating-point numbers. When you add a very small number to a very large number, the lower bits of the small number are “absorbed” (lost), which, when accumulated, produces large deviations.

The central principle is to maintain an additional “compensation” variable \(c\). At each iteration, first subtract the compensation from the previous iteration from the value to be added, then perform the addition as usual, and then compute the low-order part lost in this addition (that is, the new compensation value) using the difference between the sum and the original value. In simple terms, it “recovers” and temporarily stores the small values that would be lost, in order to “try again” in the next addition.

The method is applied in scenarios that require high summation precision, such as scientific computing libraries, processing of large datasets (for example, Flink’s CompensatedSum), and numerical simulation algorithms that require stable results.

Imagine that we want to add an element \(x\) to our current sum:

  1. \(y = x - c\)
    → Subtracts the accumulated error compensation from the new element \(x\).

  2. \(t = \text{sum} + y\)
    → Performs the addition in the main accumulator. This is where precision is lost due to rounding.

  3. \(c = (t - \text{sum}) - y\)
    → Recovers the error. Mathematically, \((t - \text{sum})\) should equal \(y\), but numerically, due to rounding, the difference reveals exactly what was discarded. We store this in \(c\) with the sign inverted for the next iteration.

  4. \(\text{sum} = t\)
    → Updates the main accumulator.

Practical note: NumPy does not use Kahan summation in np.mean, np.var, np.std, or np.cov. Instead, it uses pairwise summation (pairwise/hierarchical summation), which reduces the rounding error from \(O(n)\) to \(O(\log n)\) and is almost as fast as naive summation. For most statistical cases, this is sufficient. Kahan summation offers even greater precision (error close to \(O(1)\)), but with a slightly higher computational cost.

5.4.3 Practical Demonstration in Python

The code below runs both scenarios, comparing the naive approach against the numerically stable approach.

5.5 Exercises

  1. Show the numerical equivalence between the following expressions \[\begin{align*} W2_k &= \sum_{i=1}^{k-1} X_i^2 +X_{k}^2- \dfrac{\left(\displaystyle\sum_{i=1}^{k-1} X_i +X_k\right)^2}{k}\\ &= W2_{k-1} + k\left(X_k-\bar{X}_{k}\right)^2/(k-1) \end{align*}\] and \[ W2_k = W2_{k-1} + (k-1)\left(X_k-\bar{X}_{k-1}\right)^2/k.\]

    To do this, implement both functions in Python and perform a numerical comparison (a single example is enough).

  2. Implement a function in Python to obtain the sum of products, equation (5.7), and the covariance between the \(n\) observations of two variables whose values are arranged in two vectors \(\mathbf{X}\) and \(\mathbf{Y}\). Create a matrix with \(n\) rows and \(p=2\) columns from some example and use the function medcov() to compare the results obtained.

  3. The sample skewness and kurtosis coefficients are functions of the sums of powers of deviations from the mean. The skewness coefficient is given by \(\sqrt{b_1}\) \(=\) \((W3_n/n)/(W2_n/n)^{3/2}\), and the kurtosis coefficient is \(b_2 = (W4_n/n)/(W2_n/n)^2\). Implement a Python function using medsq() to estimate the univariate skewness and kurtosis coefficients.

  4. Use a sample from an area of your specialty and determine the mean, variance, sum of squares, sum of cubed deviations, and sum of fourth-power deviations. Also determine the skewness and kurtosis coefficients.