Wiederverwendung der Zufallszahl bei der Probenahme im Reservoir
Es wurde kürzlich in Bezug auf eine andere Frage gefragt: Bei einer Liste unbekannter Länge geben Sie ein zufälliges Element zurück, indem Sie es nur einmal scannen
Ich weiß, dass Sie nicht sollten, ich kann mich einfach nicht auf eine kanonische Erklärung dafür konzentrieren, warum nicht.
Sehen Sie sich den Beispielcode an:
%Vor%Die Auswahlmöglichkeiten für die richtige Reservoir-Probenahme, die eine neue Zufallszahl pro Element erzeugt, sind gleichmäßig verteilt:
%Vor%Wenn Sie die gleiche Zufallszahl für alle Elemente erneut verwenden, erhalten Sie eine Verteilung auf die sehr niedrigen Zahlen:
%Vor%Was ist die Mathematik hier? Warum können Sie nicht dieselbe Zufallszahl erneut verwenden?
3 Antworten
Bearbeite als Antwort auf einen Kommentar:
Die Art und Weise, wie Reservoir-Sampling funktionieren sollte, ist: Sie möchten genau den richtigen Anteil an Samples aus jedem der vorhandenen Bins auswählen, um ein zusätzliches Bin mit der gleichen Wahrscheinlichkeit zu erstellen. In Ihrer sample() -Schleife müssen Sie Proben aus jeder Bin mit der Wahrscheinlichkeit item auswählen, da Sie zufällig eine der 1/(item + 1) -Bins gesampelt haben.
Bei fixed() hängen jedoch sowohl die Auswahlentscheidung als auch die vorherige Bin-Nummer von derselben festen 32-Bit-Nummer ab. Dies bedeutet, dass die Wahrscheinlichkeit, dass eine Probe aus jedem der Behälter entfernt wird, nicht einheitlich ist.
Überlegen Sie, was während der dritten Iteration der sample() -Schleife passiert. Sie haben drei vorhandene Bins (0, 1 und 2) und möchten jeweils 1/4 der Samples auswählen und zu einem neu erstellten Bin 3 hinzufügen.
Beachten Sie, dass alle 32-Bit fixed() -Zahlen in Bin 1 gerade sind (weil der erste Durchgang alle durch 2 teilbaren Zahlen ausgewählt hat) und alle Zahlen in Bin 0 ungerade sind (weil die geraden verschoben wurden) zu Mülleimer 1). Der zweite Durchlauf verschiebt alle Zahlen, die durch drei teilbar sind, in den Behälter 2 (was bis jetzt OK sein sollte und die geradzahlige / ungerade Teilung in den Behältern 0 und 1 nicht ändert).
Der dritte Durchlauf verschiebt dann alle fixed() -Zahlen, die durch 4 teilbar sind, in Fach 3. Dies wird jedoch die Hälfte der Zahlen aus Fach 1 auswählen (weil die Hälfte aller geraden Zahlen durch 4 teilbar ist), und keine der Zahlen aus bin 0 (weil sie alle ungerade sind). Obwohl die erwartete Größe der neuen Bin korrekt sein sollte, sind die erwarteten Größen der alten Bins nicht mehr dieselben.
So erzeugt fixed() eine ungleiche Verteilung: Die implizite Annahme, dass Sie durch Auswahl einer Zufallszahl einen exakten Bruchteil jedes Bins auswählen können, wird verletzt, wenn diese Zahl in vorhersehbarer Weise von den verwendeten Zahlen abhängt das Original bin.
Die Grundeigenschaft von Zufallszahlen besteht darin, dass jede Stichprobe statistisch unabhängig von den vorhergehenden Stichproben verteilt werden muss. Algorithmen, die auf Zufallszahlen basieren, hängen von dieser Eigenschaft ab.
Pseudozufallszahlengeneratoren (PRNGs) sind nicht wirklich zufällig; Wie Sie wissen, sind ihre Ergebnisse tatsächlich eine feste Reihenfolge. Die PRNG-Ergebnisse sind absichtlich verschlüsselt, so dass sie für die meisten Zwecke wie echte Zufallszahlen agieren. Wenn jedoch der PRNG für eine bestimmte Anwendung "schwach" ist, können die inneren Abläufe des PRNG mit den Details der Anwendung auf seltsame Weise mit sehr zufälligen Ergebnissen interagieren.
Was Sie hier ausprobieren, indem Sie dieselbe Zufallszahl erneut verwenden, baut eine schlechte PRNG auf. Die tatsächlichen Ergebnisse hängen von den Details ab, wie die Anwendung die Zufallszahlen verwendet ...
Obwohl fixed() eine absichtlich gebrochene PRNG ist, sind viele PRNGs in kommerziellen Bibliotheken "schwach" und können mit ähnlichen seltsamen Interaktionen mit einigen Anwendungen enden. In der Praxis ist "Schwäche" relativ zur Anwendung - und obwohl es statistische Tests gibt, die häufig verwendet werden, um schwache PRNGs aufzudecken, gibt es keine Garantie dafür, dass Ihre Anwendung nicht auf einer ungeraden Korrelation von even stolpern wird ein "starker" PRNG.
Wenn Sie jedes Mal eine Zufallszahl auswählen, hat das nächste Element aus dem Stream eine Chance von 1 / CURRENTSIZE, das zuvor ausgewählte Element zu schlagen.
Was ist das Problem mit einer Zufallszahl pro Stream ? Warum verdreht es die Verteilung?
Ich habe noch keine vollständige Antwort gefunden, aber ich habe eine Idee.
Nehmen wir zum Beispiel einen Strom von 100 Zahlen und wählen Sie eine Zufallszahl 0 ... 999. Jetzt betrachten wir es vom Standpunkt des zweiten Gegenstandes.
Wann gewinnt es? Nun, zuerst muss es N% 2 == 0 sein. Also muss es eine gerade Zahl sein. Außerdem wird es auch von jedem weiteren Vielfachen jedes Vielfachen von 2 im Stream übertroffen, 4 ... 6 ... 8 .... 10 usw. Aber es gewinnt zB auf 106.
Berechne alle Zahlen, mit denen es gewinnt, 0..999 und wir erhalten 81 mal!
Nun nehmen wir 4, es muss N% 4 == 0 sein und es wird um alle Vielfachen von 4 bis N (8 ... 12 .... 16) beatmet. Wenn wir berechnen, wie oft 4 gewinnen können, bekommen wir 45 mal ...! Die Verteilung ist also nicht fair.
Dies kann behoben werden, wenn Sie die Zufallszahl maximal auf die Größe des Streams setzen, dann haben alle eine Chance zu gewinnen, was wiederum zu einer gleichmäßigen Verteilung führt.
Zum Beispiel, wenn wir eine Streamgröße von 100 haben und wir eine Zufallszahl von 0..199 auswählen. Wir kennen die ersten 100 Zufallszahlen, die alle genau 1 Übereinstimmung haben, so dass sie gleichmäßig verteilt sind. Aber was passiert mit Zufallszahlen 99 ... 199? Die Verteilung ist nicht einmal! Zum Beispiel wird 101 nur 101% X == 0 für 1 geben. Dies gilt für alle Primzahlen (101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199). Der erste Punkt hat also eine viel größere Chance zu gewinnen als die anderen.
Dies ist nicht der Fall, wenn Sie für jeden Gegenstand eine neue Zufallszahl wählen. In diesem Fall können die Chancen hinzugefügt werden. Zum Beispiel, wenn der erste Gegenstand kommt, hat er eine Chance zu gewinnen, nämlich:
NICHT (1/2 + 1/3 + 1/4 + 1/5 + 1/6 (... usw.))
Tags und Links math random probability