Was ist der effizienteste Weg, um aus probabilistischen paarweisen Swaps eine zufällige Permutation zu generieren?

Die Frage, die mich interessiert, bezieht sich auf die Erzeugung zufälliger Permutationen. Was ist der effizienteste Weg, um eine gleichmäßig zufällige Permutation von $n$ Elementen zu erzeugen, wenn ein probabilistisches paarweises Swap-Gate als Grundbaustein gegeben ist ? Hier nehme ich "probabilistisches paarweises Swap-Gate" als die Operation, die ein Swap-Gate zwischen ausgewählten Elementen $i$ und $j$ mit einer Wahrscheinlichkeit implementiert, $p$ die für jedes Gate frei gewählt werden kann, und die Identität ansonsten.

Mir ist klar, dass dies normalerweise nicht die Art und Weise ist, wie man zufällige Permutationen erzeugt, wo man normalerweise so etwas wie einen Fisher-Yates-Shuffle verwendet. Dies funktioniert jedoch nicht für die Anwendung, an die ich denke, da die erlaubten Operationen unterschiedlich sind.

Natürlich kann dies getan werden, die Frage ist, wie effizient. Was ist die geringste Anzahl von probabilistischen Swaps, die erforderlich sind, um dieses Ziel zu erreichen?

AKTUALISIEREN:

Anthony Leverrier liefert eine Methode, die tatsächlich die korrekte Verteilung unter Verwendung von $O(n^2)$ -Gattern erzeugt, wobei Tsuyoshi Ito einen anderen Ansatz mit derselben Skalierung in den Kommentaren liefert. Die beste Untergrenze, die ich bisher gesehen habe, ist jedoch $\lceil \log_2(n!) \rceil$ , die als skaliert $O(n\log n)$ . Die Frage bleibt also weiterhin offen: Ist $O(n^2)$ das Beste, was getan werden kann (dh gibt es eine bessere Untergrenze)? Oder gibt es alternativ eine effizientere Schaltkreisfamilie?

AKTUALISIEREN:

In mehreren Antworten und Kommentaren wurden Schaltkreise vorgeschlagen, die vollständig aus probabilistischen Swaps bestehen, bei denen die Wahrscheinlichkeit auf $\frac{1}{2}$ . Eine solche Schaltung kann dieses Problem aus folgendem Grund nicht lösen (aus den Kommentaren gestrichen):

Stellen Sie sich eine Schaltung vor, die $m$ solche Tore verwendet. Dann gibt es $2^m$ äquiprobierbare Berechnungspfade, und daher muss jede Permutation mit der Wahrscheinlichkeit $k 2^{−m}$ für eine ganze Zahl k erfolgen. Für eine gleichmäßige Verteilung benötigen wir jedoch $k 2^{−m}=\frac{1}{n!}$ $k n! = 2^m$ $k$ $n\geq3$ $3|n!$ $n\geq 3$ $3\nmid 2^m$

UPDATE (von mjqxxxx, der das Kopfgeld anbietet):

Die angebotene Prämie ist für (1) einen Beweis, dass Gatter erforderlich sind, oder (2) eine Arbeitsschaltung für jedes , das weniger als Gatter verwendet. $\omega(n \log n)$ $n$ $n(n-1)/2$

co.combinatorics randomness probabilistic-circuits Joe Fitzsimons
quelle

@Anthony: Vielleicht ist es nicht offensichtlich, aber Sie können sich vorstellen, dass die Schaltung eine gleichmäßige Verteilung der Permutationen der ersten Elemente erzeugt. Dann ergibt gefolgt von einem probabilistischen Tausch (mit einer Wahrscheinlichkeit von 0,5) zwischen Position und Position eine gleichmäßig zufällige Wahl für Position . Wenn Sie danach erneut auf die ersten Elemente anwenden , sollten Sie eine gleichmäßig zufällige Verteilung erhalten.

C

$C$

n - 1

$n-1$

C

$C$

n - 1

$n-1$

n

$n$

n

$n$

C

$C$

n - 1

$n-1$

Joe Fitzsimons

ok danke für die erklärung! Beachten Sie, dass der probabilistische Tausch Proba zwischen Position und Position .

(n - 1) / n

$(n-1)/n$

n - 1

$n-1$

n

$n$

Anthony Leverrier

In Bezug auf die erforderliche Entropie benötigt der Algorithmus zufällige Bits, wobei die binäre Entropiefunktion ist. Ich kann diese Summe nicht genau berechnen, aber sie ist laut Mathematica , während das Optimum mindestens .

(n - 1) h (1 / 2) + (n - 2) h (1 / 3) + \dots + (n - k) h (1 / (k + 1)) + \dots + h (1 / n)

$(n-1) h(1/2) + (n-2) h(1/3) + \cdots + (n-k) h(1/(k+1)) + \cdots + h(1/n)$

h (.)

$h(.)$

O (n \log_{2} (n)^{2})

$O(n \log_2(n)^2)$

O (n \log_{2} (n))

$O(n \log_2(n))$

Anthony Leverrier

Dies unterscheidet sich von dem, was Sie möchten, aber es gibt eine Familie von Schaltkreisen der Größe O (n log n), die jede Permutation mit einer Wahrscheinlichkeit von mindestens 1 / p (n!) Für ein Polynom p erzeugen: Betrachten Sie ein Sortiernetz mit der Größe O (n log n) und ersetze jeden Komparator durch ein Wahrscheinlichkeits-1/2-Swap-Gate. Aufgrund der Korrektheit des Sortiernetzwerks muss jede Permutation mit einer Wahrscheinlichkeit ungleich Null auftreten, die notwendigerweise mindestens 1/2 ^ {O (n log n)} = 1 / poly (n!) Beträgt.

