Was ist, wenn überhaupt, falsch an diesem Mischalgorithmus und wie kann ich das wissen?

Gerade als Hintergrund bin ich mir des perfekten Shuffle von Fisher-Yates bewusst . Es ist ein großartiges Shuffle mit seiner O (n) -Komplexität und seiner garantierten Einheitlichkeit, und ich wäre ein Dummkopf, es nicht zu verwenden ... in einer Umgebung, die direkte Aktualisierungen von Arrays ermöglicht (also in den meisten, wenn nicht allen) zwingende Programmierumgebungen).

Leider bietet Ihnen die funktionale Programmierwelt keinen Zugriff auf den veränderlichen Status.

Aufgrund von Fisher-Yates gibt es jedoch nicht viel Literatur, die ich zum Entwerfen eines Mischalgorithmus finden kann. Die wenigen Orte, die sich überhaupt damit befassen, tun dies kurz, bevor sie tatsächlich sagen: "Also hier ist Fisher-Yates, das ist alles, was Sie wissen müssen." Am Ende musste ich meine eigene Lösung finden.

Die Lösung, die ich mir ausgedacht habe, funktioniert wie folgt, um eine beliebige Datenliste zu mischen:

• Wenn die Liste leer ist, geben Sie den leeren Satz zurück.
• Wenn die Liste ein einzelnes Element enthält, geben Sie dieses einzelne Element zurück.
• Wenn die Liste nicht leer ist, partitionieren Sie die Liste mit einem Zufallszahlengenerator und wenden Sie den Algorithmus rekursiv auf jede Partition an, um die Ergebnisse zusammenzustellen.

Im Erlang-Code sieht es ungefähr so ​​aus:

shuffle([])  -> [];
shuffle([L]) -> [L];
shuffle(L)   ->
  {Left, Right} = lists:partition(fun(_) -> 
                                    random:uniform() < 0.5 
                                  end, L),
  shuffle(Left) ++ shuffle(Right).

(Wenn dies für Sie wie eine gestörte schnelle Sortierung aussieht, ist es im Grunde genommen so.)

Hier ist mein Problem: Die gleiche Situation, die das Finden von Mischalgorithmen, die nicht Fisher-Yates sind, erschwert, macht das Finden von Werkzeugen zum Analysieren eines Mischalgorithmus ebenso schwierig. Es gibt viel Literatur, die ich zur Analyse von PRNGs auf Einheitlichkeit, Periodizität usw. finden kann, aber nicht viele Informationen darüber, wie man ein Shuffle analysiert. (In der Tat waren einige der Informationen, die ich bei der Analyse von Shuffles gefunden habe, einfach falsch - leicht durch einfache Techniken zu täuschen.)

Meine Frage lautet also: Wie analysiere ich meinen Mischalgorithmus (unter der Annahme, dass der random:uniform()Aufruf dort der Aufgabe entspricht, geeignete Zufallszahlen mit guten Eigenschaften zu generieren)? Welche mathematischen Werkzeuge stehen mir zur Verfügung, um zu beurteilen, ob beispielsweise 100.000 Durchläufe des Mischers über eine Liste von ganzen Zahlen im Bereich von 1 bis 100 plausibel gute Mischergebnisse geliefert haben oder nicht? Ich habe einige eigene Tests durchgeführt (z. B. das Vergleichen von Inkrementen mit Dekrementen in den Mischvorgängen), aber ich würde gerne ein paar mehr wissen.

Und wenn es einen Einblick in diesen Shuffle-Algorithmus selbst gibt, wäre dies ebenfalls wünschenswert.

Allgemeine Bemerkung

Mein persönlicher Ansatz zur Korrektheit von Wahrscheinlichkeitsalgorithmen: Wenn Sie wissen, wie man beweist, dass es richtig ist, dann ist es wahrscheinlich richtig; Wenn Sie dies nicht tun, ist es sicherlich falsch.

Anders gesagt, es ist im Allgemeinen hoffnungslos zu versuchen, jeden Algorithmus zu analysieren, den Sie sich einfallen lassen könnten: Sie müssen so lange nach einem Algorithmus suchen, bis Sie einen finden, den Sie als richtig erweisen können .

