permutationen.tex

Wir haben bereits mehrfach zufällige Permutationen benötigt;
in der Tat müssen so häufig Sequenzen von Elementen zufällig angeordnet werden, dass fast jede allgemeine Programmiersprache über sog. Shuffle Funktionen verfügt.

\begin{algorithm}
    \KwIn{Eingabearray $A[1 \ldots n]$}
    \KwOut{Array~$A$}
    \For{$i \gets n \ldots 2$}{
        $j \gets$ uniform aus $[1 \ldots i]$\;
        tausche $A[i]$ und $A[j]$
    }
    Gebe $A$ zurück
    \caption{Fisher-Yates Shuffle.}
    \label{alg:fisher-yates}
\end{algorithm}

Für kleine Eingaben $A[1 \ldots n]$ ist meist Fisher-Yates Shuffle die beste Wahl.
Wie in \cref{alg:fisher-yates} dargestellt, partitioniert Fisher-Yates konzeptionell die Eingabe in den Urnenpräfix und den Ergebnissuffix.
In jeder Iteration wird genau ein Element~$A[j]$ aus der Urne gewählt, und dem Ergebnis an Position~$A[i]$ hinzugefügt.
Durch den Tausch von $A[i]$ und $A[j]$ stellen wir sicher, dass hierbei keine Elemente verloren gehen.
Dieser Algorithmus hat eine Laufzeit von $\Oh{n}$ und benötigt nur $\Oh{\log n}$ Bits zusätzlichen Speicher (u.A. für $i$ und $j$).
Zur Erinnerung eine Definition:

\begin{definition}
    Wir bezeichnen einen Algorithmus als \emph{in-place}, wenn dieser auf einer Eingabe der Größe~$n$ nur $o(N)$ zusätzliche Speicherworte verwendet werden.
\end{definition}

Beim Fisher-Yates Shuffle handelt es sich also um einen in-place Algorithmus.

\section{Paralleles Fisher-Yates}
Fisher-Yates ist auf den ersten Blick ein inhärent sequentielles Problem.
In jedem Schritt wird ein Element aus der Urne entnommen und verändert dabei den Zustand der Urne.
Daher ist das Ergebnis von Shun et al.~\cite{DBLP:conf/soda/ShunGBFG15} besonders spannend.

Sie zeigten, dass der Algorithmus fast ohne Modifikation in erwartetet linearer Arbeit und $\Oh{\log n \log^* n}$ auf einer Priority-Write CRCW implemeniert werden kann.
Die Idee hierbei ist einfach.
Statt in jedem Schritt einen zufälligen Index zu ziehen, gehört das Array $H[1 \ldots n]$ zur Eingabe.
Dabei entspricht $H[i]$ dem Index, mit dem $A[i]$ getauscht werden soll; es übernimmt also die Rolle von $j$ in \cref{alg:fisher-yates}.

Das Vorberechnen der Indizes erlaubt es uns, schon Abhängigkeiten zu erkennen, bevor Swaps durchgeführt werden.
Weiter können wir die Swap nebenläufig und out-of-order ausführen, wenn hierbei die erkannten Abhängigkeiten beachtet werden.
Hierzu nutzen die Autoren ihr \emph{Reserve and Commit} Framework:
Wir suchen für jeden Index~$j$ in $A$ den ersten Swap, der dieses Element in der sequentiellen Ausführen verändern würde (d.h. das größte $i$ mit $H[i] = j$).
Diesen Swap können wir ausführen und aus dem Spiel nehmen.

Sollte es weitere Swaps geben, die ebenfalls dieses Element verarbeiten möchten, werden diese verzögert.
In jedem Schritt wird also pro Abhängigkeitskette mindestens ein Swap verarbeitet.
Die Haupterkenntnis der Autoren ist, dass Fisher-Yates einen Abhängigkeitswald impliziert, der mit hoher Wahrscheinlichkeit eine Tiefe von $\Oh{\log n}$ hat.

