Введение
K-е наименьшее значение в статистической выборке
В статистике k-я порядковая статистика статистической выборки равна её k-му наименьшему значению. Вместе со статистиками рангов, порядковые статистики являются одними из самых фундаментальных инструментов в непараметрической статистике и выводе. Важными частными случаями порядковых статистик являются минимальное и максимальное значения выборки, а также (с некоторыми оговорками, которые будут рассмотрены ниже) медиана выборки и другие квантили выборки. При использовании теории вероятностей для анализа порядковых статистик случайных выборок из непрерывного распределения, кумулятивная функция распределения используется для упрощения анализа до случая порядковых статистик равномерного распределения.
Вероятностный анализ
При любых случайных величинах X1, X2, …, Xn, статистики порядка X(1), X(2), …, X(n) также являются случайными величинами, определяемыми упорядочиванием значений (реализаций) X1, X2, …, Xn по возрастанию. Если случайные величины X1, X2, …, Xn образуют выборку, то они независимы и одинаково распределены. Этот случай рассматривается ниже. В общем случае случайные величины X1, X2, …, Xn могут быть получены из нескольких генеральных совокупностей. Тогда они независимы, но не обязательно одинаково распределены, и их совместное распределение вероятностей описывается теоремой Бапат–Бега. Далее мы будем предполагать, что рассматриваемые случайные величины непрерывны и, где это целесообразно, что они имеют функцию плотности вероятности (PDF), то есть являются абсолютно непрерывными. Особенности анализа распределений, присваивающих массу точкам (в частности, дискретных распределений), обсуждаются в заключении.
Статистика заказов, выбранная из экспоненциального распределения
Для случайной выборки размера n из экспоненциального распределения с параметром λ, статистики порядка X(i) при i = 1, 2, 3, ..., n каждая имеет распределение
где Zj – независимые и одинаково распределённые стандартные экспоненциальные случайные величины (т.е. с параметром скорости 1). Этот результат был впервые опубликован Альфредом Реньи.
Статистика заказов, взятых из распределения Erlang
Трансформация Лапласа статистики порядков может быть получена из распределения Эрланга методом подсчета путей.
Применение: доверительные интервалы для квантилов
Интересный вопрос состоит в том, насколько эффективно статистики порядка оценивают квантили исходного распределения.
Пример с небольшим размером выборки
Самый простой случай для рассмотрения – это то, насколько хорошо выборочная медиана оценивает медиану генеральной совокупности. В качестве примера рассмотрим случайную выборку размером 6. В этом случае выборочная медиана обычно определяется как середина интервала, ограниченного статистиками 3-го и 4-го порядков. Однако, из предыдущего обсуждения мы знаем, что вероятность того, что этот интервал действительно содержит медиану генеральной совокупности, равна…
Хотя выборочная медиана, вероятно, является одной из лучших точечных оценок медианы генеральной совокупности, не зависящих от распределения, этот пример иллюстрирует, что она не особенно хороша в абсолютном выражении. В этом конкретном случае, лучшим доверительным интервалом для медианы является интервал, ограниченный статистиками 2-го и 5-го порядков, который содержит медиану генеральной совокупности с вероятностью…
При таком небольшом размере выборки, если требуется хотя бы 95% уровень доверия, можно лишь утверждать, что медиана находится между минимальным и максимальным значениями из 6 наблюдений с вероятностью 31/32, или приблизительно 97%. Размер выборки, равный 6, является, фактически, наименьшим размером выборки, при котором интервал, определяемый минимальным и максимальным значениями, представляет собой доверительный интервал для медианы генеральной совокупности, по крайней мере, с уровнем доверия 95%.
Статистика вычислений заказов
Проблема вычисления k-го наименьшего (или наибольшего) элемента списка называется задачей выбора и решается алгоритмом выбора. Хотя эта задача сложна для очень больших списков, были разработаны эффективные алгоритмы выбора, способные решать её за время, пропорциональное количеству элементов в списке, даже если список полностью неупорядочен. Если данные хранятся в определенных специализированных структурах данных, это время можно сократить до O(log n). Во многих приложениях требуется вся статистика упорядоченности, в этом случае можно использовать алгоритм сортировки, и время выполнения составит O(n log n).