Эффективное эмпирическое вычисление/хранение CDF

Question

Я пытаюсь прекомпретировать распределения нескольких случайных величин. В частности, эти случайные величины являются результатами функций, оцененных в местах в геноме, поэтому для каждого из них будет порядка 10^8 или 10^9 значений. Функции довольно гладкие, поэтому я не думаю, что потеряю много точности, оценивая только на каждом втором/10-м/100-м? базы или около того, но независимо от того, будет ли большое количество образцов. Мой план состоит в том, чтобы предварительно компилировать таблицы (например, процентили) для каждой функции и ссылаться на них при выполнении моей основной программы, чтобы избежать необходимости вычислять статистику распределения в каждом прогоне.

Но я действительно не вижу, как я могу это сделать: хранение, сортировка и сокращение массива из 10^9 поплавков на самом деле невозможно, но я не могу думать о другом способе, который не потерять информацию о распределении. Есть ли способ измерения квантилей выборочного распределения, который не требует хранения всего этого в памяти?

Answer 1

Я согласен с комментарием @ katriealex: спросите кого-нибудь с сильным фоном статистики.

Вы можете легко оценить min/max/mean/std отклонение без необходимости хранить какой-либо значительный объем памяти. (Обратите внимание на среднее + станд отклонение: используйте метод Кнута:..

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) 

Это предотвращает вас от плавающей точки переполнения/нижних продукт проблем, возникающих при наивном расчете станда разработчика, например 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) Смотрите также Wikipedia)

Есть, вероятно, другие поточно-ориентированные алгоритмы для вычисления более высоких характерных моментов распределения, но я не знаю, что они собой представляют.

Или вы также можете использовать методы histogramming с достаточным количеством бункеров для характеристики распределения.