Was ist falsch an diesem "naiven" Mischalgorithmus?

23

Dies ist eine Folgefrage zu einer Stackoverflow- Frage zum zufälligen Mischen eines Arrays .

Es gibt etablierte Algorithmen (wie das Knuth-Fisher-Yates-Shuffle ), mit denen man ein Array mischen sollte, anstatt sich auf "naive" Ad-hoc-Implementierungen zu verlassen.

Ich bin jetzt daran interessiert zu beweisen (oder zu widerlegen), dass mein naiver Algorithmus kaputt ist (wie in: Es werden nicht alle möglichen Permutationen mit gleicher Wahrscheinlichkeit erzeugt).

Hier ist der Algorithmus:

Wiederholen Sie die Schleife ein paar Mal (die Länge des Arrays sollte ausreichen), und erhalten Sie in jeder Iteration zwei zufällige Array-Indizes, und tauschen Sie die beiden Elemente dort aus.

Offensichtlich braucht dies mehr Zufallszahlen als KFY (doppelt so viel), aber abgesehen davon funktioniert es richtig? Und welche Anzahl von Iterationen ist angemessen (ist die "Länge des Arrays" ausreichend)?

Thilo
quelle
4
Ich kann einfach nicht verstehen, warum die Leute denken, dass dieses Tauschprogramm "einfacher" oder "naiver" ist als FY ... Als ich dieses Problem zum ersten Mal löste, habe ich gerade FY implementiert (ohne zu wissen, dass es auch nur einen Namen hat) , nur weil es für mich der einfachste Weg zu sein schien.
1
@mbq: Ich persönlich finde sie genauso einfach, obwohl ich der Meinung bin, dass FY für mich "natürlicher" erscheint.
Nico
3
Als ich nach dem Schreiben meiner eigenen (einer Praxis, die ich seitdem aufgegeben habe) Nachforschungen über Mischalgorithmen anstellte, war ich ganz "heiliger Mist, es wurde getan, und es hat einen Namen !!"
JM ist kein Statistiker

Antworten:

12

Es ist kaputt, obwohl es eine ausgezeichnete Annäherung sein kann, wenn Sie genug mischen (wie die vorherigen Antworten gezeigt haben).