Tsuyoshi Ito

Zurück zum ursprünglichen Problem. Es ist zu beachten, dass die von Anthony beschriebene O (n ^ 2) -Lösung so angesehen werden kann, dass sie jeden Komparator im Sortiernetz, der die Auswahlsortierung darstellt, durch ein probabilistisches Swap-Gate mit einer geeigneten Wahrscheinlichkeit ersetzt. (mehr)

Tsuyoshi Ito

Antworten:

Ein Arbeitsalgorithmus, den ich oben in einem Kommentar beschrieben habe, ist der folgende:

Zuerst bringen Sie ein zufälliges Element mit der Wahrscheinlichkeit in Position : Vertauschen Sie die Positionen 1 und 2 mit der Sonde , dann 2 und 3 mit der Sonde , ... dann und mit der Sonde . $1/n$ $n$ $1/2$ $2/3$ $n-1$ $n$ $(n-1)/n$
Wenden Sie dasselbe Verfahren an, um ein zufälliges Element in Position : Vertauschen Sie die Positionen 1 und 2 mit prob ... und dann die Positionen und mit proba . $n-1$ $1/2$ $n-2$ $n-1$ $(n-2)/(n-1)$
Usw

Die Anzahl der von diesem Algorithmus benötigten Gatter beträgt . $(n-1)+(n-2)+ \cdots + 2+1 = n(n-1)/2 = O(n^2)$

Anthony Leverrier
quelle

Dieser Algorithmus hat eine Verbindung zur Blasensortierung. Berücksichtigen Sie insbesondere den Zustandsraum aller Permutationen der Größe n. Die Wahrscheinlichkeit, dass 1. Elemente größer als 2. sind, ist 1/2, tauschen Sie mit dieser Wahrscheinlichkeit. Angenommen, die ersten beiden Elemente sind sortiert, was ist die proba 2. Element> 3. Element 2/3 usw. Daher scheint es möglich, den Sortieralgorithmus in eine Swap-Gate-Schaltung umzuwandeln, bei der jeder folgende Schritt bedingte Wahrscheinlichkeiten berücksichtigen sollte, die sich aus den vorherigen ergeben Schritte. Was in gewissem Sinne eine explizit ineffiziente Methode zum Aufbau derartiger Schaltungen nahe legt.

mkatkov

Dies ist weder eine Antwort noch eine neue Information. Hier werde ich versuchen, die Diskussionen zusammenzufassen, die in Kommentaren über die Beziehungen zwischen diesem Problem und Sortiernetzwerken stattgefunden haben . In diesem Beitrag sind alle Zeiten in UTC und ein "Kommentar" bedeutet einen Kommentar zu der Frage, sofern nicht anders angegeben.

Eine Schaltung, die aus probabilistischen Swap-Gates besteht (die zwei Werte zufällig tauschen), erinnert uns natürlich an ein Sortiernetz, das nichts anderes als eine Schaltung ist, die aus Komparatoren besteht (die zwei Werte abhängig von der Reihenfolge zwischen ihnen tauschen). Schaltkreise für das aktuelle Problem und Sortiernetzwerke sind in der Tat auf folgende Weise miteinander verknüpft:

Die Lösung von Anthony Leverrier mit n ( n −1) / 2 probabilistischen Swap-Gattern kann als Sortiernetz für die Blasensortierung verstanden werden, bei der die Komparatoren durch probabilistische Swap-Gatter mit geeigneten Wahrscheinlichkeiten ersetzt werden. Siehe mkatkovs Kommentar am 10. März, 4:53 zu dieser Antwort für Details. Das Sortiernetz für die Auswahlsortierung kann auf die gleiche Weise verwendet werden. (In dem Kommentar am 7. März, 23:04, habe ich Anthonys Schaltung als Auswahlsorte beschrieben, aber das war nicht korrekt.)
Wenn wir nur wollen, dass jede Permutation mit einer Wahrscheinlichkeit ungleich Null ist und die Verteilung nicht einheitlich ist, erledigt jedes Sortiernetzwerk die Aufgabe, wenn alle Komparatoren durch Wahrscheinlichkeits-1/2-Swap-Gates ersetzt werden. Wenn wir ein Sortiernetz mit O ( n log n ) Komparatoren verwenden, erzeugt die resultierende Schaltung jede Permutation mit einer Wahrscheinlichkeit von mindestens 1/2 ^{O ( n log n )} = 1 / poly ( n !), Wie in meinem Kommentar vom März beobachtet 7 22:59.
Bei diesem Problem ist es erforderlich, dass die probabilistischen Swap-Gates unabhängig voneinander feuern. Wenn wir diese Einschränkung aufheben, kann jedes Sortiernetzwerk in eine Schaltung umgewandelt werden, die die gleichmäßige Verteilung erzeugt, wie ich in den Kommentaren vom 7. März, 23:08 Uhr und vom Benutzer 1749, die am 8. März, 14:07 Uhr, ausführlicher beschrieben wurden, erwähnt habe.

Diese Tatsachen legen offenbar nahe, dass dieses Problem eng mit dem Sortieren von Netzwerken zusammenhängt. Peter Taylor fand jedoch einen Beweis dafür, dass die Beziehung möglicherweise nicht sehr eng ist. Es kann nämlich nicht jedes Sortiernetz in eine gewünschte Schaltung umgewandelt werden, indem die Komparatoren durch probabilistische Austauschgatter mit geeigneten Wahrscheinlichkeiten ersetzt werden. Das Fünf-Komparator-Sortiernetz für n = 4 ist ein Gegenbeispiel. Siehe seine Kommentare am 10. März 11.08 und 10. März 14.01.

