Median der Verteilung mit Speichereinschränkung

Question

Task

Ich möchte annähernd dem Median einer bestimmten Verteilung $ D $ , aus der ich probieren kann.

Ein einfacher Algorithmus für diesen, mit $ n $ -Mamples, ist:

generasacodicetagpre.

Ich suche jedoch nach einem Algorithmus, der weniger benötigt, der weniger als $ O (n) $ Raum ist.

Ideen

Ich habe in diese Algorithmen gesucht:

.
• Median der Mediane : Bedarf $ o (n) $ space, so funktioniert es nicht für mich.
• Randomisiertes Median : Es scheint wie Dies kann leicht zu einem Algorithmus verallgemeinert werden, der $ O (N ^ {3/4}) $ Speicherplatz verwendet.

Gibt es andere Algorithmen, die weniger als $ o (n) $ space verwenden, der mein problem lösen könnte? Ich dachte insbesondere, es könnte ein Algorithmus geben, der $ O (m) $ Space verwendet, indem er Stapel von Proben von erzeugt $ D $ Größe $ M $ ...

Details

.
• Idealerweise suche ich nach einem Hinweis auf einen Algorithmus, der auch Analyse enthält (Erfolgswahrscheinlichkeit, erwartete Laufzeit usw.).
• Eigentlich brauche ich einen Algorithmus, um $ D $ 's $ P $ -th-Perzentil abzuschätzen Für einen bestimmten $ P $ , aber ich hoffe, dass die meisten mittelfindenden Algorithmen dazu verallgemeinert werden können.
• Ich möchte die gleiche Genauigkeit wie der oben gezeigte einfache Algorithmus erreichen. Eine Möglichkeit, dies zu erreichen, besteht darin, einen Algorithmus mit einem Algorithmus zu verwenden, dessen Ausgabeverteilung der Sample-Algorithmus (aber vielleicht der neue Algorithmus kann in seltenen Fällen fehlschlagen)

Answer 1

Sicher, Sie können dies definitiv mit etwas mehr Laufzeit erreichen. Hier ist ein konzeptionell einfacher Ansatz, der möglicherweise nicht optimal ist, aber Sie werden begonnen und ist wahrscheinlich ziemlich gut:

Binäre Suche verwenden, um einen ungefähren Median- $ M $ zu finden. Woher wissen Sie, ob der Kandidat $ M $ ist zu groß oder zu klein? Sample $ n '$ Zeiten aus der Verteilung, zählen Sie, wie oft die Proben $ \ ge M $ und vergleichen Sie, dass das Zählen auf $ N '/ 2 $ angezeigt wird. Dies kann mit $ O (1) $ Platz erfolgen.

Dann wird die Schlüsselfrage: Wie wählen wir $ n '$ , um die Fehlerwahrscheinlichkeit zu steuern? Ein einfacher Ansatz besteht darin, $ n '$ ausreichend größer als $ N $ , dass die Wahrscheinlichkeit von Fehler in jeder Iteration von Binärsuche ist $ T $ kleiner als die Wahrscheinlichkeit des Fehlers, wenn $ N $ Beispiele, wobei $ T $ die Anzahl der iterationen der binären Suche ist, um die gewünschte Genauigkeit zu erreichen. Dann stellt eine Union gebunden sicher, dass dies Ihre Genauigkeitsbedingungen erfüllt.

Leider ist Ihre Genauigkeitsbedingung ein bisschen schwer zu arbeiten, wenn wir nichts über die Verteilung der Daten kennen, da die Genauigkeit des Mustermedians willkürlich schlecht sein kann. Betrachten Sie zum Beispiel eine Verteilung, die die Ausgänge $ 0 $ mit Wahrscheinlichkeit $ (1- \ Epsilon) / 2 $ und 100 $ $ mit Wahrscheinlichkeit $ (1+ \ Epsilon) / 2 $ . Dann ist der Probenmedian um gleichermaßen wahrscheinlich 0 oder 100, während der Verteilermedian 100 ist, Der durchschnittliche Fehler des Probenmedians beträgt also etwa 50 (es sei denn, Sie zeichnen $ \ gg 1 / \ Epsilon ^ 2 $ proben). Das ist eine besonders böse Verteilung, und es wird schwer zu arbeiten. Wenn Sie jedoch davon ausgehen, dass die Verteilung annähernd Gaußscheinig ist (Sagen) mit Standardabweichung $ \ Sigma $ , dann der Fehler des Mustermedians mit $ N $ Samples, ist ungefähr $ 1,25 \ SIGMA / \ SQRT {N} $ . Somit kann der obige Algorithmus verwendet werden, wenn wir $ t \ ca. \ lg (\ sqrt {n} /1.25) $ set, und wir setzen $ n '\ ca. ^ 2 $ .

das ist ein einfacher Ansatz. Sie können wahrscheinlich besser machen. Sie möchten vielleicht streaming Algorithmen für den Computer, um den Median zu berechnen, da sie das Problem angehen, mit dem Sie arbeiten, mit der Sie mit einer unbegrenzten Anzahl von Proben aus der Verteilung, aber nur eine begrenzte Anzahl von Raum, was ist der beste Schätzbetrag, den wir für Sie bekommen können der Median? Zum Beispiel ist hier ein einfacher Algorithmus: Die erste Schicht dauert wiederholt drei Proben und gibt den Median dieser drei aus; Die zweite Schicht dauert wiederholt drei Zahlen von der ersten Schicht und gibt den Median dieser drei aus; und so weiter. Nach logarithmischer Anzahl von Ebenen erhalten Sie eine angemessene Annäherung an den Median. Zu diesem Thema gibt es eine ganze Literatur, und Sie sollten in der Lage sein, vieles mehr zu finden.