Zufällige Permutation

Grundidee und Definition

Eine zufällige Permutation oder Zufallspermutation ist eine zufällige Anordnung einer endlichen Menge von Objekten. Ein einfaches Beispiel ist das ideale Mischen der Karten eines Kartenspiels: Jede mögliche Reihenfolge der Karten soll gleich wahrscheinlich sein.

Mathematisch betrachtet man die symmetrische Gruppe S_n, also die Menge aller Permutationen der Menge {1,...,n}. Eine zufällige Permutation ist eine auf S_n gleichverteilte Zufallsvariable Π. Das bedeutet: Für jede Permutation π ∈ S_n gilt

P(Π = π) = 1/n!.

Allgemeiner kann man auch Permutationen beliebiger endlicher Mengen betrachten, zum Beispiel eines Alphabets. Für die mathematische Analyse reicht es jedoch, die Zahlen 1 bis n zu verwenden. Zufällige Permutationen sind wichtig in der Stochastik, bei der Analyse von Sortierverfahren, in der Kryptographie und Kodierungstheorie sowie bei randomisierten Algorithmen.

Ein einfaches Beispiel

Für n = 3 besteht S_3 aus den sechs Permutationen der Zahlen 1, 2 und 3:

S_3 = {(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}.

Eine zufällige Permutation Π nimmt jede dieser sechs Permutationen mit derselben Wahrscheinlichkeit an:

P(Π = π) = 1/6.

Wählt man als Wahrscheinlichkeitsraum (S_3, P(S_3), P) mit P({π}) = 1/6 für alle π ∈ S_3, dann kann Π durch die identische Abbildung dargestellt werden. Das Beispiel zeigt die zentrale Idee: Nicht eine bestimmte Reihenfolge wird bevorzugt, sondern alle möglichen Reihenfolgen sind gleich wahrscheinlich.

Kenngrößen und erzeugende Funktionen

Zu einer zufälligen Permutation kann man weitere Größen betrachten, etwa die Anzahl der Fixpunkte, Fehlstände oder Zyklen. Diese Größen sind selbst diskrete Zufallsvariablen X = X(Π). Ihre Verteilungen sind im Allgemeinen nicht gleichverteilt, auch wenn die zugrunde liegenden Permutationen gleichverteilt sind.

Ein wichtiges Hilfsmittel zur Analyse solcher Verteilungen sind erzeugende Funktionen. Ist P_X(k) = P(X = k) die Wahrscheinlichkeit, dass X den Wert k ∈ N_0 annimmt, dann ist die wahrscheinlichkeitserzeugende Funktion definiert durch

g(x) = Σ_{k=0}^{∞} P_X(k) · x^k.

Der Erwartungswert, also der durchschnittlich zu erwartende Wert von X, ist

E(X) = Σ_{k=0}^{∞} k · P_X(k) = g'(1).

Die Varianz, also ein Maß für die Streuung um den Erwartungswert, ist

Var(X) = Σ_{k=0}^{∞} (k − E(X))^2 · P_X(k) = g''(1) + g'(1)(1 − g'(1)).

Fixpunkte, Anstiege, Fehlstände und Zyklen

Ein Fixpunkt einer Permutation π ist eine Zahl i ∈ {1,...,n}, für die π(i) = i gilt. Die Anzahl der Permutationen π ∈ S_n mit genau k Fixpunkten wird durch die Rencontres-Zahlen D_{n,k} angegeben. Die wahrscheinlichkeitserzeugende Funktion lautet

g(x) = Σ_{k=0}^{n} (D_{n,k}/n!) x^k = Σ_{k=0}^{n} Σ_{j=0}^{n-k} ((−1)^j x^k)/(j! k!).

Für die Anzahl der Fixpunkte gilt E(X) = 1 und Var(X) = 1. Für n → ∞ ist sie asymptotisch poisson-verteilt mit Intensität λ = 1.

Ein Anstieg ist eine Zahl i, für die π(i+1) > π(i) gilt. Die Anzahl der Permutationen mit genau k Anstiegen wird durch die Euler-Zahlen A_{n,k} angegeben. Für die Anzahl der Anstiege gilt

E(X) = (n − 1)/2 und Var(X) = (n + 1)/12.

Bei entsprechender Normierung ist sie für n → ∞ asymptotisch normalverteilt.

Ein Fehlstand ist ein Paar (i,j), für das i < j und π(i) > π(j) gilt. Die Anzahl der Permutationen mit genau k Fehlständen wird durch die McMahon-Zahlen M_{n,k} angegeben. Die erzeugende Funktion hat die Form