Tsuyoshi Ito
quelle

@mkatkov: Ich habe drei oder vier gelöschte Antworten gesehen und ich erinnere mich nicht, welche wessen war, sorry. Wenn Sie eine Lösung mit weniger als n (n - 1) / 2 Toren gefunden haben, würde ich gerne die gesamte Konstruktion kennen (und es ist nicht so, Ihnen die Prämie von mjqxxxx zu stehlen :)).

Tsuyoshi Ito

@mkatkov: Ich bin immer noch skeptisch. Wie ich im letzten Absatz dieses Beitrags schrieb, stellte Peter Taylor fest, dass das Fünf-Komparator-Sortiernetzwerk für n = 4 nicht in eine Lösung für das aktuelle Problem umgewandelt werden kann, indem die Komparatoren durch probabilistische Swap-Gates ersetzt werden. Dies impliziert, dass Ihre Logik nicht für jedes Sortiernetzwerk funktioniert, schließt jedoch nicht aus, dass sie beispielsweise für das Mergesort ungerade-gerade funktioniert.

Tsuyoshi Ito

@mkatkov: Der Grund, warum diese Art von Lösung nicht zu funktionieren scheint (oder zumindest kein funktionierendes Beispiel gezeigt wurde), ist, dass die Swap-Gates in einem paarweisen Sortiernetzwerk in stark korrelierter Weise ausgelöst werden. Bei diesem Problem feuern alle Tore unabhängig voneinander, was zu einem sehr unterschiedlichen Raum möglicher Schaltkreise führt.

mjqxxxx

@mkatbov, bei jedem Schritt in Anthonys Netzwerk wird einer von m Eingängen ausgewählt (wobei m von n bis 2 reicht). Sie können keinen von m Eingängen mit weniger als m-1 Gattern auswählen. Dies ist insbesondere bei log m Gattern nicht möglich. Das Schlagen von erfordert wahrscheinlich einen Divide-and-Conquer-Ansatz.

O (n^{2})

$O(n^2)$

Peter Taylor

@ Tsuyoshi, Yuval und ich haben alle möglichen 5-Gate-Lösungen für analysiert und eliminiert, was das Ergebnis verstärkt, dass nicht alle Sortiernetzwerke in einheitliche Permutationsnetzwerke umgewandelt werden können, sodass es Problemgrößen gibt, für die die Für ein optimales gleichmäßiges Permutationsnetzwerk sind mehr Tore erforderlich als für ein optimales Sortierungsnetzwerk.

n = 4

$n=4$

Peter Taylor

Dies ist keineswegs eine vollständige Antwort, aber es enthält ein Ergebnis, das nützlich sein kann und das angewendet wird, um einige Einschränkungen für den Fall die die möglichen 5-Gate-Lösungen auf 2500 leicht aufzählbare Fälle begrenzen. $n=4$

Zunächst das allgemeine Ergebnis: In jeder Lösung, die Objekte permutiert , müssen mindestens Swaps mit der Wahrscheinlichkeit . $n$ $n-1$ $\frac{1}{2}$

Beweis: Betrachten Sie die Permutationsdarstellung der Permutationen der Ordnung . Dies sind die Matrizen die erfüllen . Betrachten Sie einen Tausch zwischen und mit der Wahrscheinlichkeit : Dies hat die Darstellung (unter Verwendung der Zyklusnotation, um die Permutation darzustellen). Sie können sich die Multiplikation mit dieser Matrix als Darstellungstheorie oder als Markov-Multiplikation vorstellen, indem Sie die Permutation mit der Wahrscheinlichkeit anwenden und die Dinge mit der Wahrscheinlichkeit unverändert lassen . $n$ $n\times n$ $A_\pi$ $(A_\pi)_{i,j} = [i = \pi(j)]$ $i$ $j$ $p$ $(1-p)I + pA_{(i j)}$ $(i j)$ $p$ $1-p$

Das Permutationsnetzwerk ist daher eine Kette solcher Matrixmultiplikationen. Wir beginnen mit der Identitätsmatrix und das Endergebnis wird eine Matrix in der , also gehen wir von einer Matrix mit Rang zu einer Matrix mit Rang durch Multiplikationen - dh der Rang nimmt um . $U$ $U_{i,j} = \frac{1}{n}$ $n$ $1$ $n-1$

Betrachtet man den Rang der Matrizen , so sieht man, dass es sich im Wesentlichen um Identitätsmatrizen handelt, abgesehen von einer untergeordneten , sie haben also den vollen Rang, es sei denn, . In diesem Fall haben sie den Rang . $(1-p)I + pA_{(i j)}$ $\begin{pmatrix}1-p & p \\ p & 1-p\end{pmatrix}$ $p=\frac{1}{2}$ $n-1$

Unter Anwendung von Sylvesters Matrixungleichung stellen wir daher fest, dass jeder Swap den Rang nur dann verringert, wenn , und wenn diese Bedingung erfüllt ist, verringert er ihn um nicht mehr als 1. Daher benötigen wir mindestens Swaps der Wahrscheinlichkeit . $p=\frac{1}{2}$ $n-1$ $\frac{1}{2}$

Beachten Sie, dass diese Grenze nicht verschärft werden kann, da Anthony Leverriers Netzwerk dies erreicht.

