Fórmula recursiva para la varianza

Question

Me gustaría saber cómo puedo calcular recursivamente (editar: iterativamente) la varianza, para poder calcular la desviación estándar de un conjunto de datos muy grande en javascript. La entrada es un array ordenado de enteros positivos.

Answer 1

Recordemos que, para cada $n\geqslant1$ , $$ \bar x_n=\frac1n\sum_{k=1}^nx_k, $$ y $$ \bar\sigma^2_n=\frac1n\sum_{k=1}^n(x_k-\bar x_n)^2=\frac1n\sum_{k=1}^nx_k^2-(\bar x_n)^2. $$ Por lo tanto, simples manipulaciones algebraicas a partir de las identidades $$ (n+1)\bar x_{n+1}=n\bar x_n+x_{n+1}, $$ y $$ (n+1)(\bar\sigma^2_{n+1}+(\bar x_{n+1})^2)=n(\bar\sigma^2_n+(\bar x_n)^2)+x_{n+1}^2, $$ llevar a $$ \bar x_{n+1}=\bar x_n+\frac{x_{n+1}-\bar x_n}{n+1}, $$ y $$ \bar\sigma^2_{n+1}=\bar\sigma^2_n+(\bar x_n)^2-(\bar x_{n+1})^2+\frac{x_{n+1}^2-\bar\sigma^2_n-(\bar x_n)^2}{n+1}. $$ Así, $(n,\bar x_n,x_{n+1})$ rendimiento $\bar x_{n+1}$ y $(n,\bar\sigma^2_n,\bar x_n,\bar x_{n+1},x_{n+1})$ rendimiento $\bar\sigma^2_{n+1}$ .

Answer 2

Hay dos problemas en la respuesta anterior, el primero es que la fórmula de la varianza es incorrecta (ver la fórmula de abajo para la versión correcta) y el segundo es que la fórmula de la recursión termina restando números grandes, casi iguales.

La definición para las estimaciones insesgadas de la media( $\bar x$ ) y la varianza( $\sigma^2$ ) para una muestra de tamaño n son: $$ \bar x_n=\frac1n\sum_{k=1}^nx_k, $$ y $$ \bar\sigma^2_n=\frac1{n-1}\sum_{k=1}^n(x_k-\bar x_n)^2 $$

Definir las variables de recursión

$$ M_n = n \bar x_n=\sum_{k=1}^nx_k, $$ y $$ S_n = (n-1)\bar\sigma^2_n=\sum_{k=1}^n(x_k-\bar x_n)^2 $$

La relación de recursión para $M_{n+1}$ es evidente $$ M_{n+1} = M_n + x_{n+1} $$ y la relación de recursión para $S_n$ se obtiene mediante $$ S_{n+1} = (x_{n+1}-\bar x_{n+1})^2+\sum_{k=1}^n(x_k-\bar x_{n+1})^2\phantom{XXXXXX}\\ \phantom{S_{n+1}} = (x_{n+1}-\bar x_{n+1})^2+\sum_{k=1}^n(x_k-\bar x_n+\bar x_n-\bar x_{n+1})^2\\ \phantom{S_{n+1}XXXXXXXXXX} = (x_{n+1}-\bar x_{n+1})^2+\sum_{k=1}^n(x_k-\bar x_n)^2+2(\bar x_n-\bar x_{n+1})\sum_{k=1}^n(x_n-\bar x_n) + \sum_{k=1}^n(\bar x_n -\bar x_{n+1})^2\\ $$ Y como $$S_n = \sum_{k=1}^n(x_k-\bar x_n)^2$$ $$\sum_{k=1}^n(\bar x_n-\bar x_{n+1})^2 = n(\bar x_n-\bar x_{n+1})^2$$ y $$\sum_{k=1}^n(x_k-\bar x_n) = 0$$ esto se simplifica a $$ S_{n+1} = S_n+(x_{n+1}-\bar x_{n+1})^2 +n(\bar x_n -\bar x_{n+1})^2 $$

Ahora bien, esta relación de recursión tiene la agradable propiedad de que $S_n$ una suma de términos al cuadrado, y por tanto no puede ser negativa. Escrito en términos de $M_n$ y $S_n$ las relaciones de recursión son: $$ M_{n+1} = M_n + x_{n+1} $$ $$ S_{n+1} = S_n+\left(x_{n+1}-\frac{M_n+x_{n+1}}{n+1}\right)^2 +n\left(\frac{M_n}{n} -\frac{M_n+x_{n+1}}{n+1}\right)^2 $$ y podemos simplificar aún más la relación de recursión para $S_n$ a \begin{eqnarray} S_{n+1} &= S_n + \left(\frac{n x_{n+1}-M_n}{n+1}\right)^2+n\left(\frac{M_n-n x_{n+1}}{n(n+1)}\right)^2\\ &=S_n+ \left(1+\frac1n\right)\left(\frac{n x_{n+1}-M_n}{n+1}\right)^2\\ &=S_n+ \frac{(n x_{n+1}-M_n)^2}{n(n+1)} \end{eqnarray}

Así que tenemos las relaciones de recursión simples: $$ M_{n+1} = M_n + x_{n+1} $$ $$ S_{n+1} = S_n + \frac{(n x_{n+1}-M_n)^2}{n(n+1)}$$

con la media dada por $$\bar x_n = \frac1n M_n$$ y la estimación insesgada de la varianza viene dada por $$\sigma_n^2 = \frac1{n+1}S_n$$ .

Answer 3