Überlegen Sie, wie oft Ihr Algorithmus Shuffles eines Element-Arrays generiert, in dem das erste Element festgelegt ist, . Wenn Permutationen mit gleicher Wahrscheinlichkeit generiert werden, sollte dies der Zeit passieren . Sei die relative Häufigkeit dieses Auftretens, nachdem mit Ihrem Algorithmus gemischt wurde. Lassen Sie uns auch großzügig sein und annehmen, Sie wählen tatsächlich unterschiedliche Paare von Indizes für Ihre Mischen gleichmäßig zufällig aus, so dass jedes Paar mit der Wahrscheinlichkeit =k 2 1 / k p n n 1 / ( kkk21/kpnn 2/(k(k-1))1/(k2)2/(k(k-1)). (Dies bedeutet, dass keine "trivialen" Shuffles verschwendet werden. Andererseits wird Ihr Algorithmus für ein Array mit zwei Elementen völlig zerstört, da Sie abwechselnd die beiden Elemente fixieren und austauschen, wenn Sie also nach einer vorgegebenen Anzahl von anhalten Schritte, es gibt überhaupt keine Zufälligkeit für das Ergebnis!)

Diese Frequenz erfüllt eine einfache Wiederholung, da das erste Element an seiner ursprünglichen Stelle gefunden wird, nachdem auf zwei getrennte Arten gemischt wurde. Einer ist, dass es nach Shuffles behoben wurde und das nächste Shuffle das erste Element nicht bewegt. Das andere ist, dass es nach Mischen verschoben wurde, aber das Mischen es zurück verschiebt. Die Chance , dass nicht das erste Element zu bewegen ist gleich = , während die Möglichkeit des ersten Elements zurück zu bewegen ist gleich = . Woher:n n n + 1 s t ( k - 1n+1nnn+1st (k-2)/k1/ ( k(k-12)/(k2)(k-2)/k 2/(k(k-1))1/(k2)2/(k(k-1))

p0=1
weil das erste Element an seiner richtigen Stelle beginnt;

pn+1=k-2kpn+2k(k-1)(1-pn).

Die Lösung ist

pn=1/k+(k-3k-1)nk-1k.

Wenn wir subtrahieren , sehen wir, dass die Frequenz um falsch ist . Für großes und ist eine gute Näherung . Dies zeigt, dass der Fehler in dieser bestimmten Frequenz mit der Anzahl der Auslagerungen im Verhältnis zur Größe des Arrays ( ) exponentiell abnimmt , was darauf hinweist, dass es bei großen Arrays schwierig ist, zu erkennen, ob Sie eine relativ große Anzahl von Auslagerungen vorgenommen haben - aber der Fehler ist immer da.( k - 31/k knk-1(k3k1)nk1kknn/kk1kexp(2nk1)n/k

Eine umfassende Analyse der Fehler in allen Frequenzen ist schwierig. Es ist jedoch wahrscheinlich, dass sie sich wie folgt verhalten werden, was zeigt, dass Sie mindestens (die Anzahl der Auslagerungen) benötigen , um den Fehler akzeptabel klein zu machen. Eine ungefähre Lösung istn

n>12(1-(k-1)log(ϵ))

Dabei sollte im Vergleich zu sehr klein sein . Dies impliziert, dass sogar für grobe Näherungen ein Mehrfaches von sollte ( dh , wenn in der Größenordnung von mal oder so liegt).1 / k n k 0,01 1 / kϵ1/knkϵ0.011/k

All dies wirft die Frage auf: Warum sollten Sie sich für einen Algorithmus entscheiden, der nicht ganz (aber nur annähernd) korrekt ist, genau die gleichen Techniken anwendet wie ein anderer Algorithmus, der nachweislich korrekt ist und dennoch mehr Berechnung erfordert?

Bearbeiten

Thilos Kommentar ist zutreffend (und ich hatte gehofft, dass niemand darauf hinweisen würde, sodass mir diese zusätzliche Arbeit erspart bleiben könnte!). Lassen Sie mich die Logik erklären.

  • Wenn Sie sicherstellen, dass Sie jedes Mal echte Swaps generieren, sind Sie total durchgeknallt. Das Problem, auf das ich für den Fall hingewiesen habe, erstreckt sich auf alle Arrays. Nur die Hälfte aller möglichen Permutationen kann durch Anwenden einer geraden Anzahl von Swaps erhalten werden. Die andere Hälfte ergibt sich aus einer ungeraden Anzahl von Swaps. In dieser Situation können Sie also niemals annähernd eine gleichmäßige Verteilung der Permutationen erzeugen (es gibt jedoch so viele mögliche, dass eine Simulationsstudie für ein beliebiges das Problem nicht erkennen kann). Das ist wirklich schlimm.kk=2k

  • Daher ist es ratsam, zufällige Swaps zu generieren, indem die beiden Positionen unabhängig voneinander zufällig generiert werden. Dies bedeutet, dass jedes Mal eine Chance besteht, ein Element mit sich selbst zu tauschen. das heißt, nichts zu tun. Dieser Prozess verlangsamt den Algorithmus ein wenig: Nach Schritten erwarten wir, dass nur etwa echte Swaps stattgefunden haben.n k - 11/knk-1kN<N

  • Beachten Sie, dass die Größe des Fehlers mit der Anzahl der unterschiedlichen Auslagerungen monoton abnimmt. Das Durchführen von durchschnittlich weniger Swaps erhöht daher auch den Fehler im Durchschnitt. Dies ist jedoch ein Preis, den Sie bereit sein sollten zu zahlen, um das im ersten Punkt beschriebene Problem zu lösen. Folglich ist meine Fehlerschätzung konservativ niedrig, ungefähr um einen Faktor von .(k-1)/k

Ich wollte auch auf eine interessante offensichtliche Ausnahme hinweisen: Ein genauer Blick auf die Fehlerformel deutet darauf hin, dass im Fall kein Fehler vorliegt . Dies ist kein Fehler: Es ist richtig. Ich habe hier jedoch nur eine Statistik untersucht, die sich auf die gleichmäßige Verteilung von Permutationen bezieht. Die Tatsache, dass der Algorithmus diese eine Statistik reproduzieren kann, wenn (nämlich die richtige Häufigkeit von Permutationen zu erhalten, die eine gegebene Position fixieren), garantiert nicht, dass die Permutationen tatsächlich gleichmäßig verteilt worden sind. Tatsächlich sind nach tatsächlichen Swaps die einzigen möglichen Permutationen, die erzeugt werden können, ,k=3k=32n(123)(321)und die Identität. Nur letzteres legt eine bestimmte Position fest, so dass tatsächlich genau ein Drittel der Permutationen eine Position festlegt. Aber die Hälfte der Permutationen fehlt! Im anderen Fall sind nach tatsächlichen Swaps die einzig möglichen Permutationen , und . Wiederum wird genau eine von diesen jede gegebene Position fixieren, so dass wir wieder die korrekte Häufigkeit von Permutationen erhalten, die diese Position fixieren, aber wieder erhalten wir nur die Hälfte der möglichen Permutationen.2n+1(12)(23)(13)

Dieses kleine Beispiel verdeutlicht die Hauptaspekte des Arguments: Indem wir "großzügig" sind, unterschätzen wir konservativ die Fehlerrate für eine bestimmte Statistik. Da diese Fehlerrate für alle ungleich Null ist , stellen wir fest, dass der Algorithmus fehlerhaft ist. Indem wir den Abfall der Fehlerrate für diese Statistik analysieren, bestimmen wir außerdem eine Untergrenze für die Anzahl der Iterationen des Algorithmus, die erforderlich sind, um überhaupt Hoffnung auf eine Annäherung an eine gleichmäßige Verteilung der Permutationen zu haben.k4

whuber
quelle
1
"Seien wir auch großzügig und nehmen an, Sie wählen tatsächlich verschiedene Indexpaare für Ihre Mischen gleichmäßig nach dem Zufallsprinzip aus." Ich verstehe nicht, warum diese Annahme gemacht werden kann und wie großzügig sie ist. Es scheint mögliche Permutationen zu verwerfen, was zu einer noch weniger zufälligen Verteilung führt.
Thilo
1
@Thilo: Danke. Ihr Kommentar verdient eine erweiterte Antwort, daher habe ich ihn in die Antwort selbst eingefügt. Lassen Sie mich hier darauf hinweisen, dass "großzügig" eigentlich keine Permutationen verwirft: Es werden nur Schritte im Algorithmus eliminiert, die sonst nichts bewirken würden.
Whuber
2
Dieses Problem kann vollständig als Markov-Kette im Cayley-Diagramm der Permutationsgruppe analysiert werden. Numerische Berechnungen für k = 1 bis 7 (eine 5040 mal 5040-Matrix!) Bestätigen, dass die größten Eigenwerte in der Größe (nach 1 und -1) genau . Dies impliziert, dass, sobald Sie das Problem des Wechsels des Vorzeichens der Permutation (entsprechend dem Eigenwert von -1) bewältigt haben, die Fehler aller Wahrscheinlichkeiten mit der Rate oder schneller. Ich vermute, dass dies weiterhin für alle größeren . (k3)/(k1)=12/(k1)(12/(k1))nk
Whuber
1
Sie können weitaus bessere als da die Wahrscheinlichkeiten für Konjugationsklassen unveränderlich sind und es nur Partitionen von sodass Sie stattdessen eine Matrix analysieren können . 5040×504015715×15
Douglas Zare
8

Ich denke, Ihr einfacher Algorithmus wird die Karten korrekt mischen, da die Anzahl der Mischen gegen unendlich geht.

Angenommen, Sie haben drei Karten: {A, B, C}. Angenommen, Ihre Karten beginnen in der folgenden Reihenfolge: A, B, C. Nach einem Shuffle haben Sie folgende Kombinationen:

{A,B,C}, {A,B,C}, {A,B,C} #You get this if choose the same RN twice.
{A,C,B}, {A,C,B}
{C,B,A}, {C,B,A}
{B,A,C}, {B,A,C}

Daher ist die Wahrscheinlichkeit, dass sich Karte A in Position {1,2,3} befindet, {5/9, 2/9, 2/9}.

Wenn wir die Karten ein zweites Mal mischen, dann:

Pr(A in position 1 after 2 shuffles) = 5/9*Pr(A in position 1 after 1 shuffle) 
                                     + 2/9*Pr(A in position 2 after 1 shuffle) 
                                     + 2/9*Pr(A in position 3 after 1 shuffle) 

Dies ergibt 0,407.

Mit der gleichen Idee können wir eine wiederkehrende Beziehung bilden, dh:

Pr(A in position 1 after n shuffles) = 5/9*Pr(A in position 1 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 2 after (n-1) shuffles) 
                                     + 2/9*Pr(A in position 3 after (n-1) shuffles).

Codiert man dies in R (siehe Code unten), ergibt sich die Wahrscheinlichkeit, dass sich Karte A nach zehn Mischvorgängen an Position {1,2,3} mit {0,33334, 0,33333, 0,33333} befindet.

R-Code

## m is the probability matrix of card position
## Row is position
## Col is card A, B, C
m = matrix(0, nrow=3, ncol=3)
m[1,1] = 1; m[2,2] = 1; m[3,3] = 1

## Transition matrix
m_trans = matrix(2/9, nrow=3, ncol=3)
m_trans[1,1] = 5/9; m_trans[2,2] = 5/9; m_trans[3,3] = 5/9

for(i in 1:10){
  old_m = m
  m[1,1] = sum(m_trans[,1]*old_m[,1])
  m[2,1] = sum(m_trans[,2]*old_m[,1])
  m[3,1] = sum(m_trans[,3]*old_m[,1])

  m[1,2] = sum(m_trans[,1]*old_m[,2])
  m[2,2] = sum(m_trans[,2]*old_m[,2])
  m[3,2] = sum(m_trans[,3]*old_m[,2])

  m[1,3] = sum(m_trans[,1]*old_m[,3])
  m[2,3] = sum(m_trans[,2]*old_m[,3])
  m[3,3] = sum(m_trans[,3]*old_m[,3])
}  
m
csgillespie
quelle
1
+1. Dies zeigt, dass die Wahrscheinlichkeit, dass eine bestimmte Karte in einer bestimmten Position landet, in etwa dem erwarteten Verhältnis entspricht, wenn die Anzahl der Mischvorgänge zunimmt. Das Gleiche gilt jedoch auch für einen Algorithmus, der das Array nur einmal um einen zufälligen Betrag dreht: Alle Karten haben die gleiche Wahrscheinlichkeit, an allen Positionen zu landen, aber es gibt überhaupt keine Zufälligkeit (das Array bleibt sortiert).
Thilo,
@Thilo: Entschuldigung, ich folge deinem Kommentar nicht. Ein "Algorithmus dreht sich um einen zufälligen Betrag", aber es gibt immer noch "keine Zufälligkeit"? Können Sie das näher erläutern?
Csgillespie
Wenn Sie ein N-Element-Array "mischen", indem Sie es (zufällig) zwischen 0 und N-1 drehen, hat jede Karte genau die gleiche Wahrscheinlichkeit, an einer der N Positionen zu landen, aber 2 befindet sich immer zwischen 1 und 3.
Thilo
1
@ Thio: Ah, ich verstehe deinen Standpunkt. Nun, Sie können die Wahrscheinlichkeit (mit genau der gleichen Idee wie oben) für Pr (A in Position 2) und Pr (A in Position 3) berechnen - dito für Karten B und C. Sie werden sehen, dass alle Wahrscheinlichkeiten dazu tendieren 1/3. Hinweis: Meine Antwort gibt nur einen bestimmten Fall an, wohingegen @whuber nice answer den allgemeinen Fall angibt.
Csgillespie
4

Eine Möglichkeit, um zu sehen, dass Sie keine perfekt gleichmäßige Verteilung erhalten, ist die Teilbarkeit. In der Gleichverteilung beträgt die Wahrscheinlichkeit jeder Permutation . Wenn Sie eine Folge von t zufälligen Transpositionen erzeugen und dann Folgen nach ihrem Produkt sammeln, haben die Wahrscheinlichkeiten für eine ganze Zahl A die Form A / n 2 t . Wenn 1 / n ! = A / n 2 t , dann n 2 t / n ! = A1/n!tA/n2tA1/n!=A/n2tn2t/n!=A. Nach Bertrands Postulat (ein Theorem) gibt es für Primzahlen, die im Nenner vorkommen und die n nicht teilen , also n 2 t / n ! ist keine ganze Zahl und es gibt keine Möglichkeit, die Transpositionen gleichmäßig in n zu unterteilen ! Permutationen. Wenn beispielsweise n = 52 , dann ist der Nenner von 1 / 52 ! teilbar ist durch 3 , 5 , 7 , . . . , 47 während der Nenner von 1 /n3nn2t/n!n!n=521/52!3,5,7,...,47 ist nicht, also A / 52 2 t nicht reduzieren 1 / 52 ! .1/522tA/522t1/52!

Wie viele benötigen Sie, um eine zufällige Permutation gut zu approximieren? Die Erzeugung einer zufälligen Permutation durch zufällige Transpositionen wurde von Diaconis und Shahshahani unter Verwendung der Darstellungstheorie der symmetrischen Gruppe in analysiert

Diaconis, P., Shahshahani, M. (1981): "Erzeugen einer zufälligen Permutation mit zufälligen Transpositionen." Z. Wahrsch. Verw. Geb. 57, 159–179.

Eine Schlussfolgerung war, dass es 1 dauertTranspositionen in dem Sinne, dass nach(1-ϵ)112nlogn(1ϵ)12nlogn(1+ϵ)12nlognL27

Douglas Zare
quelle
2

Denken Sie daran, ich bin kein Statistiker, aber ich werde meine 2 Cent setzen.

Ich habe einen kleinen Test in R gemacht (Vorsicht, es ist sehr langsam für hoch numTrials, der Code kann wahrscheinlich optimiert werden):

numElements <- 1000
numTrials <- 5000

swapVec <- function()
    {
    vec.swp <- vec

    for (i in 1:numElements)
        {
        i <- sample(1:numElements)
        j <- sample(1:numElements)

        tmp <- vec.swp[i]
        vec.swp[i] <- vec.swp[j]
        vec.swp[j] <- tmp
        }

    return (vec.swp)
    }

# Create a normally distributed array of numElements length
vec <- rnorm(numElements)

# Do several "swapping trials" so we can make some stats on them
swaps <- vec
prog <- txtProgressBar(0, numTrials, style=3)

for (t in 1:numTrials)
    {
    swaps <- rbind(swaps, swapVec())
    setTxtProgressBar(prog, t)
    }

Dadurch wird eine Matrix swapsmit numTrials+1Zeilen (eine pro Versuch + Original) und numElementsSpalten (eine pro Vektorelement) erstellt. Wenn die Methode korrekt ist, sollte sich die Verteilung jeder Spalte (dh der Werte für jedes Element über die Versuche) nicht von der Verteilung der Originaldaten unterscheiden.

Da unsere ursprünglichen Daten normal verteilt waren, würden wir erwarten, dass alle Spalten nicht davon abweichen.

Wenn wir rennen

par(mfrow= c(2,2))
# Our original data
hist(swaps[1,], 100, col="black", freq=FALSE, main="Original")
# Three "randomly" chosen columns
hist(swaps[,1], 100, col="black", freq=FALSE, main="Trial # 1") 
hist(swaps[,257], 100, col="black", freq=FALSE, main="Trial # 257")
hist(swaps[,844], 100, col="black", freq=FALSE, main="Trial # 844")

Wir bekommen:

Histogramme von Zufallsversuchen

das sieht sehr vielversprechend aus. Wenn wir nun statistisch bestätigen wollen, dass die Verteilungen nicht vom Original abweichen, könnten wir, glaube ich, einen Kolmogorov-Smirnov-Test verwenden (kann ein Statistiker dies bestätigen?) Und dies zum Beispiel tun

ks.test(swaps[1, ], swaps[, 234])

Das gibt uns p = 0,9926

Wenn wir alle Spalten überprüfen:

ks.results <- apply(swaps, 2, function(col){ks.test(swaps[1,], col)})
p.values <- unlist(lapply(ks.results, function(x){x$p.value})

Und wir rennen

hist(p.values, 100, col="black")

wir bekommen:

Histogramm der Kolmogorov-Smirnov-Test-p-Werte

Für die große Mehrheit der Elemente des Arrays hat Ihre Swap-Methode also ein gutes Ergebnis geliefert, wie Sie auch sehen können, wenn Sie die Quartile betrachten.

1> quantile(p.values)
       0%       25%       50%       75%      100% 
0.6819832 0.9963731 0.9999188 0.9999996 1.0000000

Beachten Sie, dass die Situation bei einer geringeren Anzahl von Versuchen offensichtlich nicht so gut ist:

50 Versuche

1> quantile(p.values)
          0%          25%          50%          75%         100% 
0.0003399635 0.2920976389 0.5583204486 0.8103852744 0.9999165730

100 Versuche

          0%         25%         50%         75%        100% 
 0.001434198 0.327553996 0.596603804 0.828037097 0.999999591 

500 Versuche

         0%         25%         50%         75%        100% 
0.007834701 0.504698404 0.764231550 0.934223503 0.999995887 
nico
quelle
0

So interpretiere ich Ihren Algorithmus in Pseudocode:

void shuffle(array, length, num_passes)
  for (pass = 0; pass < num_passes; ++pass) 
    for (n = 0; n < length; ++)
      i = random_in(0, length-1)
      j = random_in(0, lenght-1)
      swap(array[i], array[j]

2×lenGth×num_peinsses[0,lenGth-1]lenGth

lenGth2×lenGth×num_peinsses

lenGth!lenGth!<lenGth2×lenGth×num_peinsses

lenGth!|lenGth2×lenGth×num_peinsses

pp<lenGthplenGthlenGth>2p|lenGth!lenGth2×lenGth×num_peinsseslength!lenGth2×lenGth×num_peinsseslenGth>2

lenGthp<lenGthlenGth-1lenGth-1length

lengthlength1length!length!|length!. Es ist nicht schwer zu zeigen, dass jede Spur zu einer anderen Permutation führt, und von dort ist leicht zu erkennen, dass Fisher-Yates jede Permutation mit gleicher Wahrscheinlichkeit erzeugt.

tzs
quelle