Anwendung auf den Fall . Wir haben bereits Lösungen mit 6 Toren, die Frage ist also, ob Lösungen mit 5 Toren möglich sind. Wir wissen jetzt, dass mindestens 3 der Gates 50/50 Swaps sein müssen, also haben wir zwei "freie" Wahrscheinlichkeiten, und . Es gibt 32 mögliche Ereignisse (5 unabhängige Ereignisse mit jeweils zwei Ergebnissen) und Eimer, von denen jeder mindestens ein Ereignis enthalten muss. Die Ereignisse teilen sich in 8 mit Wahrscheinlichkeit , 8 mit Wahrscheinlichkeit , 8 mit Wahrscheinlichkeit und 8 mit der Wahrscheinlichkeit . $n=4$ $p$ $q$ $4! = 24$ $\frac{pq}{8}$ $\frac{\overline{p}q}{8}$ $\frac{p\overline{q}}{8}$ $\frac{\overline{p}\overline{q}}{8}$

32 Ereignisse in 24 Buckets ohne leere Buckets implizieren, dass mindestens 16 Buckets genau ein Ereignis enthalten, sodass mindestens zwei der vier oben angegebenen Wahrscheinlichkeiten gleich . Unter Berücksichtigung von Symmetrien gibt es zwei Fälle: oder . $\frac{1}{24}$ $pq = \overline{p}q = \frac{1}{3}$ $pq = \overline{p}\overline{q} = \frac{1}{3}$

Der erste Fall ergibt , ( Korrektur oder , wobei die Symmetrie abgewickelt wird). Der zweite Fall ergibt , also , was keine wirklichen Lösungen hat. $p=\overline{p}=\frac{1}{2}$ $q=\frac{2}{3}$ $q=\frac{1}{3}$ $pq=1-p-q+pq$ $pq = p(1-p) = \frac{1}{3}$

Wenn es also eine 5-Gate-Lösung gibt, haben wir vier Gates mit der Wahrscheinlichkeit und ein Gate mit der Wahrscheinlichkeit entweder oder . Wlog der erste Swap ist und der zweite ist entweder oder ; Die anderen drei haben jeweils (nicht mehr als) fünf Möglichkeiten, weil es keinen Sinn macht, denselben Swap zweimal hintereinander durchzuführen. Wir müssen also Swap-Sequenzen berücksichtigen und 10 Möglichkeiten zur Zuordnung der Wahrscheinlichkeiten finden, was zu 2500 Fällen führt, die mechanisch aufgezählt und getestet werden können. $\frac{1}{2}$ $\frac{1}{3}$ $\frac{2}{3}$ $0\leftrightarrow 1$ $0\leftrightarrow 2$ $2\leftrightarrow 3$ $2\times 5^3$

Update: Yuval Filmus und ich haben die Fälle sowohl aufgezählt als auch getestet und keine Lösungen gefunden. Die optimale Lösung für umfasst also 6 Tore, und Beispiele für Lösungen mit 6 Toren finden sich in anderen Antworten. $n=4$

Peter Taylor
quelle

Meine Fallaufzählung ergab kein kürzeres Beispiel.

Yuval Filmus

... auch nach der Korrektur.

Yuval Filmus

Hervorragend, das ist eine sehr schöne Beobachtung.

Joe Fitzsimons

@mjqxxxx, ich berechne, dass Sie bei der Suche nach einer 9-Gate-Lösung für ungefähr 104 Millionen Fälle berücksichtigen müssten (obwohl dies mit Bedacht etwas reduziert werden könnte), aber für jeden Fall würden Sie 120 Gleichungen berechnen 5 Variablen mit Kreuzbegriffen und dann nach einer Lösung suchen. Dies ist wahrscheinlich mit einem Standard-Desktop-Computer möglich, erfordert jedoch etwas mehr Aufwand, da Sie die möglichen Werte der Wahrscheinlichkeiten nicht so einfach einschränken können.

n = 5

$n=5$

Peter Taylor

Ich vergebe das Kopfgeld hier, obwohl die Antwort weder eine asymptotische Verbesserung gegenüber der unteren Grenze von noch irgendeine Verbesserung gegenüber der oberen Grenze von liefert, weil es zumindest das beweist ist in einem einzelnen nichttrivialen Fall optimal.

Ω (n \log n)

$\Omega(n \log n)$

n (n - 1) / 2

$n(n-1)/2$

n (n - 1) / 2

$n(n-1)/2$

mjqxxxx

Folgendes scheint neu und relevant zu sein:

Die Arbeit [CKKL99] zeigt, wie man 1 / n mit einem Schaltnetzwerk der Tiefe O (log n) und damit insgesamt O (n log n) Komparatoren einer gleichmäßigen Permutation von n Elementen nahe kommt.

Diese Konstruktion ist nicht explizit, kann aber explizit gemacht werden, wenn Sie die Tiefe auf polylog (n) erhöhen. Siehe die Hinweise in der Veröffentlichung [CKKL01], die auch weitere Informationen enthält.

Ein vorheriger Kommentar hat bereits ein Ergebnis gezeigt, das besagt, dass O (n log n) Schalter ausreichen, aber der Unterschied besteht darin, dass in Vermittlungsnetzwerken die zu vergleichenden Elemente fest sind.

