Оценка медианы за один проход без сортировки

[askrotov]

Собственно, сабж существует с приемлемой точностью.
То есть, по мере поступления данных $X_i$ можно сразу получить выборочное среднее $\bar{X} = \frac{1}{n}\sum_{i=1}^n X_i$, выборочную дисперсию $S^2_n = \frac{1}{n}\sum\limits_{i=1}^nX_i^2-\left(\frac{1}{n}\sum\limits_{i=1}^nX_i\right)^2$ при каждом изменении $n$.

А выборочную медиану или какое-нибудь ее приближение без сортировки можно получить?

Анатолий

[Евгений Машеров]

Смотря что дозволено.
Скажем, формально решением является формирование "по мере поступления" вставками отсортированного массива. Это "без сортировки" или нет? Можно немного сэкономить, массив формировать из первой половины данных, а последующие точки нам просто позволят отметить, где в этом массиве медиана (экономия 50% памяти).
Если распределение входных данных не слишком прихотливо (ну, скажем, мы уверены, что оно одномодальное и с конечными моментами), то можно "по мере поступления" считать моменты, по ним строить аппроксимирующее распределение (разложение Грама-Шарлье, система Пирсона и т.п.) и по нему вычислять медиану.

[askrotov]

Спасибо за быстрый ответ. Буду разбираться.

То есть, все подобные попытки от лукавого?

[Александрович]

Евгений Машеров в сообщении #788874 писал(а):

Если распределение входных данных не слишком прихотливо (ну, скажем, мы уверены, что оно одномодальное и с конечными моментами), то можно "по мере поступления" считать моменты, по ним строить аппроксимирующее распределение (разложение Грама-Шарлье, система Пирсона и т.п.) и по нему вычислять медиану.

А ведь медиана со средним значением и коэффициентом асимметрии должна быть как-то связана?

[nikvic]

askrotov в сообщении #788870 писал(а):

А выборочную медиану или какое-нибудь ее приближение без сортировки можно получить?

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

[askrotov]

Александрович в сообщении #788896 писал(а):

Евгений Машеров в сообщении #788874 писал(а):

Если распределение входных данных не слишком прихотливо (ну, скажем, мы уверены, что оно одномодальное и с конечными моментами), то можно "по мере поступления" считать моменты, по ним строить аппроксимирующее распределение (разложение Грама-Шарлье, система Пирсона и т.п.) и по нему вычислять медиану.

А ведь медиана со средним значением и коэффициентом асимметрии должна быть как-то связана?

Я видел где-то такую связь: оценка медианы $me=avg-std\frac {skew} {3}$, оценка моды $mo=avg-std\cdot skew$, где $avg$ - выборочное среднее, $std$ - выборочная дисперсия, $skew$ - выборочный коэффициент ассиметрии.

[Евгений Машеров]

askrotov в сообщении #788893 писал(а):

Спасибо за быстрый ответ. Буду разбираться.

То есть, все подобные попытки от лукавого?

Ну отчего же "от лукавого"? Они же начинают с Relationship between the mean, median, mode, and standard deviation in a unimodal distribution
То есть это не "универсальная оценка", а некое приближение для важного частного случая. На мой взгляд, довольно грубое, но может быть полезно.

[Александрович]

Вопрос к ТС. Какое количество значений с.в. можно запомнить?

[askrotov]

Александрович в сообщении #788911 писал(а):

Вопрос к ТС. Какое количество значений с.в. можно запомнить?

около $500000$

[Евгений Машеров]

Да, через гистограмму можно за один проход получить оценку медианы (и вообще любого квантиля) с гарантированной ошибкой в один бин, причём реальная точность за счёт интерполяции может быть заметно выше. Но, чтобы начать построение гистограммы, надо бы знать максимальное и минимальное значение выборки (ну, или дико резервировать память, или использовать списки).

[askrotov]

Понятно, спасибо за ответы.

[Александрович]

askrotov в сообщении #788913 писал(а):

Александрович в сообщении #788911 писал(а):

Вопрос к ТС. Какое количество значений с.в. можно запомнить?

около $500000$

А тогда какие проблемы с нахождением медианы?

[Евгений Машеров]

Александрович в сообщении #788896 писал(а):

Евгений Машеров в сообщении #788874 писал(а):

Если распределение входных данных не слишком прихотливо (ну, скажем, мы уверены, что оно одномодальное и с конечными моментами), то можно "по мере поступления" считать моменты, по ним строить аппроксимирующее распределение (разложение Грама-Шарлье, система Пирсона и т.п.) и по нему вычислять медиану.

А ведь медиана со средним значением и коэффициентом асимметрии должна быть как-то связана?

Вообще говоря, нет. Можно построить контрпример, в котором медиана и среднее неизменны, а асимметрия растёт неограничено.
Но для распределений, похожих на нормальное (унимодальны, асимметрия и эксцесс невелики) можно получить прикидку.

[nikvic]

Евгений Машеров в сообщении #788916 писал(а):

Да, через гистограмму можно за один проход получить оценку медианы (и вообще любого квантиля) с гарантированной ошибкой в один бин

В "моём" варианте, когда границы интервалов образуют данные начального куска массива, бины различны.
Во многих случаях медиана попадёт в интервал, длина которого существенно меньше средней.

[Евгений Машеров]

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