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

Question

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

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

Answer 1

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

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

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)

Это предотвращает проблемы с переполнением или недостаточным вычислением с плавающей точкой, возникающие при простом вычислении std dev, например принимая S1 = сумму x [k] и S2 = сумму x [k] ^ 2 и пытаясь вычислить стандартное отклонение = sqrt (S2 / N - S1 ^ 2 / N ^ 2) . Смотрите также Википедия .)

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

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