[CKKL99] Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski und Krzysztof Lorys. Verzögerte Pfadkopplung und Erzeugung zufälliger Permutationen über verteilte stochastische Prozesse. In Symposium on Discrete Algorithms (SODA), S. 271 {280, 1999.

[CKKL01] Artur Czumaj, Przemyslawa Kanarek, Miroslaw Kutylowski und Krzysztof Lorys. Vermittlungsnetze zur Erzeugung zufälliger Permutationen, 2001.

— Manu
quelle

Danke, das ist sicher nützlich zu wissen. Ich bin jedoch immer noch daran interessiert, die Gate-Nummer für die Generierung der genauen Verteilung zu kennen.

— Joe Fitzsimons

Hier ist eine etwas interessante Lösung für . Die gleiche Idee gilt auch für . $n=4$ $n=6$

Beginnen Sie mit den Schaltern mit der Wahrscheinlichkeit . wir auf und auf reduzieren , befinden wir uns in der Situation . Wenden Sie die Schalter mit der Wahrscheinlichkeit . Das Ergebnis ist Unser nächster Zug wird mit einer Wahrscheinlichkeit von . Wir kümmern uns also wirklich nur darum, ob das Ergebnis der vorherigen Stufe die Form (Fall A) oder die Form hat $(0,1),(2,3)$ $1/2$ $0,1$ $X$ $2,3$ $Y$ $XXYY$ $(0,3),(1,2)$ $p$

\begin{aligned} X X Y Y & w.p. (1 - p)^{2}, \\ Y Y X X & w.p. p^{2}, \\ X Y X Y & w.p. p (1 - p), \\ Y X Y X & w.p. p (1 - p) \end{aligned}

$\begin{align*} XXYY &\text{ w.p. } (1-p)^2, \\ YYXX &\text{ w.p. } p^2, \\ XYXY &\text{ w.p. } p(1-p), \\ YXYX &\text{ w.p. } p(1-p) \end{align*}$

(0, 2), (1, 3)

$(0,2),(1,3)$

1 / 2

$1/2$

X X Y Y / Y Y X X

$XXYY/YYXX$

X Y X Y / Y X Y X

$XYXY/YXYX$ (Fall B). Im Fall A ergeben diese Schalter eine einheitliche Wahrscheinlichkeit über . In Fall B sind sie unwirksam. Daher erfüllen müssen Vorausgesetzt, das Ergebnis ist einheitlich.

X X Y Y / X Y Y X / Y X X Y / Y Y X X

$XXYY/XYYX/YXXY/YYXX$

p

$p$

p (1 - p) = 1 / 6 ⟹ p = \frac{3 \pm \sqrt{3}}{6} .

$p(1-p) = 1/6 \Longrightarrow p = \frac{3 \pm \sqrt{3}}{6}.$

Eine ähnliche Idee gilt für - Sie sortieren jede Hälfte zunächst nach dem Zufallsprinzip und "verschmelzen" sie dann. Allerdings kann ich auch für nicht sehen, wie die Hälften richtig zusammengeführt werden. $n=6$ $n=8$

Das Interessante an dieser Lösung ist die seltsame Wahrscheinlichkeit . $p$

Als Randnotiz ist der Satz von Wahrscheinlichkeiten die uns möglicherweise helfen können, durch , wobei über alle Eigenwerte aller Darstellungen von bei allen Transpositionen geht. $p$ $1/(1-\lambda)$ $\lambda \leq 0$ $S_n$

— Yuval Filmus
quelle

Die seltsamen Werte für sind in der Tat ermutigend, da es meines Erachtens einen einigermaßen einfachen Beweis dafür gibt, dass das Beste, was Sie tun können, ist , wenn wir die Wahrscheinlichkeiten für die ganze Zahl auf beschränken .

p

$p$

1 / k

$1/k$

k

$k$

O (n^{2})

$O(n^2)$

— Joe Fitzsimons

Ein etwas anderer Weg für 2n Elemente, der in einem ähnlichen Sinne immer noch seltsam ist, besteht darin, die ersten n Elemente zu mischen, die letzten n Elemente zu mischen und (i, i + n) mit der Wahrscheinlichkeit p_i für i = 1,…, n zu tauschen , mische die ersten n Elemente und mische die letzten n Elemente. Die Wahrscheinlichkeiten p_i müssen so gewählt werden, dass die Wahrscheinlichkeit, dass genau k aus den n Swap-Gates ausgelöst wird, gleich Solche Wahrscheinlichkeiten p_i sind gegeben durch ( 1 + x_i) / 2 wobei x_1,…, x_n die Wurzeln des Legendenpolynoms P_n sind. (mehr)

{(\binom{n}{k})}^{2} / (\binom{2 n}{n})

$\binom{n}{k}^2/\binom{2n}{n}$

— Tsuyoshi Ito

(Fortsetzung) Eine enttäuschende Sache an der von mir beschriebenen Variation ist, dass sie n (n - 1) / 2 probabilistische Swaps erfordert, wenn n eine Potenz von zwei ist, das heißt genau die Anzahl von Toren wie die Blasensorte Lösung von Anthony Leverrier.

— Tsuyoshi Ito

@ Tsuyoshi, deine Konstruktion ist eindeutig korrekt, aber ich frage mich, ob es mehr als nötig macht. Ich habe im Moment keine Zeit, um die Analyse durchzuarbeiten, aber wenn Sie dies tun, sollten Sie sich überlegen, ob es gibt sodass ; ; ; ; dann bewerben Sie sich eine geeignete Permutation der Legendre-Wurzeln (und füllen Sie die anderen Viertel aus) kann funktionieren.

p_{0}, p_{1}

$p_0, p_1$

0 \leftrightarrow 1, p = \frac{1}{2}

$0\leftrightarrow 1, p=\frac{1}{2}$

2 \leftrightarrow 3, p = \frac{1}{2}

$2\leftrightarrow 3, p=\frac{1}{2}$

0 \leftrightarrow 2, p = p_{0}

$0\leftrightarrow 2, p=p_0$

1 \leftrightarrow 3, p = p_{1}

$1\leftrightarrow 3, p=p_1$

— Peter Taylor

Betrachten Sie das Problem des zufälligen Mischens der Zeichenfolge , wobei jeder Block die Länge , mit einer Schaltung, die aus probabilistischen paarweisen Vertauschungen besteht. Das heißt, alle Strings mit s und n muß gleich wahrscheinlich Ausgänge der Schaltung sein, angesichts der angegebene Eingabe. Sei eine optimale Schaltung für dieses Problem und sei eine optimale Schaltung für das ursprüngliche Problem (zufälliges Mischen von Elementen). Eine Zufallspermutation Anwendung genügt , um zufällig Verschachtelung der S und S, SO $XX..XY..YY$ $n$ $(2n)!/(n!)^2$ $n$ $X$ $n$ $Y$ $B_{2n}$ $C_{2n}$ $2n$ $X$ $Y$ $\lvert{B_{2n}}\rvert \le \lvert{C_{2n}}\rvert$ . Andererseits können wir Elemente mischen , indem wir die ersten Elemente mischen , die letzten Elemente mischen und schließlich die Schaltung anwenden . Dies impliziert, dass . Wenn wir diese beiden Grenzen kombinieren, können wir das folgende Ergebnis ableiten: $2n$ $n$ $n$ $B_{2n}$ $\lvert{C_{2n}}\rvert \le 2\lvert{C_{n}}\rvert + \lvert{B_{2n}}\rvert$

$\lvert{B_{2n}}\rvert$ und sind beide , oder keiner ist. $\lvert{C_{2n}}\rvert$ $o(n^2)$

Wir sehen, dass die beiden Probleme zumindest in diesem Sinne gleich schwierig sind. Dieses Ergebnis ist etwas überraschend, da zu erwarten ist, dass das Shuffle-Problem einfacher ist. Insbesondere die entropischen Argument zeigt , dass heißt , sondern gibt das stärkere Ergebnis , dass heißt . $XY$ $\lvert{B_{2n}}\rvert$ $\Omega(n)$ $\lvert{C_{2n}}\rvert$ $\Omega(n \log n)$

— mjqxxxx
quelle

Diaconis und Shahshahani 1981, "Generieren einer zufälligen Permutation mit zufälligen Transponierungen", zeigen, dass 1/2 n log n zufällige Transponierungen (Anmerkung: hier gibt es kein "O") zu einer Permutation führen, die (in der gesamten Variationsentfernung) der Uniform nahe kommt. Ich bin nicht sicher, ob genau das, was in Ihrer Anwendung erlaubt ist, Sie dieses Ergebnis verwenden lässt, aber es ist ziemlich schnell und eng, da es ein Beispiel für ein Cut-Off-Phänomen ist. Eine Übersicht über ähnliche Ergebnisse finden Sie unter Random Walks on Finite Groups von Saloff-Coste.

— Jason Morton
quelle

Und vermutlich können zwei beinahe zufällige Permutationen zusammengesetzt werden, um eine noch beinahe zufällige Permutation zu erzeugen.

— mjqxxxx

... Es ist jedoch anzumerken, dass dies nicht wirklich dasselbe Problem ist (auch wenn eine ungefähre und keine exakte Lösung möglich ist), da die Autoren die Transpositionen zufällig ausgewählter Elementpaare und nicht die probabilistischen Transpositionen bestimmter Elementpaare berücksichtigen.

— mjqxxxx

Dies ist wirklich ein Kommentar, aber zu lang, um einen Kommentar zu verfassen. Ich vermute, dass die Darstellungstheorie der symmetrischen Gruppe nützlich sein könnte, um eine bessere Untergrenze zu beweisen. Obwohl ich so gut wie nichts über Repräsentationstheorie weiß und möglicherweise falsch liege, möchte ich erklären, warum dies möglicherweise mit dem aktuellen Problem zusammenhängt.

Es ist zu beachten, dass das Verhalten einer Schaltung, die aus probabilistischen Swap-Gattern besteht, vollständig als Wahrscheinlichkeitsverteilung p über _Sn , der Gruppe von Permutationen auf n Elementen, spezifiziert werden kann . Eine Permutation g ∈ S _n kann als das Ereignis betrachtet werden, dass die i- te Ausgabe die g ( i ) -te Eingabe für alle i ∈ {1,…, n } ist. _{Stellen Sie} nun eine Wahrscheinlichkeitsverteilung p als formale Summe ∑ _{g ∈ S _n} p ( g ) g dar . Zum Beispiel der probabilistische Wechsel zwischen den Drähten i undj mit der Wahrscheinlichkeit p wird dargestellt als (1 - p ) e + p τ _ij , wobei e ∈S _n das Identitätselement ist und τ _ij ∈S _n die Transposition zwischen i und j ist .

Eine interessante Tatsache bei dieser formalen Summe ist, dass das Verhalten der Verkettung zweier unabhängiger Schaltkreise formal als Produkt dieser formalen Summen beschrieben werden kann. Wenn nämlich das Verhalten der Schaltungen C ₁ und C ₂ als formale Summen a ₁ = _≤_{g ≤ S _n} p ₁ ( g ) g bzw. a ₂ = _≤_{g ≤ S _n} p ₂ ( g ) g dargestellt wird, dann das Verhalten der Schaltung C ₁ gefolgt von C ₂wird dargestellt als _≤_{g ₁ , g ₂ ≤ S _n} p ₁ ( g ₁ ) p ₂ ( g ₂ ) g ₁g ₂ = a ₁a ₂ .

Daher entspricht eine gewünschte Schaltung mit m probabilistischen Swaps genau einer Schreibweise der Summe (1 / n !) ∑ _{g ∈ S _n} g als Produkt von m Summen, von denen jede die Form (1 - p ) e + hat p τ _ij . Wir möchten die minimale Anzahl m von Faktoren kennen.

Die formale Summe Σ _{g ∈S _n} f ( g ) g , wobei f eine Funktion von S _n zu c, ausgestattet mit natürlich definiert Addition und Multiplikation, bildet den Ring genannt Algebra Gruppe c [S _n ]. Die Gruppenalgebra ist eng mit der Repräsentationstheorie von Gruppen verwandt, die, wie wir alle wissen und befürchten, eine tiefe Theorie ist :). Dies lässt mich vermuten, dass etwas in der Darstellungstheorie auf das aktuelle Problem anwendbar sein könnte.

