Welche Verteilung erhalten Sie von diesem kaputten zufälligen Shuffle?

Der berühmte Fisher-Yates-Shuffle-Algorithmus kann verwendet werden, um ein Array A der Länge N zufällig zu permutieren:

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

Ein häufiger Fehler, von dem mir immer wieder gesagt wurde, dass ich ihn nicht machen soll, ist folgender:

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

Das heißt, anstatt eine zufällige Ganzzahl von k bis N auszuwählen, wählen Sie eine zufällige Ganzzahl von 1 bis N.

Was passiert, wenn Sie diesen Fehler machen? Ich weiß, dass die resultierende Permutation nicht gleichmäßig verteilt ist, aber ich weiß nicht, welche Garantien es für die resultierende Verteilung gibt. Hat jemand einen Ausdruck für die Wahrscheinlichkeitsverteilungen über die Endpositionen der Elemente?

Ein empirischer Ansatz.

Lassen Sie uns den fehlerhaften Algorithmus in Mathematica implementieren:

p = 10; (* Range *)
s = {}
For[l = 1, l <= 30000, l++, (*Iterations*)
   a = Range[p];
   For[k = 1, k <= p, k++, 
     i = RandomInteger[{1, p}];
     temp = a[[k]];
     a[[k]] = a[[i]];
     a[[i]] = temp
   ];
   AppendTo[s, a];
]  

Ermitteln Sie nun, wie oft sich jede Ganzzahl an jeder Position befindet:

r = SortBy[#, #[[1]] &] & /@ Tally /@ Transpose[s]  

Nehmen wir drei Positionen in den resultierenden Arrays und zeichnen die Häufigkeitsverteilung für jede Ganzzahl an dieser Position:

Für Position 1 lautet die Frequenzverteilung:

Für Position 5 (Mitte)

Und für Position 10 (letzte):

und hier haben Sie die Verteilung für alle Positionen zusammen geplottet:

Hier haben Sie eine bessere Statistik über 8 Positionen:

Einige Beobachtungen:

• Für alle Positionen ist die Wahrscheinlichkeit von "1" gleich (1 / n).
• Die Wahrscheinlichkeitsmatrix ist symmetrisch in Bezug auf die große Antidiagonale
• Die Wahrscheinlichkeit für eine beliebige Zahl an der letzten Position ist also ebenfalls einheitlich (1 / n).

Sie können diese Eigenschaften visualisieren, indem Sie den Anfang aller Linien vom selben Punkt (erste Eigenschaft) und der letzten horizontalen Linie (dritte Eigenschaft) betrachten.

Die zweite Eigenschaft ist aus dem folgenden Beispiel für eine Matrixdarstellung ersichtlich, in der die Zeilen die Positionen, die Spalten die Insassenzahl und die Farbe die experimentelle Wahrscheinlichkeit darstellen:

Für eine 100x100-Matrix:

Bearbeiten

Nur zum Spaß habe ich die genaue Formel für das zweite diagonale Element berechnet (das erste ist 1 / n). Der Rest kann erledigt werden, aber es ist viel Arbeit.

h[n_] := (n-1)/n^2 + (n-1)^(n-2) n^(-n)

Verifizierte Werte von n = 3 bis 6 ({8/27, 57/256, 564/3125, 7105/46656})

Bearbeiten

Wenn wir die allgemeine explizite Berechnung in der Antwort von @wnoise ein wenig ausarbeiten, können wir ein wenig mehr Informationen erhalten.

Wenn wir 1 / n durch p [n] ersetzen, damit die Berechnungen nicht bewertet werden, erhalten wir beispielsweise für den ersten Teil der Matrix n = 7 (klicken, um ein größeres Bild zu sehen):

Nachdem wir mit den Ergebnissen für andere Werte von n verglichen haben, können wir einige bekannte ganzzahlige Sequenzen in der Matrix identifizieren:

{{  1/n,    1/n      , ...},
 {... .., A007318, ....},
 {... .., ... ..., ..},
 ... ....,
 {A129687, ... ... ... ... ... ... ..},
 {A131084, A028326 ... ... ... ... ..},
 {A028326, A131084 , A129687 ... ....}}

Sie können diese Sequenzen (in einigen Fällen mit unterschiedlichen Zeichen) in der wunderbaren http://oeis.org/ finden.

Das allgemeine Problem zu lösen ist schwieriger, aber ich hoffe, dies ist ein Anfang

Der "häufige Fehler", den Sie erwähnen, ist das Mischen durch zufällige Transpositionen. Dieses Problem wurde von Diaconis und Shahshahani bei der Erzeugung einer zufälligen Permutation mit zufälligen Transpositionen (1981) ausführlich untersucht . Sie führen eine vollständige Analyse der Stoppzeiten und der Konvergenz zur Gleichmäßigkeit durch. Wenn Sie keinen Link zum Papier erhalten, senden Sie mir bitte eine E-Mail und ich kann Ihnen eine Kopie weiterleiten. Es macht wirklich Spaß zu lesen (wie die meisten Artikel von Persi Diaconis).

Wenn das Array wiederholte Einträge hat, ist das Problem etwas anders. Als schamloser Plug wird dieses allgemeinere Problem von mir, Diaconis und Soundararajan in Anhang B einer Faustregel für das Mischen von Riffeln (2011) angesprochen .

Sagen wir

• a = 1/N
• b = 1-a
• B _i (k) ist die Wahrscheinlichkeitsmatrix nach iSwaps für das kth-Element. dh die Antwort auf die Frage "Wo ist knach iSwaps?". Zum Beispiel B ₀ (3) = (0 0 1 0 ... 0)und B ₁ (3) = (a 0 b 0 ... 0). Was Sie wollen, ist B _N (k) für jedes k.
• K _i ist eine NxN-Matrix mit 1s in der i-ten Spalte und der i-ten Zeile, überall Nullen, z.

• I _i ist die Identitätsmatrix, aber mit dem Element x = y = i auf Null. ZB für i = 2:

• A _i ist

Dann,

Da jedoch B _N (k = 1..N) die Identitätsmatrix bildet, ist die Wahrscheinlichkeit, dass sich ein gegebenes Element i am Ende an Position j befindet, durch das Matrixelement (i, j) der Matrix gegeben:

Zum Beispiel für N = 4:

Als Diagramm für N = 500 (Farbstufen sind 100 * Wahrscheinlichkeit):

Das Muster ist für alle N> 2 gleich:

• Die wahrscheinlichste Endposition für das k-te Element ist k-1 .
• Die am wenigsten wahrscheinliche Endposition ist k für k <N * ln (2) , sonst Position 1

Ich wusste, dass ich diese Frage schon einmal gesehen hatte ...

" Warum führt dieser einfache Shuffle-Algorithmus zu voreingenommenen Ergebnissen? Was ist ein einfacher Grund? " Die Antworten enthalten viele gute Informationen, insbesondere einen Link zu einem Blog von Jeff Atwood über Coding Horror .

Wie Sie vielleicht bereits erraten haben, hängt die genaue Verteilung basierend auf der Antwort von @belisarius stark von der Anzahl der zu mischenden Elemente ab. Hier ist Atwoods Handlung für ein 6-Elemente-Deck:

Was für eine schöne Frage! Ich wünschte ich hätte eine vollständige Antwort.

Fisher-Yates ist schön zu analysieren, denn sobald es sich für das erste Element entscheidet, lässt es es in Ruhe. Der Voreingenommene kann ein Element wiederholt an jedem Ort ein- und auswechseln.

Wir können dies genauso analysieren wie eine Markov-Kette, indem wir die Aktionen als stochastische Übergangsmatrizen beschreiben, die linear auf Wahrscheinlichkeitsverteilungen wirken. Die meisten Elemente werden alleine gelassen, die Diagonale beträgt normalerweise (n-1) / n. Wenn sie bei Pass k nicht alleine gelassen werden, werden sie mit Element k (oder einem zufälligen Element, wenn sie Element k sind) getauscht. Dies ist 1 / (n-1) in Zeile oder Spalte k. Das Element in Zeile und Spalte k ist ebenfalls 1 / (n-1). Es ist einfach genug, diese Matrizen für k von 1 bis n zu multiplizieren.

Wir wissen, dass das Element an der letzten Stelle wahrscheinlich gleich irgendwo war, da der letzte Durchgang die letzte Stelle gleich wahrscheinlich mit einem anderen tauscht. In ähnlicher Weise wird das erste Element wahrscheinlich überall platziert. Diese Symmetrie ist darauf zurückzuführen, dass die Transponierte die Reihenfolge der Matrixmultiplikation umkehrt. Tatsächlich ist die Matrix in dem Sinne symmetrisch, dass Zeile i dieselbe wie Spalte (n + 1 - i) ist. Darüber hinaus zeigen die Zahlen nicht viel offensichtliches Muster. Diese genauen Lösungen stimmen mit den von belisarius durchgeführten Simulationen überein: In Slot i nimmt die Wahrscheinlichkeit ab, j zu erhalten, wenn j auf i steigt, seinen niedrigsten Wert bei i-1 erreicht und dann bei i auf seinen höchsten Wert springt abnehmend bis j n erreicht.

In Mathematica habe ich jeden Schritt mit generiert

 step[k_, n_] := Normal[SparseArray[{{k, i_} -> 1/n, 
                      {j_, k} -> 1/n, {i_, i_} -> (n - 1)/n} , {n, n}]]

(Ich habe es nirgendwo dokumentiert gefunden, aber die erste Übereinstimmungsregel wird verwendet.) Die endgültige Übergangsmatrix kann berechnet werden mit:

Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]]

