Wie beweise ich die Korrektheit eines Shuffle-Algorithmus?

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

Die erste Methode, die ich verwende, besteht darin, die gesamte Liste der Elemente zu erstellen und sie dann zu mischen (z. B. eine Fisher-Yates-Mischung). Die zweite Methode ist eher eine iterative Methode, bei der die Liste bei jeder Einfügung gemischt wird. Im Pseudocode lautet die Einfügefunktion:

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

Ich bin daran interessiert, wie man die Fairness dieses speziellen Mischens demonstriert. Die Vorteile dieses Algorithmus, wo er verwendet wird, reichen aus, dass es in Ordnung wäre, auch wenn er etwas unfair ist. Um zu entscheiden, brauche ich einen Weg, um seine Fairness zu bewerten.

Meine erste Idee ist, dass ich die auf diese Weise möglichen Gesamtpermutationen im Vergleich zu den für eine Menge der endgültigen Länge möglichen Gesamtpermutationen berechnen muss. Ich bin jedoch ein bisschen ratlos darüber, wie man die Permutationen berechnet, die sich aus diesem Algorithmus ergeben. Ich kann auch nicht sicher sein, ob dies der beste oder einfachste Ansatz ist.

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

1. _.random_item kann die letzte Position wählen.
2. _.random_itemwählt jede Position mit der Wahrscheinlichkeit .$\frac{1}{n+1}$

Um die Korrektheit Ihres Algorithmus zu beweisen, benötigen Sie ein induktives Argument ähnlich dem hier verwendeten :

• Für die Singleton-Liste gibt es nur eine Möglichkeit, daher wird sie einheitlich ausgewählt.
• Angenommen, die Liste mit Elementen wurde einheitlich ausgewählt (aus allen Permutationen), zeigen Sie, dass die mit Ihrer Technik erhaltene Liste mit Elementen einheitlich ausgewählt ist.n + $n$$n+1$

^{Ab hier ist der Beweis falsch. Einen korrekten Beweis finden Sie weiter unten. Ich lasse dies hier, weil sowohl der Fehler als auch die folgenden Schritte (die stichhaltig sind) lehrreich sein könnten.}

Es ist nützlich, eine lokale (dh elementweise) Eigenschaft abzuleiten, die gelten muss, da es schmerzhaft ist, über die gesamte Permutation zu streiten. Beachten Sie, dass eine Permutation gleichmäßig gewählt wird, wenn jedes Element die gleiche Wahrscheinlichkeit hat, sich an jeder Position zu befinden, d. H

$\qquad \displaystyle \mathop{\forall}\limits_{\pi \in \mathrm{Perm}_n} \operatorname{Pr}(L = \pi) = \frac{1}{n!} \quad \Longleftrightarrow \quad \mathop{\forall}\limits_{i=1}^n\ \mathop{\forall}\limits_{j=1}^n \operatorname{Pr}(L_i = j) = \frac{1}{n} \qquad (1)$