In der Praxis ist der Algorithmus leider nicht besonders effizient:
Echte Maschinen sind in der Regel keine Priority CRCW --- dies muss mittels atomaren Compare-And-Swap Operationen implementiert werden.
Diese Zugriffe sind überdies auch noch wahlfrei und verursachen für große Eingaben Cache-Misses.
Letztlich ist auch der Speicherbedarf sub-optimal:
\begin{enumerate}
    \item Die Eingabe $H$ benötigt mindestens $\Omega(n \log n)$ Bits.
    \item Die Datenstruktur zum Finden der Kollisionen $\Omega(n \log P)$ Bits.
\end{enumerate}
Der Algorithmus ist also nicht in-place und benötigt viele Prozessoren um überhaupt einen Speed-up zu erzielen.

In einem weiteren Papier zeigten die Autoren, dass die Kollisionen mittels $o(n)$ Bits gefunden werden können.
Unter der Annahme das $H$ zur Eingabe gehört, handelt es sich also um einen in-place Algorithmus.
Im Vergleich zu Fisher-Yates wird jedoch weiterhin mindestens linear viel Speicher benötigt --- dann Fisher-Yates benötigt $H$ nicht.

\section{Paralleles Shuffling}
\textcolor{red}{Vorsicht:} In diesem Abschnitt verwenden wir null-indizierte Sequenzen $[x_0, \ldots, x_{n-1}]$ und Prozessoren $\set{p_0, \ldots, p_{P-1}}$.

Ein einfacher und deshalb besonders praktischer paralleler Algorithmus basiert auf~\cite{SANDERS2016489}.
Das Papier diskutiert (u.A.) einen Algorithmus zum Shufflen auf verteilten Computern ---
jeder Prozessor interagiert mit seiner Umwelt durch explizites Senden von Nachrichten.
%Auch wenn auf echten Maschinen hierdurch natürlich erhebliche Kosten entstehen, ignorieren wir in diesem Abschnitt die benötigte Kommunikation.
Der Algorithmus eignet sich mit geringen Modifikationen auch für shared-memory parallele Maschinen und funktioniert auch im External-Memory Modell.

Als Eingabe erhalten wir Elemente $X=[x_0, \ldots, x_{n-1}]$, die arbiträr auf $P$ Prozessoren partitioniert sind, s.d. jeder Prozessor $\Theta(n/P)$ Elemente erhält.
Diese sollen in eine uniform zufällige Permutation überführt werden.
Die Ausgabereihenfolge ergibt sich dadurch, dass wir die lokalen Sequenzen der Prozessoren in aufsteigender Reihenfolge konkatenieren ---
erst kommen alle Elemente für die Prozessor~0 im Ergebnis zuständig ist, dann Prozessor~1, usw.
Hierzu führt Prozessor~$\ell$ das folgende Programm aus:

\begin{enumerate}
    \item Sende jedes lokale Element der Eingabe~$x_i$ zu einem Prozessor, der unabhängig und uniform zufällig gewählt wurde.
    \item Empfange alle Elemente $T = [t_0, \ldots, t_{k_\ell-1}]$
          \iffalse\item Berechne die Präfixsumme $\Delta_\ell = \sum_{i=0}^{\ell - 1} k_i$.
          Der Wert $\Delta_\ell$ entspricht dann der Position des ersten Elements von Prozessor~$\ell$ in der Ausgabe.\fi
    \item Permutiere $T$ lokal z.B. mit Fisher-Yates
    \item Speichere $T$ als $\ell$-ten Teil der Ausgabe
\end{enumerate}

Die Korrektheit des Algorithmus folgt aus dem folgendem Theorem.

\begin{theorem}[nach~\cite{SANDERS2016489}]
    Jede mögliche Permutation wird mit Wahrscheinlichkeit $1/n!$ erzeugt.
    Der Algorithmus erzeugt also eine uniforme Permutation.
\end{theorem}