ListDensityPlot ist ein nützliches Visualisierungswerkzeug.

Bearbeiten (von belisarius)

Nur eine Bestätigung. Der folgende Code enthält dieselbe Matrix wie in der Antwort von @ Eelvex:

step[k_, n_] := Normal[SparseArray[{{k, i_} -> (1/n), 
                      {j_, k} -> (1/n), {i_, i_} -> ((n - 1)/n)}, {n, n}]];
r[n_, s_] := Fold[Dot, IdentityMatrix[n], Table[step[m, n], {m, s}]];
Last@Table[r[4, i], {i, 1, 4}] // MatrixForm

Die Wikipedia-Seite zum Fisher-Yates-Shuffle enthält eine Beschreibung und ein Beispiel dafür, was genau in diesem Fall passieren wird.

Sie können die Verteilung mit stochastischen Matrizen berechnen . Die Matrix A (i, j) beschreibe die Wahrscheinlichkeit, dass die Karte ursprünglich an Position i an Position j endet. Dann hat der k-te Swap eine Matrix Ak, die durch Ak(i,j) = 1/Nif i == koder gegeben j == kist (die Karte in Position k kann überall landen und jede Karte kann mit gleicher Wahrscheinlichkeit an Position k landen), Ak(i,i) = (N - 1)/Nfür alle i != k(jede andere Karte bleibt an derselben Stelle mit Wahrscheinlichkeit (N-1) / N) und alle anderen Elemente Null.

Das Ergebnis des vollständigen Mischens ergibt sich dann aus dem Produkt der Matrizen AN ... A1.

Ich gehe davon aus, dass Sie nach einer algebraischen Beschreibung der Wahrscheinlichkeiten suchen. Sie können eines erhalten, indem Sie das obige Matrixprodukt erweitern, aber ich kann mir vorstellen, dass es ziemlich komplex sein wird!

UPDATE: Ich habe gerade die entsprechende Antwort von wnoise oben gesehen! Hoppla...

Ich habe mich weiter damit befasst und es stellt sich heraus, dass diese Verteilung ausführlich untersucht wurde. Der Grund, warum es von Interesse ist, ist, dass dieser "kaputte" Algorithmus im RSA-Chip-System verwendet wird (oder wurde).

