Calcular la varianza de un flujo de valores de muestra

Question

Me gustaría calcular la desviación estándar para una muy grande (pero conocido) número de valores de la muestra, con la mayor precisión posible. El número de muestras es mayor que el que puede ser eficientemente almacenados en la memoria.

El básico de la fórmula de varianza es:

$\sigma^2 = \frac{1}{N}\sum (x - \mu)^2$

... pero esta formulación depende de conocer el valor de $\mu$ ya.

$\mu$ puede ser calculado de forma acumulativa, es decir, se puede calcular la media sin almacenar cada valor de ejemplo. Usted sólo tiene que guardar su suma.

Pero para calcular la varianza, es necesario almacenar cada valor de ejemplo? Dada una secuencia de muestras, puedo acumular un cálculo de la varianza, sin necesidad de una memoria de cada una de las muestras? Dicho de otra manera, hay una formulación de la varianza que no depende del conocimiento previo del valor exacto de $\mu$ antes de que todo el conjunto de la muestra se ha visto?

Answer 1

Estoy un poco tarde a la fiesta, pero parece que este método es bastante inestable, pero que no es un método que permite la transmisión de cálculo de la varianza sin sacrificar la estabilidad numérica.

Cook describe un método de Knuth, el remate de las cuales es inicializar $m_1 = x_1$, e $v_1 = 0$ donde $m_k$ es la media de la primera $k$ valores. A partir de allí,

$$ \begin{align*} m_k & = m_{k-1} + \frac{x_k - m_{k-1}}k \\ v_k & = v_{k-1} + (x_k - m_{k-1})(x_k - m_k) \end{align*} $$

La media en este punto es simplemente extrae como $m_k$, y la variación es $\sigma^2 = \frac{v_k}{k-1}$. Es fácil comprobar que funciona para la media, pero todavía estoy trabajando en el grokking la varianza.

Answer 2

Usted puede mantener dos contadores de corriente - $\sum_i x_i$ y $\sum_i x_i^2$. Puesto que la varianza puede ser escrita como $$ \sigma^2 = \frac{1}{N} \left[ \sum_i x_i^2 - \frac{(\sum_i x_i)^2}{N} \right] $ $

Usted puede calcular la varianza de los datos que has visto hasta el momento con solo estos dos contadores. Tenga en cuenta que el $N$ aquí no es la longitud total de todas sus muestras, pero sólo el número de muestras que usted ha observado en el pasado.

Answer 3

tldr: Creo que hay un falta $(k-1)$ término en el cálculo de la varianza de @Dan. Creo que debe ser $$\sigma^2_k = \frac{1}{k} \left( (k-1) \sigma^2_{k-1} + (x_k-m_{k-1})(x_k-m_k)\right) $$

Validation: I tried what Dan's formula but am getting something different from Matlab's var command. For example, take 1000 Gaussian numbers (mean 0, var 100) and compute their mean and var:

clear; clc
n=1000;
x=round(randn(1,n)*10);

% calcs
mm(1)=x(1);
vm(1)=0;
m(1)=x(1);
v(1)=0;
ma(1)=x(1);
va(1)=0;
for k=2:n
    mm(k) = mean(x(1:k)); %matlab mean
    vm(k) = var(x(1:k),1); %matlab var

    m(k) = m(k-1) + 1/k * (x(k)-m(k-1)) ; %Knuth mean
    v(k) = (1/k) * (v(k-1) + (x(k)-m(k-1)) * (x(k)-m(k))) ; %Knuth var

    ma(k) = (1-1/k) * ma(k-1) + (1/k) * x(k); %Finch mean
    %va(k) = (1-1/k) * (va(k-1) + (1/k) * (x(k)-ma(k-1))^2 ); %Finch 143
    va(k) = (1/k) * ((k-1)*va(k-1) + (x(k)-m(k-1)) * (x(k)-m(k)) ); %Finch 143 rearranged to look like Knuth
end

% plots
figure(1); clf
subplot 211
plot(1:n, x, 'k--')
hold on
plot(1:n,mm, 'b-')
plot(1:n,m, 'g-')
plot(1:n,ma, 'r--')
hold off
ylabel('means')
legend('x','Matlab','Knuth','Finch')

subplot 212
plot(1:n,vm, 'b-')
hold on
plot(1:n,v, 'g-')
plot(1:n,va, 'r--')
hold off
ylabel('vars')
xlabel('steps')
legend('Matlab','Knuth','Finch')

As you can see I selected Matlab's (octave's) VAR(X,1) command which divides by $N $ and not by $% de %(N-1) #%(k-1) $, which goes back to @errr's comment - it has to do with using biased vs unbiased estimator (I usually go to biased one because it makes more sense to me)

So it seems like Knuth variance is ok for a couple of steps and then it's way below because of the missing $%\alpha=\frac {1} {k} $. Hay que reconocer que es un hack como mi alfa cambia con cada paso, mientras que su supone que es constante (?), pero al final esta fórmula concuerda con matlab var(X,1) .