Analyse eines Zufallsalgorithmus durch Berechnung der Verteilung

Ich kenne einen Weg, um ein Shuffle (oder allgemeiner einen Algorithmus mit zufälliger Verwendung) "automatisch" zu analysieren, der stärker ist als das einfache "viele Tests werfen und auf Gleichmäßigkeit prüfen". Sie können die Verteilung, die jeder Eingabe Ihres Algorithmus zugeordnet ist, mechanisch berechnen.

Die allgemeine Idee ist, dass ein Algorithmus mit zufälliger Verwendung einen Teil einer Welt von Möglichkeiten erforscht. Jedes Mal, wenn Ihr Algorithmus nach einem zufälligen Element in einer Menge fragt ({ true, false} beim Werfen einer Münze), gibt es zwei mögliche Ergebnisse für Ihren Algorithmus, von denen eines ausgewählt wird. Sie können Ihren Algorithmus so ändern, dass er nicht eines der möglichen Ergebnisse zurückgibt , sondern alle Lösungen parallel untersucht und alle möglichen Ergebnisse mit den zugehörigen Verteilungen zurückgibt.

Im Allgemeinen müsste dazu Ihr Algorithmus gründlich umgeschrieben werden. Wenn Ihre Sprache begrenzte Fortsetzungen unterstützt, müssen Sie dies nicht tun. Sie können die "Untersuchung aller möglichen Ergebnisse" in der Funktion implementieren, indem Sie nach einem zufälligen Element fragen (die Idee ist, dass der Zufallsgenerator, anstatt ein Ergebnis zurückzugeben, die Ihrem Programm zugeordnete Fortsetzung erfasst und mit allen unterschiedlichen Ergebnissen ausführt). Ein Beispiel für diesen Ansatz finden Sie in olegs HANSEI .

Eine vermittelnde und wahrscheinlich weniger arkane Lösung besteht darin, diese "Welt möglicher Ergebnisse" als Monade darzustellen und eine Sprache wie Haskell mit Einrichtungen für monadische Programmierung zu verwenden. Hier ist eine Beispielimplementierung einer Variante¹ Ihres Algorithmus in Haskell unter Verwendung der Wahrscheinlichkeitsmonade des Wahrscheinlichkeitspakets :

import Numeric.Probability.Distribution

shuffleM :: (Num prob, Fractional prob) => [a] -> T prob [a]
shuffleM [] = return []
shuffleM [x] = return [x]
shuffleM (pivot:li) = do
        (left, right) <- partition li
        sleft <- shuffleM left
        sright <- shuffleM right
        return (sleft ++ [pivot] ++ sright)
  where partition [] = return ([], [])
        partition (x:xs) = do
                  (left, right) <- partition xs
                  uniform [(x:left, right), (left, x:right)]

Sie können es für eine bestimmte Eingabe ausführen und die Ausgabeverteilung abrufen:

*Main> shuffleM [1,2]
fromFreqs [([1,2],0.5),([2,1],0.5)]
*Main> shuffleM [1,2,3]
fromFreqs
  [([2,1,3],0.25),([3,1,2],0.25),([1,2,3],0.125),
   ([1,3,2],0.125),([2,3,1],0.125),([3,2,1],0.125)]

Sie können sehen, dass dieser Algorithmus bei Eingaben der Größe 2 einheitlich ist, bei Eingaben der Größe 3 jedoch nicht einheitlich.

