Estimativa online de variação com memória limitada

Estou criando um componente que visa calcular a média e a variação de uma métrica associada a eventos que ocorrem durante o tempo, mas com uma memória interna limitada.

Imagine que os eventos são visitantes que entram em uma loja e a métrica é a idade deles.

Durante o tempo, meu componente recebe eventos com a idade de cada visitante. Não quero que meu componente memorize a história de cada idade. Idealmente, eu gostaria de armazenar apenas um componente leve: a média A, a variação V e o número de eventos N.

Após cada evento com a idade E, desejo atualizar esses três valores:

N<=N+1
A<=(A*N+E)/(N+1)
V<=???

Para que V? Estou pensando em algo como:

V<=(V*N+(E-A)^2)/(N+1)

Eu sei que não é exato, pois o meu anterior Vestá usando o antigo, Aque não é mais a média.

Q1 - Existe uma fórmula exata?
Q2 - Se não, minha proposta é uma boa estimativa? É tendencioso? Irá convergir corretamente quando Naumentar?
Q3 - Existe uma fórmula melhor?

Um algoritmo agradável e simples para a variância computacional da maneira online foi descrito por Welford (1962). Abaixo, você pode ver a implementação em C ++ / Rcpp que funciona offline, mas pode ser facilmente adaptada ao cenário online:

List welford_cpp(NumericVector x) {

  int n = x.length();
  double delta;
  double msq = 0;
  double mean = x[0];

  if (n > 1) {
    for (int i = 1; i < n; i++) { 
      delta = x[i] - mean;
      mean += delta / (i+1);
      msq += delta * (x[i] - mean);
    }
    return Rcpp::List::create(Rcpp::Named("mean") = mean,
                              Rcpp::Named("variance") = msq / (n-1));
  }

  return Rcpp::List::create(Rcpp::Named("mean") = mean,
                            Rcpp::Named("variance") = NAN);
}

Como você pode ver, ele precisa armazenar apenas quatro variáveis: n, delta, msqe meane calcula média e variância, simultaneamente, como você queria.

---

Welford, BP (1962). Observe um método para calcular somas corrigidas de quadrados e produtos . Technometrics 4 (3): 419-420.

A variância pode ser expressa como proporcional à diferença ao quadrado entre cada valor e o valor médio, ou (como muitos threads aqui em stats.SE documentados, como esta resposta que escrevi para outra pergunta) ela pode ser expressa como proporcional ao quadrado diferença de pares entre cada amostra.

Então sabemos:

$$\text {Var}(x) = \frac{1}{n} \cdot \sum_{i}(X_i-\overline{X})^2 = \frac{1}{2n^2} \cdot \sum_{i,j}(X_i-X_j)^2$$

Digamos que você adicione outra amostra, indexada como o último índice, . Sua variação anterior seria:$k$

$$\text {Var}_{old}(x) = \frac{1}{2(n-1)^2} \cdot \sum_{i<k,j<k}(X_i-X_j)^2$$

Sua nova variação é

$$\text {Var}_{new}(x) = \frac{1}{2n^2} \cdot \sum_{i,j}(X_i-X_j)^2 = \frac{1}{2n^2} \cdot \left( \sum_{i<k,j<k}(X_i-X_j)^2 + \sum_{j<k}(X_k-X_j)^2 + \sum_{i<k}(X_i-X_k)^2 \right)$$

Mas

$$\sum_{j<k}(X_k-X_j)^2 = \sum_{i<k}(X_i-X_k)^2\\ \sum_{i<k,j<k}(X_i-X_j)^2 = {2(n-1)^2} \cdot \text {Var}_{old}(x)$$

assim

$$\text {Var}_{new}(x) = \left(\frac{n-1}{n}\right)^2 \text{Var}_{old}(x)+ \frac{1}{n^2} \sum_{j<k}(X_k-X_j)^2$$

Como o @ MarkL.Stone disse nos comentários, isso ainda não é eficiente, porque devemos manter todos os . Então, vamos expandir a fórmula para chegar a algo mais tratável.$X_i$

$$\frac{1}{n^2}\sum_{j<k}(X_k-X_j)^2=\\ \frac{1}{n^2}\sum_{j<k}(X_k^2 - 2 \cdot X_j \cdot X_k + X_j^2)=\\ \frac{1}{n^2}\left(\sum_{j<k}X_k^2 - 2 \cdot X_k \cdot \sum_{j<k} X_j + \sum_{j<k} X_j^2\right)=\\ \frac{1}{n^2}\left(k\cdot X_k^2 - 2 \cdot X_k \cdot (k-1) \cdot \overline{X_{old}} + (k-1) \cdot \overline{X^2_{old}}\right)\\ $$ Porque $$\sum_{j<k} X_j = (k-1) \cdot \overline{X_{old}}\\ \sum_{j<k} X_j^2 = (k-1) \cdot \overline{X^2_{old}}$$

O formulário final é então

$$\text {Var}_{new}(x) = \left(\frac{n-1}{n}\right)^2 \text{Var}_{old}(x)+ \frac{1}{n^2}\left(k\cdot X_k^2 - 2 \cdot X_k \cdot (k-1) \cdot \overline{X_{old}} + (k-1) \cdot \overline{X^2_{old}}\right)$$

Você pode usar esta fórmula para atualizar a variação efetivamente em memória. Você também pode complementá-lo para usar lotes em vez de atualizações de ponto único.

Basicamente, você precisa armazenar a média, a média das amostras ao quadrado e a variação a cada iteração e usá-la para atualizar a fórmula de variação.

---

Mais longe

$$\overline{X^2_{old}} = \text{Var}_{old}(x) + (\overline{X_{old}})^2\\ \therefore\text {Var}_{new}(x) = \left(\frac{n-1}{n}\right)^2 \text{Var}_{old}(x)+ \frac{1}{n^2}\left(k\cdot X_k^2 - 2 \cdot X_k \cdot (k-1) \cdot \overline{X_{old}} + (k-1) \cdot \left(\text{Var}_{old}(x) + (\overline{X_{old}})^2\right)\right)$$

O que reduz o número de quantidades que precisam ser armazenadas para 2.

OK, Andy W deu a resposta. Conservando a média da mesma maneira que a média E, você pode usar .$E^2$$V = exp(E^2)-exp(E)^2$