Oder vielleicht ist das nur weit hergeholt.

Tsuyoshi Ito
quelle

Hier ist was dies reduziert. Es gibt eine Reihe von Darstellungen der symmetrischen Gruppe, die für Transpositionen mit einigen Arbeiten explizit berechnet werden können (normalerweise werden sie nur explizit für Transpositionen berechnet ). Der Anfangswert jeder Darstellung ist die entsprechende Identitätsmatrix. Die Anwendung eines probabilistischen Swaps multipliziert jede Darstellung mit , wobei der Wert der Darstellung beim durchgeführten Swap . (Fortsetzung)

(k, k + 1)

$(k,k+1)$

(1 - p) I + p A_{i j}

$(1-p)I + pA_{ij}$

A_{i j}

$A_{ij}$

(i j)

$(ij)$

Yuval Filmus

Damit die Ausgabe einheitlich ist, müssen alle Darstellungen außer der Identitätsdarstellung Null sein. Daher sollten die Wahrscheinlichkeiten so gewählt werden, dass mindestens einige der Matrizen singulär sind. Die Matrizen für jede Darstellung haben unterschiedliche Eigenvektoren, so dass es nicht klar ist, welche Bedingung eine bestimmte Darstellung zwingen würde, Null zu sein. (Fortsetzung)

