Среднее распространение с ограничением памяти

Question

задача

Я хочу приблизить медиану данного распределения $ d $ что я могу образец.

Простой алгоритм для этого, используя $ n $ Образцы, это:

samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

.

Тем не менее, я ищу алгоритм, который требует меньше, чем $ O (n) $ пространство .

идеи

Я посмотрел в эти алгоритмы:

.
• Медиана медианов : нуждается в $ o (n) $ space, поэтому он не работает для меня.
• Рандомизированная медиана : Это может быть легко обобщено в алгоритме, который использует $ O (n ^ {3/4}) $ пространство.

Есть ли другие алгоритмы, которые используют менее, то $ O (n) $ Space, которое может решить мою проблему? В частности, я думал, что может быть алгоритм, который использует $ O (M) $ пространство, создавая партии образцов из $ D $ размер $ m $ ...

Детали

.
• В идеале я ищу ссылку на алгоритм, который также включает в себя анализ (вероятность успеха, ожидаемое время выполнения и т. Д.).
• На самом деле, мне нужен алгоритм, чтобы оценить $ d $ 's $ p $ -th Proctile Для заданного $ P $ , но я надеюсь, что большинство средних алгоритмов нахождения могут быть обобщены для этого.
• Я хотел бы достичь той же точности, что и простой алгоритм, показанный выше. Один из способов добиться этого - использование алгоритма, выходное распределение которого совпадает с алгоритмом образца (но, возможно, новый алгоритм может потерпеть неудачу в редких случаях)

Answer 1

Конечно, вы определенно можете достичь этого, используя немного больше времени работы. Вот концептуально простым подходом, который может быть не оптимальным, но начнет вас и, вероятно, довольно хорошо:

Используйте двоичный поиск, чтобы найти приблизительный медианный $ m $ . Откуда вы знаете, является ли кандидатом $ m $ слишком большой или слишком маленький? Образец $ n '$ Times от распределения, подсчитайте, сколько раз образцы $ \ Ge m $ и сравните этот счет на $ n '/ 2 $ . Это можно сделать с помощью $ O (1) $ пространство.

Тогда ключевой вопрос становится: как мы выбираем $ n '$ , чтобы контролировать вероятность ошибки? Простой подход состоит в том, чтобы выбрать $ n '$ , чтобы быть достаточно больше, чем $ n $ что вероятность Ошибка в каждой итерации двоичного поиска - $ T $ меньше, чем вероятность ошибки при использовании $ n $ Образцы, где $ T $ - это количество итераций двоичных поисков, необходимых для достижения желаемой точности. Затем, связанная союза гарантирует, что это будет соответствовать вашим условиям точности.

К сожалению, ваше условие точности немного трудно работать, когда мы ничего не знаем о распределении данных, так как точность образца медиана может быть произвольно плохо. Например, рассмотрим распределение, которое выводит выходы $ 0 $ с вероятностью $ (1- \ Epsilon) / 2 $ и $ 100 $ с вероятностью $ (1+ \ epsilon) / 2 $ . Тогда средний образцы одинаково вероятно, может быть 0 или 100, тогда как медиана распределения составляет 100, Таким образом, средняя ошибка медиана образца составляет около 50 (если вы не рисуете $ \ gg 1 / \ epsilon ^ 2 $ Образцы). Это особенно неприятное распределение, и это будет трудно работать. Но если вы предполагаете, что распределение примерно гауссово (говорит) со стандартным отклонением $ \ Sigma $ , затем ошибка медиана, с $ n $ Образцы, примерно $ 1.25 \ sigma / \ sqrt {n} $ . Таким образом, вышеуказанный алгоритм может быть использован, где мы устанавливаем $ T \ Phoon \ LG (\ SQRT {N} /1.25) $ и мы устанавливаем $ n '\ Приблизительно NT ^ 2 $ .

Это один простой подход. Вы, вероятно, можете сделать лучше. Возможно, вы хотели бы посмотреть алгоритмы потокового потока для вычисления медиана, поскольку они решают проблему, с которым вы работаете: учитывая неограниченное количество образцов из распределения, но только ограниченное количество пространства, какую наилучшую оценку мы можем получить медиана? Например, вот один простой алгоритм: первый слой неоднократно занимает три образца и выводит медиану из этих трех; Второй слой неоднократно занимает три числа от первого слоя и выводит медиану из этих трех; и так далее. После логарифмически числа слоев вы получаете разумное приближение к медиану. Есть целая литература на эту тему, и вы сможете больше найти много.