Вероятность нахождения медианы с конечным пространством

Question

Это ответвление этого StackOverflow вопрос .

Предположим, что у вас есть фиксированное число k мест хранения и место для двух счетчиков.Вы получите n предметов в случайном порядке (все перестановки n предметов одинаково вероятны).После получения каждого предмета вы можете либо сохранить его в одном из k мест (отменить одно из ранее сохраненных значений), либо отбросить предмет.Вы также можете увеличить или уменьшить один из счетчиков.Ни один выброшенный предмет не может быть найден.

Вопросы:

1. Какая стратегия максимально увеличивает вашу вероятность нахождения точной медианы?
2. Какова эта вероятность?

Очевидно, что если k> n / 2 , мы можем найти медиану.В целом, похоже, что та же стратегия попыток сохранить количество отброшенных высоких значений равным количеству отброшенных низких значений должна быть оптимальной, но я не уверен, как это доказать или как выяснить вероятность того, что он найдетМедиана.

Также интересен случай, когда мы не знаем n , но знаем распределение вероятностей n .

Редактировать: Предположим, что значения различны (без дубликатов). Однако, если вы можете решить и не отдельный случай, то это будет впечатляющим.

Answer 1

Манро и Патерсон изучили эту проблему в своей статье Отбор и сортировка при ограниченном хранении .Они показывают, что ваш алгоритм требует k = Ω (√n) для успеха с постоянной вероятностью и что это асимптотически оптимально, если обратиться к основным результатам об одномерных случайных блужданиях.

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

Answer 2

Дикая догадка: отбросить элемент, который находится дальше всего от среднего сохраненных в данный момент значений.

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