Calcul/stockage CDF empirique efficace

Question

J'essaye de précalculer les distributions de plusieurs variables aléatoires. En particulier, ces variables aléatoires sont les résultats de fonctions évaluées à des emplacements dans un génome, de sorte qu'il y aura de l'ordre de 10^8 ou 10^9 valeurs pour chacun. Les fonctions sont assez fluides, donc je ne pense pas que je vais perdre beaucoup de précision en n'évaluant qu'à chaque 2ème/10ème/100ème. base ou plus, mais indépendamment, il y aura un grand nombre d'échantillons. Mon plan est de pré-calculer des tables de quantiles (peut-être des centiles) pour chaque fonction et de les référencer dans l'exécution de mon programme principal pour éviter d'avoir à calculer ces statistiques de distribution dans chaque exécution. Mais je ne vois pas vraiment comment je peux facilement faire cela: stocker, trier, et réduire un tableau de 10^9 flotteurs n'est pas vraiment possible, mais je ne peux pas penser à une autre manière qui ne fonctionne pas. perdre des informations sur la distribution. Existe-t-il un moyen de mesurer les quantiles d'une distribution d'échantillon qui ne nécessite pas de stocker le tout en mémoire?

Answer 1

Je suis d'accord avec le commentaire de @ katriealex: demander à quelqu'un avec de solides antécédents en statistiques.

Vous pouvez facilement évaluer l'écart min/max/mean/std sans avoir besoin de stocker une quantité significative de mémoire. (Note pour la déviation moyenne + std: utiliser la technique de Knuth:..

delta = x - m[n-1] 
m[n] = m[n-1] + 1/n * delta 
S[n] = S[n-1] + (x[n] - m[n])*delta 
mean = m[n] 
std dev = sqrt(S[n]/n) 

Cela vous empêche de trop-plein virgule flottante/problèmes sousverse rencontrés dans le calcul naïf de std dev, par exemple taking S1 = the sum of x[k] and S2 = the sum of x[k]^2 and trying to calculate std deviation = sqrt(S2/N - S1^2/N^2) Voir aussi Wikipedia)

Il existe probablement d'autres algorithmes orientés flux pour calculer des moments caractéristiques plus élevés de la distribution, mais je ne sais pas ce qu'ils sont.

Ou bien, vous pouvez également utiliser les techniques histogramming avec suffisamment de casiers pour caractériser la distribution.