p

$p$

(1 - p) I + p A_{i j}

$(1-p)I + pA_{ij}$

A_{i j}

$A_{ij}$

Yuval Filmus

Wenn wir jedoch beweisen könnten, dass jede Transposition den durchschnittlichen Rang einer Repräsentation um höchstens verringert , würden wir eine Untergrenze erhalten. Eine solche Grenze kann bewiesen werden, wenn wir die Eigenvektoren kennen, die jeder Darstellung und jeder Transposition entsprechen. Diese Informationen können prinzipiell ausgearbeitet werden, es gibt jedoch keine Garantie dafür, dass dieser Ansatz nicht-triviale Ergebnisse liefert.

1 / n^{2}

$1/n^2$

n^{2}

$n^2$

Yuval Filmus

(Fortsetzung) und diese lineare Transformation ist genau die Matrix, die bei der Darstellung von S_n durch n × n Permutationsmatrizen entsteht. Obwohl n − 1 als Untergrenze für die Anzahl der Gatter trivial ist (das Entropieargument gibt bereits eine bessere Untergrenze), hoffe ich, dass es möglich ist, Ihr Argument auf andere Darstellungen zu verallgemeinern, um eine bessere Untergrenze für das zu erhalten Gesamtzahl der Tore.

Tsuyoshi Ito

@Yuval, @Peter: Ich habe festgestellt, dass (1 - p) I + pA_ {ij} für jede Darstellung nicht singulär ist, es sei denn, p = 1/2 (weil A_ {ij} ^ 2 = I impliziert, dass die Eigenwerte von A_ {ij } sind ± 1). Daher ist das Zählen des Ranges nur nützlich, um die Anzahl der Wahrscheinlichkeits-1/2-Gatter zu verringern, was bereits von Peter optimal durchgeführt wurde. Mit anderen Worten, wenn die Darstellungstheorie in der von mir in diesem Beitrag vorgeschlagenen Weise nützlich ist, brauchen wir etwas anderes als das Zählen des Rangs von Matrizen! Ich bin mir nicht sicher, ob das realistisch ist.

Tsuyoshi Ito

Anthonys -Algorithmus kann parallel ausgeführt werden, indem die nächste Iteration der Prozedur nach den ersten beiden probabilistischen Swaps gestartet wird, was zu einer -Laufzeit führt. $O(n^2)$ $O(n)$

Dave
quelle

Ich denke, das relevante Maß für die Komplexität dieser Frage ist die Anzahl der Gates und nicht die Laufzeit.

Anthony Leverrier

@Anthony ist richtig, dass ich mich nur für die minimale Anzahl von Toren interessiere.

Joe Fitzsimons

Wenn ich das richtig verstehe, brauchen Sie mindestens probabilistic gates , wenn Sie möchten, dass Ihre Schaltung alle Permutationen erzeugen kann , obwohl ich nicht sicher bin, wie die minimale Schaltung aufgebaut werden kann. $\lceil \log_2(n!) \rceil$

AKTUALISIEREN:

Ich denke, wenn Sie den Mergesort-Algorithmus verwenden und alle Vergleiche durch zufällige Auswahlen mit entsprechenden Wahrscheinlichkeiten ersetzen, erhalten Sie die Schaltung, nach der Sie suchen.