Elchanan Mossel, Yuval Peres und Alistair Sinclair untersuchen in Shuffling by semi-random transpositions dies und eine allgemeinere Klasse von Shuffles. Das Ergebnis dieses Papiers scheint zu sein, dass es log(n)unterbrochene Mischvorgänge erfordert, um eine nahezu zufällige Verteilung zu erreichen.

In The Bias of Three Pseudorandom Shuffles ( Aequationes Mathematicae , 22, 1981, 268-292) analysieren Ethan Bolker und David Robbins dieses Shuffle und stellen fest, dass der gesamte Variationsabstand zur Gleichmäßigkeit nach einem einzelnen Durchgang 1 beträgt, was darauf hinweist, dass es nicht sehr ist überhaupt zufällig. Sie geben auch asympotische Analysen.

Schließlich fanden Laurent Saloff-Coste und Jessica Zuniga eine schöne Obergrenze in ihrer Untersuchung inhomogener Markov-Ketten.

Diese Frage bittet um eine interaktive visuelle Matrixdiagrammanalyse des erwähnten gebrochenen Shuffle. Ein solches Tool finden Sie auf der Seite Wird es mischen? - Warum zufällige Komparatoren von Mike Bostock schlecht sind .

Bostock hat ein hervorragendes Tool zur Analyse von Zufallskomparatoren zusammengestellt. Wählen Sie in der Dropdown-Liste auf dieser Seite einen naiven Austausch (zufällig ↦ zufällig) , um den fehlerhaften Algorithmus und das von ihm erzeugte Muster anzuzeigen .

Seine Seite ist informativ, da man sehen kann, welche unmittelbaren Auswirkungen eine Änderung der Logik auf die gemischten Daten hat. Zum Beispiel:

Dieses Matrixdiagramm mit einem ungleichmäßigen und sehr voreingenommenen Shuffle wird mit einem naiven Swap (wir wählen von "1 bis N") mit folgendem Code erstellt:

function shuffle(array) {
    var n = array.length, i = -1, j;
    while (++i < n) {
        j = Math.floor(Math.random() * n);
        t = array[j];
        array[j] = array[i];
        array[i] = t;
    }
}

Wenn wir jedoch ein nicht voreingenommenes Shuffle implementieren, bei dem wir zwischen "k und N" wählen, sollten wir ein Diagramm wie das folgende sehen:

wobei die Verteilung einheitlich ist und aus Code wie dem folgenden erstellt wird:

function FisherYatesDurstenfeldKnuthshuffle( array ) {
    var pickIndex, arrayPosition = array.length;
    while( --arrayPosition ) {
        pickIndex = Math.floor( Math.random() * ( arrayPosition + 1 ) );
        array[ pickIndex ] = [ array[ arrayPosition ], array[ arrayPosition ] = array[ pickIndex ] ][ 0 ];
    }
}

Die hervorragenden Antworten, die bisher gegeben wurden, konzentrieren sich auf die Verteilung, aber Sie haben auch gefragt: "Was passiert, wenn Sie diesen Fehler machen?" - was ich noch nicht beantwortet habe, deshalb werde ich eine Erklärung dazu geben:

Der Knuth-Fisher-Yates-Shuffle-Algorithmus wählt 1 von n Elementen aus, dann 1 von n-1 verbleibenden Elementen und so weiter.

Sie können es mit zwei Arrays a1 und a2 implementieren , wo Sie ein Element aus a1 entfernen und in a2 einzufügen, aber der Algorithmus tut es an Ort und Stelle (was bedeutet, dass es nur ein Array benötigt), wie erklärt sich hier (Google: " Mischalgorithmen Fisher-Yates DataGenetics ") sehr gut.

Wenn Sie die Elemente nicht entfernen, können sie erneut zufällig ausgewählt werden, wodurch die voreingenommene Zufälligkeit entsteht. Dies ist genau das, was das zweite Beispiel, das Sie beschreiben, bewirkt. Das erste Beispiel, der Knuth-Fisher-Yates-Algorithmus, verwendet eine Cursor-Variable von k bis N, die sich merkt, welche Elemente bereits aufgenommen wurden, und daher vermeidet, Elemente mehr als einmal auszuwählen.