Der Unterschied zum testbasierten Ansatz besteht darin, dass wir in einer endlichen Anzahl von Schritten absolute Sicherheit erlangen können: Er kann ziemlich groß sein, da es sich um eine erschöpfende Erforschung der Welt der Möglichkeiten handelt (aber im Allgemeinen kleiner als 2 ^ N, as Es gibt Faktorisierungen ähnlicher Ergebnisse. Wenn jedoch eine ungleichmäßige Verteilung zurückgegeben wird, wissen wir mit Sicherheit, dass der Algorithmus falsch ist. Wenn es eine gleichmäßige Verteilung für [1..N]und zurückgibt 1 <= N <= 100, wissen Sie natürlich nur, dass Ihr Algorithmus bis zu Listen der Größe 100 einheitlich ist. es kann immer noch falsch sein.

¹: Dieser Algorithmus ist aufgrund der spezifischen Pivot-Behandlung eine Variante der Erlang-Implementierung. Wenn ich wie in Ihrem Fall keinen Pivot verwende, verringert sich die Eingabegröße nicht mehr bei jedem Schritt: Der Algorithmus berücksichtigt auch den Fall, in dem sich alle Eingaben in der linken (oder rechten) Liste befinden und in einer Endlosschleife verloren gehen . Dies ist eine Schwäche der Wahrscheinlichkeitsmonadenimplementierung (wenn ein Algorithmus eine Wahrscheinlichkeit 0 für die Nichtbeendigung hat, kann die Verteilungsberechnung immer noch abweichen), die ich noch nicht beheben kann.

Sortierbasierte Mischvorgänge

Hier ist ein einfacher Algorithmus, von dem ich überzeugt bin, dass ich ihn als richtig erweisen kann:

1. Wählen Sie einen zufälligen Schlüssel für jedes Element in Ihrer Sammlung.
2. Wenn die Tasten nicht alle verschieden sind, starten Sie ab Schritt 1 neu.
3. Sortieren Sie die Sammlung nach diesen zufälligen Schlüsseln.

Sie können Schritt 2 weglassen, wenn Sie wissen, dass die Wahrscheinlichkeit einer Kollision (zwei ausgewählte Zufallszahlen sind gleich) ausreichend niedrig ist, aber ohne sie ist das Mischen nicht perfekt gleichmäßig.

Wenn Sie Ihre Schlüssel in [1..N] auswählen, wobei N die Länge Ihrer Sammlung ist, treten viele Kollisionen auf ( Geburtstagsproblem ). Wenn Sie Ihren Schlüssel als 32-Bit-Ganzzahl auswählen, ist die Wahrscheinlichkeit eines Konflikts in der Praxis gering, unterliegt jedoch weiterhin dem Geburtstagsproblem.

Wenn Sie unendliche (träge ausgewertete) Bitstrings als Schlüssel anstelle von Schlüsseln endlicher Länge verwenden, wird die Wahrscheinlichkeit einer Kollision 0, und die Überprüfung der Unterscheidbarkeit ist nicht mehr erforderlich.

Hier ist eine Shuffle-Implementierung in OCaml, bei der faule reelle Zahlen als unendliche Bitstrings verwendet werden:

type 'a stream = Cons of 'a * 'a stream lazy_t

let rec real_number () =
  Cons (Random.bool (), lazy (real_number ()))

let rec compare_real a b = match a, b with
| Cons (true, _), Cons (false, _) -> 1
| Cons (false, _), Cons (true, _) -> -1
| Cons (_, lazy a'), Cons (_, lazy b') ->
    compare_real a' b'

let shuffle list =
  List.map snd
    (List.sort (fun (ra, _) (rb, _) -> compare_real ra rb)
       (List.map (fun x -> real_number (), x) list))

Es gibt andere Ansätze für "reines Mischen". Eine schöne ist die auf Mergesort basierende Lösung von Apfelmus .

Algorithmische Überlegungen: Die Komplexität des vorherigen Algorithmus hängt von der Wahrscheinlichkeit ab, dass alle Schlüssel unterschiedlich sind. Wenn Sie sie als 32-Bit-Ganzzahlen auswählen, besteht eine Wahrscheinlichkeit von eins zu 4 Milliarden, dass ein bestimmter Schlüssel mit einem anderen Schlüssel kollidiert. Das Sortieren nach diesen Schlüsseln ist O (n log n), vorausgesetzt, die Auswahl einer Zufallszahl ist O (1).

Wenn Sie unendlich viele Bitstrings verwenden, müssen Sie die Auswahl nie neu starten, aber die Komplexität hängt dann davon ab, "wie viele Elemente der Streams durchschnittlich ausgewertet werden". Ich vermute, es ist im Durchschnitt O (log n) (daher immer noch O (n log n) insgesamt), habe aber keinen Beweis.

... und ich denke dein Algorithmus funktioniert

Nach mehr Reflexion denke ich (wie Douplep), dass Ihre Implementierung korrekt ist. Hier ist eine informelle Erklärung.

Jedes Element in Ihrer Liste wird durch mehrere Tests getestetrandom:uniform() < 0.5 . Einem Element können Sie die Liste der Ergebnisse dieser Tests als Liste der Booleschen Werte oder { 0, 1} zuordnen . Zu Beginn des Algorithmus kennen Sie die Liste, die einer dieser Nummern zugeordnet ist, nicht. Nach dem ersten partitionAnruf, wissen Sie , das erste Element jeder Liste, etc. Wenn Ihr Algorithmus zurückgibt, werden die Liste der Tests vollständig bekannt und die Elemente werden sortiert nach diesen Listen (in lexikographische Reihenfolge sortiert oder als binäre Darstellungen von realen betrachtet Zahlen).

Ihr Algorithmus entspricht also dem Sortieren nach unendlichen Bitstring-Schlüsseln. Die Partitionierung der Liste, die an die Partitionierung von Quicksort über ein Pivot-Element erinnert, ist tatsächlich eine Möglichkeit, für eine bestimmte Position im Bitstring die Elemente mit Bewertung 0von den Elementen mit Bewertung zu trennen 1.

Die Sortierung ist einheitlich, da die Bitstrings alle unterschiedlich sind. In der Tat befinden sich zwei Elemente mit reellen Zahlen, die bis zum n-ten Bit gleich sind, auf derselben Seite einer Partition, die während eines rekursiven shuffleTiefenaufrufs auftritt n. Der Algorithmus wird nur beendet, wenn alle aus Partitionen resultierenden Listen leer oder Singletons sind: Alle Elemente wurden durch mindestens einen Test getrennt und haben daher eine eindeutige binäre Dezimalstelle.

Probabilistische Beendigung

Ein subtiler Punkt über Ihren Algorithmus (oder meine äquivalente sortbasierte Methode) ist, dass die Beendigungsbedingung probabilistisch ist . Fisher-Yates endet immer nach einer bekannten Anzahl von Schritten (der Anzahl der Elemente im Array). Bei Ihrem Algorithmus hängt die Beendigung von der Ausgabe des Zufallszahlengenerators ab.

Es gibt mögliche Ausgaben, bei denen Ihr Algorithmus divergiert und nicht beendet wird. Wenn der Zufallszahlengenerator beispielsweise immer ausgibt 0, gibt jeder partitionAufruf die Eingabeliste unverändert zurück, auf der Sie die Zufallswiedergabe rekursiv aufrufen: Sie werden eine unbegrenzte Schleife ausführen.

Dies ist jedoch kein Problem, wenn Sie sicher sind, dass Ihr Zufallszahlengenerator fair ist: Er betrügt nicht und liefert immer unabhängige, gleichmäßig verteilte Ergebnisse. In diesem Fall beträgt die Wahrscheinlichkeit, dass der Test random:uniform() < 0.5immer true(oder false) zurückgibt, genau 0:

• Die Wahrscheinlichkeit, dass die ersten N Anrufe zurückkehren, truebeträgt 2 ^ {- N}
• Die Wahrscheinlichkeit, dass alle Anrufe zurückkehren, trueist die Wahrscheinlichkeit des unendlichen Schnittpunkts für alle N des Ereignisses, dass die ersten N Anrufe zurückkehren 0. es ist die unendliche Grenze¹ der 2 ^ {- N}, die 0 ist

¹: Für die mathematischen Details siehe http://en.wikipedia.org/wiki/Measure_(mathematics)#Measures_of_infinite_intersections_of_measurable_sets

Im Allgemeinen wird der Algorithmus nicht genau dann beendet, wenn einige der Elemente demselben booleschen Stream zugeordnet werden. Dies bedeutet, dass mindestens zwei Elemente denselben booleschen Stream haben. Aber die Wahrscheinlichkeit, dass zwei zufällige boolesche Ströme gleich sind, ist wieder 0: Die Wahrscheinlichkeit, dass die Ziffern an Position K gleich sind, ist 1/2, also ist die Wahrscheinlichkeit, dass die N ersten Ziffern gleich sind, 2 ^ {- N} und dieselbe Analyse gilt.

Daher wissen Sie, dass Ihr Algorithmus mit der Wahrscheinlichkeit 1 endet . Dies ist eine etwas schwächere Garantie dafür, dass der Fisher-Yates-Algorithmus immer endet . Insbesondere sind Sie anfällig für einen Angriff eines bösen Gegners, der Ihren Zufallszahlengenerator steuern würde.

Mit mehr Wahrscheinlichkeitstheorie könnten Sie auch die Verteilung der Laufzeiten Ihres Algorithmus für eine bestimmte Eingabelänge berechnen. Dies geht über meine technischen Fähigkeiten hinaus, aber ich gehe davon aus, dass es gut ist: Ich nehme an, dass Sie im Durchschnitt nur die ersten Ziffern von O (log N) betrachten müssen, um zu überprüfen, ob alle N Lazy Streams unterschiedlich sind und ob die Wahrscheinlichkeit von viel höheren Laufzeiten besteht exponentiell abnehmen.

Ihr Algorithmus ist ein sortbasiertes Shuffle, wie im Wikipedia-Artikel beschrieben.

Generell ist die Rechenkomplexität der Art-basierten schlurft ist das gleiche wie der zugrunde liegenden Sortieralgorithmus (zB O ( n log n ) Durchschnitt, O ( n ²) im schlechtesten Fall für eine quicksort-basierte Shuffle), und während der Verteilung nicht ist perfekt einheitlich, sollte es für die meisten praktischen Zwecke nahe genug an die Uniform heranreichen.

Oleg Kiselyov bietet den folgenden Artikel / Diskussion:

• Nachweislich perfektes zufälliges Mischen und seine rein funktionalen Implementierungen

betrifft , bei dem die Grenzen der Sortierbasierten mischen genauer, und bietet auch zwei Adaptionen der Fischer-Yates - Strategie: eine naive O ( n ²) ein, und ein Binärbaum-basierten O ( n log n ) ein.

Leider bietet Ihnen die funktionale Programmierwelt keinen Zugriff auf den veränderlichen Status.

Dies ist nicht wahr: Während die rein funktionale Programmierung Nebenwirkungen vermeidet , unterstützt sie den Zugriff auf den veränderlichen Zustand mit erstklassigen Effekten, ohne dass Nebenwirkungen erforderlich sind.

In diesem Fall können Sie die veränderlichen Arrays von Haskell verwenden, um den mutierenden Fischer-Yates-Algorithmus zu implementieren, wie in diesem Lernprogramm beschrieben:

• Haskell Shuffling (Brett Hall)

Nachtrag

Die spezifische Grundlage Ihrer Shuffle-Sortierung ist eigentlich eine Radix-Sortierung mit unendlichen Schlüsseln : Wie Gasche hervorhebt, entspricht jede Partition einer Zifferngruppierung.

Der Hauptnachteil ist der gleiche wie bei jedem anderen Sortier-Shuffle mit unendlichen Schlüsseln: Es gibt keine Kündigungsgarantie. Obwohl die Wahrscheinlichkeit einer Beendigung mit fortschreitendem Vergleich zunimmt, gibt es nie eine Obergrenze: Die Komplexität im schlimmsten Fall ist O (∞).

Ich habe vor einiger Zeit ähnliche Dinge gemacht, und insbesondere könnten Sie an Clojures Vektoren interessiert sein, die funktional und unveränderlich sind, aber immer noch O (1) Direktzugriffs- / Aktualisierungseigenschaften aufweisen. Diese beiden Kernelemente haben mehrere Implementierungen eines "N zufällig N Elemente aus dieser M-Größe nehmen"; Mindestens einer von ihnen wird zu einer funktionalen Implementierung von Fisher-Yates, wenn Sie N = M lassen.

https://gist.github.com/805546

https://gist.github.com/805747

Basierend auf dem Testen der Zufälligkeit (Beispiel: Mischen) schlage ich vor:

Mische Arrays (mittelgroß), die aus einer gleichen Anzahl von Nullen und Einsen bestehen. Wiederholen und verketten, bis Langeweile aufkommt. Verwenden Sie diese als Eingabe für die eingefleischten Tests. Wenn Sie eine gute Zufallswiedergabe haben, sollten Sie zufällige Folgen von Nullen und Einsen generieren (mit der Einschränkung, dass der kumulative Überschuss an Nullen (oder Einsen) an den Grenzen der mittelgroßen Arrays Null ist, was die Tests hoffentlich erkennen würden , aber je größer "Medium" ist, desto weniger wahrscheinlich ist dies.

Beachten Sie, dass ein Test Ihr Mischen aus drei Gründen ablehnen kann:

• der Shuffle-Algorithmus ist schlecht,
• Der vom Shuffler oder während der Initialisierung verwendete Zufallszahlengenerator ist fehlerhaft, oder
• Die Testimplementierung ist schlecht.

Sie müssen entscheiden, was der Fall ist, wenn ein Test abgelehnt wird.

Verschiedene Anpassungen der eingefleischten Tests (um bestimmte Zahlen aufzulösen, habe ich die Quelle von der eingefleischten Seite verwendet ). Der Hauptmechanismus der Anpassung besteht darin, den Zufallsalgorithmus als Quelle für gleichmäßig verteilte Zufallsbits zu verwenden.

• Geburtstagsabstände: Fügen Sie in ein Array von n Nullen log n Einsen ein. Mischen. Wiederholen, bis gelangweilt. Konstruieren Sie die Verteilung der Abstände zwischen den einzelnen Einheiten und vergleichen Sie sie mit der Exponentialverteilung. Sie sollten dieses Experiment mit verschiedenen Initialisierungsstrategien durchführen - die vorne, die am Ende, die zusammen in der Mitte, die zufällig verstreuten. (Letzteres hat die größte Gefahr einer schlechten Initialisierungs-Randomisierung (in Bezug auf die Shuffling-Randomisierung), die eine Ablehnung des Shufflings zur Folge hat.) Dies kann tatsächlich mit Blöcken identischer Werte durchgeführt werden, hat jedoch das Problem, dass es eine Korrelation in die Verteilungen einführt ( Eine Eins und eine Zwei können nicht in einem einzigen Shuffle an derselben Stelle sein.
• Überlappende Permutationen: Mische fünf Werte mehrmals. Stellen Sie sicher, dass die 120 Ergebnisse ungefähr gleich wahrscheinlich sind. (Chi-Quadrat-Test, 119 Freiheitsgrade - Der eingefleischte Test (cdoperm5.c) verwendet 99 Freiheitsgrade, aber dies ist (meistens) ein Artefakt der sequentiellen Korrelation, das durch die Verwendung überlappender Teilsequenzen der Eingabesequenz verursacht wird.)
• Matrizenreihen: Wählen Sie aus 2 * (6 * 8) ^ 2 = 4608 Bits 6 nicht überlappende 8-Bit-Teilzeichenfolgen aus, indem Sie die gleiche Anzahl von Nullen und Einsen mischen. Behandle diese als eine 6-mal-8-Binärmatrix und berechne ihren Rang. Wiederholen Sie dies für 100.000 Matrizen. (Zusammenfassen der Ränge 0-4. Die Ränge sind dann entweder 6, 5 oder 0-4.) Der erwartete Anteil der Ränge beträgt 0,773118, 0,217439, 0,009443. Chi-Quadrat im Vergleich zu beobachteten Fraktionen mit zwei Freiheitsgraden. Die 31-mal-31- und 32-mal-32-Tests sind ähnlich. Die Ränge 0-28 und 0-29 werden zusammengefasst. Die erwarteten Fraktionen sind 0,2887880952, 0,5775761902, 0,1283502644, 0,0052854502. Der Chi-Quadrat-Test hat drei Freiheitsgrade.

und so weiter...

Möglicherweise möchten Sie auch dieharder und / oder ent nutzen , um ähnliche angepasste Tests durchzuführen.