Aquí están las fórmulas iterativas (con derivaciones) para el población (N normalizado) y muestra (N-1 normalizada) desviaciones estándar, que expresan la $\sigma_{n+1}$ ( $s_{n+1}$ para la muestra) para el $n+1$ valor establecido en términos de $\sigma_{n}$ ( $s_{n}$ para la muestra), $\bar x_{n}$ de la $n$ valor establecido más el nuevo valor $x_{n+1}$ añadido al conjunto.

Esencialmente necesitamos encontrar:

$$\bar x_{n+1} = f(n, \bar x_n, x_{n+1})$$ y $$\sigma_{n+1} = g(n, \sigma_n, \bar x_n, x_{n+1})$$

Derivación de la media

En ambos casos, la media de $n\geqslant1$ es,

para los valores n: $$ \bar x_n=\frac1n\sum_{k=1}^nx_k $$

para los valores n+1: $$ \bar x_{n+1}=\frac1{n+1}\sum_{k=1}^{n+1}x_k = \frac1{n+1}(n\bar x_n + x_{n+1}) \leftarrow f(n, \bar x_n, x_{n+1}) $$

Derivación de la desviación estándar

Las fórmulas de desviación estándar para población y muestra son:

\begin{aligned} \sigma_{n} &= \sqrt {\frac1{n} \sum_{k=1}^{n}(x_k - \bar x_{n})^2 } && \textit{for} \textbf{ population } \textit{Standard Deviation}\\ \\ s_{n} &= \sqrt {\frac1{n-1} \sum_{k=1}^{n}(x_k - \bar x_{n})^2 } && \textit{for} \textbf{ sample } \textit{Standard Deviation } \\ \end{aligned}

Para consolidar las derivaciones de ambos población y muestra fórmulas escribiremos la desviación estándar utilizando un factor genérico $\alpha_{n}$ y reemplazarlo al final para obtener las fórmulas de población y muestra.

con:

\begin{equation} \alpha_{n} = \begin{cases} n & \textit{for} \textbf{ population } \textit{Standard Deviation} \\ n-1 & \textit{for} \textbf{ sample } \textit{Standard Deviation } \\ \end{cases} \end{equation}

la ecuación de la desviación estándar para los n valores se puede escribir como

\begin{equation} \tag{1} \alpha_{n}\sigma^2_{n} = \sum_{k=1}^{n}(x_k - \bar x_{n})^2 = \sum_{k=1}^{n}x_k^2 - n (\bar x_{n})^2 \end{equation}

Así, la misma ecuación para los valores n+1 es:

\begin{equation} \begin{aligned} \alpha_{n+1}\sigma^2_{n+1} & = \sum_{k=1}^{n+1}(x_k-\bar x_{n+1})^2 \\ & = \sum_{k=1}^{n+1}x_k^2 - (n+1)(\bar x_{n+1})^2 \\ & = \sum_{k=1}^{n}x_k^2 + (x_{n+1})^2 - (n+1)(\bar x_{n+1})^2 \\ & = \sum_{k=1}^{n}x_k^2 + (x_{n+1})^2 - (n+1) \big(\frac1{n+1}(n\bar x_{n} + x_{n+1}) \big)^2 \\ & = \sum_{k=1}^{n}x_k^2 + (x_{n+1})^2 - \frac1{n+1} \big(n^2(\bar x_{n})^2 + 2 n \bar x_{n} x_{n+1} + (x_{n+1})^2 \big) \\ \end{aligned} \end{equation}

de la ecuación (1) sustituimos $\sum_{k=1}^{n}x_k^2$ con $\alpha_{n}\sigma^2_{n} + n (\bar x_{n})^2$ y conseguir:

\begin{equation} \begin{aligned} \alpha_{n+1}\sigma^2_{n+1} & = \alpha_{n}\sigma^2_{n} + n (\bar x_{n})^2 + (x_{n+1})^2 - \frac1{n+1} \big(n^2(\bar x_{n})^2 + 2 n \bar x_{n} x_{n+1} + (x_{n+1})^2 \big) \\ \end{aligned} \end{equation}

ordenando los términos y simplificando obtenemos:

$$ \sigma_{n+1} = \sqrt { \Big( \sigma^2_{n} + \frac{n}{n+1} \frac1{\alpha_n} (\bar x_n - x_{n+1})^2 \Big) \frac{\alpha_{n}}{\alpha_{n+1}} } \leftarrow g(n, \sigma_n, \bar x_n, x_{n+1}) $$

Sustitución de la $\alpha$ las fórmulas iterativas específicas para población y muestra desviaciones estándar son:

\begin{equation} \begin{aligned} \sigma_{n+1} &= \sqrt{ \Big( \sigma^2_{n} + \frac{1}{n+1}(\bar x_n - x_{n+1})^2 \Big) \frac{n}{n+1} } &&\textit{population STD} \\ \\ s_{n+1} &= \sqrt{ \Big( s^2_{n} + \frac{n}{n^2-1}(\bar x_n - x_{n+1})^2 \Big) \frac{n-1}{n} } &&\textit{sample STD} \\ \end{aligned} \end{equation}

Answer 4

Acabé utilizando este enfoque incremental:

function mean(array) {
  var i = -1, j = 0, n = array.length, m = 0;
  while (++i < n) if (a = array[i]) m += (a - m) / ++j;
  return j ? m : undefined;
}

function variance(array, mean_value) {
  if (!mean_value) return undefined;
  var i = -1, j = 0, n = array.length, v = 0;
  while (++i < n) {
    a = Math.pow((array[i] - mean_value), 2)
    v += (a - v) / ++j;
  }
  return v * (n/(n-1));
}