wound wir nehmen aus Gründen der Vereinfachung der Notation an, dass wir in die Liste einfügen .{ 1 , … , n $n = |L|$$\{1,\dots,n\}$

Lassen Sie uns nun sehen, was Ihre Technik macht, wenn Sie das te Element einfügen . Wir müssen drei Fälle berücksichtigen (nach dem Tausch):$n+1$

1. Eines der Elemente in der Liste, nicht vertauscht, dh undj ∈ { 1 , … , n $i \in \{1,\dots,n\}$$j \in \{1,\dots,n\}$
2. Eines der Elemente in der Liste ist vertauscht, dh undj ∈ { 1 , … , n $i = n+1$$j \in \{1,\dots,n\}$
3. Das neue Element, dh undj = n + $i \in \{1,\dots,n+1\}$$j = n+1$

Für jeden Fall berechnen wir die Wahrscheinlichkeit, dass sich das Element an Position ; alle müssen sich als herausstellen (was wegen ausreicht ). Sei die Wahrscheinlichkeit, dass sich eines der ersten Elemente an einer beliebigen Position in der alten Liste befindet (Induktionshypothese), und die Wahrscheinlichkeit von jede Position, die gewählt wird von (Annahmen 1, 2). Beachten Sie, dass der Koex der Liste mit Elementen und die Auswahl der Swap-Position unabhängige Ereignisse sind , sodass die Wahrscheinlichkeiten gemeinsamer Ereignisse zi $j$$i$ (1)pn=$\frac{1}{n+1}$$(1)$ npn=$p_n = \frac{1}{n}$$n$$p_s = \frac{1}{n+1}$random_item$n$

$\qquad \displaystyle \operatorname{Pr}(L_i=j, i \text{ swapped}) = \operatorname{Pr}(L_i=j)\cdot \operatorname{Pr}(i \text{ swapped}) = p_np_s$

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

1. Wir betrachten nur die alten Elemente. Ein solches Element befindet sich an Position$n$$j$$i$$i$

   $\quad \displaystyle \operatorname{Pr}(L_i = j) = p_n(1-p_s) = \frac{1}{n}\cdot\frac{n}{n+1} = \frac{1}{n+1}$

2. $j$$j$$i$$i$

   $\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 landet genau dann an Position wenn als Swap-Position gewählt wurde$i$$i$

   $\quad \displaystyle \operatorname{Pr}(L_i = j) = p_s = \frac{1}{n+1}$ .

Alles in allem hat sich herausgestellt, dass Ihre Einfügestrategie tatsächlich die Einheitlichkeit bewahrt. Induziert 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 bzw. unterscheidbar, weil dann die allererste Gleichung nicht mehr gültig ist. Ihr Algorithmus ist jedoch weiterhin gültig. Jede Permutation mit Duplikaten wird durch die gleiche Anzahl zufälliger Ausführungen generiert. Sie können dies beweisen, indem Sie Duplikate markieren (dh sie unterscheidbar machen), den obigen Beweis durchführen und die Markierungen (virtuell) entfernen. Im letzten Schritt werden gleich große Sätze von Permutationen zu denselben reduziert.}

Wie Steven in den Kommentaren richtig bemerkt hat, ist der obige Beweis von Grund auf fehlerhaft, da nicht zutrifft; Sie können Verteilungen auf der Menge der Permutationen konstruieren, die die rechte, aber nicht die linke Seite erfüllen¹.$(1)$

Daher müssen wir mit Permutationswahrscheinlichkeiten arbeiten, was sich schließlich als nicht so schlecht herausstellt. Die Annahmen zu random_itemund die induktive Struktur, die zu Beginn des Beitrags beschrieben wurden, bleiben bestehen, wir fahren von dort fort. Let die Liste bezeichnen , nachdem eingefügt wurde. { 1 , … , k $L^{(k)}$$\{1,\dots,k\}$

Es sei eine beliebige Permutation von . Es kann eindeutig als geschrieben werden$\pi' \in \mathrm{Perm}_{n+1}$$\{1,\dots,n+1\}$

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

für einige und . Nach Induktionshypothese ist . Außerdem wird Position mit der Wahrscheinlichkeit angenommen. Da die zufälligen Entscheidungen von und (stochastisch) unabhängig sind, erhalten wir$\pi \in \mathrm{Perm}_n$$i \in \{1,\dots,n+1\}$$\operatorname{Pr}(L^{(n)} = \pi) = \frac{1}{n!}$random_item$i$$\frac{1}{n+1}$$\pi$$i$

$\qquad \displaystyle \operatorname{Pr}(L^{(n+1)} = \pi') = \operatorname{Pr}(L^{(n)} = \pi) \cdot \operatorname{Pr}(i \text{ swapped}) = \frac{1}{(n+1)!}$

was wir zeigen mussten. Induziert beweist dies, dass Ihr Algorithmus gleichmäßig verteilte Permutationen erzeugt.

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