Antonio Valerio Miceli-Barone
quelle

Ich bin mir nicht ganz sicher, wie Sie dies in das oben angegebene probabilitsche Swap-Gate-Modell übersetzen würden. Ich verstehe nicht, wie ein probabilistischer Swap den Vergleich ersetzt und dennoch eine zufällige Verteilung erzielt. Daher bin ich mir auch nicht sicher, warum dies optimal wäre.

Joe Fitzsimons

Und ja, ist das Minimum, aber dies ist nur .

⌈ \log_{2} (n!) ⌉

$\lceil \log_2(n!) \rceil$

O (n \log (n))

$O(n\log(n))$

Joe Fitzsimons

Es sei und gehe durch Induktion auf . Sie haben zwei zufällige Permutationen der Länge . Wenn Sie diese zufällig zusammenführen (dh das nächste Element aus einer zufällig ausgewählten Subpermutation nehmen), sollten die zusammengeführten Ergebnisse auf jeden Fall zufällig sein. Die Wahrscheinlichkeit, dass die Position ein Element aus der "linken" Subpermutation hat, ist eindeutig 1/2 durch Symmetrie. Und wenn es ein Element aus der linken Subpermutation enthält, muss es ein gleichmäßig zufälliges Element enthalten. Auf diese Weise können Sie sehen, dass die resultierende Permutation tatsächlich zufällig ist.

n = 2^{k}

$n=2^k$

k

$k$

2^{k - 1}

$2^{k-1}$

i

$i$

Andrew D. King

Dies war auch meine Überlegung, als ich Mergesort vorschlug. Bei einem zweiten Gedanken scheint es mir jedoch nicht möglich zu sein, den Merge-Vorgang nur mit den erforderlichen Gattertypen zu implementieren, da diese keine Ausgabe erzeugen um festzustellen, ob sie die Permutation durchgeführt haben und keinen Steuereingang haben, um sie zu konditionieren.

Antonio Valerio Miceli-Barone

@ Andrew: Ich verstehe nicht, wie ich diese zufällig zusammenführen kann, wenn ich die in der Frage umrissenen Tore benutze.

Joe Fitzsimons

Die folgende Antwort ist falsch (siehe @ Joe Fitzsimons Kommentar), könnte aber als Ausgangspunkt nützlich sein

Ich habe einen Skizzenvorschlag in . Ich habe überprüft, dass es für (!) Funktioniert, aber ich habe noch keinen Beweis dafür, dass das Ergebnis über hinaus einheitlich ist . $O(n\log n)$ $n=4$ $n=4$

Angenommen, Sie haben eine Schaltung , die eine einheitliche zufällige Permutation auf Bits erzeugt. Les das probabilistische Swap-Gate, das die Bits und mit der Wahrscheinlichkeit 1/2 vertauscht und nichts mit der Wahrscheinlichkeit tut . Konstruiere die folgende Schaltung die auf Bits einwirkt : $C_n$ $n$ $S_{i,j}^{\frac 12}$ $i$ $j$ $1/2$ $C_{2n}$ $2n$

$\forall 1\le k\le n$ gilt das Tor ; $S_{k,k+n}^{1/2}$
Wende auf die ersten Bits an; $C_n$ $n$
Wende auf die letzten Bits an; $C_n$ $n$
$\forall 1\le k\le n$ das Gatter . $S_{k,k+n}^{1/2}$

Schritt 1. wird benötigt, damit die Bits und in der gleichen Hälfte der Permutation landen können, und Schritt 4. wird aus Symmetriegründen benötigt: Wenn eine Lösung ist, ist auch Eine Lösung ist auch, wenn die Tore in umgekehrter Reihenfolge angebracht werden. $1$ $n+1$ $C_{2n}$ $C_{2n}^-1$

Die Größe dieser Schaltkreisfamilie folgt der folgenden Rekursionsrelation: mit offensichtlich . Man sieht dann leicht, dass .

| C_{2 n} | = 2 | C_{n} | + 2 n

$|C_{2n}| = 2|C_n|+2n$

| C_{1} | = 0

$|C_1|=0$

| C_{n} | = n \log n

$|C_n|=n\log n$

Dann bleibt die naheliegende Frage: Führen diese Schaltungen gleichmäßige Permutationen durch? Nein, siehe ersten Kommentar unten

Frédéric Grosshans
quelle

Ich glaube nicht, dass diese einheitliche Permutationen durchführen. Tatsächlich denke ich, dass es unmöglich ist, genau mit solchen Toren umzugehen, wenn man die Wahrscheinlichkeit auf 1/2 festlegt. Der Grund dafür ist einfach: Stellen Sie sich eine Schaltung vor, die solche Gatter verwendet. Dann gibt es gleichwahrscheinliche Berechnungspfade, und daher muss jede Permutation mit der Wahrscheinlichkeit für eine ganze Zahl . Für eine gleichmäßige Verteilung benötigen wir jedoch . Offensichtlich kann dies für einen ganzzahligen Wert von für nicht erfüllt werden .

m

$m$

2^{m}

$2^{m}$

k 2^{- m}

$k 2^{-m}$

k

$k$

k 2^{- m} = \frac{1}{n!}

$k 2^{-m} = \frac{1}{n!}$

k

$k$

n \geq 3

$n\geq 3$

Joe Fitzsimons

Tatsächlich. Ich habe auch vergessen, die Homogenität für zu überprüfen ...

n = 4

$n=4$

Frédéric Grosshans