\noindent
\textcolor{red}{Beweis wird nachgereicht.}

\iffalse
    \begin{proof}
        Sei $\pi$ eine vom Algorithmus erzeugte Permutation und $\pi'$ eine beliebige fixierte Permutation.
        Dann gilt
        \begin{align}
            \prob{\pi = \pi'} & = \prob{\bigwedge\limits_{i=0}^{n-1} \pi(i) = \pi'(i)}                                                        \\
                              & = \prod_{i=0}^{n-1} \prob{\pi(i) = \pi'(i) \quad\middle|\quad \bigwedge\limits_{j=0}^{i-1} \pi(j) = \pi'(j) }
        \end{align}

        \noindent
        Wir werden zeigen, dass für $0 \le i < n$ gilt
        \begin{equation}
            \prob{\pi(i) = \pi'(i) \quad\middle|\quad \bigwedge\limits_{j=0}^{i-1} \pi(j) = \pi'(j) } = \frac{1}{n - i}.
        \end{equation}

        \noindent
        Aufgrund der folgenden Identität folgt dann das Theorem
        \begin{equation}
            \frac{1}{n!}
            \quad = \quad \prod_{i=1}^{n} \frac{1}{i}
            \quad = \quad \prod_{i=0}^{n-1}\frac{1}{n-i}.
        \end{equation}

        Sei $K = [k_0, \ldots, k_{P-1}]$ die Anzahl der Elemente, die den Prozessoren geschickt wurden, und $K'$ eine beliebige valide Anzahl (d.h. insbesonder, dass $\sum_i k_i = n$ und $k_i > 0$ für alle $i$).
        Wir zeigen nun, dass
        \begin{align}
            P_i & := \prod_{i=0}^{n-1} \prob{\pi(i) = \pi'(i) \quad\middle|\quad K = K' \land \bigwedge\limits_{j=0}^{i-1} \pi(j) = \pi'(j) } \\
                & = \frac{1}{n - i}
        \end{align}

        Für ein fixiertes Element $x_i$ sei $\ell$ der Prozessor, der es in der Ausgabe enthält.
        Es gilt $\pi(i) = \pi'(i)$ genau dann, wenn $x_i$ zunächst an Prozessor~$\ell$ geschickt wird und dort dann an den lokalen Rank~$\pi(i) - \Delta_\ell$ permutiert wird.

        Aufgrund der bedingten Wahrscheinlichkeit nehmen wir an, dass bereits $i-1$ Element fixiert wurden und $n-i$ noch ihren Platz suchen.
        Da $K = K'$ gilt weiter, dass $k'$ noch an Prozessor~$\ell$ geschickt werden müssen:
        \begin{equation}
            k' = \underbrace{\Delta_\ell + k_\ell}_\text{Ende von $\ell$'s Bereich} - \underbrace{\pi(i)}_\text{Ausgabeposition von $x_i$}
        \end{equation}

        Daher wird unter den verbleibenden $n-i$ Elementen $x_k$ mit Wahrscheinlichkeit $k' / (n-i)$ Prozessor~$\ell$ geschickt.
        Die Wahrscheinlichkeit, dass es dann an die erste noch nicht fixierte Stelle geshuffelt wird, ist $1 / 'k$.
        Somit folgt
        \begin{equation}
            P_i = \frac{k'}{n - i} \quad \cdot \quad \frac{1}{k'}.
        \end{equation}

        \noindent
        Die Behauptung folgt.
    \end{proof}
\fi

Die Laufzeit des Algorithmus entfällt primär auf das zufällige Versenden der Element und das lokale Permutieren der empfangen Elemente.
Der erste Schritt benötigt Zeit linear in der größten Partition, die nach Voraussetzung auf $\Theta(n / P)$ beschränkt ist.
Das lokale Permutieren benötigt dann Zeit $\max_\ell k_i$, d.h. linear in der größten empfangen Partition.

