Online Weighted Mean

Given the following set of inputs and their associated weights:

$\left\{\left(x_1,w_1\right),\left(x_2,w_2\right),\dots ,\left(x_{n-1},w_{n-1}\right),\left(x_n,w_n\right)\right\}$

Let $n$ be the number of inputs and their associated weights, ${\overline{x}}_n^{\text{weighted}}$ is the weighted sample mean for the first $n$ inputs and their associated weights, ${\overline{x}}_{n-1}^{\text{weighted}}$ be the weighted sample mean of the first $n-1$ inputs and their associated weights, $w_n$ be the $n$ -th weight associated with input $x_n$, and $x_n$ be the $n$ -th input associated with $w_n$. Then, the recurrence equation for the weighted sample mean (a.k.a. online weighted mean) is:

${\overline{x}}_n^{\text{weighted}}={\overline{x}}_{n-1}^{\text{weighted}}-\frac{w_n\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{{\displaystyle \sum _{i=1}^n{w}_i}}$

where ${\displaystyle \sum _{i=1}^n{w}_i}\ne 0$. Preferably, all the weights are positive such that ${\displaystyle \sum _{i=1}^n{w}_i}>0$.

Proof:

The definition of the sample mean is:

${\overline{x}}_n=\frac{{\displaystyle \sum _{i=1}^n{x}_i}}{n}$

The definition of the weighted sample mean is:

${\overline{x}}_n^{\text{weighted}}=\frac{{\displaystyle \sum _{i=1}^n{w}_i{x}_i}}{{\displaystyle \sum _{i=1}^n{w}_i}}$

If we expand this definition, we have:

${\overline{x}}_n^{\text{weighted}}=\frac{{\displaystyle \sum _{i=1}^{n-1}{w}_i{x}_i}+w_n{x}_n}{{\displaystyle \sum _{i=1}^{n-1}{w}_i}+w_n}$

From algebra, we know that for arbitrary $a$, $b$, $c$, and $d$:

$\begin{array}{c}\frac{a+b}{c+d}=\frac{a+b}{c+d}+\frac{a}{c}-\frac{a}{c}\\ =\frac{a}{c}+\frac{a+b}{c+d}-\frac{a}{c}\\ =\frac{a}{c}+\left(\frac{a+b}{c+d}\right)\left(\frac{c}{c}\right)-\left(\frac{a}{c}\right)\left(\frac{c+d}{c+d}\right)\\ =\frac{a}{c}+\frac{ac+bc-ac-ad}{c\left(c+d\right)}\\ =\frac{a}{c}+\frac{\cancel{ac}+bc-\cancel{ac}-ad}{c\left(c+d\right)}\\ =\frac{a}{c}+\frac{bc-ad}{c\left(c+d\right)}\\ =\frac{a}{c}+\frac{bc}{c\left(c+d\right)}+\frac{-ad}{c\left(c+d\right)}\\ =\frac{a}{c}+\frac{b\cancel{c}}{\cancel{c}\left(c+d\right)}+\frac{-ad}{c\left(c+d\right)}\\ =\frac{a}{c}+\frac{-ad}{c\left(c+d\right)}+\frac{b}{\left(c+d\right)}\end{array}$

Hence, we have:

$\begin{array}{c}{\overline{x}}_n^{\text{weighted}}=\frac{\stackrel{a}{\overbrace{{\displaystyle \sum _{i=1}^{n-1}{w}_i{x}_i}}}+\stackrel{b}{\overbrace{w_n{x}_n}}}{\underset{c}{\underbrace{{\displaystyle \sum _{i=1}^{n-1}{w}_i}}}+\underset{d}{\underbrace{w_n}}}\\ =\frac{\left({\displaystyle \sum _{i=1}^{n-1}{w}_i{x}_i}\right)}{\left({\displaystyle \sum _{i=1}^{n-1}{w}_i}\right)}+\frac{-\left({\displaystyle \sum _{i=1}^{n-1}{w}_i{x}_i}\right)\left(w_n\right)}{\left({\displaystyle \sum _{i=1}^{n-1}{w}_i}\right)\left(\left({\displaystyle \sum _{i=1}^{n-1}{w}_i}\right)+\left(w_n\right)\right)}+\frac{\left(w_n{x}_n\right)}{\left(\left({\displaystyle \sum _{i=1}^{n-1}{w}_i}\right)+\left(w_n\right)\right)}\\ =\left(\frac{{\displaystyle \sum _{i=1}^{n-1}{w}_i{x}_i}}{{\displaystyle \sum _{i=1}^{n-1}{w}_i}}\right)-\left(\frac{{\displaystyle \sum _{i=1}^{n-1}{w}_i{x}_i}}{{\displaystyle \sum _{i=1}^{n-1}{w}_i}}\right)\left(\frac{w_n}{{\displaystyle \sum _{i=1}^n{w}_i}}\right)+\frac{\left(w_n{x}_n\right)}{\left({\displaystyle \sum _{i=1}^n{w}_i}\right)}\end{array}$

Since the weighted sample mean for the first $n-1$ inputs and their associated weights is defined as ${\overline{x}}_{n-1}^{\text{weighted}}=\frac{{\displaystyle \sum _{i=1}^{n-1}{w}_i{x}_i}}{{\displaystyle \sum _{i=1}^{n-1}{w}_i}}$ , we have:

${\overline{x}}_n^{\text{weighted}}=\left({\overline{x}}_{n-1}^{\text{weighted}}\right)-\left({\overline{x}}_{n-1}^{\text{weighted}}\right)\left(\frac{w_n}{{\displaystyle \sum _{i=1}^n{w}_i}}\right)+\frac{\left(w_n{x}_n\right)}{\left({\displaystyle \sum _{i=1}^n{w}_i}\right)}$

Factoring out the $-1$, we have:

${\overline{x}}_n^{\text{weighted}}=\left({\overline{x}}_{n-1}^{\text{weighted}}\right)-\left(\left({\overline{x}}_{n-1}^{\text{weighted}}\right)\left(\frac{w_n}{{\displaystyle \sum _{i=1}^n{w}_i}}\right)-\frac{\left(w_n{x}_n\right)}{\left({\displaystyle \sum _{i=1}^n{w}_i}\right)}\right)$

Combining the fractions and factoring out the $w_n$, we have:

$\begin{array}{c}{\overline{x}}_n^{\text{weighted}}={\overline{x}}_{n-1}^{\text{weighted}}-\left(\frac{{\overline{x}}_{n-1}^{\text{weighted}}{w}_n-w_n{x}_n}{{\displaystyle \sum _{i=1}^n{w}_i}}\right)\\ ={\overline{x}}_{n-1}^{\text{weighted}}-\frac{w_n\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{{\displaystyle \sum _{i=1}^n{w}_i}}\end{array}$

Therefore, the recurrence equation for the weighted sample mean (a.k.a. online weighted mean) is:

${\overline{x}}_n^{\text{weighted}}={\overline{x}}_{n-1}^{\text{weighted}}-\frac{w_n\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{{\displaystyle \sum _{i=1}^n{w}_i}}$

where ${\displaystyle \sum _{i=1}^n{w}_i}\ne 0$.

Note: If all the weights are the same constant value $c$ (i.e. $w_i=c$ for $i=1,\dots ,n$ ), the weighted sample mean would be:

$\begin{array}{c}{\overline{x}}^{\text{weighted}}=\frac{{\displaystyle \sum _{i=1}^n{w}_i{x}_i}}{{\displaystyle \sum _{i=1}^n{w}_i}}\\ =\frac{{\displaystyle \sum _{i=1}^{n}c{x}_i}}{{\displaystyle \sum _{i=1}^{n}c}}\\ =\frac{c\left({\displaystyle \sum _{i=1}^n{x}_i}\right)}{c\left({\displaystyle \sum _{i=1}^{n}1}\right)}\\ =\frac{\cancel{c}\left({\displaystyle \sum _{i=1}^n{x}_i}\right)}{\cancel{c}\left(n\right)}\\ =\frac{{\displaystyle \sum _{i=1}^n{x}_i}}{n}\\ =\overline{x}\end{array}$

For instance, if all the weights are $1$, then the weighted sample mean is the sample mean:

$\begin{array}{c}{\overline{x}}^{\text{weighted}}=\frac{{\displaystyle \sum _{i=1}^n{w}_i{x}_i}}{{\displaystyle \sum _{i=1}^n{w}_i}}\\ =\frac{{\displaystyle \sum _{i=1}^n\left(1\right)x_i}}{{\displaystyle \sum _{i=1}^n\left(1\right)}}\\ =\frac{{\displaystyle \sum _{i=1}^n{x}_i}}{n}\\ =\overline{x}\end{array}$

Similarly, the online weighted mean with weights of the same constant value $c$ would be:

$\begin{array}{c}{\overline{x}}_n^{\text{weighted}}={\overline{x}}_{n-1}^{\text{weighted}}-\frac{w_n\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{{\displaystyle \sum _{i=1}^n{w}_i}}\\ ={\overline{x}}_{n-1}^{\text{weighted}}-\frac{c\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{{\displaystyle \sum _{i=1}^{n}c}}\\ ={\overline{x}}_{n-1}^{\text{weighted}}-\frac{c\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{c\left({\displaystyle \sum _{i=1}^{n}1}\right)}\\ ={\overline{x}}_{n-1}^{\text{weighted}}-\frac{\cancel{c}\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{\cancel{c}\left(n\right)}\\ ={\overline{x}}_{n-1}^{\text{weighted}}-\frac{\left({\overline{x}}_{n-1}^{\text{weighted}}-x_n\right)}{n}\\ ={\overline{x}}_{n-1}-\frac{\left({\overline{x}}_{n-1}-x_n\right)}{n}\\ ={\overline{x}}_n\end{array}$

Therefore, if all the weights are the same constant value $c$, the online weighted mean is the same as the online mean.

Example of C++ code that computes the online weighted mean:

#include <iostream>
#include <iomanip>
 
int main() {
 
    double x;
    double weight;
    double sum_of_weights = 0;
    double weighted_mean = 0;
    double prev_weighted_mean;
 
    if ( std::cin >> x && std::cin >> weight ) {
        sum_of_weights += weight;
        weighted_mean = x;
        while ( std::cin >> x && std::cin >> weight ) {
            prev_weighted_mean = weighted_mean;
            sum_of_weights += weight;
            weighted_mean = (
                prev_weighted_mean - weight * ( prev_weighted_mean - x ) / sum_of_weights
            );
        }
    }
 
    std::cout << "sum_of_weights: " << std::setprecision( 17 ) << sum_of_weights << '\n';
    std::cout << "weighted_mean:  " << std::setprecision( 17 ) << weighted_mean << '\n';
}

Example of data.txt:

-19.313117172629575    2.718281828459045
-34.14656787734913     7.38905609893065
-14.117521595690334    20.085536923187668
.                      .
.                      .
.                      .

Command line:

g++ -o main.exe main.cpp -std=c++11 -march=native -O3 -Wall -Wextra -Werror -static
./main.exe < data.txt

Sample Output:

sum_of_weights: 34843.773845331321
weighted_mean:  -28.368899576339764

Online Weighted Mean
online_weighted_mean.pdf
online_weighted_mean.docx

• ← Online Covariance
• A New Beginning! →