Online-Generierung einheitlicher Muster

Question

Eine Quelle stellt einen Stream von Elementen $x_1, x_2,\dots$ bereit.Bei jedem Schritt $n$ wollen wir eine Zufallsstichprobe $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ der Größe $k$ speichern, d.h.$S_n$ sollte eine einheitlich ausgewählte Stichprobe aus allen $ binom{n}{k}$ möglichen Stichproben sein, die aus gesehenen Elementen bestehen.Wir müssen also bei jedem Schritt $n \ge k$ entscheiden, ob wir das nächste Element zu $S$ hinzufügen oder nicht.Wenn ja, müssen wir auch entscheiden, welche der aktuellen Elemente aus $S$ entfernt werden sollen.

Geben Sie einen Algorithmus für das Problem an.Beweisen Sie die Richtigkeit.

Answer 1

Da die Frage zweifelhaft ist, gebe ich nur Hinweise.

Haben Sie das Offensichtliche versucht?Fügen Sie das neue Element mit der Wahrscheinlichkeit $\frac{1}{n}$ zur Stichprobe hinzu.Wenn es hinzugefügt wird, wählen Sie zufällig eines der bereits in der Stichprobe vorhandenen Elemente aus und lassen Sie es fallen.Klingt ziemlich fair, nicht wahr?

Für einen Beweis müssen Sie induktiv vorgehen.In diesem Schritt gehen Sie davon aus, dass $S_{n-1}$ tatsächlich eine einheitliche Stichprobe ist.Daraus und aus der Art und Weise, wie Sie auswählen, ob $x_n$ einbezogen werden soll und welches Element entfernt werden soll, müssen Sie feststellen, dass $S_n$ ebenfalls eine einheitliche Stichprobe ist.

Versuchen Sie, die Richtigkeit der obigen Idee zu beweisen.Ist dies nicht der Fall, finden Sie heraus, wo das Problem liegt, und beheben Sie es.Sehen diese Antwort zu einer ähnlichen Frage für eine detaillierte Anwendung dieser Technik.

Answer 2

Der beste Algorithmus für Ihr Problem ist der Reservoir Sampling-Algorithmus.Lesen Das