## Computing a running variance the smart way

Suppose we compute the running mean of a list of numbers $x_1,\,x_2,\,...,x_p,...$ when the $p^{th}$ number $x_p$ arrives the *smart way* (as shown above)

\begin{equation}
h_{p}^{\text{ave}} = \frac{p-1}{p}h_{p-1}^{\text{ave}} + \frac{1}{p}x_p
\end{equation}

and then - on top of this - we would like to compute the *running variance* of our ever-increasing list of numbers.  If we used the standard formula for variance we would compute

\begin{equation}
h_p^{\text{var}} = \frac{1}{p}\sum_{j=1}^p\left(x_j - h_p^{\text{ave}}\right)^2
\end{equation}

each time a new point $x_p$ arrived.  However computing the running variance this way would be wasteful - both in terms of storage (we would need to store all of the previous input points) and computation (we're repeating the same sorts of computation over and over again) - in complete analogy to the use of the standard formula when computing the running mean (as we saw above). 

Multiplying both sides of Equation (2) by $p$ we have 

\begin{equation}
p\,h_p^{\text{var}} = \sum_{j=1}^p\left(x_j - h_p^{\text{ave}}\right)^2
\end{equation}

Plugging in $p-1$ in place of $p$ in the Equation above yields

\begin{equation}
\left(p-1\right)\,h_{p-1}^{\text{var}} = \sum_{j=1}^{p-1}\left(x_j - h_{p-1}^{\text{ave}}\right)^2
\end{equation}

Subtracting (4) from (3), and simple re-arrangement of terms gives

\begin{equation}
\begin{split}
p\,h_p^{\text{var}} - \left(p-1\right)\,h_{p-1}^{\text{var}} & =  \sum_{j=1}^p\left(x_j - h_p^{\text{ave}}\right)^2 - \sum_{j=1}^{p-1}\left(x_j - h_{p-1}^{\text{ave}}\right)^2 \\
& = \left[\left(x_p - h_p^{\text{ave}}\right)^2 + \sum_{j=1}^{p-1}\left(x_j - h_p^{\text{ave}}\right)^2 \right] - \sum_{j=1}^{p-1}\left(x_j - h_{p-1}^{\text{ave}}\right)^2 \\
& = \left(x_p - h_p^{\text{ave}}\right)^2 + \left[\sum_{j=1}^{p-1}\left(x_j - h_p^{\text{ave}}\right)^2 - \sum_{j=1}^{p-1}\left(x_j - h_{p-1}^{\text{ave}}\right)^2\right] \\
& = \left(x_p - h_p^{\text{ave}}\right)^2 + \sum_{j=1}^{p-1}\left[\left(x_j - h_p^{\text{ave}}\right)^2 - \left(x_j - h_{p-1}^{\text{ave}}\right)^2\right] \\
\end{split}
\end{equation}

We now use the identity $a^2 - b^2 = \left(a-b\right)\left(a+b\right)$ to simplify each summand in Equation (5) as follows

\begin{equation}
\begin{split}
p\,h_p^{\text{var}} - \left(p-1\right)\,h_{p-1}^{\text{var}} & = \left(x_p - h_p^{\text{ave}}\right)^2 + \sum_{j=1}^{p-1}\left(h_{p-1}^{\text{ave}} - h_p^{\text{ave}}\right) \left(2 x_j - h_{p}^{\text{ave}}-h_{p-1}^{\text{ave}}\right) \\
 & = \left(x_p - h_p^{\text{ave}}\right)^2 + \left(h_{p-1}^{\text{ave}} - h_p^{\text{ave}}\right) \sum_{j=1}^{p-1} \left(2 x_j - h_{p}^{\text{ave}}-h_{p-1}^{\text{ave}}\right)\\
\end{split}
\end{equation}

Notice, the last summation in Equation above can be written equivalently as

\begin{equation}
\begin{split}
\sum_{j=1}^{p-1} \left(2 x_j - h_{p}^{\text{ave}}-h_{p-1}^{\text{ave}}\right) & = \left(2\sum_{j=1}^{p-1} x_j\right) - \left(p-1\right) \left( h_{p}^{\text{ave}} + h_{p-1}^{\text{ave}} \right)\\
& = 2\left(p-1\right)h_{p-1}^{\text{ave}} - \left(p-1\right) \left( h_{p}^{\text{ave}} + h_{p-1}^{\text{ave}} \right)\\
& = \left(p-1\right) h_{p-1}^{\text{ave}} - \left(p-1\right) h_{p}^{\text{ave}} \\ 
& = \left(p \,h_{p}^{\text{ave}} - x_p\right) - \left(p-1\right) h_{p}^{\text{ave}} \\ 
& = h_{p}^{\text{ave}} - x_p
\end{split}
\end{equation}

where we have made use of the fact that $\left(p-1\right) h_{p-1}^{\text{ave}} = p \,h_{p}^{\text{ave}} - x_p$.

Substituting the result above into (6) we now have

\begin{equation}
\begin{split}
p\,h_p^{\text{var}} - \left(p-1\right)\,h_{p-1}^{\text{var}} & = \left(x_p - h_p^{\text{ave}}\right)^2 + \left(h_{p-1}^{\text{ave}} - h_p^{\text{ave}}\right)  \left(h_{p}^{\text{ave}} - x_p\right)\\
 & = \left(x_p - h_p^{\text{ave}}\right)\left(x_p - h_{p-1}^{\text{ave}}\right)
\end{split}
\end{equation}

A little re-arrangement finally gives 


\begin{equation}
h_{p}^{\text{var}} = \frac{p-1}{p}h_{p-1}^{\text{var}} + \frac{1}{p}\left(x_p^{\,} - h_{p}^{\text{ave}}\right)\left(x_p^{\,} - h_{p-1}^{\text{ave}}\right)
\end{equation}

e6a84fc9e1b682d74cf15c01f06e80c720033c96
ipynb
Jupyter Notebook
posts/dynamic_systems_limited_memory/running_variance_derivation.ipynb
jermwatt/blog
3dd0d464d7a17c1c7a6508f714edc938dc3c03e9
MIT
2019-04-17T23:55:14.000Z
2021-08-08T02:18:49.000Z
posts/dynamic_systems_limited_memory/running_variance_derivation.ipynb
jermwatt/blog
3dd0d464d7a17c1c7a6508f714edc938dc3c03e9
MIT
posts/dynamic_systems_limited_memory/running_variance_derivation.ipynb
jermwatt/blog
3dd0d464d7a17c1c7a6508f714edc938dc3c03e9
MIT
2019-04-10T22:46:27.000Z
2020-11-06T09:16:30.000Z
Qwen/Qwen-72B
1. YES
2. YES