Ich möchte gerne schnell zufällige Shuffles mit minimaler Verzerrung erzeugen.
Es ist bekannt, dass Fisher-Yates Shuffle so lange unvoreingenommen ist wie die zugrunde liegende Zufallszahl Generator (RNG) ist unvoreingenommen.
%Vor%Aber was, wenn der Zufallsgenerator voreingenommen ist (aber schnell)?
Angenommen, ich möchte viele zufällige Permutationen eines Arrays von 25 Elementen erzeugen. Wenn ich den Fisher-Yates-Algorithmus mit einer verzerrten RNG verwende, dann ist meine Permutation voreingenommen, aber ich gehe davon aus, dass das 25-Element-Array vor jeder Anwendung des Shuffle-Algorithmus aus demselben Zustand startet. Ein Problem, zum Beispiel, wenn der Zufallszahlengenerator nur eine Periode von 2 ^ 32 ~ 10 ^ 9 hat, können wir nicht jede mögliche Permutation der 25 Elemente erzeugen, weil dies 25 ist! ~ 10 ^ 25 Permutationen.
Meine allgemeine Frage lautet: Wenn ich die gemischten Elemente, die vor dem Start jeder neuen Anwendung des Fisher-Yates Shuffle gemischt werden, belassen würde, würde dies die Verzerrung reduzieren und / oder dem Algorithmus erlauben, jede Permutation zu erzeugen?
Meine Vermutung ist, dass es im Allgemeinen bessere Ergebnisse liefern würde, aber es sieht so aus, als hätte das Array, das wiederholt gemischt wurde, eine Anzahl von Elementen, die mit der zugrunde liegenden RNG in Beziehung standen, die Permutationen könnten tatsächlich öfter als erwartet wiederholt werden.
Kennt irgendjemand irgendeine Forschung, die das anspricht?
Als Unterfrage, was ist, wenn ich nur wiederholte Permutationen von 5 der 25 Elemente im Array möchte, also verwende ich den Fisher-Yates-Algorithmus, um 5 Elemente auszuwählen und anzuhalten, bevor ich einen vollständigen Shuffle mache? (Ich verwende die 5 Elemente am Ende des Arrays, das ausgetauscht wurde.) Dann beginne ich mit dem vorherigen teilweise gemischten 25-Element-Array, um eine weitere Permutation von 5 auszuwählen. Wieder scheint es, als wäre das besser als von der ursprüngliches 25-Element-Array, wenn der zugrunde liegende RNG eine Verzerrung aufwies. Irgendwelche Gedanken dazu?
Ich denke, es wäre einfacher, den Partial-Shuffle-Fall zu testen, da es nur 6.375.600 mögliche Permutationen von 5 von 25 Elementen gibt. Gibt es also einfache Tests zur Überprüfung von Verzerrungen?
wenn der RNG nur eine Periode von 2 ^ 32 ~ hat 10 ^ 9 wir können nicht alle möglichen produzieren Permutation der 25 Elemente, weil das ist 25! ~ 10 ^ 25 Permutationen
Das ist nur wahr, solange der Keim jede nachfolgende Auswahl bestimmt. Solange von Ihrem RNG erwartet wird, dass er eine genau gleichmßige Verteilung über den für jede nächste Auswahl spezifizierten Bereich liefert, kann er jede Permutation erzeugen. Wenn Ihr RNG das nicht kann, hilft eine größere Seed Base nicht.
Was deine Nebenfrage betrifft, könntest du genauso gut für jede Ziehung reseedieren. Das erneute Seeding des Generators ist jedoch nur sinnvoll, wenn das erneute Seeding genügend Entropie enthält. Zeitstempel enthalten nicht viel Entropie, auch keine algorithmischen Berechnungen.
Ich bin mir nicht sicher, wozu diese Lösung gehört, weil Sie sie nicht aufgelistet haben, aber wenn Sie versuchen, etwas aus einer größeren Domäne mit zufälligen Eingaben zu berechnen, gibt es wahrscheinlich bessere Methoden.
Ein paar Punkte:
1) Wer den Fisher Yates shuffle benutzt, sollte dies lesen und stellen Sie sicher, dass ihre Implementierung korrekt ist.
2) Wiederholt der Shuffle nicht den Zweck, einen schnelleren Zufallsgenerator zu verwenden? Sicher, wenn du jeden Shuffle 5 Mal wiederholen musst, um die gewünschte Entropie zu erhalten, solltest du besser einen Low-Bias-Generator verwenden
3) Haben Sie eine Einrichtung, wo Sie das testen können? Wenn ja, versuchen Sie es mit den Dingen - Jeffs Graphen machen deutlich, dass Sie mit kleinen Decks ziemlich viele Fehler entdecken und die Ergebnisse visuell darstellen können.
Mein Gefühl ist, dass mit einem verzerrten RNG wiederholte Runs des Knuth Shuffle alle Permutationen erzeugen würden, aber ich kann es nicht beweisen (es hängt von der Periode des RNG ab und wie viel voreingenommen es ist ).
Lassen Sie uns also die Frage umkehren: Wenn ein Algorithmus eine zufällige Eingabe und eine verzerrte RNG benötigt, ist es dann einfacher, die Ausgabe des Algorithmus zu verfälschen oder die Ausgabe des RNG zu verfälschen?
Es ist nicht überraschend, dass Letzteres viel einfacher ist (und von größerem Interesse ist): Es gibt mehrere Standardtechniken, um das zu tun. Eine einfache Technik, die von Neumann stammt, ist: Geben Sie einen Bitstrom von einem voreingestellten RNG, nehmen Sie Bits in Paaren, werfen Sie jedes (0,0) und (1,1) Paar weg, geben Sie eine 1 für jeden (1,0) zurück. Paar und eine 0 für jedes (0,1) Paar. Diese Technik setzt voraus, dass die Bits aus einem Strom stammen, wobei jedes Bit die gleiche Wahrscheinlichkeit hat, eine 0 oder 1 zu sein wie jedes andere Bit in dem Strom und dass die Bits nicht korreliert sind. Elias verallgemeinert von Neumanns Technik zu einem effizienteren Schema (eine Stelle, an der weniger Bits verworfen werden).Aber auch stark verzerrte oder korrelierte Bits können nützliche Mengen an Zufälligkeit enthalten, zum Beispiel mit einer Technik, die auf Fast Fourier Transform basiert .
Eine weitere Option besteht darin, die verzerrte RNG-Ausgabe einer kryptografisch starken Funktion zuzuführen, beispielsweise einem Message Digest-Algorithmus, und ihre Ausgabe zu verwenden.
Für weitere Hinweise, wie man Zufallszahlengeneratoren entstellt, empfehle ich Ihnen, den Randomness Recommendations for Security RFC .
Mein Punkt ist, dass die Qualität, wenn die Ausgabe eines Zufalls-basierten Algorithmus durch die Entropie, die durch den RNG bereitgestellt wird, begrenzt ist: wenn sie extrem voreingenommen ist, wird die Ausgabe extrem voreingenommen sein, egal was Sie tun. Der Algorithmus kann nicht mehr Entropie erzwingen als der, der in dem voreingestellten Zufallsbitstrom enthalten ist. Schlimmer noch: es wird wahrscheinlich einige zufällige Bits verlieren. Selbst wenn angenommen wird, dass der Algorithmus mit einem verzerrten RNG arbeitet, müssen Sie, um ein gutes Ergebnis zu erhalten, einen Rechenaufwand mindestens so groß wie den Aufwand machen, um den RNG zu entschärfen (aber es wird wahrscheinlich mehr Aufwand erfordern, da Sie beide den Algorithmus ausführen müssen und die Verzerrung gleichzeitig "besiegen" müssen.
Wenn Ihre Frage nur theoretisch ist, dann ignorieren Sie bitte diese Antwort. Wenn es praktisch ist, dann denken Sie bitte ernsthaft darüber nach, den Zufallszahlengenerator zu entstellen, anstatt Annahmen über die Ausgabe des Algorithmus zu machen.
Ich kann Ihre Frage nicht vollständig beantworten, aber diese Beobachtung schien zu lang für einen Kommentar.
Was passiert, wenn Sie sicherstellen, dass die Anzahl der Zufallszahlen, die von Ihrem RNG für jede Iteration von Fisher-Yates gezogen werden, ein hohes geringstes gemeinsames Vielfaches mit dem RNG-Zeitraum aufweist? Das kann bedeuten, dass Sie am Ende des Algorithmus eine zufällige Ganzzahl "verschwenden". Wenn Sie 25 Elemente mischen, benötigen Sie 24 Zufallszahlen. Wenn Sie am Ende eine weitere Zufallszahl ziehen, die 25 Zufallszahlen ergibt, haben Sie nicht garantiert, dass Sie eine Wiederholung für viel länger als die RNG-Periode haben. Nun, zufällig, könnten Sie natürlich die gleichen 25 Zahlen nacheinander vor dem Erreichen der Periode auftreten. Aber da 25 keine anderen gemeinsamen Faktoren als 1 mit 2 ^ 32 hat, würden Sie keine garantierte Wiederholung bis 25 * (2 ^ 32) treffen. Nun, das ist keine große Verbesserung, aber Sie haben gesagt, dass dieser RNG schnell ist. Was wäre, wenn der "Abfall" -Wert viel größer wäre? Es ist vielleicht immer noch nicht praktisch, jede Permutation zu bekommen, aber Sie könnten zumindest die Anzahl erhöhen, die Sie erreichen können.
Es hängt ganz von der Voreingenommenheit ab. Im Allgemeinen würde ich sagen "Zählen Sie nicht darauf".
Biased-Algorithmus, der gegen nicht-voreingenommen konvergiert:
Mach die halbe Zeit nichts, und die andere Hälfte mischt richtig. Konvergiert exponentiell zu nicht-voreingenommen. Nach n Shuffles gibt es eine 1-1 / 2 ^ n Chance, dass der Shuffle nicht verzerrt ist und eine 1/2 ^ n Chance, dass die Inputsequenz ausgewählt wurde.
Biased Algorithmus, der voreingenommen bleibt:
Mische alle Elemente mit Ausnahme des letzten. Permanent voreingenommen, um das letzte Element nicht zu verschieben.
Allgemeineres Beispiel:
Stellen Sie sich einen Shuffle-Algorithmus als einen gewichteten gerichteten Graphen von Permutationen vor, bei dem die Gewichte eines Knotens der Wahrscheinlichkeit entsprechen, beim Mischen von einer Permutation zu einer anderen überzugehen. Ein voreingestellter Shuffle-Algorithmus hat ungleichmäßige Gewichte.
Nun nehmen wir an, Sie haben einen Knoten in diesem Graphen mit Wasser gefüllt, und Wasser floss von einem Knoten zum nächsten, basierend auf den Gewichten. Der Algorithmus konvergiert zu nicht-voreingenommen, wenn die Verteilung von Wasser gleichförmig konvergiert, unabhängig vom Startknoten.
In welchen Fällen wird sich das Wasser nicht gleichmäßig ausbreiten? Nun, wenn Sie einen Zyklus von überdurchschnittlichen Gewichten haben, tendieren Knoten im Zyklus dazu, sich gegenseitig zu füttern und über der durchschnittlichen Wassermenge zu bleiben. Sie werden nicht alles davon nehmen, denn wenn sie mehr Wasser bekommen, nimmt die Menge, die hereinkommt, ab und die Menge, die hinausgeht, wird zunehmen, aber sie wird über dem Durchschnitt liegen.
Tags und Links algorithm random permutation shuffle