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

Question

Это спина от этого StackOverflow question.

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

Вопросы

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

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

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

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

Answer 1

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

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

Answer 2

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

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