g(x) = Σ_{k=0}^{n(n−1)/2} (M_{n,k}/n!) x^k = (1/n!) Π_{i=1}^{n} Σ_{j=0}^{n-i} x^j = (1/n!) Π_{i=1}^{n} (1 − x^i)/(1 − x).

Für Fehlstände gilt

E(X) = n(n − 1)/4 und Var(X) = n(2n + 5)(n − 1)/72.

Auch diese Anzahl ist bei entsprechender Normierung für n → ∞ asymptotisch normalverteilt.

Ein Zyklus ist eine Folge verschiedener Zahlen i_1, i_2, ..., i_k, für die π(i_j) = i_{j+1} für j = 1,...,k−1 und π(i_k) = i_1 gilt. Jede Permutation kann vollständig in Zyklen zerlegt werden. Die Anzahl der Permutationen mit genau k Zyklen wird durch die Stirling-Zahlen der ersten Art s_{n,k} angegeben. Ihre erzeugende Funktion ist

g(x) = Σ_{k=1}^{n} (s_{n,k}/n!) x^k = (1/n!) Π_{k=1}^{n} (x + k − 1).

Für die Anzahl der Zyklen gilt

E(X) = Σ_{k=1}^{n} 1/k = H_n

und

Var(X) = Σ_{k=1}^{n} (k − 1)/k^2 = H_n − H_n^{(2)}.

Dabei ist H_n die n-te harmonische Zahl und H_n^{(2)} die n-te harmonische Zahl zweiter Ordnung. Für n → ∞ ist die Anzahl der Zyklen bei entsprechender Normierung asymptotisch normalverteilt mit Erwartungswert und Varianz log n.

Erzeugung am Computer

Bei Anwendungen wie Monte-Carlo-Simulationen oder der Analyse von Algorithmen muss man zufällige Permutationen auf dem Computer erzeugen. Dazu verwendet man in der Regel uniform verteilte Pseudozufallszahlen aus geeigneten Zufallszahlengeneratoren. Diese Zahlen werden so kombiniert, dass eine pseudozufällige Permutation entsteht.

Beim direkten Verfahren beginnt man mit einer Liste der Zahlen 1 bis n. Zuerst wird eine uniform verteilte Zufallszahl zwischen 1 und n gezogen. Das entsprechende Listenelement wird als erste Zahl der Ergebnispermutation übernommen und aus der Liste entfernt. Danach wird eine Zufallszahl zwischen 1 und n−1 gezogen, das entsprechende noch vorhandene Element wird als zweite Zahl übernommen, und so weiter, bis die Liste leer ist.

Alternativ kann man die Zahlen der Reihe nach betrachten und jeder Zahl einen zufällig ausgewählten noch freien Platz zuweisen. In beiden Varianten ist das Verfahren ineffizient, weil das Entfernen eines bestimmten Listenelements oder das Finden eines freien Platzes in einer Standardimplementierung im Mittel O(n) Operationen benötigt. Insgesamt ergibt sich dadurch eine Laufzeitkomplexität der Ordnung O(n^2).

Fisher-Yates-Verfahren

Das Fisher-Yates-Verfahren, benannt nach Ronald Fisher und Frank Yates, verbessert die Erzeugung zufälliger Permutationen deutlich. Es arbeitet am Platz: Die Zahlen werden im vorhandenen Feld umsortiert und nicht in zusätzlichen Speicher kopiert.

Das Verfahren startet zum Beispiel mit der identischen Permutation P = [1:n]. Dann läuft eine Schleife von i = n bis 2. In jedem Schritt wird eine uniform verteilte Zufallszahl z mit 1 ≤ z ≤ i gezogen, und die Elemente P(i) und P(z) werden vertauscht. Auf diese Weise wird die ausgewählte Zahl an das Ende des aktuell betrachteten Teilfelds gestellt. Dadurch entfällt die aufwändige Suche nach einer noch nicht verwendeten Zahl.

Da das Vertauschen zweier Elemente eines Felds fester Größe konstanten Aufwand hat, besitzt das Fisher-Yates-Verfahren eine Laufzeitkomplexität der Ordnung O(n). Das ist eine erhebliche Verbesserung gegenüber dem direkten Verfahren mit O(n^2). Es kann auch von einer beliebigen Permutation ausgehen, die dann zufällig umsortiert wird. Es ist möglich, dass eine Zahl mit sich selbst vertauscht wird; das hat keinen Effekt. Das Verfahren ist zum Beispiel im numerischen Softwarepaket MATLAB als eingebaute Funktion randperm verfügbar.