Wie kann man die Korrektheit eines Shuffle -Algorithmus beweisen?

Question

Ich habe zwei Möglichkeiten, eine Liste von Elementen in einer zufälligen Reihenfolge zu erstellen und möchte feststellen, ob sie gleichermaßen fair sind (unvoreingenommen).

Die erste Methode, die ich verwende, besteht darin, die gesamte Liste der Elemente zu konstruieren und dann ein Mischen zu machen (sagen wir, ein Fisher-yates-Shuffle). Die zweite Methode ist eher eine iterative Methode, die die Liste bei jeder Insertion mischt. In Pseudo-Code ist die Einfügungsfunktion:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

Ich bin daran interessiert, wie man die Fairness dieses besonderen Mischens zeigt. Die Vorteile dieses Algorithmus, in dem er verwendet wird, reichen aus, wenn es etwas unfair ist, wäre es in Ordnung. Um zu entscheiden, brauche ich eine Möglichkeit, seine Fairness zu bewerten.

Meine erste Idee ist, dass ich die Gesamtpermutationen auf diese Weise im Vergleich zu den für einen Satz der endgültigen Länge möglichen Gesamtpermutationen berechnen muss. Ich bin jedoch ein wenig mit Verlust darüber, wie die Permutationen in diesem Algorithmus berechnet werden können. Ich kann auch nicht sicher sein, dass dies der beste oder einfachste Ansatz ist.

Answer 1

Lassen Sie uns zunächst zwei offensichtliche, aber wichtige Annahmen machen:

1. _.random_item kann die letzte Position auswählen.
2. _.random_item Wählt jede Position mit Wahrscheinlichkeit $ frac {1} {n+1} $.

Um die Korrektheit Ihres Algorithmus nachzuweisen, benötigen Sie ein induktives Argument, das dem verwendeten ähnelt, ähnlich wie hier:

• Für die Singleton -Liste gibt es nur eine Möglichkeit, so dass sie einheitlich ausgewählt wird.
• Unter der Annahme, dass die Liste mit $ n $ Elementen (aus allen Permutationen) einheitlich ausgewählt wurde, zeigen die mit $ n+1 $ Elemente, die von Ihrer Technik erhalten wurden, einheitlich ausgewählt.

---

^{Von hier an ist der Beweis falsch. Weiter unten finden Sie einen korrekten Beweis. Ich überlasse dies hier, weil sowohl der Fehler als auch die folgenden Schritte (die solide) lehrreich sein könnten.}

Es ist nützlich, ein lokales (IE-Element-) Eigentum abzuleiten, das auftreten muss, weil es schmerzhaft ist, über die gesamte Permutation zu streiten. Beachten Sie, dass eine Permutation gleichmäßig ausgewählt wird, wenn jedes Element die gleiche Wahrscheinlichkeit hat, an jeder Position zu sein, dh