Da die Prozessoren unabhängig uniform gewählt werden, handelt es sich also um ein klassisches $n$~Bälle auf $P$~Eimer Gedankenexperiment.
Man kann daher mit einem Chernoffargument zeigen, dass für $\beta > 0$ gilt
\begin{equation}
    \prob{\max_\ell k_i > \frac{n}{P} + \sqrt{2 \frac n p (\beta \ln n + \ln P)  } + \Oh{\ln n}} <  n^{-\beta}
\end{equation}

Unter realistischen Annahmen ($n / P = \Omega(\ln n)$) folgt also eine Laufzeit von $\Oh{n / P}$ mit hoher Wahrscheinlichkeit.

\iffalse
    \section{MergeShuffle}
    In Analogie zu MergeSort können wir auch zufällige Permutation erzeugen;
    der Algorithmus kann im Fork-Join-Modell analysiert werden, verursacht $\Oh{n \log n}$ Arbeit und hat einen Span von $\Oh{n}$.
    Die Idee ist grob wie folgt:
    wir teilen eine Eingabe von $n$ Elementen in zwei (etwa) gleich große Partition.
    Dann permutieren wir beide Teile unabhängig und rekursive (das gelingt also trivial nebenläufig).
    Schließlich \emph{mischen} wir die beiden Teile wieder.

    Im Gegensatz zu MergeSort, verstehen wir aber unter \emph{Mischen} hier den Prozess,
    zwei uniforme Permutationen in eine uniforme Permutation der Elemente beider Eingaben zu überführen.
    Der Algorithmus an sich ist wenig praktisch, eine Generalisierung dieses Mischens ist aber für andere Algorithmen nützlich.

    \begin{theorem}
        Seien $A$ und $B$ zwei zufällig permutierte Sequenzen mit $n_A = |A|$ und $n_B = |B|$.
        Dann erzeugt \cref{algo:mergeshuffle_merge} eine uniform permutierte Vereinigung der Elemente in $A$ und $B$ mit Größe $n = n_A + n_B$.
    \end{theorem}

    \begin{proof}[Beweisskizze]
        Wir nehmen an, dass $B$ vollständig in der ersten Schleife konsumiert wird, und aus $A$ exakt $k$ Elemente verbleiben --- der andere Fall läuft analog.

        Zu diesem Zeitpunkt wurden also $n-k$ Elemente in die Ausgabe übertragen.
        Davon stammen $n_B$ aus $B$ und $n_A - k$ aus $A$.
        Wir können uns den Prozess als zufällige Sequenz von $a$ und $b$, wobei jedes $a$ bewirkt, dass das nächste Elemente aus $A$ in die Ausgabe kopiert wird, und $b$ analog für $B$.
        Die Sequenz endet mit einem $b$ --- sonst hätten wir nicht festgestellt, dass $B$ bereits erschöpft ist.

        Da sowohl $A$ als auch $B$ bereits zufällig permutiert sind, ist es nicht notwendig jeweils ein zufälliges zu entnehmen --- das jeweils erste nicht gezogene hat diesselbe Verteilung.
        Daher können wir zwei $a$s bzw. $b$s als ununterscheidbar annehmen und tatsächlich direkt über die zufällige $\set{a,b}^{n-k}$ Sequenz argumentieren.
        Da jedes Zeichen $a$/$b$ unbiased und unabhängig gezogen wird, ist die $\set{a,b}$-Sequenz bedingt auf die Anzahl von $a$ und $b$ uniform.
        Daraus folgt, dass die Sequenz der ersten $n - k$ Elemente eine zufällige Permutation ist.

        Nun müssen wir noch die verbleibenden $k$ Elemente behandelt.
        Die Beweisstruktur läuft analog zu Fisher Yates:
        zu Beginn jeder Schleife ist die bereits erstellte Ausgabe per IV eine uniforme Permutation.
        Durch Einfügen eines Elements an einer zufälligen Stelle, ist die neue ---größere--- Permutation ebenfalls uniform.
    \end{proof}
\fi