Шортная концентрация для отбора посредством случайного разделения?

Question

Обычный простой алгоритм для поиска медианного элемента в массиве $ a $ $ n $ номера - это:

• Пример $ n^{3/4} $ Элементы из $ a $ с заменой в $ b $
• Сортировать $ b $ и найти ранг $ | b | pm sqrt {n} $ elements $ l $ и $ r $ of $ b $
• Проверьте, что $ l $ и $ r $ находятся на противоположных сторонах среднего размера $ a $ и что в размере максимум $ c sqrt {n} $ elements в $ a $ от $ l $ до $ $ для некоторых подходящих Постоянный $ C> 0 $. Терпит неудачу, если этого не произойдет.
• В противном случае, найдите медиану, сортируя элементы $ A $ от $ l до $ r $

Нетрудно видеть, что это работает в линейное время и что он успешен с высокой вероятностью. (Все плохие события - это большие отклонения от ожидания биномиала.)

Альтернативный алгоритм той же проблемы, который более естественен для обучения студентам, которые видели быстрый сортинг, - это описанный здесь: Рандомизированный выбор

Также легко увидеть, что у этого есть линейное ожидаемое время работы: скажем, что «круглый»-это последовательность рекурсивных вызовов, которые заканчиваются, когда кто-то дает разделение 1/4-3/4, а затем наблюдает, что ожидаемая длина Раунд не более 2 (в первом розыгрыше раунда вероятность получения хорошего разделения составляет 1/2, а затем после того, как фактически увеличивается, так как алгоритм описывался так раунд, в которой преобладает геометрическая случайная переменная.)

Итак, теперь вопрос:

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

У нас есть раунды $ o ( log n) $, и каждый раунд имеет длину как минимум $ k $ с вероятностью, не более $ 2^{-k+1} $, поэтому в профсоюзном границу дает время выполнения $ o (n log log n) $ с вероятностью $ 1-1/o ( log n) $.

Это довольно неудовлетворительно, но на самом деле это правда?

Answer 1

Не правда, что алгоритм работает в линейное время с высокой вероятностью. Учитывая только первый раунд, время работы составляет не менее $ theta (n) $ times a $ g (1/2) $ случайная переменная. Пусть $ p (n) longrightarrow 0 $ будет допустимой вероятностью отказа. Поскольку $ pr [g (1/2) geq log_2 p (n)^{-1}] = p (n) $, время работы составляет не менее $ omega (n log_2 p (n)^ {-1}) = omega (n) $.

(Существует некоторое мошенничество, поскольку длина первого раунда на самом деле не является $ g (1/2) $. Более тщательный анализ может или не может подтвердить этот ответ.)

РЕДАКТИРОВАТЬ: Грюбель и Рослер доказали, что ожидаемое количество сравнений, деленных на $ n $, имеет тенденцию (в некотором смысле) до некоторого лимитного распределения, которое не ограничено. См., Например, статья Гюбеля «Алгоритм отбора Хоара: подход к цепочке Маркова», который ссылается на их оригинальную статью.