$ qquad displayStyle mathop { forall} limits _ { pi in mathrm {perm} _n} operatorname {pr} (l = pi) = frac {1 {n!}} quad vadlefightarrows quad mathop { forall} limits_ {i = 1}^n mathop { forall} limits_ {j = 1}^n operatorname {pr} (l_i = j) = frac {1 {1 {1 {1 {1 {1 {1 {1 {1 n} qquad (1) $

wobei $ n = | l | $ und wir annehmen, dass wir $ {1, dots, n } $ in die Liste einfügen.

Lassen Sie uns nun sehen, was Ihre Technik beim Einfügen des Elements $ n+1 $ st macht. Wir müssen drei Fälle in Betracht ziehen (nach dem Tausch):

1. Eines der Elemente in der Liste, nicht ausgetauscht, dh $ i {1, dots, n } $ und $ j in {1, dots, n } $
2. Eines der Elemente in der Liste, getauscht, dh $ i = n+1 $ und $ j in {1, dots, n } $
3. Das neue Element, dh $ i in {1, dots, n+1 } $ und $ j = n+1 $

Für jeden Fall berechnen wir die Wahrscheinlichkeit, dass Element $ J $ in Position $ i $ ist. Alle müssen sich als $ frac {1} {n+1} $ herausstellen (was aufgrund von $ (1) $) ausreicht. Sei $ p_n = frac {1} {n} $ die Wahrscheinlichkeit, dass eines der ersten $ n $ Elemente an einer beliebigen Position in der alten Liste (Induktionshypothese) und $ p_s = frac {1} {n+ ist 1} $ Die Wahrscheinlichkeit, dass jede Position von ausgewählt wird von random_item (Annahmen 1, 2). Beachten Unabhängige Ereignisse, so die Wahrscheinlichkeiten des gemeinsamen Ereignisfaktors, z. B.

$ qquad displaystyle operatorname {pr} (l_i = j, i text {sieged}) = operatorname {pr} (l_i = j) cdot operatorname {pr} (i text {swapt}) = p_npp_ss $

für $ i, j in {1, dots, n } $. Nun für die Berechnungen.

1. Wir betrachten nur die alten Elemente von $ n $. Ein solches Element $ J $ ist in Position $ i $ i $ wenn und nur wenn es vor dem letzten Einfügen da war und $ i $ nicht als Swap -Position ausgewählt wird, das heißt

   $ quad displayStyle operatorname {pr} (l_i = j) = p_n (1-p_s) = frac {1} {n} cdot frac {n} {n+1} = frac {1 {1 {1 {1 {n} {n} {n+1} n+1} $.

2. Hier betrachten wir, dass eines der alten Elemente gegen die letzte Position ausgetauscht wird. Element $ J $ hätte in einer der alten Positionen sein können, daher summen wir alle Wahrscheinlichkeiten, dass $ j $ in Position $ i $ und $ i $ als Swap -Position ausgewählt wurde

   $ quad displaystyle operatorname {pr} (l_ {n+1} = j) = sum_ {i = 1}^n p_np_s = sum_ {i = 1}^n frac {1} {n} CDOT Frac {1} {n+1} = frac {1} {n+1} $.

3. Das neue Element endet an Position $ i $, wenn und nur wenn $ i $ als Swap -Position ausgewählt wird, das heißt

   $ quad displayStyle operatorname {pr} (l_i = j) = p_s = frac {1} {n+1} $.

Alle haben sich gut herausgestellt, Ihre Einfügungsstrategie bewahrt in der Tat Einheitlichkeit. Durch die Macht der Induktion beweist dies, dass Ihr Algorithmus gleichmäßig verteilte Permutationen erzeugt.

^{Ein Wort der Warnung: Dieser Beweis bricht zusammen, wenn die eingefügten Elemente nicht paarweise unterschiedlich sind. Unterscheidbar, denn dann ist die allererste Gleichung nicht mehr gültig. Aber Ihr Algorithmus ist immer noch gültig; jeder Die Permutation mit Duplikaten wird durch die gleiche Anzahl zufälliger Hinrichtungen generiert. Sie können dies beweisen, indem Sie Duplikate markieren (dh sie unterscheidbar machen), oberhalb von Beweisen ausführen und die Markierungen (praktisch) entfernen. Der letzte Schritt bricht gleichen Sätzen von Permutationen auf demselben zusammen.}

---

Wie Steven hat in den Kommentaren korrekt bemerkt, ob der oben genannte Beweis grundlegend fehlerhaft ist, da $ (1) $ nicht gilt; Sie können Verteilungen auf dem Satz von Permutationen konstruieren, die die rechte Hand erfüllen, jedoch nicht die linke Seite.

Daher müssen wir mit Wahrscheinlichkeiten von Permutationen arbeiten, was sich doch nicht so schlimm herausstellt. Die Annahmen auf random_item und die induktive Struktur, die zu Beginn des Pfostens skizziert ist, bleiben wir von dort aus. Sei $ l^{(k)} $ die Liste nach $ {1, dots, k } $ wurden eingefügt.

Sei $ pi ' in mathrm {Perm} _ {n+1} $ Eine beliebige Permutation von $ {1, dots, n+1 } $. Es kann geschrieben werden einzigartig wie

$ qquad displayStyle pi '= ( pi (1), pi (2), dots, pi (i-1), n+1, pi (i+1), dots, pi (n), pi (i)) $

Für einige $ pi in mathhrm {perm} _n $ und $ i in {1, dots, n+1 } $. Durch Induktionshypothese $ operatorname {pr} (l^{(n)} = pi) = frac {1} {n!} $. Außerdem, random_item Picks Position $ i $ mit Wahrscheinlichkeit $ frac {1} {n+1} $ durch Annahme. Da die zufälligen Entscheidungen von $ pi $ und $ i $ (stochastisch) unabhängig sind, bekommen wir

$ qquad displaystyle operatorname {pr} (l^{(n+1)} = pi ') = operatorname {pr} (l^{(n)} = pi) cdot operatorname {pr} (i text {ausgetauscht}) = frac {1} {(n+1)!} $

was wir zeigen mussten. Durch die Macht der Induktion beweist dies, dass Ihr Algorithmus gleichmäßig verteilte Permutationen erzeugt.

---

1. Weisen Sie beispielsweise jede Permutation in $ {(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3) zu } $ Wahrscheinlichkeit $ Frac {1} {4} $ und alle anderen $ 0 $. Es gibt auch Beispiele, die jeder Permutation eine Wahrscheinlichkeit ungleich Null zuweisen.